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)

自底向上传递:节点的值只依赖子节点的属性和自身,不依赖兄弟或父节点。

A→X1X2⋯Xn,A.s=f(X1.a,X2.b,… )A \to X_1 X_2 \cdots X_n, \quad A.s = f(X_1.a, X_2.b, \dots)

典型:E.val、类型、生成的代码串。可以在一次自底向上遍历(后序遍历)中算完。

继承属性(Inherited)

自顶向下 / 横向传递:节点的值依赖父节点或左兄弟的属性。

A→X1X2⋯Xn,Xj.s=f(A.a,X1.a,…,Xj−1.a)A \to X_1 X_2 \cdots X_n, \quad X_j.s = f(A.a, X_1.a, \dots, X_{j-1}.a)

典型:

  • 符号表往下传(子节点要知道父作用域有哪些变量)
  • 声明语句 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
  • 边a→ba \to b 表示"算 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 的组合
  • 累加器沿链向左传,最后在ϵ\epsilon 处返回

这就是为什么消除左递归后代码会变丑。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 的动作外置成回调,便于复用文法