编译原理第7章中间语言

----语义分析之二第7章中间代码及其翻译7.1常用的中间代码形式示例7.2各种语法成分的中间代码设计7.3中间代码翻译算法7.4中间代码翻译的实现中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。中间代码设置的目的是便于编译的后期处理（如优化和目标生成）。源语言目标语言两小步一大步内容提要中间代码7.1常用的中间代码形式※设有赋值语句：x=a*b+c则：⑴逆波兰式:xab*c+=⑵四元式：⑴(*abt1)⑵(+t1ct2)⑶(=t2_x)⑶三元式：①(*ab)②(+①c)③(=②x)⑷语义树：=x+*cab※简单比较之，各有所长：逆波兰式简单；四元式清楚；三元式节省；语义树直观。或⑴t1=a*b⑵t2=t1+c⑶x=t27.2各种语法成分的中间代码设计7.2.1逆波兰式逆波兰式是一位波兰学者发明的，最初用于表达式的语义表式；基本形式如：源表达式逆波兰式a+b=Ⅰ.表达式的逆波兰式设计设pos(E)为表达式E的逆波兰式；其中：ω(运算符),i运算对象（变量或常量）①pos(E1ωE2)=pos(E1)pos(E2)ω②pos((E))=pos(E)③pos(i)=i⑴方框内的三个定义式，为逆兰式翻译法则；⑵定义式中的ω为E1ωE2中最后运算的算符！则：【注】ab+※表达式逆波兰式翻译示例:【例7.1】x*(a+b/d)(-e+5),pos()?=x∵pos(x*(a+b/d)(-e+5))=pos(x*(a+b/d))=x-=xa∴pos()=xabd/+*e5+=xabd/+*-【注】单目运算的逆波兰式：pos(-e)=e-为便于与双目运算符相区别，这里用代之。-pos(-e+5)*pos(-e+5)+*5+pos((a+b/d))*apos(b/d)+bd/pos(-e)5+epos((-e+5))⑵赋值语句的逆波兰式Ⅱ.其他语法成分的逆波兰式设计示例:【定义】v=E=vpos(E)=⑴单目运算“-”的逆波兰式改写单目算符“-”=“-”【定义】pos(-E）=pos(E)-或0pos(E)-例7.2x=(a+b)/-e*5,∵pos(x=(a+b)/-e*5)=xpos((a+b)/-e*5)==xpos((a+b)/-e)pos(5)*=xpos((a+b))pos(-e)/5*==pos()?=xab+e/5*=-∴pos()=-xab+e/5*=7.2.2四元式Ⅰ.表达式的四元式设计:设quat(E),res(E)⑴方框内的三个定义式，为四元式翻译法则；⑵定义式中的ω为E1ωE2中最后运算的算符！则：【注】其中：ω(运算符);i运算对象（变量或常数）②quat((E))=quat(E)③quat(i)=空,res(i)=iq:(ωres(E1)res(E2)ti)※基本形式q:(ωo1o2t）分别为表达式E的四元式和结果变量。①quat(E1ωE2)=quat(E1)算符，对象1，对象2，结果quat(E2)※表达式四元式翻译示例：【例7.3】a+b*(c-d)=quat(a),quat(a+b*(c-d))∵quat(b*(c-d)),q(+res(a)res(b*(c-d))t)空quat(b),quat((c-d)),q(*res(b)res(c-d)t)空q(-cdt1),q(*q(+⑴(-cdt1)⑵(*bt1t2)⑶(+at2t3)※按最终结果的生成顺序，可得:⑴⑵⑶t1t2),at2t3).b※表达式逆波兰式和四元式最简翻译算法示例:【例7.4】(a+b/d)e*(f-g),pos()?,Quat()?【逆波兰式生成要点】：※运算对象顺序不变，运算符紧跟运算对象之后！则：abd/+efg-*即：pos()=abd/+efg-*【四元式生成要点】：※按照运算法则，依次生成四元式！则：quat()=⑴(/bdt1)⑵(+at1t2)⑶(-fgt3)⑷(*et3t4)⑸(t2t4t5)【例7.5】x=a*(b-c)/(d+e)※设有赋值语句：v=EⅡ.赋值语句的四元式设计则有v=E=∵四元式结构：quat(E),q(=res(E)_v).∴四元式：⑴(-bct1)⑵(*at1t2)⑶(+det3)⑷(/t2t3t4)⑸(:=t4_x)quat(v=E)=q(:=res(E)_v)quat(E),语句标号为转向语句提供转入语句标识,二者用标号相关联。Ⅲ.转向语句与语句标号的四元式设计则有i:S=q(lb__i),⑴设有转向语句：gotoi则有gotoi=q(gt__i)【例7.4】gotoi;…i:x=(a+b)/c;则有四元式序列：⑴(gt__i)…⑾(:=t2_x)⑽(/t1ct2)⑻(lb__i)⑼(+abt1)⑵设有标号语句：i：S标号后面是语句quat(S)Ⅳ.条件语句的四元式设计⑴文法：S-if（E）S1[elseS2]⑵语义结构：可选E执行S1执行S2可选falsetrue入口出口⑶四元式结构：quat(E)q1(ifres(E)__)quat(S1)q2(el___)quat(S2)q3(ie___)【注】q1：当res(E)=false则转向S2入口四元式；q2：无条件转向出口四元式；q3：条件语句出口四元式。可选※条件语句四元式翻译示例：【例7.5】if(ab)x=a+b;quat(E)q1(ifres(E)__)quat(S1)q2(el___)quat(S2)q3(ie___)elsey=a-b;※四元式序列：⑴(abt1)⑵(ift1__)⑶(+abt2)⑷(=t2_x)⑸(el___)⑹(-abt3)⑺(=t3_y)⑻(ie___)【注】如果语句中没有elsey=a-b部分，则四元式结构中和四元式序列中的相应部分也不存在了！请看Ⅴ.循环语句的四元式设计:⑴文法：S-while（E）S⑵语义结构：⑶四元式结构：E执行Sfalsetrue入口出口q2(dores(E)__)quat(S)q3(we___)q1(wh___)quat(E)【注】q1：while语句的入口四元式（提供转向E参照）；q2：当res(E)=folse转向出口四元式；q3：while尾（兼循环转向E）四元式。q1四元式用作标识quat(E)的入口！※循环语句四元式翻译示例:【例7.6】※四元式序列：⑴(wh___)⑵(abt1)⑶(act2)⑷(∧t1t2t3)⑸(dores(E)__)⑹(+bct4)⑺(/t42t5)⑾(we___)while(ab∧ac){x=(b+c)/2;a=a-1;}quat(E)q1(wh___)quat(S)q2(dores(E)__)q3(we___)⑻(=t5_x)⑼(-a1t6)⑽(=t6_a)⑴t1=c/d⑵t2=t1-e⑶t3=b*t2⑷t4=a+t3t3⑷abcd/e-*+⑴t1⑵⑶t2t4(结果)【注】令人感兴趣的是表达式逆波兰式的计算过程也就是四元式的计算过程；二者在翻译算法也会是一致的。a+b*(c/d-e)的逆波兰式四元式【算法】设置一个“栈”,每当NEXT(w),重复执行：⑴若w=运算对象，则压入栈中暂存：PUSH(w);⑵若w=运算符,则弹出栈顶对象计算之,并把结果压栈。※逆波兰式(四元式)计算过程示例:练习题：【习题7.1】解释下列词语：中间代码；常见的几种中间代码形式；【习题7.2】指出下述语法成分的四元式结构设计：条件语句；while循环语句；【习题7.3】写出的四元式序列：(1)if(x0)x=(a-b/2)*c；(2)while(a∨b)b=2*a/5;(3)a1:y=2*x-6;…;gotoa1;※SLR(1)分析表设计示例1:【例5.12】G(E):E-E+T|TT-(E)|i0TE#)(+i确定的SLR(1)分析表构造：982,765431,2r(4)r(4)r(4)r(4)r(4)r(3)r(3)r(3)r(3)r(3))8+3T5E2,7(6i9r(2)r(2)r(2)r(2)r(2)r(1)r(1)r(1)T4(6i9T5E1,2(6i9OK+3r(1)r(1)E`-E1(0)E-E2+3T4(1)|T5(2)T-(6E7)8(3)|i9(4)G`(E`)注∵状态{1,2}处出现冲突，∴不是LR(0)文法！谢谢收看！