【编译原理复习专题4】语法制导翻译

语法制导翻译，边做语法分析，边做语义分析。它使用CFG引导对语言的翻译，是一种面向文法的翻译技术。

语义信息

如何表示语义信息？

将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号。

如何计算语义属性？

属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式。在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理。

换句话说就是：为每一个产生式配上语义规则并且在适当的时候执行这些规则。

SDD 语法制导定义

SDD是一个上下文无关文法和属性及规则的结合。属性和文法符号相关联，而规则和产生式相关联，有时也称为属性文法。
如果𝑿是一个符号，而𝒂是𝑿的一个属性，那么用𝑿.𝒂来表示在某个标号为𝑿的分析树节点上的属性值。属性可以有很多类型，比如变量的数据类型、表达式的值、变量的地址、数字的有效位数等等。

属性

属性分为综合属性和继承属性。

综合属性只能由当前结点或者结点的子节点的属性值来计算。通常，产生式左侧的属性都来自右侧的话，那么左侧的属性就是综合属性。

继承属性是由当前结点的父节点或兄弟节点或本身的属性值来定义的。（只要有父节点或兄弟结点定义就是继承属性了）

终结符可以有综合属性，就是词法分析的词法值。终结符没有继承属性。

属性文法写成表格形式，相同的非终结符需要用下标区分。

S属性的SDD

只包含综合属性的SDD称为S属性的SDD。它可以按照任何自底向上的顺序进行求值。

L属性SDD的特例。

L属性的SDD

要么是综合属性，要么是继承属性，且满足以下i条件：

对于产生式$A\rightarrow X_1 X_2 …X_n$,$X_i$的继承属性仅能依赖于：

• A的继承属性（如果是综合属性可能会有环路）

• 产生式$X_i$左侧的属性。（继承属性只能右侧的继承左侧的，规定了依赖图的边只能从左往右)

SDD的求值

如果是综合属性，就可以按照任何自底向上的顺序进行求值，如果是同时具有继承属性和综合属性的话，首先要看有没有出现环状的依赖关系，最好不要出现循环的情况。

1.绘制依赖图dependency graph

2.求DAG的依赖图的拓扑排序（如果图存在环，就不存在拓扑排序）

拓扑排序不是唯一的，平行关系可以交换。

SDT 语法制导的翻译方案

SDT是在产生式中嵌入了程序片段的一个上下文无关文法。这些片段称为语义动作，它们可以出现在产生式的任何位置。默认用{}括起来。

SDD时语言翻译的高层次规格说明，隐藏了很多具体实现细节，使用户不必显式地说明翻译发生的顺序。

SDT是SDD的一种补充，是SDD的具体实施方案，显式地指明了语义规则的计算顺序，以便说明某些实现细节。

语法制导翻译可以用于抽象语法树的构建，

如何用SDT实现两类重要的SDD

产生式右侧的动作在它左边的所有文法符号后被匹配后立即执行。

将内嵌语义动作替换成一个新的非终结符，可以执行相应的语义动作。

S属性的SDD

后缀翻译方案：

S属性的SDD可以构造出SDT: 每个动作都放在产生式的结尾。

所有属性都是综合属性。

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

$B\rightarrow X{a}Y$

自底向上，X出现在分析栈栈顶时，立即执行动作a。

自顶向下，在展开Y的本次出现或者在输入中检测Y之前执行动作a。

L属性的SDD

将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上。

将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端 。

如果基本文法可以用LL分析，那么可以用递归下降、在LL预测分析过程中翻译(属性值存放在语法分析栈中)或者用LR分析。

在递归下降分析中加入语义翻译

函数A的参数是非终结符A的继承属性
函数A的返回值是非终结符A的综合属性