@
levelworm > 但是什么叫做 each rule here only matches expressions at its precedence level or higher?
意思就是说优先级低的（也就是 BNF 靠上的、行数小的）可以兼容他自己那行和优先级更高的那行（也就是 BNF 靠下的，行数大的）。比如调用 factor，它不仅自己可以解析乘除，而且还可以递归解析 unary 和 primary，但是他不能解析 term 。
> 我感觉他这里很巧妙的就把之前比较复杂的东西，比如说 expression 简化成 equality 了，但是对于我这个看的人来说，似乎就需要一个个调用下去，才能真正知道这行到底对应的是什么东西。
这个就是 recursive descent 的特点，因为 CFG 是可以递归嵌套的（ expression 里面有 binary，binary 里还能有 binary ），我们用的编程语言的表达式是可以互相任意无限嵌套的，所以需求就是递归的，如果不这样一层层调用其他的方式其实看起来更复杂。如果 BNF 没有这层递归，那么就只能得到一个比 basic 还 basic 很多的语言了，写起来可能跟汇编一样。
至于实现 BNF，其实本质上就是照着 BNF 结构做一个 N 叉树 DFS，而且代码很像 BNF 本身很直观。
private Expr equality() {
Expr expr = comparison();
while (match(BANG_EQUAL, EQUAL_EQUAL)) {
Token operator = previous();
Expr right = comparison();
expr = new Expr.Binary(expr, operator, right);
}
return expr;
}
其实就和平常刷 LeetCode 差不多，只不过多了 match 判断到底该用几叉树和构建哪种 AST：
fn traverse(root) {
left = traverse(root.left)
right = traverse(root.right)
return AST(left, right)
}
如果也就是说，上面的 equality match 的结果为 true 时，这段代码的骨架等于二叉树后序遍历，就在原地建起来 Binary：
fn equality() {
left = comparison()
right = comparison()
return Binary(left, right)
}
如果 match 为 false 时，那就交给子规则去递归，有点像链表（一叉树）遍历但不干活，有点像 LeetCode 那种删除链表后 N 个节点那种题里，前面节点 length - N 个节点无操作只递归一样：
fn equality() {
exp = comparison()
return exp
}
可以尝试做一下二叉树的序列化和反序列化，还有根据前序中序 / 中序后序结果反推二叉树的题。然后把这几道题扩展一下变成多态，其实就能得到 recursive descent 了。
本质上就是序列化字符串或者源码本身是一个隐式树，你控制代码递归遍历这个隐式树来创建一个真树。如果你把 N 叉树的遍历搞熟了，假如你从来没听说过 recursive descent，有人给你讲明白 BNF 的需求，你很可能也会凭空发明出 recursive descent 。