递归下降分析
复习
- 上下文无关文法：用递归规则描述语法
- 设计递归：把问题拆成更小的同类问题
- 函数：把一段工作命名、传入参数并获得结果
TL;DR
- 递归下降让每个非终结符对应一个函数
- 函数按产生式尝试匹配输入
- 它直观、容易手写
- 遇到多分支时，通常需要提前看一两个词
正文
有了上下文无关文法，怎样写成程序去解析？最直观的一种方法，叫递归下降分析（recursive descent parsing）。
一个非终结符，一个函数
递归下降的核心思想非常简单：为文法里的每个非终结符，写一个函数。
函数做的事，就是“按这个非终结符的产生式，尝试匹配接下来的输入”：
- 如果产生式要求一个终结符，就检查当前词是不是它，是就“吃掉”这个词，继续往下
- 如果产生式要求另一个非终结符，就调用那个非终结符对应的函数
- 全部匹配成功，说明这个成分解析成功
因为文法规则是递归的，这些函数之间也会互相调用，甚至自己调用自己——这正是“递归下降”名字的由来。文法的递归结构，直接映射成了函数的调用结构。
一个例子
假设有文法：
表达式 → 项 加减
加减 → + 项 加减 | 空
项 → 数字
那么解析“表达式”，就先调用“项”的函数读一个数字，再调用“加减”的函数去读后续的加减。每个非终结符一个函数，逐层往下，逻辑清清楚楚。
遇到选择怎么办
麻烦出现在一条非终结符有多条产生式的时候。比如解析“语句”时，看到当前词，怎么知道该按 if 那条还是按 {} 那条展开？
常见的做法有两种：
- 提前看（lookahead）：看下一个（或几个）词，据此决定用哪条产生式
- 回溯：先试一条，走不通再退回来试另一条（代价较高，一般尽量避免）
用“提前看”就能选对分支、无需回溯的文法，属于后面要讲的 LL 文法。
好的写法
递归下降的优点是贴近人的思维：拿到文法，几乎可以对照着写出代码，可读性也好。因此它是手写解析器时最常用的方式。前提是文法设计得当，让每步都能靠少量前瞻决定分支。
但如果一条非终结符有多个分支、又无法靠提前看区分，这种“从左边、自上而下”的写法就会吃力。那时就需要另一类思路：从输入往上“归约”。下一组会看到它。
思考题 1
递归下降分析器为什么让“每个非终结符对应一个函数”？
思考题 2
递归下降遇到一个非终结符有多条产生式时，需要怎么处理？
小结
知识点
- 递归下降为每个非终结符写一个函数
- 函数按产生式匹配并消费输入，递归调用子成分
- 多分支时需提前看或回溯来选路
- 文法设计良好时，可只用少量前瞻
参考资料
- Wikipedia(zh)：递归下降解析器：为每个非终结符编写函数的解析方法
- Wikipedia(zh)：LL解析器：只向前看固定数量词法单元的解析器
思考题答案（仅供参考）
思考题 1
因为每个非终结符代表一种语法成分，而解析这种成分的过程是确定的：按它的产生式匹配输入、并在需要时递归解析更小的成分。这正好对应一个函数，函数之间互相调用即对应文法规则间的引用。
思考题 2
需要判断该用哪条产生式。常见做法是提前查看后面一个或几个词法单元（lookahead），据此选择分支；若无法确定，则可能需要回溯尝试。用提前看就能唯一决定分支的文法，属于 LL 文法。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪