《中间代码及其翻译》PPT课件.ppt

第6章中间代码及其翻译,对语法分析后的语法单位要进行语义分析，包括两个阶段：(1)静态语义审查；(2)如果静态语义正确，生成中间代码。中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。中间代码设置的目的：(1)便于进行与机器无关的代码优化；(2)使编译程序改变目标机更容易；(3)使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。,静态语义审查,.作用：验证语法结构合法的程序是否真正有意义,.包含的内容：,(1)类型检查条件表达式的类型是不是boolean型验证指针地址访问只作用于指针函数必须有正确的参数个数和参数类型,(2)控制流检查break语句是否有转向点,(3)一致性检查在相同作用域中标识符只能说明一次,第6章中间代码及其翻译,源语言,目标语言,两小步,一大步,6.1常用的中间代码形式6.2几种语法成分的四元式设计6.3语法制导翻译6.4语法制导翻译器的实现,【内容提要】,6.1常用的中间代码形式,设有赋值语句：x=a*b+c则：,(1)逆波兰式:xab*c+=,(2)四元式：,(3)三元式：,(4)语义树：,简单比较，各有所长：,逆波兰式简单；四元式清楚；,三元式节省；语义树直观。,或,.表达式的四元式设计,6.2几种语法成分的四元式设计,设quat(E),res(E)分别为表达式E的四元式和结果变量。,(1)方框内的三个定义式，为四元式翻译法则；,(2)定义式中的为E1E2中最后运算的算符！,则：,【注】,其中：(运算符),i运算对象(变量或常量),quat(E)=quat(E),quat(i)=空,res(i)=i,q(res(E1)res(E2)ti),基本形式q:(o1o2t),quat(E1E2)=quat(E1)quat(E2),算符，对象1，对象2，结果,.赋值语句的四元式设计,=quat(a*(b-c),q(=res(E)_x),=quat(b-c),q(*ares(b-c)t),q(=res(E)_x),=quat(b-c),q(*ares(b-c)t),q(=res(E)_x),q(-bct),q(*ares(b-c)t),q(=res(E)_x),顺序编码,(1)(-bct1),(2)(*at1t2),(3)(=t2_x),6.2几种语法成分的四元式设计,语句标号为转向语句提供转入语句标识，二者用标号相关联。,.转向语句与语句标号的四元式设计,则有四元式序列：,(1)(gt_i),(11)(=t2_x),(10)(/t1ct2),(8)(lb_i),(9)(+abt1),标号后面是语句,自行练习一下！,6.2几种语法成分的四元式设计,.条件语句的四元式设计,(1)文法：S-if(E)S1elseS2,(2)语义结构：,可选,(3)四元式结构：,【注】q1：当res(E)=false则转向S2入口四元式；,q2：无条件转向出口四元式；,q3：条件语句出口四元式。,6.2几种语法成分的四元式设计,中间代码设计示例：,【例6.3】if(aT,=T*FGEQ(*),=T*(E)GEQ(*),=T*(E-TGEQ(-)GEQ(*),=T*(T-TGEQ(-)GEQ(*),=T*(T/FGEQ(/)-TGEQ(-)GEQ(*),算术表达式四元式属性翻译文法设计,a,b,c,t2,执行过程,a,ab,at1d,abc,a,t1,d,(3)(*at2t3),(2)(-t1dt2),(1)(/bct1),t3,a,根据符号串a*(b/c-d)的以上导出序列，去掉文法符号，可得四元式动作序列：,apush(a)*(bpush(b)/cpush(c)GEQ(/)-dpush(d)GEQ(-)GEQ(*),.赋值语句四元式翻译文法：,6.3.3各种语句四元式翻译文法设计,S-vPUSH(v)=EASSI(=);,.标号、转向语句四元式翻译文法：,S-iPUSH(i):LABEL(i)S;S-gotoiGOTO(i);,.条件语句四元式翻译文法：,6.3.3各种语句四元式翻译文法设计(续1),S-if(R)IF(if)S;elseEL(el)SIE(ie),(1)SEND(if,SEMm,_,_);,(2)POP;,R-EEGEQ(),GEQ()-表达式四元式生成函数；,其中的为当前匹配的关系算符。,需要回填,属性翻译文法应用示例,【例6.7】已知条件语句if(aE)功能增加：初始化和结果输出。,6.4.1递归子程序法四元式翻译器构造,return,6.4.1递归子程序法四元式翻译器构造,return,【例6.8】a*(b/c)#四元式递归子程序翻译过程:,QTq,SEMm,w,返回地址栈,所在源程序栈,Z,E,R0,a,T,R1,F,R4,a,*,ZET,R0R1,(,ZET,F,R0R1,R5,a,a,b,ZETF,E,R0R1R5,R7,T,R1,F,R4,a,b,/,ZETFET,R0R1R5R7R1,ab,c,ZETFET,F,R0R1R5R7R1,R6,ab,c,ZETFET,R0R1R5R7R1,),abc,(1)(/b,c,t1),a,t1,),ZETFE,R0R1R5R7,),at1,ZETF,R0R1R5,#,at1,ZET,R0R1,(2)(*a,t1,t2),t2,#,ZE,R0,#,t2,Z,Ok!,6.4.1递归子程序法四元式翻译器构造,主程序,子程序E,子程序T,子程序F,6.4.2LL(1)法四元式翻译器构造,2.LL(1)分析器的扩展,3.属性翻译文法设计,E-TEE-+TGEQ(+)E|-TGEQ(-)E|T-FTT-*FGEQ(*)T|/FGEQ(/)T|F-iPUSH(i)|(E),4.LL(1)分析表,【例6.13】a+b*c#四元式LL(1)法翻译过程:,#E,a,E,PUSHR,#,ET,T,a,PUSHR,TF,#E,F,a,PUSHR,#ET,PUSH(a)a,a,a,#ETPUSH(a),+,NEXT(w),a,#ET,T,+,a,PUSHR,#E,E,+,PUSHR,a,#,EGEQ(+)T+,+,+,a,NEXT(w),b,#EGEQ(+)T,T,PUSHR,a,#EGEQ(+),TF,F,b,PUSHR,a,接下页,6.4.2LL(1)法四元式翻译器构造,【例6.9】a+b*c#四元式LL(1)法翻译过程(续1):,6.4.2LL(1)法四元式翻译器构造,SEMm,QTq,操作,w,x,SYNn,#EGEQ(+)T,PUSH(b)b,b,b,NEXT(w),a,#EGEQ(+)TPUSH(b),*,a,b,#EGEQ(+)T,*,T,ab,PUSHR,#EGEQ(+),TGEQ(*)F*,*,ab,*,NEXT(w),c,#EGEQ(+)TGEQ(*)F,ab,F,PUSHR,#EGEQ(+)TGEQ(*),c,ab,PUSH(c)c,c,NEXT(w),#,ab,#EGEQ(+)TGEQ(*),PUSH(c),c,#EGEQ(+)TGEQ(*),#,abc,(1)(*b,c,t1),#EGEQ(+)T,#,a,T,#EGEQ(+),#,at1,(2)(+a,t1,t2),#E,t2,#,E,#,#,t2,ok,接上页,t1,PUSHR,PUSHR,6.4.3LR()法四元式翻译器构造,1.设置,2.属性翻译文法设计,3.LR()分析器的扩展,动作符号一定在最右侧,算术表达式句柄识别器的构造,I1:ZEEE+T,I4:ETTT*F,I7:TF,I9:F(E)EE+TETTT*FTFF(E)Fi,I8:Fi,I0:ZEEE+TETTT*FTFF(E)Fi,I5:TT*FF(E)Fi,I2:EE+TTT*FTFF(E)Fi,I10:F(E)EE+T,I11:F(E),I3:EE+TTT*F,I6:TT*F,E,T,i,F,(,+,*,(,E,T,F,i,T,F,(,i,F,(,i,),+,*,r(i)含义：(1)执行动作符号；(2)执行归约操作。,SLR(1)分析表,6.4.3LR()法四元式翻译器构造,【例6.10】a*b+c#四元式SLR(1)法翻译过程:,#0,0,a,#0,a8,8,*,PUSH(a),a,#0,F7,7,*,a,#0,T4,4,*,a,#0T4,*5,5,b,a,#0T4*5,8,+,a,PUSH(b),b,b8,#0T4*5,F6,6,+,ab,#0,T4,4,+,GEQ(*),(1)(*abt1),t1,#0,E1,1,+,t1,#0E1,+2,2,c,t1,#0E1+2,c8,8,#,t1,#0E1+2,F7,7,#,PUSH(c),c,t1c,#0E1+2,T3,3,#,GEQ(+),t1c,(2)(+t1ct2),#0,E1,1,#,结束,6.4.3LR()法四元式翻译器构造,6.4.4属性翻译文法的变换问题,自底向上中间代码翻译，要求属性翻译文法的动作符号必须位于产生式的最右端。不