【编译原理笔记09】语法制导翻译：语法制导翻译方案，在非递归的预测分析过程中进行翻译
本次笔记内容：
5-5 语法制导翻译方案
5-6 在非递归的预测分析过程中进行翻译
本节课幻灯片，见于我的 GitHub 仓库：第9讲 语法制导翻译_2
文章目录
语法制导翻译方案
语法制导翻译方案 SDT
语法制导翻译方案 (SDT) 是在产生式右部中嵌入了程序片段(称为语义动作)的CFG。
如上，大括号括起的部分就是一些语义动作。
SDT可以看作是SDD的具体实施方案。
本节主要关注如何使用SDT来实现两类重要的SDD，因为在这两种情况下，SDT可在语法分析过程中实现：
- 基本文法可以使用LR分析技术，且SDD是S属性的
- 基本文法可以使用LL分析技术，且SDD是L属性的
将S-SDD转换为SDT
将一个S-SDD转换为SDT的方法：将每个语义动作都放在产生式的最后。
S-属性定义的SDT 实现
如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现。
如上，只有当归约时，才执行相应的语义动作。
扩展的LR语法分析栈
如果一个属性值的大小没有限制，最好将其存在栈外，在栈内存指针。
将语义动作中的抽象定义式改写成具体可执行的栈操作
如上，A的综合属性由其子节点X，Y，Z来定义的。左边为归约前分析栈的格局。
归约后，X、Y、Z出栈，A入栈。
例：在自底向上语法分析栈中实现桌面计算器
如上，语义动作中的抽象定义式，已经被改写成了具体的栈操作。没有给出符号栈和状态栈对应的栈操作。
初始时，输入指针指向3，状态I0遇到数字，进入I5，将5 d 3 入栈。
然后，输入指针指向*。I5是一个归约状态，其对应第 7 个产生式，不需要改属性，只需要将 d 出栈， F 入栈，并且进入状态I3。
对于I5，需要将F出栈，T入栈。并且进入状态I2。
状态I2遇到*，进入状态I7，无事可干。将指针指向5。
I7遇到数字，采取移入动作，将5移到栈中，进入状态I5。
I5是一个归约状态，将d出栈，F状态进栈。
因此，I7遇到F，则进入状态I10。
I10是一个归约状态，是对第4条产生式的应用。第4条产生式对应着语义动作，将[栈顶]与[栈顶-2]的值相乘，放到[栈顶-2]。
之后进行归约，将T、*、F出栈，将T进栈。
得到如上。
将L-SDD转换为SDT
将L-SDD转换为SDT的规则：
- 将计算某个非终结符号A的
继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上 - 将计算一个产生式左部符号的
综合属性的动作放置在这个产生式右部的最右端
L-属性定义的SDT 实现
如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现。
如上，2)、3)具有相同左部，但是其SELECT集不相交，因此其是LL文法。
之后我们将：
- 在非递归的预测分析过程中进行语义翻译；
- 在递归的预测分析过程中进行语义翻译；
- 在LR分析过程中进行语义翻译。
在非递归的预测分析过程中进行翻译
扩展语法分析栈
A的继承属性放在其本身的记录中，A的综合属性产生的时间不同，因此，放在Asyn中。此外，还有用于记录语义动作代码的指针。
如上，用来替代如上的语义动作。我们成为“动作符号”。
因为采用自顶向下的分析方法，因此分析栈的栈底在右侧、栈顶在左侧。
初始时刻，分析栈中有文法的开始符号，T没有继承属性，T有综合属性，val。
根据第1条产生式，将T替换成F {a_1} T' {a_2}，但是，Tsyn不能出栈，因为Tsyn对应的T的综合属性val的值，要等即将进栈的T的子节点都分析完毕，才能计算出来。
如上，因为F、T’、都有综合属性，因此，其综合属性syn一起进栈。
此外，根据第4条产生式，将F替换成digit {a_6}。
digit 是一个终结符，其只有综合属性，是由词法分析器提供的词法值。
栈顶的 digit 与 指针指向的 3 匹配成功，digit 可以出栈了。此外，a_6 将进行动作。因此，digit出栈前，要把自己的综合属性值备份到 a_6 中。
指针后移。
此时，a_6 执行自己的动作。F之前存在时，所在的位置就是a_6所在的位置。因此将Fsyn对应的val设为3。这时 a_6 出栈。
F的综合属性 Fsyn 记录后，就看出栈了，但是根据F其后面的动作属性 a_1 ，Fsyn 要在出栈前把其属性被分到 a_1 对应的字段中。
然后 a_1 执行自己的动作，则 T’ 的 inh 属性值就计算出来了。a_1 出栈。
此时，栈顶是非终结符 T’ ，当前的输入符号是 * ，因此选择第 2 个产生式进行替换。并且根据第 2 个产生式的 a_3 动作，其要使用 T’ 的 inh 值，因此要将 T’ 的 inh 值备份到 a_3 的动作记录中。
可以推算，a_3 进栈后，应处于 top+3 的位置，因此有如下的向左的箭头。
如上，a_3 已经备份好了 T’ 的 inh 属性值。
此时，指针指向的*与栈顶匹配成功。
*出栈。
指针指向 5 ，将栈顶的 F 替换为 digit {a_6} 。
此时，5 与 digit 匹配，digit 可以出栈，出栈前，要把其属性值备份到 {a_6} 中。
此时输入指针指向 $ 。
如上，最后将获得文法开始符号的 Tsyn 的 val 的属性为 15 。
分析栈中的每一个记录都对应着一段执行代码
- 综合记录出栈时，要将综合属性值复制给后面特定的语义动作;
- 变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作
如上，这一个产生式对应着六个符号。