语法制导的语义计算

属性文法

属性文法在上下文无关文法的基础上进行如下扩展：

• 为每个文法符号关联多个属性，用来刻画一个文法符号的特性
• 为文法的每个产生式关联一个语义规则集合，用于描述如何计算当前产生式中文法符号的属性值
• 对于 $A\to \alpha$
  • 如果 b 是 A 的属性, 只由 $\alpha$ 中的属性决定，则称 b 是 A 的一个综合属性
  • 如果 b 是 $\alpha$ 中某个文法符号 X 的属性，且由该产生式中其他属性决定，则称 b 是文法符号 X 的一个继承属性
  • 综合属性代表自下而上传递的信息，继承属性代表自上而下传递的信息

基于属性文法的语义计算

树遍历方法

通过遍历分析树进行属性计算。

• 构造输入串的语法分析树
• 构造依赖图
  • 依赖图是一个有向图，用来描述分析树中的属性与属性之间的相互依赖关系
• 若该依赖图是无圈的，则按造此无圈图的一种拓扑排序对分析树进行遍历，则可以计算所有的属性
• 若依赖图含有圈，则相应的属性文法不可采用这种方法进行语义计算，此类属性文法不是良定义的

依赖图构建算法：

单遍的方法

只适用于特定的属性文法

• S-属性文法：只包含综合属性
• L-属性文法：可以包含综合属性，也可以包含继承属性，产生式右端某文法符号的继承属性的计算只取决于该符号左边文法符号的属性

S-属性文法的语义计算

• 通常采用自下而上的方式进行
• 若采用LR分析技术，可以通过扩充分析栈中的域，形成语义栈来存放综合属性的值，计算相应产生式左部文法符号的综合属性值刚好发生在每一步归约之前的时刻

L-属性文法的语义计算

• 采用自上而下的方式可以较方便地进行

基于翻译模式的语义计算

• 受限的翻译模式
  • 受 S-属性文法的启示，对于仅需要综合属性的情形，只要创建一个语义规则集合，放在相应产生式右端的末尾，把属性的计算规则加入其中即可
  • 受 L-属性文法的启示，对于既包含继承属性又包含综合属性的情形，但需要满足
    • 产生式右端某个符号继承属性的计算必须位于该符号之前，其语义动作不访问位于它右边符号的属性，只依赖于该符号左边符号的属性 （对于产生式左部的符号，只能是继承属性）
    • 产生式左部非终结符的综合属性的计算只能在所用到的属性都已计算出来之后进行，通常将相应的语义动作置于产生式的尾部

自上而下

• 构造的子程序中，继承属性为形参，综合属性为返回值

消除左递归

$$\begin{array}{rl}A& \to A_{1}Y\{A.a:=g(A_1.a,Y.y)\}\\ A& \to X\{A.a:=f(X.x)\}\end{array}$$

变换为

$$\begin{array}{rl}A& \to X\{R.i:=f(X.x)\}R\{A.a:=R.s\}\\ R& \to Y\{R_1.i:=g(R.i,Y.y)\}{R}_1\{R.s:=R_1.s\}\\ R& \to ϵ\{R.s:=R.i\}\end{array}$$

翻译模式中去掉嵌在产生式中间的语义动作

Note

现代编译器中一般采用多遍分析的方式，不需要处理以下内容。只在需要用单遍分析完成语法分析和语义分析时才需要考虑。

在移进-归约分析中，分析器只能在归约时机做出相应的语义动作，所以要将嵌在产生式中间的语义动作去掉，改写到产生式末端，来自下而上计算综合属性。

• 若语义规则中未关联任何属性，引入新的非终结符 N 和产生式 $N\to ϵ$，把语义规则放在该产生式后
• 若有关联的属性，引入新的非终结符 N 和产生式 $N\to ϵ$，把语义规则放在产生式后，同时在适当位置增加复写规则

分析栈中继承属性的访问

继承属性的访问需要通过栈中已有文法符号的综合属性间接进行。可以通过添加新的文法符号和复写规则来实现。

$$\begin{array}{rl}S& \to aA\{C.i:=A.s\}C|bAB\{C.i:=A.s\}C\\ C& \to c\{C.s:=g(C.i)\}\end{array}$$

使用 $C\to c$ 归约时，$C.i$ 或存在于次栈顶，或存在于次次栈顶，无法确定。可以引入新的非终结符 $M$

$$\begin{array}{rl}S& \to aA\{C.i:=A.s\}C|bAB\{M.i:=A.s\}M\{C.i:=M.s\}C\\ C& \to c\{C.s:=g(C.i)\}\\ M& \to ϵ\{M.s:=M.i\}\end{array}$$

这样 $C.i$ 就一定在次栈顶。

更复杂的例子：

当在不同地方对同一符号的同一继承属性赋值，且源数据和该符号的相对位置不固定时，需要引入空的非终结符来同一间隔。

用综合属性代替继承属性

改变基础文法可能避免继承属性。

$$\begin{array}{rl}D& \to L:T\\ T& \to \text{int}\\ T& \to \text{real}\\ L& \to L,v\\ L& \to v\end{array}$$

可变换为

$$\begin{array}{rl}D& \to vL\\ L& \to ,vL\\ L& \to :T\\ T& \to \text{int}\\ T& \to \text{real}\end{array}$$

这样类型就可以通过综合属性进行传递。