引言
什么是 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();
}
}