语法制导翻译
使用CFG来引导对语言的翻译，是一种面向文法的翻译技术。
语义翻译：语义分析、中间代码生成
语法制导翻译：语法分析、语义分析、中间代码生成
概述
基本思想
为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息
- 对于给定的输入串，构建语法分析树，利用与产生式相关联的语义规则来计算分析树中各结点对应的语义属性值
语法制导定义（SDD）
SDD是对CFG的推广
- 将每个文法符号和一个语义属性集合相关联
- 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值
语法制导翻译方案（SDT）
在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内。
1
2
D → T { L.inh = T.type } L
T → int { T.type = int }
一个语义动作在产生式中的位置决定了这个动作的执行时间 SDT可以看作是SDD的具体实施方案
语法制导定义（SDD）
属性
注释分析树：每个节点都带有属性值的分析树
综合属性
在分析树节点N上的非终结符A的综合属性只能通过N的子节点或N本身的属性值来定义
1
E → E1 + T E.val = E1.val + T.val
终结符可以具有综合属性，其就是由词法分析器提供的词法值。因此在SDD中没有计算终结符属性值的语义规则
继承属性
在分析树节点N上的非终结符A的继承属性只能通过N的父节点、N的兄弟节点或N本身的属性值来定义
1
D → T L L. inh = T. type
终结符没有继承属性。终结符从词法分析器获得的属性值被归为综合属性值
属性文法
一个没有副作用的SDD也称为属性文法
- 副作用：通常是一个过程调用（用来打印…)
- 如：
print(E.val)
- 如：
- 属性文法的规则仅仅通过其它属性值和常量表来决定一个属性值
SDD的求值顺序
在对语法分析树结点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值
依赖图
- 分析树中每个结点X的每个属性a都对应着依赖图中的一个结点
- 如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b结点指向X.a结点的有向边
按照拓扑排序进行求值，前提是不存在循环依赖关系
- 存在一个SDD的有用子类，它们能够保证对每棵语法树都存在一个求值顺序，因为它们不允许产生带环的依赖图
S-属性定义
仅仅使用综合属性的SDD称为S属性的SDD（S-SDD）
- 如果一个SDD是S属性的，可以按照语法分析树结点的任何自底向上顺序来计算它的各个属性值
L-属性定义
直观：在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左
定义：一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：
- 假设存在一个产生式$A\rightarrow X_1X_2….X_n$，其右部符号$X_i$的继承属性仅依赖于下列属性：
- $A$的继承属性（不能是综合属性，因为会产生循环依赖）
- 产生式中$X_i$左边的符号$X_1, X_2, …, X_{i-1}$的属性
- $X_i$本身的属性，但$X_i$的全部属性不能在依赖图中形成环路
每个S-属性定义都是L-属性定义
语法制导翻译方案（SDT）
将S-SDD转换为SDT
将每个语义动作都放在产生式的最后
1
2
3
4
5
6
7
(1) L → E n { L.val = E.val }
(2) E → E1 + T { E.val = E1.val + T.val }
(3) E → T { E.val = T.val }
(4) T → T1 * F { T.val = T1.val × F.val }
(5) T → F { T.val = F.val }
(6) F → ( E ) { F.val = E.val }
(7) F → digit { F.val = digit.lexval }
SDT在LR中的实现
如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现
- 为每个栈记录增加属性值字段，存放文法符号的综合属性
- 若支持多个属性
- 使栈记录变得足够大
- 在栈记录中存放指针
- 若支持多个属性
- 在每次归约时调用计算综合属性值的语义子程序
1 2 3 4 5 6 7
(1)E′ → E { print (stack[top].val);} (2)E → E1 + T { stack[top-2].val = stack[top-2].val + stack[top].val; top=top-2; } (3)E → T (4)T → T1 * F { stack[top-2].val = stack[top-2].val × stack[top].val; top=top-2; } (5)T → F (6)F → ( E ) { stack[top-2].val = stack[top-1].val;top=top-2; } (7)F → digit
将L-SDD转换为SDT
- 将计算某个非终结符A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
- 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端
1
2
3
4
1) T → F { T′.inh = F.val } T′ { T.val = T′.syn }
2) T′ → *F { T1′.inh = T′.inh×F.val } T1′ { T′.syn = T1′.syn }
3) T′ → ε { T′.syn = T′.inh }
4) F → digit { F.val = digit.lexval }
L-SDD的自顶向下翻译
在预测分析的同时实现语义翻译
非递归预测分析的翻译
- 扩展语法分析栈
- 增加属性值字段
- 将继承属性和综合属性存放在不同的记录中
- 增加动作记录来存放指向语义动作代码的指针
- 不光是动作记录，其实分析栈中的每一个记录都对应着一段执行代码
| action | A | Asyn |
|---|---|---|
| 指向将被执行的语义动作代码的指针 | A的继承属性 | A的综合属性 |
- 综合记录出栈时，要将综合属性值赋值给后面特定的语义动作
- 变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作
递归预测分析的翻译
将非终结符对应的过程扩展为函数
- 函数的参数为继承属性值
- 函数的返回值为综合属性值
语义动作中将会使用产生式右部符号的属性值
- 所以对出现在A产生式右部中的每个文法符号的每个属性都设置一个局部变量
对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对响应变量的引用
L-SDD的自底向上翻译
给定一个以LL文法为基础的L-属性定义，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD
- 首先构造SDT
- 对每个内嵌的语义动作，向文法中引入一个标记非终结符M来替换它，对于每一个标记M都有一个产生式$M\rightarrow \varepsilon$
- 修改后的SDT，所有语义动作都位于产生式末尾