引言
什么是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 IntanyInt = read <$> many1 (satisfy isDigit)-- 指标解析器，通过组合anyInt 和 char函数实现timeParser :: Parser TimetimeParser = 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实现之后的成果
同样是下面两个例子
// timeParserParser 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); //secondResult result = timeParser.runParser(new Buffer("2023-05-01 12:30:30".getBytes()));assert result.<Integer>get(0) = 2023assert result.<Integer>get(1) = 5assert result.<Integer>get(2) = 1assert result.<Integer>get(3) = 12assert result.<Integer>get(4) = 30assert result.<Integer>get(5) = 30//csvLineParserParser 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 = EE = O | A | S | N | B | NullO = '{' [ (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 JsonValuejsonParser = JsonString <$> stringParser <|> nullParser <|> numberParser <|> objectParser <|> arrayParsernullParser :: Parser JsonValuenullParser = text "null" $> JsonNullstringParser :: Parser StringstringParser = 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 $> cmemberParser :: Parser JsonMembermemberParser = JsonMember <$> stringParser <* char8 ':' <*> jsonParser arrayParser :: Parser JsonValuearrayParser = 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(); }}