从零开始Java实现Parser Combinator

引言

什么是Parser Combinator

Parser Combinator是函数式语言中的概念，它是一种通过组合小型解析器来构建复杂解析器的技术。其中Parser是把输入数据(通常是文本)转换成特定数据结构的函数或者对象。Parser接收一个字符串(或者字节流)作为输入，尝试根据预定义的规则对其进行解析，最终返回成功或者失败的结果。Combinator是组合器，它是一些用于组合各种Parser的函数。

Parser Combinator的优势与劣势

Parser Combinator的优势是它具有非常高的可读性和灵活性，可读性体现在它对解析对象的语法描述非常的直观，灵活性体现它可以随心所欲的组合。

Parser Combinator的劣势在于它的性能会比专门的解析器(例如使用Flex/Bison生成的解析器)差，易用性和性能难以兼得。

为什么要用Java来实现

第一，我的工作是一个Java程序员；

第二，文本解析或者语法解析的在日常中需求比较多；

第三，大部分的解析工作对性能的要求不会太高，好用且易读的Parser Combinator非常有使用价值；

第四，目前没有找到好用的Parser Combinator的实现。

函数式语言中的Parser Combinator

以haskell中的parsec为例。假设有一个解析格式化之后的时间字符串的需求，格式化之后的时间是这样的：2023-05-01 12:30:30，使用parsec来解析这个时间字符串的代码可以这样写:

-- 定 * 析的目标数据结构
data Time = Time
 { year :: Int
 , month :: Int
 , day :: Int
 , hour :: Int
 , minute :: Int
 , second :: int
 }
-- 解析整数的解析器
anyInt :: Parser Int
anyInt = read <$> many1 (satisfy isDigit)
-- 目标解析器，通过组合anyInt 和 char函数实现
timeParser :: Parser Time
timeParser = Time <$> anyInt << char '-'
                 <*> anyInt << char '-'
                 <*> anyInt << char ' '
                 <*> anyInt << char ':'
                 <*> anyInt << char ':'    
                 <*> anyInt

即使没学过haskell的人也可以体会到使用Parser Combinator带来的那种直观感。再举个解析解析一行csv数据的例子：

csvLineParser :: Parser [String]
csvLineParser = many (satisfy (/= ',')) `sepBy` (symbol ',')

我们简单的认为csv行就是一个按逗号分隔的字符串。

使用Java实现之后的效果

同样是上面两个例子

// timeParser
Parser intParser = NumberParser.anyIntStr();
Parser timeParser = intParser.chain(() -> TextParsers.one('-').ignore()) //year
                            .chain(() -> intParser).chain(() -> TextParsers.one('-').ignore()) //month
                            .chain(() -> intParser).chain(() -> TextParsers.one(' ').ignore()) //day
                            .chain(() -> intParser).chain(() -> TextParsers.one(':').ignore()) //hour
                            .chain(() -> intParser).chain(() -> TextParsers.one(':').ignore()) //minute
                            .chain(() -> intParser); //second
Result result = timeParser.runParser(new Buffer("2023-05-01 12:30:30".getBytes()));
assert result.<Integer>get(0) = 2023
assert result.<Integer>get(1) = 5
assert result.<Integer>get(2) = 1
assert result.<Integer>get(3) = 12
assert result.<Integer>get(4) = 30
assert result.<Integer>get(5) = 30
//csvLineParser
Parser csvLineParser = TextParser.satisfy(Character::isLetterOrDigit).some()
                   .map(Mapper.toStr())
                   .sepBy(TextParsers.one(',');

其中

• chain方法用于连接另一个Parser

• map方法用于将解析的结果收集目标结构

• some方法是一个组合函数，意思是重复当前Parser 1次或无限次，类似于正则表达式中的+

• sepBy方法是一个组合函数，意思是使用其参数中的Parser作为分隔符

设计

Parser

Parser由四个部分组成：

• runParser函数：Parser的核心函数，它解析输入并返回解析结果

• isIgnore：标识此Parser的结果是否需要忽略，例如解析时间字符串时的横杠(-)和冒号(:)是不需要出现在结果里面的。

• map：将Parser的结果转换成目标数据结构

• Combinators：各种用于组合的函数,例如(chain, some, many,sepBy, repeat...)

Result

Result用于表示Parser解析的结果，其中包含两个主要组成部分：

• 一个表示解析成功的List：由于解析器是可以组合的，所以Result是各个小解析器的结果的组合，需要用List来存储

• 一个表示失败的错误信息：用一个字符串就可以了

IBuffer

用于表示输入的数据，其内部维护的是一个byte[]和表示解析位置的下标，另外还有一些用于操作下标的方法。

基础解析器

• TextParsers：用于解析文本数据

• NumberParsers：用于解析数字

• ByteParsers：用于解析字节流

实现

Parser

public abstract class Parser {
   //是否需要忽略解析结果
   protected boolean ignore = false;
   //判断此解析器的结果是否需要忽略
   public boolean isIgnore() {
       return this.ignore;
   }
   //设置此解析器的结果需要忽略
   public Parser ignore() {
       this.ignore = true;
       return this;
   }
   //解析器的执行函数，内部执行parser
   public Result runParser(IBuffer buffer) {
       Result result = parse(buffer);
       if (result.isError()) {
           return result;
       }
       if (isIgnore()) {
           result.clear();
           return result;
       }
       return result;
   }
   //抽象方法，具体的解析逻辑
   public abstract Result parse(IBuffer buffer);
   ...
}

Result

public class Result {
   //结果列表
   private List result;
   //错误信息
   String errorMsg;
   //解析消耗的输入的长度
   int length;
   //解析的位置，相对于整个输入来说
   int pos;
}

IBuffer

public interface IBuffer {
   //回溯
   void backward(int n);
   //前进，消耗输入
   void forward(int n);
   //读取输入，但不设置position
   byte[] headN(int n);
   ... //其他的辅助方法
}

基础解析器

ByteParsers

public class ByteParsers {
   //解析一个满足条件的字符
   public static Parser satisfy(Predicate<Byte> predicate) {
       return new Parser() {
           @Override
           public Result parse(IBuffer buffer) {
               Optional<Byte> b = buffer.head();
               if (b.isEmpty() || !predicate.test(b.get())) {
                   return Result.builder()
                           .pos(buffer.getPos())
                           .errorMsg(ErrorUtil.error(buffer))
                           .build();
               }
               buffer.forward(1);
               return Result.builder()
                       .result(List.of(b))
                       .length(1)
                       .build();
           }
       };
   }
   //解析指定的字节数组
   public static Parser bytes(byte[] data, String desc) {
       return new Parser() {
           @Override
           public Result parse(IBuffer buffer) {
               byte[] bs = buffer.headN(data.length);
               if (!Arrays.equals(data, bs)) {
                   return Result.builder()
                           .pos(buffer.getPos())
                           .errorMsg(ErrorUtil.error(buffer))
                           .build();
               }
               buffer.forward(bs.length);
               return Result.builder()
                       .length(data.length)
                       .result(List.of(data))
                       .build();
           }
       };
   }
   //解析一个指定字节
   public static Parser one(byte b) {
       return satisfy(a -> a == b);
   }
   //读取n个字节
   public static Parser take(int n) {
       ...
   }
   //路过n个字节
   public static Parser skip(int n) {
       ...
   }
   ...
}

TextParsers

public class TextParsers {
   //解析一个满足条件的，特别编码的字符
   public static Parser satisfy(Predicate<Character> predicate, Charset charset) {
       return new Parser() {
           @Override
           public Result parse(IBuffer buffer) {
               byte[] bytes = buffer.headN(4);
               Optional<Character> ch = CharUtil.read(bytes, charset);
               if (ch.isPresent() && predicate.test(ch.get())) {
                   int len = String.valueOf(ch.get()).getBytes(charset).length;
                   buffer.forward(len);
                   return Result.builder()
                           .result(List.of(ch.get()))
                           .length(len)
                           .build();
               }
               return Result.builder()
                       .pos(buffer.getPos())
                       .errorMsg(ErrorUtil.error(buffer))
                       .build();
           }
       };
   }
   //使用默认编码UTF-8
   public static Parser satisfy(Predicate<Character> predicate) {
       return satisfy(predicate, StandardCharsets.UTF_8);
   }
   //解析一个特定编码的特定字符
   public static Parser one(char ch, Charset charset) {
       ...
   }
   ... //其他的各种基础解析器
}

NumberParser

public class NumberParsers {
   //解析一个字符串表示的指定整数
   public static Parser intStr(int a) {
   }
   //解析一个字符表示的任意整数
   public static Parser anyIntStr() {
   }
   //解析一个小端序编码的整数
   public static Parser intLE(int a) {
   }
   //解析一个大端序编码的整数
   public static Parser intBE(int a) {
   }
   ... //其他的解析器
}

Combinators

public abstract class Parser{
   ...  
   //重复0到无限次
   public Parser many() {
       ....
   }
   //连接另一个Parser，先执行当前解析器，再执行被连接的解析器
   //如果当前解析器失败则直接失败，被连接的解析器不一定会用到
   //所以使用Supplier来模拟惰性求值
   public Parser chain(Supplier<Parser> parser) {
      ...
   }
   //如果当前解析器失败，则尝试使用另一个解析器
   public Parser or(Supplier<Parser> parser) {
       ...
   }
   //使用一个函数将解析结果转换成任意数据结构
   public Parser map(Function<List, ?> mapper) {
       ...
   }
   //重复当前解析器n次
   public Parser repeat(int n) {
       ...
   }
   //添加了停止条件的many
   //当遇到参数中指定的Parser可以解析的内容时就停止重复操作
   public Parser manyTill(Parser parser) {
       ...
   }
   //去掉前后的空格
   public Parser trim(boolean includeNewline) {
       ...
   }
   ... //其他的组合函数
}

使用Parser Combinator

通常使用Parser Combinator需要完成几个步骤:

• 定义目标数据结构

• 分析语法

• 使用Parser Combinator描述语法

下面我们来用它分别实现csv,json,xml和正则表达式(Regex)

json解析器

语法描述：

使用EBNF描述JSON的语法如下:

J = E
E = O | A | S | N | B | Null
O = '{' [ (S ':' E) { ',' (S ':' E) } ] '}'
A = '[' [ E { ',' E } ] ']'
S = "string"
N = "number"
B = "true" | "false"
Null = "null"

json由六种类型组成，分别是Object, Array, String, Number, null, bule

数据结构

根据json的语法可以定义以下几个class用于表示json：JsonValue, JsonObject, JsonMember, JsonArray, JsonType。其中JsonValue：

public class JsonValue {
   /**
    * type of json value
    */
   JsonType type;
   /**
    * value
    */
   Object value;
}

使用Parser Combinator描述Json

...
  public static Parser jsonParser() {
      return stringParser()
              .or(() -> objectParser().trim(true))
              .or(() -> arrayParser().trim(true))
              .or(() -> nullParser().trim(true))
              .or(() -> boolParser().trim(true))
              .or(() -> numberParser().trim(true))
              .trim(true);
  }
  //stringParser
  ...
  //objectParser
  ...
  //nullParser
  ...
  //boolParser
  ...
  //numberParser
  ...

CSV解析器、XML解析器

类似于json，详见源码

正则表达式(Regex)

正则表达式是另一种解析的技术，它和确定性有限自动机(DFA)是等价的。理论上正则可以做的事情，Parser Combinator也能做，而且Parser Combinator更灵活与强大一些。我们这里要实现的实际上是一个转换器，将一个正则表达式转换成由Parser Combinator表示的解析器。

语法表示

R = E ;
E = T { "|" T } ;
T = F { F } ;
F = A [ Q ] ;
A = C | "." | "(" E ")" | "[" [ "^" ] CC "]" ;
C = <non-meta character> | "\\" <any character> ;
Q = "*" | "+" | "?" | "{" N [ "," [ N ] ] "}" ;
CC = { CR } ;
CR = <non-hyphen character> | <non-hyphen character> "-" <non-hyphen character> ;
N = <non-zero sequence of digits> ;

数据结构

定义RParser类，用于描述Regex表示中每一个部分对应的解析器

public class RParser {
   private ParserType type;
   private int quoteId;
   private int groupId;
   private Parser parser;
   private Function<Parser, Parser> func;
   public RParser apply(Function<Parser, Parser> func) {
       if (this.parser != null) {
           this.parser = func.apply(this.parser);
       }
       this.func = func;
       return this;
   }
   public enum ParserType {
       PARSER,
       QUOTE,
       GROUP;
   }
}

RParser中有一个ParserType类型用于表示它是一人普通的Parser、一个分组(Group)或者是一个引用(Quote)。同时对应不同的ParserType还有一些额外的数据：分组编号，引用编号，对应的Parser，一个表示正则中重复的函数(Function<Parser, Parser>)

使用Parser Combinator描述Regex

public Parser parser() {
       return Parser.choose(
               () -> many(),  // *号重复
               () -> some(),  // +号重复
               () -> range(), //{m,n}重复
               () -> repeat(),//{n}重复
               () -> optional(), //?可有可无
               () -> validToken() //普通合法的token
       ).many().map(s -> {
           return RParser.builder().parser(chainParsers(s))
                   .type(RParser.ParserType.PARSER)
                   .build();
       });
   }

其中的第一个子解析器的结果都是的RParser的对象，再使用chainParsers方法来将它们连接起来。

关于回溯

之前实现的Combinator组合都是非回溯的，但正则表达式是需要回溯的，例如

使用".*abc"来匹配"xxxabc"是可以成功的
*但是，TextParser.any().many().chain(() -> TextParsers.string("abc"))来解析"xxxabc"却会失败。原因是TextParser.any().many()会消耗掉所有的输入，后面的 TextParsers.string("abc")就没有输入了。 因此，我们要限制第一个Parser让它不要消耗所有的输入。

我使用循环切分Buffer的方式来限制第一个解析器，具体来说，我会将当前的Buffer从位置i(i >= 0 && i <= length)把它切成两个(left, right)，将left给到第一个解析器，将right给到第二个解析器，同时添加一个参数(greedy)来表示是否需要找到最优(最长)匹配结果或者直接在第一个匹配结果的时候退出循环并返回成功。具体的回溯实现参见BacktraceParser中

关于分组与引用的实现

分组：使用一个AopParser类来给Parser的parser函数添加装饰，在解析前使用全局自增id生成分组编号。在解析后缓存解析结果(以便后续引用的时候使用)

引用：使用编号查询对应分组所缓存的解析结果，动态生成解析器

性能测试

目前的性能与经过优化的专业的解析器相关非常大，使用Parser Combinator实现的json解析器比fastjson要慢100倍的样子。对于性能要求高的场景，还是建议使用专门的解析器，或者使用Flex/Bison来生成解析器

完整的项目地址：https://github.com/janlely/jparser

---性能测试更新----

用Haskell的Z.Data.Parser也写了一个json parser，和fastjson对比了一下，比fastjson稍快一些。看来还是java不适合函数式编程，并不是Parser Combinator这个模式的问题。

import Z.Data.Parser
   ( anyCharUTF8, char8, parse', satisfy, text, Parser )
import Text.Printf (printf)
import Control.Applicative.Combinators ( some, (<|>), many, sepBy )
import Data.Functor (($>))
import Z.Data.CBytes (unpack)
import Z.Data.ASCII (w2c)
import Z.Data.Vector.Base (packASCII, elem)
import Prelude hiding (elem)
import Control.Monad (replicateM_)
data JsonMember = JsonMember String JsonValue deriving (Show)
data JsonValue = JsonString String
              | JsonNull
              | JsonNumber Double
              | JsonObject [JsonMember]
              | JsonArray [JsonValue] deriving (Show)
jsonParser :: Parser JsonValue
jsonParser = JsonString <$> stringParser <|> nullParser <|> numberParser <|> objectParser <|> arrayParser
nullParser :: Parser JsonValue
nullParser = text "null" $> JsonNull
stringParser :: Parser String
stringParser = char8 '"' *> contentParser <* char8 '"'
 where charParser = do
         ch <- anyCharUTF8
         if ch == '\\' || ch == '"'
            then fail $ printf "unexpect char ％c" ch
            else pure ch
       escapeParser = char8 '\\' *> char8' '"' <|> char8 '\\' *> char8' '\\'
       contentParser = some (charParser <|> escapeParser)
       char8' c = char8 c $> c
memberParser :: Parser JsonMember
memberParser = JsonMember <$> stringParser <* char8 ':'
                         <*> jsonParser
arrayParser :: Parser JsonValue
arrayParser = JsonArray <$> (char8 '[' *> jsonParser `sepBy` char8 ',' <* char8 ']')
objectParser ::Parser JsonValue
objectParser = JsonObject <$> (char8 '{' *> memberParser `sepBy` char8 ',' <* char8 '}')
numberParser :: Parser JsonValue
numberParser = JsonNumber . read <$> some validChar
 where validChar = w2c <$> satisfy (`elem` packASCII ".-0123456789e")

---5月22日更新----

最近在研究如何进行性能优化时发现，性能不好的主要原因是当目标对象的语法中含有递归时，由于不得不使用Supplier来防止暴栈，导致了每次调用Supplier::get方法的额外性能开销。例如json和语法中，json包含array，同时array也包含json，因此JsonParser中不得不使用Supplier。由于haskell中不存在这个问题，因此使用haskell实现在的json parser的性能就很好。

关于如何选择解析器的一点建议：

1、当需目标语法中有递归，同时对性能要求比较高的场景，建议使用ANTLR

2、对性能要求不高场景，可以使用jparser，因为它使用起来比ANTLR要简单的多。

一个使用jparser实现计算器的例子:

语法: 注意要避免左递归

<expr> ::= <term> | <term> "+" <expr> | <term> "-" <expr>
<term> ::= <factor> | <factor> "*" <term> | <factor> "/" <term>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= <digit> | <digit> <number>
<digit> ::= "0" | "1" | "2" | ... | "9"

实现：

public class Calculator {
   @Test
   public void testCalc() {
       Result result = expr().parse(Buffer.builder().data("(1+2)*3-(4*2)".getBytes()).build());
       assert result.<Double>get(0).compareTo(1.0) == 0;
       result = expr().parse(Buffer.builder().data("1+2*3-(4*2)".getBytes()).build());
       assert result.<Double>get(0).compareTo(-1.0) == 0;
   }
   public Parser expr() {
       return Parser.choose(
               () -> term().chain(TextParsers.one('+').ignore())
                       .chain(() -> expr()).map(s -> (double)s.get(0) + (double)s.get(1)),
               () -> term().chain(TextParsers.one('-').ignore())
                       .chain(() -> expr()).map(s -> (double)s.get(0) - (double)s.get(1)),
               () -> term()
       );
   }
   public Parser term() {
       return Parser.choose(
               () -> factor().chain(TextParsers.one('*').trim(false).ignore())
                       .chain(() -> term()).map(s -> (double)s.get(0) * (double)s.get(1)),
               () -> factor().chain(TextParsers.one('/').trim(false).ignore())
                       .chain(() -> term()).map(s -> (double)s.get(0) / (double)s.get(1)),
               () -> factor()
       );
   }
   public Parser factor() {
       return Parser.choose(
               TextParsers.one('(').ignore()
                       .chain(() -> expr())
                       .chain(TextParsers.one(')').ignore()),
               number()
       );
   }
   public Parser number() {
       return NumberParsers.anyDoubleStr();
   }
}

来源：https://segmentfault.com/a/1190000043819297