4 Syntax-Directed Translation
要解决的问题
语法分析只回答"结构对不对"。但编译器真正要的是在识别结构的同时做点事:算类型、建符号表、生成代码。
语法制导翻译(Syntax-Directed Translation, SDT)就是这套机制:把语义动作(semantic action)挂在语法规则上,语法分析器走到哪儿就执行到哪儿。
E → E₁ + T { E.code = E₁.code || T.code || "add"; }两套 notation
语法制导定义(SDD / Syntax-Directed Definition)
比较"声明式":给文法的每个符号附上属性(attribute),给每条产生式附上语义规则(semantic rule)。只说明属性之间应该满足什么关系,不规定什么时候算。
产生式 语义规则
L → E n L.val = E.val
E → E₁ + T E.val = E₁.val + T.val
E → T E.val = T.val
T → num T.val = num.lexval语法制导翻译方案(SDT / Translation Scheme)
比较"命令式":把语义动作写成 {...} 直接嵌在产生式右部,位置即执行时机。
E → T { print('+') } E'SDD 更形式化(便于讨论属性求值顺序、做静态分析),SDT 更贴近实现(yacc/bison、ANTLR 里的 action 就是 SDT)。实际写编译器时脑子里是 SDT,讨论优化时用的是 SDD。
属性分类
综合属性(Synthesized)
自底向上传递:节点的值只依赖子节点的属性和自身,不依赖兄弟或父节点。
典型:E.val、类型、生成的代码串。可以在一次自底向上遍历(后序遍历)中算完。
继承属性(Inherited)
自顶向下 / 横向传递:节点的值依赖父节点或左兄弟的属性。
典型:
- 符号表往下传(子节点要知道父作用域有哪些变量)
- 声明语句
int a, b, c;中,a的类型要传给b、c int x = f(1)中,x的声明类型下传给初始化表达式做隐式转换检查
继承属性让求值顺序变复杂,是衡量"这个方案好不好实现"的关键指标。
内在属性(Intrinsic)
词法分析器直接给出的:标识符名、常量值、源码位置。
两类可实现的 SDD
S-属性定义(S-attributed)
只用综合属性。
- 求值方式:后序遍历(自底向上)一次搞定
- 配合:LR 分析器 + 栈上并行存属性,天然契合
- 覆盖:表达式求值、代码生成这类"从叶子往上汇总"的任务
L-属性定义(L-attributed)
属性依赖限制为:
- 继承属性只能依赖父节点的继承属性和左侧兄弟的任意属性(不能依赖右侧,也不能依赖自身的综合属性)
- 综合属性可以任意依赖
关键约束是**"不能看右边"**——因为自顶向下(LL)分析是从左到右推导的,走到某个位置时右边的兄弟还没解析出来。
- 求值方式:深度优先、从左到右一趟遍历
- 配合:LL 分析器 + 递归下降(继承属性作为函数参数传入,综合属性作为返回值)
- S-属性 ⊂ L-属性,L-属性能表达的东西更多(比如符号表传递)
// 递归下降里 L-属性就是"参数 + 返回值"
void parseDecl(Type inheritedType) { // 继承属性 → 参数
expect(Tok::Id);
symbolTable.insert(text, inheritedType);
while (cur == Tok::Comma) { ... } // 左兄弟信息已可用
}
Type parseType() { ... } // 综合属性 → 返回值依赖图与求值顺序
对每个语法树节点构造依赖图:属性是顶点,属性间的依赖是有向边。
E.val
/ \
E₁.val T.val- 边 表示"算 b 需要先有 a"
- 无环 ⇒ 存在拓扑序,可以按拓扑序求值
- 有环 ⇒ 这个 SDD 对这棵树不可实现
判定任意 SDD 是否无环是不可判定的,但有两个足够用的充分条件:
- S-属性定义 ⇒ 一定无环
- L-属性定义 ⇒ 一定无环
所以工程上只写这两类,不追求最一般的形式。
求值方法
| 方法 | 适用 | 说明 |
|---|---|---|
| 后序遍历 | S-属性 | 最简单,自底向上算完 |
| 递归下降带参数 | L-属性 | 继承当参数,综合当返回值 |
| 依赖图拓扑排序 | 任意无环 SDD | 通用但要建图,慢 |
| 一遍扫描(on the fly) | 特定 SDT | 边分析边算,最省内存 |
自底向上求值:并行栈
LR 分析器做归约时,属性可以和文法符号放在同一个栈里,归约时同时弹出/压入:
栈: [ E₁ E₁.val ]
[ + ]
[ T T.val ]
│
│ 归约 E → E₁ + T
▼
[ E E.val = E₁.val + T.val ]栈的每一项是 <符号, 属性组>,归约时按语义规则算出新属性压回去。这就是 yacc 里 $$ / $1 / $2 的本质:
expr: expr '+' term { $$ = new Binary(ADD, $1, $3); }
| term { $$ = $1; }
;
term: NUM { $$ = new Int($1); }
;$1、$3 就是右部第 1、第 3 个符号的综合属性,$$ 是左部的综合属性。栈上的位置就是属性存储。
边分析边算 vs 建完树再算
两种工程选择:
A. Parser 直接生成 IR(一遍法):语法动作里直接发射三地址码。省内存、快,但优化几乎没法做(还没看到后面的代码),而且回溯/错误恢复时已经发射的代码不好撤销。早期的简单编译器这么干。
B. Parser 先建 AST,之后再遍历:现代编译器的标准做法。AST 建完后可以做多遍分析(类型检查、常量折叠、CFG 构造…),优化空间大得多。代价是多一份内存开销。
结论:除非在写极其受限的环境(比如一个 200 行的表达式求值器),否则都选 B。
消除左递归时,动作怎么办
左递归改写会改变推导方向,语义动作必须跟着调整。
原文法(左递归,天然左结合):
E → E₁ + T { E.val = E₁.val + T.val }
| T { E.val = T.val }改写为右递归后:
E → T { E'.inh = T.val } E' { E.val = E'.syn }
E' → + T { E'₁.inh = E'.inh + T.val } E'₁ { E'.syn = E'₁.syn }
| ε { E'.syn = E'.inh }注意变化:
- 综合属性
E.val变成了继承属性E'.inh+ 综合属性E'.syn的组合 - 累加器沿链向左传,最后在 处返回
这就是为什么消除左递归后代码会变丑。Pratt 解析 / 迭代循环没有这个问题——while 里直接 lhs = Binary(op, lhs, rhs),天然左结合且动作直观。这也是手写编译器偏爱递归下降 + 迭代的原因之一。
典型应用
表达式求值 / 常量折叠
E.val 综合属性;遇到 NUM 取 lexval;遇到运算符合并。
常量折叠就是"如果两个孩子的 val 都已知,直接算出结果替换掉子树"。符号表与作用域
典型的继承属性场景:
Program → { S.symtab = new Scope(null) } S
Stmt → { S₁.symtab = S.symtab } S₁
| '{' { S₁.symtab = new Scope(S.symtab) } S₁ '}' // 进入块:新建子作用域new Scope(parent) 构成作用域链,查找时逐级向上。这正是 L-属性"继承只能来自父/左兄"的用武之地。
类型检查
E.type 是综合属性:
E → E₁ + E₂ { if (E₁.type == E₂.type) E.type = E₁.type; else error(); }
E → id { E.type = lookup(id.name).type; }若需要隐式转换(int + float → float),还要在动作里插入转换节点(Cast)——这就是"语义动作改写 AST"的例子。
语法糖脱糖(Desugaring)
把复杂构造降级成核心构造,减少后面要处理的节点种类:
for (init; cond; step) body
⇒ init; while (cond) { body; step; }
a[i] ⇒ *(a + i)
x++ ⇒ (x = x + 1) - 1 // 后缀返回旧值脱糖越早做,后端越简单。Lua 的 for-in、C# 的 foreach、Rust 的 ? 运算符都是这么处理的。
设计语义动作的经验
- 动作尽量无副作用。Parser 里直接
printf看着爽,但错误恢复时会打出已经"撤销"的输出。让动作只构造数据结构,输出交给后面的遍。 - 中间结果要带源码位置。否则报错时无法定位。
- 别在动作里做需要全局信息的优化。语义分析阶段还没建完 CFG,做不了数据流分析。
- 属性命名要区分方向。
inh_/syn_前缀一眼看出是继承还是综合。 - L-属性的"不能看右边"约束要当真。编译器里 90% 的"我要等看完右边才能决定"需求,其实应该改成"先建节点,之后单独跑一遍来填"。
常见坑
- 在 LR 动作里引用未就绪的属性:归约发生时右部符号的属性才可用,动作写在产生式中间(如
A → B { act } C)时C的属性还没算出来。bison 里这种中间动作会被转成A → B .M C, M → ε { act },多一个空产生式——可能引入冲突。 - 继承属性在自底向上分析里很难做。LR 的栈是往上长的,传递"从上往下"的信息要在栈里存额外的继承链,容易写错。这也是为什么 LR 系的编译器倾向于"先建树,再跑一个独立的自顶向下遍来填继承属性"。
- 消除左递归忘了改动作,结果表达式算出来是右结合的(
a - b - c变成a - (b - c)),数值全错。 - 依赖成环:比如
A.x = f(B.y)且B.y = g(A.x)。编译期发现不了,运行期栈溢出或算出垃圾值。
参考
- 龙书 第 5 章(Syntax-Directed Translation)
- bison 手册的 Actions
- ANTLR4 的 listener/visitor 模式:本质上是把 SDT 的动作外置成回调,便于复用文法