《中间代码及其翻译.ppt》由会员分享，可在线阅读，更多相关《中间代码及其翻译.ppt（41页珍藏版）》请在三一办公上搜索。
1、第 6 章 中间代码及其翻译,对语法分析后的语法单位要进行语义分析，包括两个阶段：(1)静态语义审查；(2)如果静态语义正确，生成中间代码。中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。中间代码设置的目的：(1)便于进行与机器无关的代码优化；(2)使编译程序改变目标机更容易；(3)使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。,静态语义审查,.作用：验证语法结构合法的程序是否真正有意义,.包含的内容：,(1)类型检查 条件表达式的类型是不是boolean型 验证指针地址访问只作用于指针 函数必须有正确的参数个数和参数类型
2、,(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),re
3、s(E)分别为表达式E的四元式和结果变量。,(1)方框内的三个定义式，为四元式翻译法则；,(2)定义式中的为 E1E2 中最后运算的算符！,则：,【注】,其中：(运算符),i运算对象(变量或常量),quat(E)=quat(E),quat(i)=空,res(i)=i,q(res(E1)res(E2)ti),基本形式 q:(o1 o2 t),quat(E1E2)=quat(E1)quat(E2),算符，对象1，对象2，结果,.赋值语句的四元式设计,=quat(a*(b-c),q(=res(E)_ x),=quat(b-c),q(*a res(b-c)t),q(=res(E)_ x),=quat(
4、b-c),q(*a res(b-c)t),q(=res(E)_ x),q(-b c t),q(*a res(b-c)t),q(=res(E)_ x),顺序编码,(1)(-b c t1),(2)(*a t1 t2),(3)(=t2 _ x),6.2 几种语法成分的四元式设计,语句标号为转向语句提供转入语句标识，二者用标号相关联。,.转向语句与语句标号的四元式设计,则有四元式序列：,(1)(gt _ _ i),(11)(=t2 _ x),(10)(/t1 c t2),(8)(lb _ _ i),(9)(+a b t1),标号后面是语句,自行练习一下！,6.2 几种语法成分的四元式设计,.条件语句的
5、四元式设计,(1)文法：S-if(E)S1 else S2,(2)语义结构：,可选,(3)四元式结构：,【注】q1：当 res(E)=false 则转向S2入口四元式；,q2：无条件转向出口四元式；,q3：条件语句出口四元式。,6.2 几种语法成分的四元式设计,中间代码设计示例：,【例6.3】if(ab)x=a+b;,else y=a-b;,四元式序列：,(1)(a b t1),(2)(if t1 _ _),(3)(+a b t2),(4)(=t2 _ x),(5)(el _ _ _),(6)(-a b t3),(7)(=t3 _ y),(8)(ie _ _ _),【注】如果语句中没有,els
6、e y=a-b 部分，则,四元式结构中和四元式序列中的相应部分也不存在了！,请看,.while循环的四元式设计,(1)文法：S-while(E)S,(2)语义结构：,(3)四元式结构：,【注】q1：while 语句的入口四元式（提供转向E参照）；,q2：当 res(E)=false 转向出口四元式；,q3：while尾（兼循环转向 E）四元式。,6.2 几种语法成分的四元式设计,中间代码设计示例(续1)：,【例6.4】,四元式序列：,(1)(wh _ _ _),(2)(a b t1),(3)(a c t2),(4)(t1 t2 t3),(5)(do t3 _ _),(6)(+b c t4),(
7、7)(/t4 2 t5),(11)(we _ _ _),(8)(=t5 _ x),(9)(-a 1 t6),(10)(=t6 _ a),自行练习！,6.3 语法制导翻译,6.3.1 属性文法,【定义】属性文法是上下文无关文法在语义上的扩展，是一种接近形式化的语义描述方法，可定义为如下三元组：,其中：,G(文法)；V(属性集)；E(语义规则集)。,(1)属性代表与文法符号相关的信息，这里主要指语义信息(类型、种类、值和值地址)；文法产生式中的每个文法符号都附有若干个这样的属性。,(2)属性可以进行计算和传递，语义规则就是在同一产生式中，相互关联的属性求值规则。,(3)属性分两类（按属性求值规则区
8、分）：,综合属性：其值由子女属性值来计算(自底向上求值)；,继承属性：其值由父兄属性值来计算(自顶向下求值)。,说明,属性文法构造示例,【例6.5】类型说明的属性文法,属性值,已知类型说明文法G(D)：,下述属性文法用于把类型值传递给相应变量；,文法符号 X 的类型属性；,属性求值规则,【注】可以看出，X.type 属性是继承属性。,variable,属性文法构造示例(续1)：,(1)属性传递路线如,(2)由此可见，如果用此属性文法进行语法分析，,再附加一些语义处理手段，那么，标识符a,b,c获得属性值int，同时填写符号表，是很容易办到的。,属性文法构造示例(续2)：,【例6.6】算术表达式
9、的属性文法,下述属性文法用于算术表达式的求值运算：,return,属性文法构造示例(续3)：,根据算术表达式属性文法及其相应的属性求值规则，,属性传递、属性计算过程：,语法制导翻译技术,【定义】语法制导翻译(syntax_directed translations)是在语法分析过程中，随着分析(推导或归约)的逐步进展，每识别出一个语法结构，根据文法的每个规则所对应的语义子程序进行翻译的方法；核心技术是构造属性翻译文法-,在原文法产生式中插入语义动作符号(翻译子程序)，借以指明属性文法中属性求值时机和顺序。,以算术表达式文法为例，探讨属性翻译文法的构造！,通俗地说，所谓语法制导翻译技术，是指：,
10、算术表达式四元式属性翻译文法设计,假定：SEM(m)-语义栈(属性传递、赋值场所)；,(1)PUSH(i)压栈函数(把当前 i 压入语义栈)；,则：,其中：,QTq-四元式区；,语义栈次栈顶、栈顶,算术表达式四元式属性翻译文法设计,符号串 a*(b/c-d)的分析(翻译)过程(推导法),E=T,=T*F GEQ(*),=T*(E)GEQ(*),=T*(E-T GEQ(-)GEQ(*),=T*(T-T GEQ(-)GEQ(*),=T*(T/F GEQ(/)-T GEQ(-)GEQ(*),算术表达式四元式属性翻译文法设计,a,b,c,t2,执行过程,a,a b,a t1 d,a b c,a,t1,
11、d,(3)(*a t2 t3),(2)(-t1 d t2),(1)(/b c t1),t3,a,根据符号串 a*(b/c-d)的以上导出序列，去掉文法符号，可得四元式动作序列：,a push(a)*(b push(b)/c push(c)GEQ(/)-d push(d)GEQ(-)GEQ(*),.赋值语句四元式翻译文法：,6.3.3 各种语句四元式翻译文法设计,S-v PUSH(v)=E ASSI(=);,.标号、转向语句四元式翻译文法：,S-i PUSH(i):LABEL(i)S;S-goto i GOTO(i);,.条件语句四元式翻译文法：,6.3.3 各种语句四元式翻译文法设计(续1),
12、S-if(R)IF(if)S;else EL(el)S IE(ie),(1)SEND(if,SEMm,_,_);,(2)POP;,R-E E GEQ(),GEQ()-表达式四元式生成函数；,其中的 为当前匹配的关系算符。,需要回填,属性翻译文法应用示例,【例6.7】已知条件语句 if(ab)a=a+1;,通过语法制导分析(属性推导树)，写出动作序列：,属性翻译文法应用示例(续1),根据以上四元式翻译的动作序列，四元式生成过程：,a,a,b,a b,(1)(a b t1),t1,(2)(if t1 _ _),a,a,a,a a,1,a a 1,(3)(+a 1 t2),a t2,(4)(=t2
13、_ a),(5)(ie _ _ _),.循环语句四元式翻译文法：,6.3.3 各种语句四元式翻译文法设计(续2),S-while WH(wh)(R)DO(do)S WE(we);,(1)SEND(wh,_,_,_);,(1)SEND(do,SEMm,_,_);,【注】文法中的 R 为 关系表达式（见条件语句四元式翻译文法）。,(2)POP;,需要回填,6.4 语法制导翻译器的实现,语法制导翻译器的结构，可描述为：,1.自顶向下属性翻译文法的要求：,(1)原文法应满足自顶向下分析要求(如 LL(1)文法)；,(2)属性是自顶向下可求值的；,(3)动作符号可插入到产生式右部任何位置。,2.自底向上
14、属性翻译文法的要求：,(1)原文法应满足自底向上分析要求(如 LR()文法)；,(2)属性是自底向上可求值的；,(3)动作符号只能位于产生式的最右端。,其中,6.4 语法制导翻译器的实现(续1),6.4.1 递归子程序法四元式翻译器构造,2.属性翻译文法设计,3.递归子程序的扩展,动作符号在哪，就在哪执行之；,主控程序(Z-E)功能增加：初始化和结果输出。,6.4.1 递归子程序法四元式翻译器构造,return,6.4.1 递归子程序法四元式翻译器构造,return,【例6.8】a*(b/c)#四元式递归子程序翻译过程:,QTq,SEMm,w,返回地址栈,所在源程序栈,Z,E,R0,a,T,R
15、1,F,R4,a,*,Z E T,R0R1,(,Z E T,F,R0R1,R5,a,a,b,Z E T F,E,R0R1R5,R7,T,R1,F,R4,a,b,/,Z E T F E T,R0R1R5R7R1,ab,c,Z E T F E T,F,R0R1R5R7R1,R6,ab,c,Z E T F E T,R0R1R5R7 R1,),abc,(1)(/b,c,t1),a,t1,),Z E T F E,R0R1R5 R7,),at1,Z E T F,R0R1R5,#,at1,Z E T,R0R1,(2)(*a,t1,t2),t2,#,Z E,R0,#,t2,Z,Ok!,6.4.1 递归子程序法
16、四元式翻译器构造,主程序,子程序E,子程序T,子程序F,6.4.2 LL(1)法四元式翻译器构造,2.LL(1)分析器的扩展,3.属性翻译文法设计,E-T E E-+T GEQ(+)E|-T GEQ(-)E|T-F T T-*F GEQ(*)T|/F GEQ(/)T|F-i PUSH(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,+,PUS
17、HR,a,#,EGEQ(+)T+,+,+,a,NEXT(w),b,#EGEQ(+)T,T,PUSHR,a,#EGEQ(+),TF,F,b,PUSHR,a,接下页,6.4.2 LL(1)法四元式翻译器构造,【例6.9】a+b*c#四元式 LL(1)法翻译过程(续1):,6.4.2 LL(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(+)T
18、GEQ(*)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(+),#,a t1,(2)(+a,t1,t2),#E,t2,#,E,#,#,t2,ok,接上页,t1,PUSHR,PUSHR,6.4.3 LR()法四元式翻译器构造,1.设置,2.属性翻译文法设计,3.LR()分析器的扩展,动作符号一定在最右侧,算术表达式句柄识别器的构造,I1:Z E E E+T,I4:
19、E T T T*F,I7:T F,I9:F(E)E E+T E T T T*F T F F(E)F i,I8:F i,I0:Z E E E+T E T T T*F T F F(E)F i,I5:T T*F F(E)F i,I2:E E+T T T*F T F F(E)F i,I10:F(E)E E+T,I11:F(E),I3:E E+T T T*F,I6:T T*F,E,T,i,F,(,+,*,(,E,T,F,i,T,F,(,i,F,(,i,),+,*,r(i)含义：(1)执行动作符号；(2)执行归约操作。,SLR(1)分析表,6.4.3 LR()法四元式翻译器构造,【例6.10】a*b+c#
20、四元式 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)(*a b t1),t1,#0,E1,1,+,t1,#0E1,+2,2,c,t1,#0E1+2,c8,8,#,t1,#0E1+2,F7,7,#,PUSH(c),c,t1 c,#0E1+2,T3,3,#,GEQ(+),t1 c,(2)(+t1 c t2),#0,E1,1,#,结束,6.4.3 LR()法四元式翻译器构造,6.4.4 属性翻译文法的变换问题,自底向上中间代码翻译，要求属性翻译文法的动作符号必须位于产生式的最右端。不满足此条件的属性翻译文法，需要通过文法变换来解决。,1.赋值语句的属性翻译文法：,则有,2.标号、转向语句属性翻译文法：,令 Si-i PUSH(i),令 Sl-Si:LABEL(i),则有,6.4.4 属性翻译文法的变换问题,3.条件语句属性翻译文法 G(S):,则有 G(S):,6.4.4 属性翻译文法的变换问题,4.循环语句属性翻译文法 G(S):,则有 G(S):,6.4.4 属性翻译文法的变换问题,
