再探 Parser 和 Parser Combinator
在几年前的文章《Policy Engine 的前世今生》里，我谈到了自己探索如何生成高效的表达式求值的工具的整个过程。我先是使用 JISON（javascript 的 Flex/Bison）做了一个解析器（parser），后来又用 Elixir 自己的宏编程进行了优化，让单个表达式的验证从 200+ us 提升到 20+ us。最近无意间看到了 Guido van Rossum 大神的文章 [1]，讲他探索 PEG 解析器的历程（Python 3.9 已经实现了新的 PEG parser [2]）。于是，这个周末，我花了一个晚上，尝试了用 Rust 下的 PEG 解析器 — pest 重新实现了 policy 表达式解析器部分，为了更好地对比 pest 和 Rust 下的另外一个神器 nom 的效果，我也同时实现了 nom 下的 policy 表达式解析器。
本文讲讲我在使用这两个工具过程中的心得。如果大家对解析器还知之甚少，可以看我之前的文章《如何愉快地写个小parser》，以及 A Guide to Parsing: Algorithms and Terminology [3]，它是对各种 parser 的一个非常棒的总结。
PEG, CFG 和 Parser Combinator
在正式开始之前，先简单讲讲几个概念（我知道你们不太会看参考文献滴）。
PEG - Parsing Expression Grammar，是一种分析性形式文法，在 2004 年推出。它的语法和 CFG - Context Free Grammar 很类似。我们之前用的 BNF 工具（比如 Flex/Bison）用于撰写解析 CFG。PEG 和 CFG 的主要区别是：PEG 会在语法歧义发生时总选择第一个匹配项，而 CFG 则是未定义的。所以，PEG 总会只生成一棵满足规则的语法树，而 CFG 有可能产生多棵，需要开发者手动消歧。
比如下面的例子[4]：
定义：
if_statement := "if" "(" expr ")" statement "else" statement
| "if" "(" expr ")" statement;
输入：
if (x1) if (x2) y1 else y2这个输入可以有两种解释：
if_statement(x1, if_statement(x2, y1, y2)) // case 1
if_statement(x1, if_statement(x2, y1), y2) // case 2PEG 只会选择第一种，而 CFG 会产生解析冲突（开发者需要消除歧义）。
PEG/CFG 对应的工具都属于 Parser Generator 的范畴。因为一般手写解析器是一件非常枯燥且容易出错的行为，所以会有符合 PEG/CFG 的比较抽象的语言产生，专门用于描述语法，而用这种语言写出来的代码最后会被编译成解析器代码，所以叫 Parser Generator。
Parser Combinator 是和 Parser Generator 平行的概念。如果我们把解析器看成一幢大楼的话，用 Parser Generator 我们每次都几乎从零开始构建这个大楼，大楼和大楼之间相似的部分（如门窗）无法复用；而 用 Parser Combinator 就像搭乐高积木 — 我们不断构建小的，可复用的，可测试的组件，然后用这些组件来构建大楼。当我们要构建新的大楼时，之前创建的组件可以拿来使用，非常方便。
Parser Combinator 最早出现于 Haskell 社区的 Parsec，因为它的思路实在是太优美，太符合软件工程的思想了，于是后来 Parsec 在各个语言遍地开花，比如我之前介绍过的 Elixir 下的 nimble_parsec，以及今天我们要涉及的 nom。
多说两句 Parser Combinator。在 Parsec 问世之前，写应用软件的方法论比写解析器先进了整整一代。应用软件强调的代码的可测试，可组装，可复用，可重构等要素在解析器中的代码中很难应用，所有的解析器都是撰写起来不简单，维护起来非常困难，读复杂的没有文档的解析器就跟读天叔一样，添加功能或者修改 bug 更是要了老命，往往很小一个改动都会伤筋动骨。Parsec 的出现弥合了这个差距：开发者可以一个部分一个部分地实现解析器，每个部分可以单独测试，最后将其组装起来即可。这样大大提升了开发和维护的效率。
使用 pest 实现解析器
我们以下面的表达式为例：
country in ["US", "CA"] and (
(date > 01/01/2021 and date <= 02/01/2021) or
(date > 03/01/2021 and date <= 05/01/2021)
)使用 pest，这个语法大概 20 行就可以描述：
WHITESPACE = _{ " " | "\t" | "\r" | "\n" }
policy = _{ SOI ~ expr ~ (logic_op ~ expr)* ~ EOI }
expr = _{ sub_expr | sub_expr_group }
logic_op = { "and" | "or" }
sub_expr_group = { ... }
sub_expr = { name ~ op ~ value }
name = @{ "platform" | "country" | "date" | ... }
op = @{ "==" | ">=" | ... }
array = { "[" ~ value ~ ("," ~ value)* ~ "]" }
value = _{ date | ("\"" ~ string ~ "\"") | array }
string = @{ ASCII_ALPHA* }
date = ${ md ~ "/" ~ md ~ "/" ~ year }
md = { ASCII_DIGIT{1,2} }
year = { ASCII_DIGIT{4} }代码并不难懂。
我采用了自顶向下的方式来描述这个语法。首先，我让所有的空格自动解析，自动忽略。
然后是顶层的逻辑：policy 从输入开始（Start Of Input），读取一个表达式（expr），后接 任意多的逻辑运算符（ logic op）和表达式（expr），最后输入结束（End Of Input）。
那么表达式长什么样？表达式是不带括号的子表达式（sub_expr）或者带括号的子表达式（sub_expr_group），二选一。
那么不带括号的子表达式长什么样？变量名（name）+ 操作符（op）+ 值（value）。
剩下的我就不一一赘述了，很好理解。
我们可以看到，pest 声明的语法结构和 Bison 很像。为了方便解析和生成合适的语法树，pest 提供了一些方法可以控制哪些内容在语法树中生成：
- _{}：如果一条规则前加
_，意味着这个规则本身不会出现在语法树中（只出现其子规则）。 - @{}：如果规则前加
@，意味着这是原子规则（atomic rule），里面的空格需要被显式定义，且其子规则不会生成在语法树中。 - {}：如果规则前加 ，意味着这是复合原子规则（compound atomic rule），里面的空格需要给显式定义，但子规则会生成在语法树中。
写好的规则存成文件（比如 expr.pest）后，可以在 Rust 代码里这么引用：
#[derive(Parser)]
#[grammar = "expr.pest"]
pub struct ExprParser;然后，就可以生成语法树了：
let result = ExprParser::parse(Rule::policy, "date > 1/1/2021").unwrap();生成的语法树如下：
[
Pair {
rule: sub_expr,
span: Span {
str: "date > 1/1/2021",
start: 0,
end: 15,
},
inner: [
Pair {
rule: name,
span: Span {
str: "date",
start: 0,
end: 4,
},
inner: [],
},
Pair {
rule: op,
span: Span {
str: ">",
start: 5,
end: 6,
},
inner: [],
},
Pair {
rule: date,
span: Span {
str: "1/1/2021",
start: 7,
end: 15,
},
inner: [
Pair {
rule: md,
span: Span {
str: "1",
start: 7,
end: 8,
},
inner: [],
},
Pair {
rule: md,
span: Span {
str: "1",
start: 9,
end: 10,
},
inner: [],
},
Pair {
rule: year,
span: Span {
str: "2021",
start: 11,
end: 15,
},
inner: [],
},
],
},
],
},
Pair {
rule: EOI,
span: Span {
str: "",
start: 15,
end: 15,
},
inner: [],
},
]pest 提供了一系列的工具来遍历和处理语法树，比如我们要处理 sub_expr：
fn eval_sub_expr(mut rules: Pairs<Rule>, context: &Context) -> bool {
let name = rules.next().unwrap().as_str();
let op = rules.next().unwrap().as_str();
let value = rules.next().unwrap();
match value.as_rule() {
Rule::string => ...,
Rule::date => ...,
Rule::array => ...
}
}有关 pest 的更多说明，见 pest.rs。
使用 nom 来实现解析器
在使用 nom 之前，我有初级的 nimble_parsec 的使用经验，做过 csv / json 等实验性的解析器。
因为都是 parser combinator，nom（我用的是 version 6.x）的使用体验和 nimble_parsec 几乎一致，比较容易上手。这里需要吐槽一下的是，nom 的文档实在是太缺乏了，网上搜到的几乎都过时了（因为 nom 5 做过一次大的重写，几乎抛弃了之前的使用宏来构造 parsec 的方式），就连 nom 自己 github 里的文档都是过时的，唯一有效的文档是 doc.rs/nom 以及源码。我写 nom 的过程主要在 docs.rs/nom 里边搜索边写的。如果你没有 parsec 的经验，建议先看看比较通用的 parser combinator 的介绍，比如[5]。
前文说过，用 parser combinator 的感觉就像搭积木，比如要解析 Hello, world!，可以写三个小 parser，然后将其组合起来。如下图：
比如我要解析表达式里的 and 和 or 这样的逻辑表达式：
fn logic_op(input: &str) -> IResult<&str, LogicOp> {
delimited(multispace0, alt((tag("and"), tag("or"))), multispace0)(input)
}这段代码的 delimited combinator 是说前后的空格忽略，只取中间的内容。然后 alt 是从一组 combinators 里选择任意一种满足的情况。这里我们尝试匹配 and 或者 or，用 tag combinator 来描述。当 logic_op 运行完之后，它会 吃掉 输入从头开始的任何空白字符，以及随后的 and/or，以及之后的任意空白字符，然后返回 input 剩下的部分，以及匹配到的 and/or。
我们再看数组的匹配，比如这样一个数组 ["hello", "world"]。我们先用 delimited 忽略前后的语法单元 [] ，然后把所有的内容捕获到一个按逗号分隔的列表中。这是 separated_list1(tag(","), string) 所表达的。在 nom 里，一个 combinator 结尾 0 或者 1 代表它匹配 0 到多次，还是 1 到多次。separated_ist1 里的第二个参数 string 是一个 combinator，用于匹配输入中的带引号的字符串。注意这里为了简化起见，我并没有处理 string escape：
fn array(input: &str) -> IResult<&str, ExprValue> {
let (input, r) = delimited(tag("["), separated_list1(tag(","), string), tag("]"))(input)?;
Ok((input, ExprValue::Array(r)))
}
fn string(input: &str) -> IResult<&str, &str> {
delimited(
preceded(multispace0, tag("\"")),
alpha0,
terminated(tag("\""), multispace0),
)(input)
}可以看到 nom（或者任何 parser combinator）和 pest（或者任何 parser generator）撰写代码的思路类似，只不多 nom 用一个个函数来表达语法，而 pest 用 DSL 来描述语法。
pest 和 nom 的性能对比
在 pest 官网上，作者非常谦虚地附上了和 nom / serde 在解析 JSON 上的性能对比。可以看到 nom 比较接近 serde（rust 里 serde-json 的性能是顶级的存在 [6]），而 pest 还差得很远：
不知道是不是这个结果劝退了很多人，导致 pest 热度一直都比 nom 低很多。
然而我自己写的两种不同的 policy parser，实测结果咣咣打脸。pest 做的 parser 对 policy 表达式的处理速度在 4us 左右，而 nom 则超过了 5us。
这个结果让我很不开心，nom 毕竟是所有 parsec 的性能标杆，怎么到我手上就这么矬呢？后来我搜到了 nom 作者的一篇博客[7]，里面谈论了 nom 的一些优化策略，里面主要提到两点：1) 使用 jemalloc 2）使用 LTO（Link Time Optimization）。
使用 jemalloc 后
在项目中引入 jemalloc 后，我们需要使用 jemalloc 作为 global allocator。结果，pest 和 nom 性能都提升了 20% 左右：
不过大家性能都高了，nom 还是比 pest 差一大截，不开森。
使用 lto 后
随后我在 Cargo.toml 里使能了 LTO，重新编译。结果很有意思：pest 性能下降了 6-9%，而 nom 进一步提升了 15% - 20%：
这就有些奇怪了，LTO 会做很多链接时优化，让生成的二进制更小，可是为何 pest 反受其害？这一点让我百思不得其解。不过即便我们打开了这样作弊器级别的优化，nom 还是比 pest 表现差。
优化 nom
后来我发现在对解析出来的表达式求值时，在 pest 里，我采用了一些提前返回的策略，比如在某个子表达式中，如果遇到 true or expr ，我会直接返回 true，略过后一个 expr 的计算；同样的 false and expr，我会直接返回 false，略过后一个 expr 的计算。在 nom 里，因为我使用 fold_many0 来处理循环解析，它无法提前退出，所以这个策略不起作用。为了让 nom 的算法和 pest 的算法尽可能一致，我参考 itertools 里的 fold_while，为 nom 提供了 fold_many0_while 的方法（代码见：[8]），让 fold 中间我们可以提前退出整个循环。别看这样一个不起眼的小优化，它将性能提升了 7%-9%：
终于，这个例子里 nom 的性能略微超过了 pest。这个结果还是不够让我满意，我又做了一些局部的优化（比如避免几个不同的 combinator 都做 delimiter 空格的事情），性能还有 3-5% 的提升，但这基本是我能做到的优化的极限了。我觉得这个速度还不够快，理想情况下，一个复杂表达式的求值应该能在 1ms 之内，也许等我对 nom 理解更深刻，撰写的语法表达更简洁时，可以达到这一目标。
将新的 parser 应用在 Elixir 中
最终我使用 rustler [9] 把两个优化后的 parser 集成到 Elixir 中，然后用 benchee 测试了一下：
可以看到性能基本上没有太大的损失。和 4 年前 policy engine 那篇文章的结果相比，性能提升了大概 6-8 倍。但这两者对比稍微有些差别：policy engine 把所有 DB 里的 policy 都放在一个 Elixir module 里，所以 policy eval 无需从 db 中读取数据。为了达到同样对比的效果，我在 rust 代码中引入了 sled db，它是一个性能和 rocksdb 差不多的嵌入式数据库，单核单个记录的读取时间在 1us 左右。测试前我在 db 里压入了 1M 数据，让数据库贴近真实场景。测试时我模拟 policy engine 类似的场景，先从 sled db 中读取 policy，再运算，结果如我所料，差不多增加了 1us 时间：
这样，如果我们用 rust / nom / sled 重新实现一下 4 年前我做的 policy engine，将其集成到 Elixir 中，可以达到 5 倍左右的性能提升。
参考文档
- PEG parsing series overview (by Guido van Rossum): https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60
- New PEG parser for CPython: https://www.python.org/dev/peps/pep-0617/
- A Guide to Parsing: Algorithms and Terminology: https://tomassetti.me/guide-parsing-algorithms-terminology/
- What are the differences between PEGs and CFGs: https://stackoverflow.com/questions/5501074/what-are-the-differences-between-pegs-and-cfgs
- Parser combinators walkthrough: https://hasura.io/blog/parser-combinators-walkthrough/
- json-benchmark: https://github.com/serde-rs/json-benchmark
- Nom 5 is here: https://unhandledexpression.com/general/2019/06/17/nom-5-is-here.html
- fold_while support: https://github.com/Geal/nom/issues/1289
- rustler: https://github.com/rusterlium/rustler