语法制导的翻译
语法制导的翻译
语法分析 给出的只是一棵语法树,还不能拿去执行。要把树变成有用的东西——比如类型信息、符号表条目、中间代码——就得往每个产生式上"挂"一点计算逻辑。语法制导定义(SDD, Syntax-Directed Definition) 就是这么一套形式化写法:给 CFG 的每条产生式配上若干属性和语义规则,让语法结构本身驱动语义计算。
通俗理解:语法树像一栋楼的钢架,SDD 就是往每个节点上贴便利贴——有的便利贴写着"这条表达式的类型是 int",有的写着"这个变量对应的地址是 t3"。规则规定了每张便利贴该怎么算,语法树建到哪里,便利贴就贴到哪里。
写在产生式上的规则形如 A -> XY { A.val = f(X.val, Y.val) }。规则右边就是一段属性计算,可以引用产生式左右两侧任意符号的属性。所有属性一起构成语法树上的一个属性依赖网络。
综合属性与继承属性
属性按信息流方向分成两类,非常关键:
- 综合属性(Synthesized Attribute):一个节点的属性值由其子节点的属性算出。信息自底向上流动。
- 继承属性(Inherited Attribute):一个节点的属性值由其父节点或兄弟节点的属性算出。信息自顶向下、从左到右流动。
经典的类型声明例子:
D -> T id_list { id_list.inh = T.type }
T -> int { T.type = integer }
T -> float { T.type = float }
id_list1 -> id_list2 , id { id_list2.inh = id_list1.inh
addType(id.entry, id_list1.inh) }
id_list -> id { addType(id.entry, id_list.inh) }
T.type 是综合属性——它由 int 还是 float 这个终结符决定,是从叶子算上来的。而 id_list.inh 是继承属性——它从兄弟 T 那里拿到类型,再一路"传染"给每一个 id。这种"声明左边是类型、右边是一串变量"的语法,天然要求信息从左往右传,用继承属性最自然。
S-属性文法:LR 分析栈上直接求值
如果一个 SDD 只用综合属性,就叫 S-属性文法(S-attributed)。它天生适合自 底向上分析:每次归约 A -> X Y Z 的那一刻,X.val、Y.val、Z.val 都已经在分析栈里,直接算出 A.val 压回栈即可。
Yacc/Bison 的动作栈正是这么工作的。举一个简单的表达式求值:
expr : expr '+' term { $$ = $1 + $3; }
| term { $$ = $1; }
;
term : term '*' factor { $$ = $1 * $3; }
| factor { $$ = $1; }
;
factor : NUM { $$ = $1; }
| '(' expr ')' { $$ = $2; }
;
$$ 就是左侧非终结符的综合属性,$1、$3 是右部第 1、3 个符号的属性。整份翻译方案没有任何"父传子"的信息,完美契合 LR 自底向上求值。
L-属性文法:一遍递归下降走完
只有综合属性有时候不够用——类型声明这种就需要继承属性。L-属性文法(L-attributed) 允许继承属性,但加了一个限制:
产生式 A -> X1 X2 ... Xn 中,Xi 的继承属性只能依赖于 A 的继承属性,或者 X1 ... X(i-1) 的任意属性。
也就是说,信息只从左往右流。这个限制保证了:只要按从左到右的顺序访问语法树,一次深度优先遍历就能把所有属性算完。这正是递归下降分析器的工作方式,所以 L-属性文法可以在自顶向下分析中一遍走完,边分析边翻译。
属性依赖图与求值顺序
给一棵语法树上的每个属性画一个点,规则里"B 依赖 A"就画一条 A -> B 的边,得到属性依赖 图。求值顺序必须是这张图的一个拓扑排序。
如果依赖图有环,就没有任何合法的求值顺序——属性文法出了循环依赖,会被判为非法。判定任意 SDD 是否有环的复杂度是指数级的,所以实践中大家只用两类保证无环的子集:S-属性文法(依赖只在树里自底向上)和 L-属性文法(依赖只从左往右)。
翻译方案(SDT):把动作嵌进产生式
语法制导翻译方案(SDT, Syntax-Directed Translation Scheme) 是 SDD 的可实现版本:把语义动作 { ... } 直接写进产生式的右部,位置固定。
D -> T { id_list.inh = T.type } id_list
动作在分析过程中"顺路"执行——分析器走到那个位置就触发它。SDT 和原 SDD 行为等价的条件是:
- 底层 SDD 是 L-属性文法。
- 动作位置遵守"只引用左边符号已算好的属性"这条铁律。
- 综合属性的动作放在产生式最右端。
满足这几条,SDT 可以直接对着任何 LL 或 LR 分析器实现。
一个小翻译方案:生成三地址码
来做点更像真编译器的事——把加法表达式翻译成三地址码:
E -> E1 + T { E.place = newTemp();
emit(E.place, '=', E1.place, '+', T.place); }
E -> T { E.place = T.place; }
T -> ( E ) { T.place = E.place; }
T -> id { T.place = id.name; }
对 a + b + c,遍历过程会依次发射:
t1 = a + b
t2 = t1 + c
place 是纯综合属性,所以这份翻译方案是 S-属性的,直接放进 Bison 里就能跑。
在自底向上分析中处理继承属性
LR 分析天然只喜欢综合属性,但工程上经常绕不开继承属性(比如上面那个类型声明)。有三种常见手法:
-
改写文法,把继承属性转成综合属性。例如把
D -> T id_list改成先把id列表收集成一个综合属性列表,再等T归约完统一处理。虽然思路直接,但会污染文法结构。 -
嵌入标记非终结符 + 动作。在需要传值的地方插一个空产生式
M -> ε,把动作附在M上:D -> T M id_list
M -> ε { M.inh = T.type; ... 存到某处 }M归约时T已在栈上,可以把T.type记录下来,供后面id_list归约时读取。 -
复制规则(copy rule)。用形如
A.i = B.i的规则把继承属性顺着 树"复制"下去,配合 Bison 的中动作(mid-rule action)实现。中动作本质就是编译器帮你悄悄插入的空非终结符。
这三种手法背后是同一个思想:用栈的位置换取时间上的顺序——把父/兄的属性提前存进栈,让归约时能取到,本质上是把继承属性"伪装"成综合属性来求值。
理解了 SDD、SDT、S-属性、L-属性这几组概念,后面看中间代码生成、符号表构造这些章节就会顺很多——它们其实都是在同一个骨架上贴不同的便利贴。