回填拉链翻译举例.ppt

设程序结构定义如下 PSSifEthenSSifEthenSelseSSwhileEdoSSbeginLendSALL SLS布尔表达式E及赋值语句A定义见书上 为能及时地回填有关四元式串的转移地址 改写文法如下 PSC ifEthen SCS1 TpCSelse STPS2 Wwhile WdWEdo SWdS3 SbeginLend SA LSL LLSS1 自底向上语法制导翻译方案实现过程分析 关于控制结构的翻译 翻译中使用回填 拉链技术翻译while ad thenx y z 步骤1 移进while 并按如下产生式归约Wwhile W codebegin nextstat 四元式表内容如下 nextstat100 W codebegin 句型变为W ad thenx y z 步骤2 对于句型W ad thenx y z移进 a b 并按如下产生式归约Ei1relopi2 E true nextstat E false nextstat 1 E codebegin nextstat gen ifa bgoto gen goto E E1 E true E1 true E false E1 false E codebegin E1 codebegin 四元式表内容如下 E true100ifa bgoto W codebegin E false101goto 句型变为WEdoif c d thenx y z 步骤3 对于句型WEdoif c d thenx y z移进do并按如下产生式归约WdWEdo backpatch E true nextstat Wd chain E false Wd codebegin W codebegin 四元式表内容如下 100ifa bgoto102Wd codebegin Wd chain101goto nextstat 102 句型变为Wdif c d thenx y z 步骤4 对于句型Wdif c d thenx y z移进if c d 并按如下产生式归约Ei1relopi2 E true nextstat E false nextstat 1 E codebegin nextstat gen ifa bgoto gen goto E E1 E true E1 true E false E1 false E codebegin E1 codebegin 四元式表内容 100ifa bgoto102Wd codebegin Wd chain101goto nextstat 102 ifc dgoto 103goto 104 E true E false 句型变为WdifEthenx y z 步骤5 对于句型WdifEthenx y z按如下产生式归约CifEthen backpatch E true nextstat C chain E false 四元式表内容 100ifa bgoto102Wd codebegin Wd chain101goto nextstat 102 ifc dgoto104 103goto 104 C chain 句型变为WdCx y z 步骤6 对于句型WdCx y z移进x y z 按如下产生式归约Bi p lookup i name if p nil E place pelseerror BB1 B2 B place newtemp gen B place B1 place B2 place Ai B p lookup i name if p nil gen p E place elseerror 四元式表内容 100ifa bgoto102Wd codebegin Wd chain101goto nextstat 102 ifc dgoto104 103goto 104t y z C chain 句型变为 WdCA 105x t 106 步骤7 对于句型WdCA 按如下产生式归约SA S chain 0 SCS1 S chain merge C chain S1 chain 可能S1ifathenx 1elsex 2 四元式表内容 100ifa bgoto102Wd codebegin Wd chain101goto nextstat 102 ifc dgoto104 103goto 104t y z S chain 句型变为 WdS 105x t 106 步骤8 对于句型WdS 按如下产生式归约SWdS1 backpatch S1 chain Wd codebegin gen gotoWd codebegin S chain Wd chain 四元式表内容 100ifa bgoto102Wd codebegin S chain101goto nextstat 102 ifc dgoto104 103goto100 104t y z 句型变为 S 105x t 106goto100 107 步骤9 对于句型S 按如下产生式归约 假设忽略说明语句 PS backpatch S chain nextstat gen return 返回主函数 四元式表内容 100ifa bgoto102 101goto107 nextstat 102 ifc dgoto104 103goto100 104t y z 105x t 106goto100 107return 108 递归下降语法制导翻译方案中实现控制结构的翻译 翻译思路 布尔表达式求值 并设置标号避免回填 if E getlabel gen JZ E place label1 S1 getlabel gen JP label2 setlabel label1 elseS1 setlabel label2 while getlabel setlabel label1 E getlabel gen JZ E place label2 doS gen JP label1 setlabel label2 label1 label2 label1 label2 for E1 getlabel setlabel label1 E2 getlabel getlabel gen JZ E2 place label2 gen JP label3 getlabel setlabel label4 E3 gen JP label1 setlabel label3 S gen JP label4 setlabel label2 readi look gen IN 标准输入设备 i place label1 label2 label3 label4 write E gen out E place 标准输出设备 name nameplace