编译器笔记24-语法制导翻译-在非递归的预测分析过程中进行翻译(

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

扩展语法分析栈

扩展语法分析栈.png

要想在非递归的预测分析过程中进行翻译，需要对语法分析栈进行扩展，一个非终结符A其继承属性和综合属性的计算时机是不同的。其继承属性是在非终结符即将出现的时刻进行计算，而其综合属性必须在其子节点都分析完毕后才可以计算。因此我们将A的继承属性与综合属性存放在不同的记录当中。其中A的继承属性就存放在它本身的记录当中，另外我们还要增加一种综合记录的记录类型Asyn用来存放A的综合属性。在分析栈中A的综合属性存放在A本身的记录之下。另外SDT中还有一种动作属性，我们还需要增加一种动作记录的记录类型action。

ps：注意与自底向上语法分析区分开，该分析过程没有状态栈。

改写SDT.png

改写后的SDT可以看做是特殊的上下文无关文法(CFG)，在此类文法中有三类符号--终结符 非终结符 动作符号。下面通过一个输入的例子，来看如何实现翻译的过程：

T进栈.png

输入指针指向第一个输入符号3。因为采用的是自顶向下的分析法，因此分析栈栈顶在左侧，栈底在右侧（自底向上分析则相反）。初始时刻只有开始符号T，因为T没有继承属性所有T的本身字段初始记录是空的，因为T有综合属性所以T有记录Tsyn，用于存放T的综合属性val。此时栈顶是非终结符T，其表示当前句型最左非终结符。

T出栈，F Fsyn a1 T' T'syn a2进栈.png

注：继承属性相对于综合属性在左边是有原因的，根据L-SDD的定义可知继承属性可能来自于其左边的文法符号的属性或其父节点的继承属性。

根据第一条产生式，将T替换成F{a1}T′{a2}。亦即T出栈，但T的综合属性Tsyn不能出栈。因T的综合属性val值要等T的子节点都分析完毕才能计算出来。因F跟T'都具有综合属性，因此它们的综合属性与其本身属性一起进栈。T'具有继承属性，因此T'本身的记录将存放T'的继承属性inh。

F出栈 digit a6进栈.png

根据第四条产生式将栈顶F替换成digit{a6}，digit是终结符只有词法分析器提供的综合属性值，因此digit的记录存放其综合属性值。

digit出栈.png

digit与3匹配成功出栈，digit后连接的语义动作{a6}将使用digit的属性值计算F的综合属性值，因此digit出栈前需要将其属性备份到{a6}的属性中。备份后digit可以出栈。

digit出栈后指向下一个符号乘号，此时栈顶露出动作记录a6。a6记录中存放了指向用于计算F的综合属性值的语义代码的指针（红框将a6抽象定义式改写为可以执行的栈操作）。

a6的任务是利用其备份的digit的属性值计算F的综合属性值，并将结果存放在F的综合记录中。那么现在F的综合记录在哪？

可知a6进栈前F就是处于a6当前所在的位置，栈中F之下就是F的综合记录Fsyn。F出栈后Fsyn留在了栈中。此时F的位置被a6所取代，因此F的综合记录就在a6之下。

因此a6的栈操作实际上是将3赋值给其栈之后的Fsyn对应的val，此时栈中Fsyn对应的val变为3（上图没有给出操作后val变为3的情况，自行脑补）。

Fsyn出栈.png

F的综合属性计算出来后，Fsyn应该就可以像F一样出栈了。但根据第一条产生式可知，Fsyn之下连接的a1将要使用F的综合属性计算T'的继承属性（右向左从兄弟节点继承值的在翻译中的实际意义）。因此Fsyn出栈前需要将其对应的综合属性值val备份到a1对应的字段中。

备份后F的综合记录Fsyn就可以出栈了。可见继承值在翻译时可起到保存之前分析结果的作用。

T'出栈 *F a3 T1' a4进栈.png

a1是用于计算T'的继承属性值inh，因此T'的继承属性值变为3。然后动作记录a1出栈。此后栈顶变为终结符T'之后我们可以根据第二个产生式进行替换，T'出栈 *F{a3}T1'{a4}进栈。同时将T'的继承属性值备份到a3所在的动作记录中。

此时栈顶的终结符与当前的*匹配成功出栈，匹配成功后输入指针指向下一个输入符号5。

F出栈digit a6进栈.png

接着F出栈digit a6进栈。

digit出栈.png

栈顶与输入符5匹配成功digit出栈，出栈前将digit的值备份到a6中。之后输入指针指向$符号。a6是用于计算F的综合属性，计算完后Fsyn对应的值val为5。

a6出栈.png

a6计算完成后出栈。

Fsyn出栈.png

Fsyn出栈前将其值备份至a3中。然后执行a3对应的语义代码，用于计算T1'的继承属性值。计算完成后a3出栈。

T1'出栈 a5进栈.png

a3出栈后露出T1'而此时输入指针指向$，因此选用第三个产生式替换T1'即T1'出栈 a5进栈。因为a5要使用到其继承属性，因此T1'出栈前将其继承属性备份到a5的所在记录中。因为T1'出栈后a5将处于栈顶，因此栈顶的属性值字段是不需要改变的。

执行a5对应的操作，将之前T1'的继承属性保存到T1'的综合属性中，然后出栈。

T1'syn出栈.png

然后栈顶变为T1'syn接着讲起综合属性值备份到a4的所在记录中，然后T1'syn出栈。

执行a4对应的代码，其作用是用于计算T'的综合属性。计算完后T'的综合属性的值变为15，动作记录a4出栈。此时栈顶变为T'syn（结合上图执行脑补下）。

T'syn.png

T'syn出栈前将其综合属性备份至a2所对应的记录中。备份后T'syn出栈。

接着执行a2对应的语义代码，其作用是用于计算T的综合属性值的。执行完a2的语义代码后T的综合属性就计算出来了即T.val = 15。之后a2出栈

后记：从向上述分析不难看出两个非终结符间的语义动作a可以起到在两非终结符间从左往右交流数据的桥梁作用，而非终结符的继承属性则扮演着保存获取得到数据的角色（无论是从父亲节点还是从兄弟节点获取到的数据）。而产生式最右段的语义动作a的作用则是用于计算产生式左部综合属性的。