语法制导的翻译方案

语法制导的翻译方案是语法制导定义的一种补充。

语法制导的翻译方案(syntax-directed translation scheme, SDT)是在其产生式体中嵌入了一个程序片段的上下文无关文法。这些程序片段称为语义动作，它们可以出现在产生式体的任何地方。

使用SDT来实现两类重要的SDD：

1. 基本文法可以用LR技术分析，且SDD是S属性的。
2. 基本文法可以用LL技术分析，且SDD是L属性的。

## 后缀翻译方案

至今为止，最简单的实现SDD的情况是文法可以自底向上方法来分析且该SDD是S属性定义。这种情况下我们可以构造出一个SDT，其中的每个动作都放在产生式的最后，并且在规约时执行这个动作。

这种所有动作都在产生式最右端的SDT称为后缀翻译方案。

• 后缀SDT的语法分析栈实现

后缀SDT可以在LR语法分析的过程中实现，当规约发生时执行相应的语义动作。

各个文法符号的属性值可以放在栈中的某个位置，使得执行规约动的时候可以找到它们。最好的方法是将属性和文法符号（或者代表文法符号的LR状态）一起放在栈的记录里。

如下图所示：

栈顶→	Z	Z.z
	Y	Y.y
	X	X.x
	…

SDT重写为形如下面的格式：

产生式	语义动作
E -> E1 + T	{stack[top-2].val = stack[top-2].val + stack[top].val; top = top - 2;}
..	..

产生式内部带有语义动作的SDT

动作可以放置在产生式体中的任何位置上。当一个动作左边的所有符号都被处理过后，该动作就立刻执行。

自顶向下和自底向上分析都可以用这种SDT。

注意，不是所有SDT都可以在语法分析过程中实现。

CRE：有时会发生规约规约冲突和移入规约冲突。

CRE：任何SDT都可以按照下列方法实现：先忽略语义动作，生成语法分析树后，然后再在前序遍历时执行语义动作。

其他

从SDT中消除左递归…

L属性定义的SDD/LL分析…

（详见《编译原理》p210-226）

（END）