用两个数字解决优先级 — Pratt 解析
一句话总结
语法分析器把词法单元序列搭成一棵树。语句用递归下降来读，每条语法规则对应一个函数；表达式用 Pratt 解析来读，每个运算符有一个结合力（binding power，一个数字），通过比较这些数字让树不断生长。这样，优先级和结合方向就集中在一张表里，即使出错，也能从下一条语句重新开始读。
为什么需要它
1 - 2 - 3 是 (1 - 2) - 3，所以得 -4；2 ^ 3 ^ 2 是 2 ^ (3 ^ 2)，所以得 512。外形相同，结合的方向却相反。-2 ^ 2 得 -4，而 -2 * 2 则是 (-2) * 2。这些规则一旦出错，程序不会有任何语法错误，却会计算出另一个值——这是最难查的一类 bug。
为每条语法规则各写一个函数的递归下降（比如 덧셈 := 곱셈 (('+'|'-') 곱셈)*（韩文依次意为“加法”“乘法”）），同样可以读表达式，但每个优先级层都要多一个函数，十层就是十个函数，想插入一层，还得修改整条函数链。Pratt 解析把它压缩成一张表。层就是数字，结合方向则取决于读右侧时是原样使用这个数字，还是减一。
而且语法分析器不能在第一个错误处就停下。用户并不想改好一个错误、重新运行、再看下一个错误，如此反复。记下错误，并且跳到下一条语句可能开始的位置之后继续读，才能一次报告多个错误。
工作原理
Pratt 解析器的心脏是一个循环。
expression(rbp):
left = prefix() # 숫자·이름·괄호·앞에 붙는 - !
while 다음 연산자의 결합력 > rbp:
left = infix(left) # 그 연산자로 left 를 왼쪽 자식 삼아 한 층 위 노드를 만든다
return left
infix 把右操作数读作 expression(그 연산자의 결합력)（占位符为该运算符的结合力）。这样，右侧的表达式就只吞入比自己更强的运算符，遇到同一层的运算符就停下，交给外层循环——这就是左结合。右结合（^、=）则把右侧读作 결합력 - 1（占位符为结合力），让右侧一直吞到同一层。1 - 2 * 3 - 4 中树生长的过程如下（- 是 6，* 是 7）。
읽은 것 left 의 모양 다음 연산자 비교
1 1 - 6 > 0 → infix: 오른쪽을 expression(6) 으로
2 * 3 (* 2 3) - 6 > 6 ? → 아니오, 오른쪽은 여기서 멈춤
1 - (2*3) (- 1 (* 2 3)) - 6 > 0 → infix 한 번 더, 방금 트리가 왼쪽 자식으로
4 4 끝
최종 (- (- 1 (* 2 3)) 4)
这是本课程的结合力表。前缀的 - 和 ! 把操作数读作 8，所以吞不下 *（7），却吞得下 ^（9）——因此 -a*b 是 (-a)*b，-a^b 是 -(a^b)。
| 结合力 | 运算符 | 结合方向 |
|---|---|---|
| 1 | = |
右 |
| 2 · 3 | || · && |
左 |
| 4 · 5 | == != · < <= > >= |
左 |
| 6 · 7 | + - · * / % |
左 |
| 8 | 前缀 - ! |
— |
| 9 · 10 | ^ · 调用 f(…) |
右 · — |
赋值是右结合的，并且左边必须是名字。a = b = c 是 a = (b = c)，而 a + b = c 会被读成 (a + b) = c，然后以“赋值目标不是名字”被拒绝。如果去掉这项检查，语法分析器就会悄悄地构造出奇怪的树。
语句用递归下降来读。看到 if，就按 ( 表达式 ) 块 [else（if 语句 | 块）] 的顺序期待，如果不是期待的词法单元，就在该词法单元的位置报出像 “expected ';'” 这样的错误。捕获错误的地方是一条声明（declaration）。捕获之后记下错误并进行恢复（synchronize）——一直跳过词法单元，直到 ; 的正后方，或者 let、fn、if、while、print、return、{、} 的前面。这里有一件必须遵守的事：至少要前进一个词法单元。如果在最外层的 } 这样无法作为任何语句开头的词法单元处出了错，却停在原地，下一条声明就会在同一个词法单元上报出同样的错误，永远循环下去。
在现场相遇的样子
- GCC 和 Clang 手写的语法分析器。这两个编译器都不用语法分析器生成器（yacc、bison），而是使用手写的递归下降语法分析器，因为这样可以由人精细地打磨错误信息和恢复。表达式部分用优先级表来读的方式（运算符优先级解析）与 Pratt 的思路相同。
- 一次报出多个错误。如果编译器一下子显示二十个错误，而且靠后的几个莫名其妙，那就是恢复不够好。在第一个错误之后从错误的位置重新开始读，把完好的代码当成了错误来读，这就是“连锁错误”。因此大多数编译器都会说“请从第一个错误开始修”。
- 编辑器里宽容的语法分析器。编辑器的语言服务器在你输入的过程中，收到的总是语法有误的代码。恢复做得好的语法分析器，才能让写了一半的函数下面的代码也能正常自动补全和显示下划线。
下一项实验要做什么
在 parser.py 中分七块做出语法分析器——查看、消耗并期望词法单元的工具；字面量、名字和括号；Pratt 循环与二元运算；前缀运算符、右结合（^、=）与赋值目标检查；调用；语句与块；以及错误恢复。树的形状由 ast_nodes.py（课程提供）中的节点和 S 表达式规定，评分器会把几百个随机表达式的树和节点位置，与参考语法分析器逐字对照。