语法制导翻译
语法制导翻译是通过向一个文法的产生式附加一些规则或程序片段而得到的。
语法制导翻译的两个概念
下面是与语法制导翻译相关的两个概念：
- 属性(attribute) : 表示与某个程序构造相关的量。这个属性就是我们平常所理解的 属性，可以是表达式的数据类型，指定数据类型的字节大小，生成的代码中的指令数目，等等等。
- (语法制导的)翻译方案：翻译方案是一种将程序片段附加到一个文法的各个产生式上的表示法。这个程序片段就是你用来翻译这个产生式的翻译程序。将这些翻译程序的输出结果(翻译结果)按照一定的顺序组合起来，就成了最终的翻译结果。
综合属性与继承属性
综合属性即“自底向上”求值的属性，综合属性的值是由属性值所在结点及其子结点确定的。对(语法分析树的)某个结点的综合属性的值只需要对(语法分析树的)该结点做自底向上遍历就可得到。
相对于“自底向上”求值的综合属性，编译原理里还有一种重要的“自顶向下”求值的属性，叫做 继承属性 ，继承属性的值是由属性所在结点及其父节点、兄弟结点决定的。
- 语法制导定义：
- ① 每个文法符号和一个属性集合相关联。
- ② 每个产生式和一组语义规则相关联。这些规则用于计算该产生式的相关属性值。
如果将语法分析树的各个结点的属性标记在语法分析树上，那么这棵语法分析树我们称之为注释语法树。
我们通过深度优先遍历整棵注释语法树，可以自底向上计算整棵树所拥有的所有综合属性。假设我们对于每一个结点有属性t，表示该结点的翻译结果，当我们遍历完毕整棵树，每个结点的属性t都计算完毕，那么这棵树就翻译完成了—我们只需要取得树的根节点的t属性即可。
下面是一个例子，该例子演示了将中缀表达式9+5转换为后缀表达式95+的过程。
我们假设expr和term有属性t，表示该产生式对应的翻译结果：
| 编号 | 产生式 | 语义规则 |
|---|---|---|
| 1 | expr -> term + expr1 | expr.t = term.t || expr1.t || ‘+’ |
| 2 | expr -> term | expr.t = term.t |
| 3 | term -> 0 | term.t = ‘0’ |
| 4 | term -> 1 | term.t = ‘1’ |
| … | … | |
| 12 | term -> 9 | term.t = ‘9’ |
(注意上面的||代表字符串连接符)
我们可以得到如下语法分析树：
最初的注释分析树上属性都为空，故上图没有画出属性部分。
我们开始深度优先遍历这棵树。
当我们遍历到左边第一颗term结点时，我们发现其下有一个结点9.刚好符合上表中编号为12的产生式。于是我们根据12号产生式对应的语义规则给左边的term结点赋予值为’9’的属性t。当遍历到右边的expr结点时，继续深度遍历到右边的term，根据相应的语义规则赋予完右边的term、expr之后注释语法树如下图所示：
当我们遍历到根结点expr时，发现符合1号产生式。于是我们按照对应的语义规则赋予根节点的属性expr.t:
我们可以从根节点的属性t得到最终的翻译结果，如此一来，我们就完成了这棵语法树的翻译工作。下面，我们来看另一种翻译方法：
我们可以在文法产生式里附加上一些程序片断，用于输出产生式对应的语法树的节点的翻译结果，当我们遍历这颗语法树时，就可以逐步输出整棵语法树的翻译结果了。这是不同于注释语法树的翻译方法，我们称之为语法制导翻译方案。用于翻译的程序片段我们称之为语义动作。一个语义动作用花括号括起来，并写入产生式的体中。如下面所示是一个镶嵌了语义动作的产生式例子，这个例子同样是将中缀表达式翻译成后缀表达式的例子：rest -> term + term {print ('+')}term -> 0 {print ('0')} | 1 {print ('1')} | 2 {print ('2')} | ... | 9 {print ('9')}
语句1+2对应的镶嵌了语义动作的语法分析树如下所示。
我们在翻译时，按深度优先遍历这棵树，没有镶嵌了语义动作的不予以输出，只输出镶嵌了语义动作的结点的运行结果。当遍历完成，我们就得到了翻译结果：12+