做一个带错误恢复的 Pratt 解析器

目标

做出一个语法分析器，把词法单元列表搭成 AST（/root/mini/ast_nodes.py 中的节点）。表达式用 Pratt 方式，通过一张表处理优先级和结合方向；语句用递归下降来读；出错时记下错误，并从下一条语句重新开始读。

为什么重要

优先级或结合方向只要有一处出错，程序就会不报错地计算出另一个值。如果把 10 - 4 - 3 从右边开始结合，结果不是 3 而是 9，而且没有任何警告。另外，在第一个错误处就停下的语法分析器，会让用户有多少个错误就得修改、重新运行多少次。

语法与树

program     := declaration* EOF
declaration := "let" IDENT "=" expr ";"  |  "fn" IDENT "(" [IDENT ("," IDENT)*] ")" block  |  statement
statement   := "print" expr ";" | "if" "(" expr ")" block ["else" (if문 | block)]
             | "while" "(" expr ")" block | "return" [expr] ";" | block | expr ";"
block       := "{" declaration* "}"
결합력      = 1(오른쪽) · || 2 · && 3 · == != 4 · < <= > >= 5 · + - 6 · * / % 7
             앞 - ! 는 피연산자를 8 로 · ^ 9(오른쪽) · 호출 ( 10
노드 위치   ast_nodes.py 맨 위 표 — 연산자 토큰, 호출은 여는 괄호, Let·Fn 은 이름 토큰, 문장은 키워드,
             Block 은 여는 중괄호, ExprStmt 는 식의 위치. && 와 || 는 Logical, 나머지 두 항은 Binary
오류 글자   ParseError(토큰, 메시지), str() 은 "줄:칸: 메시지". 위치는 기대한 것을 찾지 못한 그 토큰
             expected expression · expected ';' · expected ')' · expected '(' · expected '{' ·
             expected '}' · expected identifier · expected '=' · invalid assignment target(그 = 의 위치)
복구        declaration 이 ParseError 를 잡아 self.errors 에 글자를 적고 synchronize() 한 뒤 None.
             synchronize: 지금 토큰이 '}' 가 아닌 STARTERS(fn let if while print return { }) 면 그대로
             멈춘다. 아니면 한 토큰을 소비하고, 끝이 아닌 동안 ';' 바로 뒤이거나 STARTERS 앞이면 멈춘다.

步骤

补全 /root/mini/parser.py 的 ParseError、Parser(tokens)（属性有 tokens、pos 和 errors）以及 peek、previous、at_end、advance（在 EOF 处原地不动）、check、match(*kinds) 和 expect(kind, message)。
补全 prefix()——INT、true/false、IDENT 和用括号括起来的表达式。- 和 ! 交给 prefix_operator()（第 4 步），其他词法单元则在其位置报 expected expression。
补全 POWER 表、expression(rbp=0) 和 infix(left)——二元运算的优先级与左结合。(、^ 和 = 交给 finish_call 和 right_assoc。
补全 UNARY、prefix_operator() 和 right_assoc(left)——前缀运算符、^ 和 = 的右结合，以及赋值目标不是名字时的 invalid assignment target。
补全 finish_call(callee)——从没有参数到多个参数，以及 f(x)(y) 这样的连续调用。
补全 declaration、let_declaration、fn_declaration、statement、if_statement、block、program，以及模块级的 parse_program(src)。它返回 (Program, 오류 목록)（占位符为错误列表）；如果出现词法分析器的错误，列表里只放那一条，树为 None。
补全 STARTERS 和 synchronize()。评分器会把错误程序的错误列表和挽救出来的树与参考对照。
评分器会把 120 个随机程序的树，以及 240 个破坏了一个词法单元的程序的错误列表，与参考对照。

参考

python3 /root/mini/mini.py parse 파일.mini（占位符为文件名）会用你的语法分析器打印 S 表达式或错误。只想看表达式时，请使用只有一行 print 식;（占位符为表达式）的文件。
词法分析器（lexer.py）和节点（ast_nodes.py）在实验开始时已经铺好。也可以把前一个模块中做好的你自己的 lexer.py 粘贴过来使用。
常见错误：把所有运算符都读成右结合，把 -a^b 结合成 (-a)^b，让调用的结合力比一元运算符更松，恢复时一个词法单元也不消耗，导致原地打转。
会话从 60 分钟开始，可以用＋时间延长，结束后 /root/mini 会消失。

查看、消耗并期望词法单元

用一个 pos 指向词法单元列表。advance 返回当前词法单元，并且只有当它不是 EOF 时才增加 pos。expect 在种类相符时 advance，否则就在当前词法单元（peek）的位置抛出 ParseError——不是刚刚经过的那个词法单元。

表达式的第一块

按词法单元的种类区分。INT 用 int(text)，true/false 是 Bool，IDENT 是 Var，节点位置是该词法单元的行和列。括号把内部用 expression() 读出来并期望 ')'，但不另外创建括号节点，而是原样返回内部的表达式。

用结合力表解决优先级

while POWER.get(peek().kind, 0) > rbp: left = infix(left)。infix 消耗运算符，并把右侧读作 expression（该运算符的结合力）。同一层的运算符结合力相同，越不过 >，所以回到外层循环，成为左结合。

前缀运算符与右结合

前缀运算符把操作数读作 expression(UNARY)。UNARY 必须比 * 大、比 ^ 小，-a*b 才是 (-a)*b，-a^b 才是 -(a^b)。^ 和 = 把右侧读作结合力 - 1，让右侧一直吞到同一层。如果 = 的左边不是 Var，就在那个 = 的位置报错。

调用——结合得最紧

把 ( 也看作结合力为 10 的后缀运算符。finish_call 消耗左括号，如果不是 ')'，就读 expression()，并在有 ',' 时重复，最后期望 ')'。Call 节点的位置是左括号。

语句与块——递归下降

declaration 区分 let 和 fn，statement 区分 print、if、while、return、块和表达式语句。else 后面如果是 if，就再次调用 if_statement 来构成链。declaration 捕获 ParseError，记下之后 synchronize，再返回 None；block 和 program 会丢弃 None。

出错之后重新站起来

如果出错的词法单元是不为 '}' 的 STARTERS，就不消耗，直接停下——以该关键字开头的语句会先吃掉关键字，所以不会原地打转。否则至少消耗一个词法单元，然后在 previous() 是 ';' 或 peek() 是 STARTERS 时停下。

随机程序与被破坏的程序

没有新代码。被破坏的程序里，如果错误比参考多，说明恢复之后在莫名其妙的地方重新开始读（连锁错误）；如果比参考少，说明在一个错误之后跳得太远。