语法制导翻译与中间代码生成.ppt

例：设有语句ifX=Y+1thenX:=X*YelsewhileX≠0dobeginX:=X-1;Y:=Y+2end则其四元式如下：1.(+,Y,1,T1)Y+12.(=,X,T1,T2)X=Y+13.(then,T2,—，—)4.(*,X,Y,T3)X*Y5.(=:,T3,—,X)X:=X*Y6.(else,—,—,—)(b+c/d)#.*#ab+c/d)#.(*#a01+c/d)#02(#03abc/d)#.+(*#ab/d)#+(#abc#01/+(#02abc03)#01/+(#02abcd03)#01+(#02abcd/0301)#02(#03abcd/+##abcd/+#01#02abcd/+*abcd/+*...动画演示三元式三元式的一般形式：i:(ω,OPR1,OPR2)i是三元式编号，不同三元式不能有相同编号。ω是运算符部分。OPR1和OPR2是运算对象部分。8.3.2表达式的三元式和树例子：a:=b*c+b*d的相应三元组(*,b,c)b*c(*,b,d)b*d(+,(1),(2))b*c+b*d(:=,(3),a)a:=b*c+b*d例子：tri(A*B+C)=tri(A*B)||TRI(c)||2:(+,①≥,C)=1：(*，A，B)A*B2：(+，①，C)A*B+Ctri(A*B+C/D)=1：(*，A，B)A*B2：(/，C，D)C/D3：(+，①，②)A*B+C/Dtri(A∨B∧X≠Y+1∨(X≥0∨B)∧D)=1:(+,Y,1)Y+12:(≠,X,①)X≠Y+13:(∧,B,②)B∧X≠Y+14:(∨,A,③)A∨B∧X≠Y+1(≥,X,0)X≥0(∨,⑤,B)X≥0∨B(∧,⑥,D)(X≥0∨B)∧D(∨,④,⑦)树二目运算对应二叉树，多目运算对应多叉树。三元式可以用二叉树表示。例：(a+b*(c-d))-e/f的树。该题的树结构如下：01(-，c，d)c-d02(*，b，(1))b*(c-d)03(+，a，(2))a+b*(c-d)04(/，e，f)e/f05(-,(3),(4))cd-+/*-abef1234该树的根后序为：abcd-*+ef/-,为该式的逆波兰式。5(ω,OPR1,OPR2，RESULT)其中ω是运算符。OPR1和OPR2是第一，二分量，RESULT是运算结果变量名。例：求a:=b*c+b*d的四元式12四元式的一般形式是：8.3.3四元式 1)(*，b，c，T1)b*c 2)(*，b,d，T2)b*d 3)(+，T1，T2，T3)b*c+b*d 4)(:=，T3，-，a)下面是表达式四元式的形式定义。FOUR(T)RES(E)=RES(T)1．E=T四元式中缀式FOUR(E1)2．E=E1+TFOUR(T)(+,RES(E1),RES(T),TEMP)RES(E)=TEMP(临时变量)空RES(F)=ID7．F=I类似于26．T=T1/F类似于25.T=T1*FFOUR(F)RES(T)=RES(F)4．T=F类似于23．E=E1-TFOUR(E)RES(F)=RES(E)8．F=(E)例：设有表达式A*(B+C*(A-B))则有(-，A，B，T1)A-B(*，C，T1,T2)C*(A-B)(+，B，T2,T3)B+C*(A-B)(*，A，T3,T4)引进一过程GENQT：GENQT(ω):BEGINRESULT:=NEWTEMP；QT[J]:=(ω,SEM[S-2],SEM[S-1],RESULT);SEM[S-2]:=RESULT；J:=J+1；S:=S-1END语法制导翻译算法如下：语义子程序空F-(E)SEM[s]:=EADDR(