【编译原理笔记10】语法制导翻译：在递归预测过程中进行翻译，L属性定义的自底向上翻译

本次笔记内容：
5-7 在递归预测过程中进行翻译
5-8 L属性定义的自底向上翻译

本节课幻灯片，见于我的 GitHub 仓库：第10讲 语法制导翻译_3

在递归的预测分析过程中进行翻译

如上，先来考虑SDT的非终结符 T’ ，上图右侧为 T’ 对应的扩展后的函数，其中：

• 黑色字体部分，表示原有的语法分析器中 T' 对应的过程；
• 蓝色的就是扩展之后的部分。

为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。

对出现在A产生式右部中的每个文法符号的每个属性都设置一个局部变量。

对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用。



如上，是分析器对应的主函数。T有一个综合属性val，因此，为T的val声明一个局部变量 Tval ，并且将函数的返回值赋给这个局部变量。

算法

• 为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量；
• 非终结符A的代码根据当前的输入决定使用哪个产生式；
• 与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的词法单元、非终结符及语义动作：
• • 对于带有综合属性x的词法单元X，把x的值保存在局部变量X.x中；然后产生一个匹配X的调用，并继续输入；
• • 对于非终结符B，产生一个右部带有函数调用的赋值语句c := B(b1 , b2 , …, bk)，其中， b1 , b2 , …, bk是代表B的继承属性的变量，c是代表B的综合属性的变量；
• • 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用。

L-属性定义的自底向上翻译

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD。

如上，在这个SDT中，有两个蓝色的内嵌的语义动作，导致无法自底向上翻译，因此要修改。

因此我们使用标记非终结符。做了两个空产生式M与N。

修改后的SDT，所有语义动作都位于产生式末尾。

无需担心“访问未出现在该产生式中的符号的属性？”的问题，这些属性将出现在必要的位置。

如上，我们构造了自动机。输入 3 * 5 。

栈底标记 $ 。

I0 遇到 digit ，采取移入动作，并且进入状态I3。

移入动作完成后，输入指针指向 *。由 I3 知，遇到 * 采取归约动作，应用第 4 个产生式进行归约。

因为 F 的属性值等于 digit 的属性值，因此，栈底的属性值字段保持不变。因此， d 出栈，F进栈。

I0遇到F，进入I2。

当前输入符号位 * ，采取归约动作，将 M 进栈。M 根据归约动作，可以看出，M 的属性值为 F 的属性值。而在产生式 1 中，F 是 M 的左兄弟。正好与栈中情况符合。

因此 M 的属性值为 3 。M在产生式中的任务为计算 T’ 的继承属性值，因此记为 T’inh = 3 。

I2遇到M，进入状态I4；I4遇到 * ，进入状态 I6 ，采取移入动作；指针后移，指向 5 。

而 I6 遇到数字 ，则进入状态 I3 ，且采取移入动作。指针后移，指向 $ 。

I3 遇到 $ 采取归约动作，使用产生式 4 。

根据归约动作，栈顶的属性值保持不变，d出栈，F进栈。

I6遇到 F ，进入 I7 。I7 遇到 N 时，要稍微复杂一些：

• N.i1 = T’.inh ，但是T’.inh 现在在哪呢？
• 我们知道，*FNT1'最终将被归约为 T' ，因此T'的继承属性值就存放在分析栈中，*左边的位置（仅靠在T’之下的，标记非终结符对应的记录中），即M所在的位置；
• 因此，我们将 3 与 5 相乘，把得到的值 15 赋给 N 的综合属性；
• N 在产生式中位于 T1’ 左侧，任务就是计算 T1’ 的继承属性，N的属性是 T1’ 的继承属性值 inh 的值，因此记为 T1’.inh = 15。

I7 遇到 N 进入 I8 。I8 遇到 $ ，将采取归约动作，T’ 将进栈。

由产生式3，T’ 的综合属性值等于其继承属性值。

T'的继承属性值，是由产生式中仅靠在 T' 左侧的标记非终结符对应的动作来计算的。因此，T' 的继承属性值，就存放在分析栈中，仅靠在 T' 之下的，标记非终结符对应的记录，因此 T' 此时就在栈顶。

因此将 T1'inh=15的值赋给 T’ ，T’ 的综合属性值 syn 等于 15。

I8 遇到 T’ ，进入 I9 。

当输入符号为 $ ，采取归约动作，*FNT' 出栈，T' 入栈，且其属性值为 T1'.syn （由产生式得）。

I4 遇到 T5，进入 I5 。进行归约动作。

1号状态是接收状态，完毕。

将语义动作改写为可执行的栈操作

总结

给定一个以LL文法为基础的L-属性定义，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD：

• 首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性，并在产生式后端放置语义动作计算综合属性
• 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生
  式M→ε
• 如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a’ ，并且将a’关联到M→ε 上。动作a’
• • (a) 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
• • (b) 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性