parser 常见技巧
发表于更新于阅读时长 5 分钟如何让你的玩具 parser 变得不那么玩具
如果你刚刚上完 parser 课，并且已经有了一个手写的 DFA 的 lexer 和一个手写的 LL(1) parser ，那么恭喜你，你已经掌握了编译器的第一个组成部分。然而，要去解析实用的编程语言，这是远远不够的；固然我们可以把语言设计成易于解析的形式，但语言的设计总是会受到其他方面的制约。本文将探讨几种在解析编程语言时常见的问题，很多教科书上并不会涉及到如此工程的部分。
1. 运算符优先级
的确我们可以连这个 feature 也放弃，smalltalk 系的语言就是如此；但我相信大多数人建立起来的直觉还是运算符应当有优先级。
教科书上往往会花大力气去介绍如何消除左递归，然而这种做法并不实用：常见的编程语言往往要支持十余种运算符，为它们分别编写解析函数是相当无聊的。所以古往今来的工程师发明了各种各样的技巧来解决这个问题。以如下的简单表达式为例子：
c
一种从五十年代流传下来的神奇技术是这样的1：先把输入的字符串预先处理一遍，把*替换成)*(，把+替换成))+((，在每个表达式前面和左括号前面加上两个额外的左括号，表达式末尾和右括号后面加上额外的两个右括号。于是，上面的表达式就变成了
c
我们可以十分惊讶地发现，上面的表达式不仅括号能匹配上，而且完全不用考虑运算符优先级问题。当然，这种做法不值得提倡。
正确的做法则是调度场算法，或者叫优先级攀爬(precedence climbing)算法。这个算法需要优先级和递归的循环。首先开启一个优先级为 0 的循环，它会消费1，然后遇上+。加号的优先级为 1 大于 0，那么就可以开始一个新的优先级为 1 的循环。第二个循环消费掉2之后遇上*。乘号的优先级为 2 大于 1,那么就可以开始一个新的优先级为 2 的循环。第三个循环消费掉3，并且遇到了表达式的结尾，于是它就产生了值为 3 的字面量表达式给第二个循环；第二个循环产生2*3给第一个循环；最后得到1+(2*3)。
相反，对于
c
则在看到*之后会产生一个优先级为 2 的循环。当第二个循环看到+的时候，它的优先级是 2 大于加号的 1，那么就立即产出1*2返回给第一个循环。第一个循环发现下一个 token 是+,那就再开启一个优先级为 1 的循环。这是左结合的情况，也就是说3 - 2 - 1应当产生(3 - 2) - 1。对于右结合运算符比如a = b = c，比较优先级时不该用大于，而应该用大于等于作为判断标准。
它的更通用的形式叫 pratt parser。pratt parser 不仅可以处理中缀运算符的优先级，还可以处理前缀和后缀运算符的优先级。举例说来
c
我们显然希望负号作用于a.b的整体上。pratt parser 里的基本算法和前面类似，只不过优先级分为了两个数字，分别称为左结合力和右结合力。在判断是否开启一个新的循环时，用左结合力进行比较，而开启的新循环的结合力则使用右结合力。也就是说对于
c
0 小于 1,就可以开启一个结合力为 2 的循环；2 小于 3，则可以开启一个结合力为 4 的循环。对于右结合运算，则有
c
回到一开始的例子上
c
注意前缀运算符不需要前一个数字，它们永远需要开启一个新的循环。
2. lex 二义性
最常见的例子是 c++ 式的泛型符号。例如
cpp
普通的 lexer 会把两个大于号解析成右移位，这显然不行。一种做法是，让 lexer 永远不要产出右移位符号，然后把 parser 改造成 LL(2) 的。这是最简单的解决方案，但会给 parser 的编写造成很多麻烦。
更好的做法则是让 lexer 支持 token 的分割与合并。当 parser 在处理泛型的时候，如果拿到一个>>，那就只消费掉前面的一个>，把剩下的一个>还给 lexer。之后再去取新 token 的时候，lexer 优先把这个>给吐出来。总而言之，要让 lexer 带上除了“当前消费了多少字符”以外的状态。一些语言正是因为这样的原因，选择了()或者[]作为泛型，然而这不过是把二义性推迟到 parse 阶段而已。
如果你不幸地需要支持 c 样式的自增自减符号，那解析+++和---时也要注意。
更大的麻烦是模板表达式，比如
js
对于正常的字符串，lexer 只需要无脑向后读到未经转义的引号即可。然而模板字符串支持嵌套，这显然超出了 DFA 的能力。一种做法自然是干脆砍掉嵌套的模板字符串，F# 便是如此；另一种则是干脆让 lexer 也用上 LL 系列算法。
工程上来讲，更好的解决方案还是让 lexer 带上更多的状态。当读到`的时候，告诉 lexer 它该处理模板字符串了，接下来应该产出abc 和${；消费掉${，再告诉 lexer 现在是正常模式，产出def和};之后再改回模板字符串模式。
3. parse 二义性
有时候，语法设计中会出现一些二义性的地方，例如在 rust 中
rust
当 parser 读到第二个Foo{的时候，它并不知道这是大括号是结构体字面量的还是 if 的。我们可以通过明智的语法设计规避这些问题，也就是说，在这里直接禁止掉结构体字面量。但是实现的时候如果按照教科书上给每种变体都写一个方法会非常麻烦。我们可以通过给 parser 也带上更多的状态来解决这些冲突。
更不幸地是，有时候真的会遇到需要无限向后看的语法，举例说来，js 的箭头函数
js
我们发现，如果不一直向后读到=>，就无法知道前面的(a, b)到底是括号表达式还是箭头函数的参数。这时候最好的做法还是干脆允许回溯：先把它当作括号表达式来解析，如果遇到问题，再把它当箭头函数来解析。
另一个不幸的例子
ts
在普通的 js 语法中，上述表达式并无歧义。然而在 ts 中，< 会被当成泛型实例化的开头。于是，parser 就只能先整个消费掉<b, c>之后，读到d时，才能发现d可以开启一个新表达式，而泛型实例化表达式后无法直接跟上一个新表达式。那只能从<重新开始 parse，这时我们知道，它是小于号。正是因为这个问题，rust 才发明了::<这个语法。
最后呼吁一下，与其如设计出到处充满歧义的语法再通过种种技巧去解决，不如一开始就想办法避免语法上的二义性，rust 就是好榜样。