《编译原理：第七章 中间语言(1)》由会员分享，可在线阅读，更多相关《编译原理：第七章 中间语言(1)（18页珍藏版）》请在金锄头文库上搜索。
1、 - - 语义分析之二语义分析之二第第 7 7 章章 中间代码及其翻译中间代码及其翻译7.1 常用的常用的中间代码形式中间代码形式示例示例7.2 各种语法成分的各种语法成分的中间代码中间代码设计设计7.3 中间代码翻译算法中间代码翻译算法 7.4 中间代码翻译中间代码翻译的实现的实现 中间代码中间代码是高级程序语言中，各种语法成分的是高级程序语言中，各种语法成分的语语义结构义结构表示；它介于源语言和目标语言之间表示；它介于源语言和目标语言之间。 中间代码中间代码设置的目的是设置的目的是便于编译的后期处理便于编译的后期处理（如（如优化和目标生成）。优化和目标生成）。源语言源语言目标语言目标语言两
2、小步两小步一大步一大步内容内容提要提要中间中间代码代码7.1 7.1 常用的常用的中间代码形式中间代码形式 设有设有 赋值语句赋值语句：x=a*b+c x=a*b+c 则：则： 逆波兰式逆波兰式: : xabxab*c+=*c+= 四元式：四元式： ( * a b t1 ( * a b t1 ) ) ( + t1 c t2 ( + t1 c t2 ) ) ( = t2 _ x ( = t2 _ x ) ) 三元式：三元式： ( * a b ) ( * a b ) ( + c ) ( + c ) ( = x ) ( = x ) 语义树：语义树：= =x x+ +* *c ca ab b 简单比较
3、之，各有所长：简单比较之，各有所长：逆波兰式逆波兰式 简单简单 ；四元式四元式 清楚清楚 ；三元式三元式 节省节省 ；语义树语义树 直观直观 。或或 t1=a*b t1=a*b t2=t1+c t2=t1+c x=t2 x=t2 7.2 7.2 各种语法成分的各种语法成分的中间代码设计中间代码设计7.2.1 7.2.1 逆波兰式逆波兰式 逆波兰式逆波兰式是一位波兰学者发明的，最初用于是一位波兰学者发明的，最初用于表达式表达式的语义表式；基本形式如：的语义表式；基本形式如：源表达式源表达式逆波逆波兰式兰式a + ba + b=. . 表达式表达式的的逆波兰式逆波兰式设计设计 设设 pos(E)
4、pos(E) 为表达式为表达式 E E 的的逆波兰式逆波兰式；其中：其中：(运算符运算符), i), i运算对象（变量或常量）运算对象（变量或常量） pos(pos(E E1 1EE2 2)=pos()=pos(E E1 1)pos()pos(E E2 2) ) pos( pos(E)(E)=pos()=pos(E E) ) pos( pos(i i)=)=i i 方框内的三个方框内的三个定义式定义式 ，为，为逆兰式逆兰式翻译法则翻译法则； 定义式定义式中的中的为为 E E1 1EE2 2 中中最后运算的最后运算的算符算符！则：则：【注注】a b +a b + 表达式表达式逆波兰式逆波兰式翻译
5、示例翻译示例: :【例【例7.17.1】 x*(a+b/d)(-e+5) , pos x*(a+b/d)(-e+5) , pos( )( ) ? ? = = x x pospos( (x*(a+b/d)(-e+5)x*(a+b/d)(-e+5) ) = = pos pos( (x*x*(a+b/d)(a+b/d) )= = x x- -= = x a x a pos( )= pos( )= xabdxabd/+*e 5+/+*e 5+= = x a x a bdbd/ + */ + *- -【注注】 单目单目运算的运算的逆波兰式：逆波兰式： pos(-e)= e -pos(-e)= e -为便
6、于与双目运算符相区别，这里用为便于与双目运算符相区别，这里用 代之。代之。- -pospos( (- -e+5e+5) ) * pos* pos( (- -e+5e+5) ) + *+ *5 5 + + pospos( ( (a+b/d)a+b/d) )* * a posa pos( (b/db/d) )+ +bdbd/ /pospos( (- -e e) )5 5 + + e epospos( (-(-e+5)e+5) ) v pos(E) =v = E = v pos(E) = 单目运算单目运算“-”-”的逆波兰式的逆波兰式改写单目算符改写单目算符 “-” =“ - -” =“ - ” ”
7、 【定义定义】 pos pos( (-E-E）= = pospos( (E E) ) - - 或或 0 pos0 pos( (E E) ) - -例例7.2 x=(7.2 x=(a+b)/-ea+b)/-e*5 , *5 , pos(pos(x=(a+b)/-e*5 ) )= x= x pos(pos( (a+b)/-e*5 ) )= = x= xpos( (a+b)/-e)pos(5)* *= x= xpos( (a+b)pos(-e)/ 5* *= = =pospos( )( ) ? ? = x= xabab+ +e/ 5* *= =- - pos()=pos()=- -xab+exab+
8、e/5*=/5*=7.2.2 7.2.2 四元式四元式. . 表达式表达式的的四元式四元式设计设计: : 设设 quat(E),res(Equat(E),res(E) ) 方框内的三个方框内的三个定义式定义式 ，为，为四元式四元式翻译法则翻译法则； 定义式定义式中的中的为为 E E1 1EE2 2 中中最后运算的最后运算的算符算符！则：则：【注注】其中：其中：(运算符运算符); i); i运算对象（变量或常数运算对象（变量或常数） quat(quat(E(E) )= )= quat(quat(E E) ) quat(quat(i i)=)= 空空 , , res(ires(i)= i)= iq
9、:(q:( res( res(E E1 1) res() res(E E2 2) ) titi ) ) 基本形式基本形式 q:q:( ( o1 o2 t o1 o2 t ）分别为表达式分别为表达式E E的的四元式四元式和和结果变量结果变量。 quat(quat(E E1 1EE2 2)= quat()= quat(E E1 1) )算符，对象算符，对象1 1，对象，对象2 2，结果，结果quat(quat(E E2 2) ) 表达式表达式四元式四元式翻译示例：翻译示例：【例例7.37.3】 a+b*(c-d) a+b*(c-d)= = quatquat( (a a),),quatquat( (
10、 a+b*(c-d)a+b*(c-d) )quatquat( (b b*(c-*(c-d)d) ), ,q(+ q(+ res(ares(a) ) res(bres(b*(c-d) t )*(c-d) t )空quatquat( (b b) ), ,quatquat( (c-d(c-d) ) ), ,q(* q(* res(bres(b) ) res(c-dres(c-d) t ) t )空q(- c d q(- c d t1)t1), ,q(*q(*q(+q(+ (- c d t1 ) (- c d t1 ) (* b t1 t2 )(* b t1 t2 )(+ a t2 t3 )(+ a
11、t2 t3 ) 按最终结果的按最终结果的生成顺序，可得生成顺序，可得: :t1t1 t2),t2),a a t2t2 t3).t3).b b 表达式表达式逆波兰式逆波兰式和和四元式四元式最简最简 翻译算法翻译算法示例示例: :【例例7.47.4】 (a+b/d)e*(f-g), pos()?, (a+b/d)e*(f-g), pos()?, QuatQuat()?()? 【逆波兰式生成要点逆波兰式生成要点】： 运算对象运算对象顺序不变，顺序不变，运算符运算符紧跟运算对象之后！紧跟运算对象之后！则：则：a a b b d d / /+ +e e f f g g - - * * 即：即： pos(
12、)= pos()= abd/+efgabd/+efg-*-*【四元式生成要点四元式生成要点】： 按照运算法则，按照运算法则，依次生成四元式！依次生成四元式！则：则：quatquat()=()= ( / b d t1 )( / b d t1 ) ( + a t1 t2 ) ( + a t1 t2 ) ( - f g t3 ) ( - f g t3 ) ( * e t3 t4 ) ( * e t3 t4 ) ( t2 t4 t5 ) ( v = E = 四元式结构：四元式结构：quatquat( (E E),),q( = q( = res(Eres(E) _ v ) _ v ).). 四元式：四元
13、式： ( - b c t1 )( - b c t1 ) ( * a t1 t2 ( * a t1 t2 ) ) ( + d e t3 )( + d e t3 ) ( / t2 t3 t4 ) ( / t2 t3 t4 ) (:= t4 _ x )(:= t4 _ x )quatquat( (v v=E=E) )= =q(:= q(:= res(Eres(E) _ v ) _ v )quat(Equat(E), ), 语句语句标号标号为为转向语句转向语句提供转入语句提供转入语句标识标识, ,二者用二者用标号标号相关联相关联。. . 转向语句转向语句与语句与语句标号标号的的四元式四元式设计设计则有
14、则有 i : S = q( lb _ _ i ), i : S = q( lb _ _ i ), 设有设有 转向语句：转向语句： gotogoto i i 则有则有 gotogoto i = q( i = q( gtgt _ _ i _ _ i ) )【例例7.47.4】 gotogoto i ; i: x=(a+b)/c; i ; i: x=(a+b)/c;则有四元式序列：则有四元式序列： ( (gtgt _ _ i ) _ _ i ) (:= t2 _ x ) (:= t2 _ x ) ( / t1 c t2 ( / t1 c t2 ) ) (lb _ _ i )(lb _ _ i ) (
15、 + a b t1 ) ( + a b t1 ) 设有设有 标号语句：标号语句： i i：S S 标号标号后面后面是是语句语句quat(Squat(S) ). . 条件语句条件语句的的四元式四元式设计设计 文法：文法：S -S - if if（E E）S1 S1 else S2 else S2 语义结构：语义结构：可选可选 E E执行执行S1S1执行执行S2S2可选可选falsefalsetruetrue入口入口出口出口 四元式结构：四元式结构：quat(Equat(E) )q q1 1(if (if res(Eres(E)_ _ )_ _ )quat(S1)quat(S1)q q2 2(el
16、 _ _ _ )(el _ _ _ )quat(S2)quat(S2)q q3 3(ie _ _ _ )(ie _ _ _ )【注注】 q q1 1：当当 res(Eres(E)=false )=false 则则 转向转向S2S2入口入口四元式四元式；q q2 2：无条件无条件转向转向出口出口四元式四元式；q q3 3：条件语句条件语句出口四元式。出口四元式。可选可选 条件语句条件语句四元式四元式翻译示例：翻译示例：【例例7.57.5】 if(ab)x=a+b; if(ab)x=a+b; quat(Equat(E) )q q1 1(if (if res(Eres(E)_ _ )_ _ ) )
17、quat(S1)quat(S1)q q2 2(el _ _ _ (el _ _ _ ) )quat(S2)quat(S2)q q3 3(ie _ _ _ )(ie _ _ _ )else y=a-b;else y=a-b; 四元式序列：四元式序列： ( a b t1 ( S - while while（E E）S S 语义结构：语义结构： 四元式结构：四元式结构： E E执行执行 S Sfalsefalsetruetrue入口入口出口出口q q2 2(do (do res(Eres(E)_ _ )_ _ ) ) quat(Squat(S) )q q3 3(we _ _ _ )(we _ _ _
18、 )q q1 1(wh _ _ _ (wh _ _ _ ) ) quat(Equat(E) )【注注】 q q1 1：while while 语句的语句的入口入口四元式四元式（提供转向（提供转向E E参照参照）；q q2 2：当当 res(Eres(E)=)=folsefolse 转向转向出口出口四元式四元式；q q3 3：whilewhile尾尾（兼循环转向（兼循环转向 E E ）四元式。四元式。q1q1四元式用作标识四元式用作标识quat(Equat(E) )的入口！的入口！ 循环语句循环语句四元式四元式翻译示例翻译示例: :【例例7.67.6】 四元式序列：四元式序列： ( (whwh
19、_ _ _ _ _ _ ) ) ( a b t1 ) ( a c t2 ) ( a c t2 ) ( t1 t2 t3 ) ( t1 t2 t3 ) (do (do res(Eres(E)_ _ )_ _ ) ) ( + b c t4 ) ( + b c t4 ) ( / t4 2 t5 ) ( / t4 2 t5 ) (we _ _ _ ) (we _ _ _ )while (ac)while (ac) x=(b+c)/2; a=a-1; x=(b+c)/2; a=a-1; quat(Equat(E) )q q1 1(wh _ _ _ )(wh _ _ _ )quat(Squat(S) )q
20、 q2 2(do (do res(Eres(E)_ _ )_ _ ) )q q3 3(we _ _ _ )(we _ _ _ ) ( = t5 _ x ) ( = t5 _ x ) ( - a 1 t6 ) ( - a 1 t6 ) ( = t6 _ a ) ( = t6 _ a ) t1 = c / dt1 = c / d t2 = t1 - e t2 = t1 - e t3 = b * t2t3 = b * t2 t4 = a + t3t4 = a + t3t3t3a b c da b c d / / e e - * + - * + t1t1t2t2t4t4 ( (结果结果) )【注注】令
21、人感兴趣的是表达式令人感兴趣的是表达式逆波兰式逆波兰式的计算过程也就是的计算过程也就是四元式四元式的计算过程；二者在翻译算法也会是一致的。的计算过程；二者在翻译算法也会是一致的。a+b*(c/d-e)a+b*(c/d-e)的逆波兰式的逆波兰式四元式四元式【算法算法】 设置一个设置一个“栈栈”, ,每当每当 NEXT(w)NEXT(w), ,重复执行：重复执行： 若若 w=w=运算对象，则运算对象，则 压入栈中暂存：压入栈中暂存：PUSH(w); PUSH(w); 若若 w=w=运算符运算符, ,则弹出栈顶对象则弹出栈顶对象计算之计算之, ,并把结果压栈。并把结果压栈。 逆波兰式逆波兰式( (四
22、元式四元式) )计算过程示例计算过程示例: :练习题：练习题：【习题习题7.17.1】解释下列词语：解释下列词语： 中间代码；常见的几种中间代码形式；中间代码；常见的几种中间代码形式；【习题习题7.27.2】指出下述语法成分的指出下述语法成分的四元式结构四元式结构设计：设计： 条件语句；条件语句；whilewhile循环语句；循环语句； 【习题习题7.37.3】写出写出 的四元式序列的四元式序列： (1) if(x0)x=(a-b/2)*c(1) if(x0)x=(a-b/2)*c； (2) while (ab) b=2*a/5;(2) while (ab) b=2*a/5; (3) a1:y
23、=2*x-6; (3) a1:y=2*x-6;gotogoto a1; a1; SLR(1) SLR(1)分析表设计示例分析表设计示例1 1 1 1: :【例例5.125.12】G(E):G(E):E - E + T | TE - E + T | TT - ( E ) | iT - ( E ) | i0 0TE#)(+i i确定的确定的SLR(1)SLR(1)分析表分析表构造：构造：9 98 82,72,76 65 54 43 31,21,2r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r
24、(3)8)8+ +3 3T5T5E2,7E2,7(6(6i9i9r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(1)r(1)r(1)r(1)r(1)r(1)T4T4(6(6i9i9T5T5E1,2E1,2(6(6i9i9OKOK+ +3 3r(1)r(1)r(1)r(1)E- EE- E1 1 (0) (0)E - EE - E2 2 + +3 3 T T4 4 (1)| (1)| T T5 5(2)(2)T - (T - (6 6 E E7 7 ) )8 8(3)| i(3)| i9 9(4)(4)G(EG(E) )注注 状态状态 1,2 1,2 处出现冲突，处出现冲突，不是不是LR(0)LR(0)文法！文法！谢谢收看！谢谢收看！
