3 Syntax Analysis
职责
输入 Token 流,输出语法树。做两件事:
- 判定:这串 Token 是否合法
- 构造:如果合法,把它的层级结构还原出来
第二点才是目的。编译器要的不是"通过/不通过",而是一棵能往下走的树。
x = a + b * c;
│
▼
Assign
/ \
x Add
/ \
a Mul
/ \
b c注意 * 在 + 下面——优先级体现在树的高低上:越靠下的运算符结合越紧。
上下文无关文法(CFG)
文法:
- :终结符(Token)
- :非终结符(语法变量)
- :开始符号
- :产生式集合,
例:简单表达式文法
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id | num这个文法同时编码了两件事:
+ -比* /低一层 → 优先级E递归出现在左边 → 左结合
推导与归约
- 最左推导:每次替换最左边的非终结符
- 最右推导(规范推导):每次替换最右边的非终结符
- 归约:推导的逆过程,LR 分析器就是在做最右推导的逆
最左推导 E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + F ⇒ id + id二义性
若存在一个句子有两棵不同的语法树(或两个不同的最左推导),文法就是二义的。
经典例子——悬空 else:
stmt → if expr then stmt
| if expr then stmt else stmt
| otherif a then if b then s1 else s2 里,else 配对内层的 if 还是外层的?两种解析都合法。
解决二义性的两条路:
- 改文法:把语句分成"已匹配"和"未匹配"两类,强制就近配对
- 加规则:语法分析器遇到冲突时按约定选一个(如 yacc 的 "shift 优先",等价于就近配对)
// 改写后的无二义文法
stmt → matched | unmatched
matched → if expr then matched else matched | other
unmatched → if expr then stmt
| if expr then matched else unmatched注意:二义性是文法的性质,不是语言的性质。有些语言(如 C 的某些部分)本质上有二义,只能靠额外规则消除。而且判定任意 CFG 是否二义是不可判定的——所以别指望有通用工具帮你检查。
消除左递归
直接左递归(如 E → E + T | T)会让自顶向下分析器无限递归,必须改写:
改写为:
直观理解:把"左边递归"变成"右边循环",递归改迭代。
E → T E'
E' → + T E' | - T E' | ε
T → F T'
T' → * F T' | / F T' | ε
F → ( E ) | id | num代价:树形变了,需要在语义动作里手工还原左结合的 AST。
间接左递归()要先把非终结符排序,逐个代入展开,再消除直接左递归。
提取左公因子
若,自顶向下无法只看一个 Token 就决定选哪条。改写为:
即"先吃掉公共前缀,再推迟决策"。
两大流派
| 自顶向下(LL) | 自底向上(LR) | |
|---|---|---|
| 方向 | 从 S 推导到输入 | 从输入归约到 S |
| 直觉 | "下一个 Token 该走哪条产生式" | "当前这一串能归约成什么" |
| 代表 | 递归下降、ANTLR | yacc/bison、LALR |
| 表达能力 | LL(k) ⊂ LR(k) | 更强,能处理左递归 |
| 手写难度 | 极低 | 高(一般用生成器) |
| 错误定位 | 好 | 一般 |
LL(k) 文法是 LR(k) 文法的真子集。任何能用递归下降写的,LR 都能写;反过来不成立(左递归文法 LR 能直接处理,LL 必须先改写)。
自顶向下:递归下降
每个非终结符对应一个函数,函数体按产生式右部展开:
// E → T { (+|-) T }
std::unique_ptr<Expr> parseExpr() {
auto lhs = parseTerm();
while (cur == Tok::Plus || cur == Tok::Minus) {
Tok op = cur; advance();
auto rhs = parseTerm();
lhs = std::make_unique<Binary>(op, std::move(lhs), std::move(rhs));
}
return lhs;
}
// T → F { (*|/) F }
std::unique_ptr<Expr> parseTerm() {
auto lhs = parseFactor();
while (cur == Tok::Star || cur == Tok::Slash) {
Tok op = cur; advance();
auto rhs = parseFactor();
lhs = std::make_unique<Binary>(op, std::move(lhs), std::move(rhs));
}
return lhs;
}
// F → ( E ) | id | num
std::unique_ptr<Expr> parseFactor() {
if (cur == Tok::LParen) {
advance();
auto e = parseExpr();
expect(Tok::RParen);
return e;
}
if (cur == Tok::Id) { auto s = text; advance(); return std::make_unique<Var>(s); }
if (cur == Tok::Num) { long long v = value; advance(); return std::make_unique<Int>(v); }
error("expected expression");
}注意这里左递归已经变成了 while 循环——递归下降只能处理右递归,所以表达式必须写成 E → T { + T } 的迭代形式。循环天然产生左结合树,正好符合 a - b - c = (a - b) - c。
LL(1) 的判定条件:对同一非终结符的任意两条产生式,要求
且若,还要。
FIRST 与 FOLLOW
FIRST(X):从 X 能推导出的串的第一个终结符的集合(含)。
若 X 是终结符: FIRST(X) = {X}
若 X → ε: 加入 ε
若 X → Y1 Y2 ... Yk:
加入 FIRST(Y1)(去掉 ε)
若 Y1 ⇒* ε,继续看 FIRST(Y2)……
若全部都能 ⇒* ε,加入 εFOLLOW(A):紧跟在 A 后面的终结符集合。
FOLLOW(S) 含 $(输入结束标记)
若 A → α B β: FOLLOW(B) 加入 FIRST(β)(去掉 ε)
若 A → α B 或 A → α B β 且 β ⇒* ε:
FOLLOW(B) 加入 FOLLOW(A)有了 FIRST/FOLLOW 就能构造 LL(1) 预测分析表 M[A, a]:对每个产生式,把 填入 M[A, t]();若,还要填入所有 M[A, t]()。任一格子里有多于一条产生式 ⇒ 不是 LL(1)。
自底向上:LR
LR 分析器维护一个栈,反复做两类动作:
- 移进(Shift):把当前 Token 压栈
- 归约(Reduce):把栈顶的 弹出,压入(其中)
决定动作的依据是状态机(由 LR 项集构造)。核心概念:
LR(0) 项:产生式加一个"圆点"表示进度,如。圆点在末尾 表示"可以归约了"。
项集闭包:若项集中有,则把(所有 B 的产生式)都加进来——因为接下来可能要先识别 B。
LR 家族
| 类型 | 决策依据 | 表大小 | 能力 |
|---|---|---|---|
| LR(0) | 只看栈内容 | 小 | 很弱,几乎不实用 |
| SLR(1) | 归约时看 FOLLOW(A) | 小 | 弱于 LALR |
| LALR(1) | 合并同心项集的前瞻 | 小 | 实用,yacc/bison 默认 |
| LR(1)(规范) | 每个项带精确前瞻集 | 大 | 最强 |
LALR(1) 是工程上的甜点:能力接近 LR(1),表大小和 SLR 相当。bison 默认生成 LALR(1)。
冲突
- 移进-归约冲突(Shift/Reduce):栈顶既可以归约,当前 Token 又可以移进。经典场景就是悬空 else。bison 默认移进优先(→ else 就近配对)。
- 归约-归约冲突(Reduce/Reduce):两条产生式都能归约。几乎总是文法设计有问题,必须改文法。
优先级声明就是解决移进-归约冲突的实用手段:
%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUSbison 用这些声明填冲突格子:比较运算符优先级和当前 Token 优先级决定 shift 还是 reduce。这比把优先级写进文法清爽得多,也解释了为什么 "precedence climbing"(见下)这么流行。
优先级爬升 / Pratt 解析
手写表达式解析最优雅的方案。每个运算符绑定一个优先级,解析时"吃掉左边所有优先级更高的"。
// binding power:数值越大结合越紧
int lbp(Tok t) {
switch (t) {
case Tok::Assign: return 1;
case Tok::Plus: case Tok::Minus: return 10;
case Tok::Star: case Tok::Slash: return 20;
default: return 0;
}
}
// nud: 前缀位置(没有左操作数)
std::unique_ptr<Expr> nud(Tok t) {
if (t == Tok::Num) { long long v = value; advance(); return std::make_unique<Int>(v); }
if (t == Tok::Id) { std::string s = text; advance(); return std::make_unique<Var>(s); }
if (t == Tok::Minus) { advance(); return std::make_unique<Neg>(expr(30)); } // 一元负号
if (t == Tok::LParen) { advance(); auto e = expr(0); expect(Tok::RParen); return e; }
error("unexpected token");
}
// led: 中缀位置(已有左操作数)
std::unique_ptr<Expr> led(Tok t, std::unique_ptr<Expr> lhs) {
if (t == Tok::Assign) { advance(); return std::make_unique<Assign>(std::move(lhs), expr(1)); }
int bp = lbp(t);
advance();
auto rhs = expr(bp); // 右结合用 expr(bp - 1)
return std::make_unique<Binary>(t, std::move(lhs), std::move(rhs));
}
// 核心:解析优先级 >= minBp 的表达式
std::unique_ptr<Expr> expr(int minBp) {
auto lhs = nud(cur);
while (lbp(cur) > minBp) // 关键:严格大于
lhs = led(cur, std::move(lhs));
return lhs;
}为什么 > 而不是 >=?因为左结合要求同优先级继续循环(a - b - c 的第二个 - 要被吃掉),右结合要求同优先级停下递归(a = b = c 的第二个 = 交给右操作数处理)。所以右结合的 led 里传 bp - 1。
优点:一个 while 循环搞定任意优先级层次,不用为每个优先级写一个产生式、也不用消除左递归。Lua、Rust、Go 的表达式解析,以及很多 JSON/CSS 解析器都是这个套路。
构造 AST
Parser 直接产出 AST 而非 CST。CST 忠实于文法(含括号、分号),AST 只留有意义的东西。
区别举例:a + b + c 的 CST 里,+ 的两个孩子还是 E 节点;AST 里直接是嵌套的 Binary(Add, Binary(Add, a, b), c)。括号在 AST 里完全消失——因为优先级已经体现在树形上了。
设计 AST 节点的经验:
- 区分表达式和语句(Expr / Stmt 两类基类)
- 携带源码位置(行、列)——报错和调试都靠它
- 节点用值语义还是指针语义:C++ 里
unique_ptr最省心;Rust 里用Box或 arena + 索引 - 要不要访问者模式:遍历操作多(类型检查、常量折叠、代码生成、打印)时用访问者,否则给节点加虚方法就够了
错误恢复
| 策略 | 做法 | 评价 |
|---|---|---|
| 恐慌模式 | 丢弃 Token 直到"同步集"(; } 语句首关键字) | 最常用,简单有效 |
| 短语层恢复 | 在栈顶填一个"假的"Token 让归约能继续 | bison 的 error 产生式 |
| 错误产生式 | 文法里显式写常见错误的产生式 | 精准提示,但要预判错误 |
| 全局纠正 | 最小编辑距离把输入改成合法串 | 理论美好,几乎不用 |
实用建议:
- 同步集选"语句边界"(
;、}、关键字),恢复后大概率能继续 - 限制报错数量(如最多 100 条),防止一个错误引发雪崩
- 报"期望什么"而不只是"出错了":
expected ';' after expression at line 12
常见坑
- 递归下降里忘了处理左递归,直接栈溢出
if-else二义没处理,导致else绑定错对象- 优先级写在文法里导致层级爆炸:加减乘除四层语法规则,加个
?:就得再插几层。改用优先级爬升或 bison 的%left/%right - 一元运算符的优先级搞错:
-a * b是(-a) * b,但-a ** b(Python)是-(a ** b)。一元和二元的绑定力要分开定义 - 前瞻不够:LL(1) 处理不了需要看两个 Token 的构造,要么改写文法,要么手动加前瞻
- AST 丢了源码位置,报错时只能说"某处出错"
参考
- Crafting Interpreters - Parsing
- Pratt 原始论文 Top Down Operator Precedence(1973)
- bison 手册的 Precedence
- ANTLR4:ALL(*) 算法,能处理需要无限前瞻的文法