从LL(1)文法判定到递归下降：一个PL/0表达式分析器的完整设计思路
从LL(1)文法到递归下降：构建表达式分析器的思维路径
当你第一次看到PL/0的BNF文法描述时，是否感觉像在读天书？那些尖括号、竖线和星号究竟如何转化为可执行的语法分析代码？本文将带你走过一条清晰的思维路径——从形式化的文法规则到可运行的递归下降分析器。不同于单纯复制实验代码，我们更关注为什么需要这些步骤以及它们之间如何衔接。如果你正在为"如何将编译原理理论落地"而困扰，这篇文章正是为你准备的。
1. 解构BNF：文法规则的逆向工程
面对PL/0表达式文法时，首先要做的是理解而非翻译。原始BNF描述如下：
<表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| '(' <表达式> ')'1.1 文法简化技巧
- 符号替换：用单字母代替冗长的非终结符名（如B代表表达式，X代表项）
- 正则扩展：将
{...}转换为(...)*的克林闭包形式 - 选项合并：用
|合并相同左部的产生式
简化后的文法：
B -> JX | X # 表达式 X -> Y (C Y)* # 项 Y -> S | N | (B) # 因子 J -> + | - # 加减运算符 C -> * | / # 乘除运算符提示：简化后的文法应保持与原BNF完全等价的表达能力，任何修改都需通过派生测试验证
1.2 语法图绘制实战
语法图是文法规则的视觉化呈现，绘制时需注意：
- 矩形框表示非终结符
- 圆形框表示终结符
- 箭头路径展示可能的符号组合
以表达式为例的语法图逻辑：
+---+ +---+ | J |------>| X | +---+ +---+ | ^ v | Start---->+-----------+--->End | | +--->X------+2. LL(1)判定：First与Follow集的博弈
2.1 计算First集的步骤
- 终结符：First(a) = {a}
- 非终结符：
- 对A→α，将First(α)的非ε元素加入First(A)
- 若α能推导出ε，则加入ε
- 序列：对X1X2...Xn：
- 加入First(X1)的非ε元素
- 若X1含ε，继续检查X2，依此类推
PL/0表达式文法的First集：
First(B) = {+, -, S, N, (} First(X) = {S, N, (} First(Y) = {S, N, (}2.2 Follow集计算要点
- 对文法的开始符号，首先将$加入其Follow集
- 对产生式A→αBβ：
- 将First(β)的非ε元素加入Follow(B)
- 若β可推导出ε，则将Follow(A)加入Follow(B)
- 对A→αB，将Follow(A)加入Follow(B)
PL/0表达式文法的Follow集：
Follow(B) = {$, )} Follow(X) = {+, -, $, )} Follow(Y) = {*, /, +, -, $, )}2.3 LL(1)判定三要素
- 无左递归：不存在A → Aα形式的产生式
- 无公共前缀：对同一非终结符的多个产生式，各右部的First集不相交
- ε产生式约束：若A能推导出ε，则First(A)与Follow(A)不相交
PL/0表达式文法的LL(1)验证表：
| 非终结符 | 产生式 | 预测符号 |
|---|---|---|
| B | B→JX | First(JX) = {+, -} |
| B | B→X | First(X) = {S, N, (} |
| X | X→Y (C Y)* | First(Y) = {S, N, (} |
| Y | Y→S | First(S) = {S} |
| Y | Y→N | First(N) = {N} |
| Y | Y→(B) | First('(') = {(} |
3. 递归下降：从文法到代码的映射
3.1 子程序设计模式
每个非终结符对应一个解析函数，其结构遵循固定模式：
void parse_X() { if (current_token ∈ First(α1)) { parse_α1(); } else if (current_token ∈ First(α2)) { parse_α2(); } else { error("Unexpected token"); } }3.2 PL/0表达式解析实现
表达式(B)的递归下降伪代码：
PROCEDURE B; BEGIN IF sym IN {'+', '-'} THEN // 匹配First(J) advance; X; ELSE IF sym IN First(X) THEN X; ELSE error; WHILE sym IN {'+', '-'} DO // 匹配Follow(X) BEGIN advance; X; END END;项(X)的解析函数示例：
PROCEDURE X; BEGIN Y; WHILE sym IN {'*', '/'} DO // 匹配First(C) BEGIN advance; Y; END END;3.3 错误恢复的关键策略
- 恐慌模式：跳过符号直到遇到同步记号（通常为Follow集元素）
- 短语级恢复：在错误点插入/删除/替换符号
- 错误产生式：在文法中显式定义常见错误模式
4. 完整实现框架：C++实战示例
4.1 核心数据结构
enum TokenType { PLUS, MINUS, TIMES, SLASH, IDENT, NUMBER, LPAREN, RPAREN, END }; struct Token { TokenType type; string value; }; vector<Token> tokens; size_t pos = 0;4.2 递归下降实现
表达式解析函数：
void parseExpression() { if (match({PLUS, MINUS})) { advance(); } parseTerm(); while (match({PLUS, MINUS})) { advance(); parseTerm(); } } void parseTerm() { parseFactor(); while (match({TIMES, SLASH})) { advance(); parseFactor(); } } void parseFactor() { if (match({IDENT, NUMBER})) { advance(); } else if (match(LPAREN)) { advance(); parseExpression(); expect(RPAREN); } else { throw SyntaxError("Expected identifier, number or '('"); } }4.3 辅助函数实现
bool match(TokenType type) { return pos < tokens.size() && tokens[pos].type == type; } bool match(initializer_list<TokenType> types) { return any_of(types.begin(), types.end(), [this](auto t) { return match(t); }); } void advance() { if (pos < tokens.size()) pos++; } void expect(TokenType type) { if (!match(type)) { throw SyntaxError("Unexpected token"); } advance(); }在实现过程中，最易出错的是边界条件处理——比如在解析嵌套表达式时，必须确保每个左括号都有对应的右括号匹配。我曾在一个项目中花费两小时调试，最终发现只是因为忘记在parseFactor()中调用advance()跳过右括号。这种细节正是理论转化为实践时最需要关注的要点。