中间代码及其翻译

1、中间代码及其翻译第1页，共41页，2022年，5月20日，5点49分，星期日静态语义审查. 作用：验证语法结构合法的程序是否真正有意义 . 包含的内容：(1) 类型检查 条件表达式的类型是不是boolean型 验证指针地址访问只作用于指针 函数必须有正确的参数个数和参数类型 (2) 控制流检查 break语句是否有转向点(3) 一致性检查 在相同作用域中标识符只能说明一次 第2页，共41页，2022年，5月20日，5点49分，星期日第 6 章 中间代码及其翻译源语言目标语言两小步一大步中间代码6.1 常用的中间代码形式6.2 几种语法成分的四元式设计6.3 语法制导翻译 6.4 语法制导翻译器

2、的实现【内容提要】第3页，共41页，2022年，5月20日，5点49分，星期日6.1 常用的中间代码形式 设有赋值语句：x=a*b+c 则：(1) 逆波兰式: xab*c+=(2) 四元式：(1) ( * a b t1 ) (2) ( + t1 c t2 ) (3) ( = t2 _ x ) (3) 三元式： ( * a b ) ( + c ) ( = x ) (4) 语义树 ：=x+*cab 简单比较，各有所长：逆波兰式 简单 ；四元式 清楚 ；三元式 节省 ；语义树 直观 。或(1) t1=a*b (2) t2=t1+c (3) x=t2 第4页，共41页，2022年，5月20日，5点49

3、分，星期日.表达式的四元式设计 6.2 几种语法成分的四元式设计设 quat(E),res(E)分别为表达式E的四元式和结果变量。(1) 方框内的三个定义式 ，为四元式翻译法则；(2) 定义式中的为 E1E2 中最后运算的算符！则：【注】其中：(运算符), i运算对象(变量或常量) quat(E)= quat(E) quat(i)= 空 , res(i)= iq( res(E1) res(E2) ti ) 基本形式 q:( o1 o2 t ) quat(E1E2)= quat(E1) quat(E2)算符，对象1，对象2，结果第5页，共41页，2022年，5月20日，5点49分，星期日 【例6

4、.1】 x=E , E= a*(b-c) 设有赋值语句： v = E. 赋值语句的四元式设计则有 v = E = quat(E) , q( = res(E) _ v )= quat(a * (b-c) , q( = res(E) _ x )= quat(b-c),q(* a res(b-c) t), q( = res(E) _ x)= quat( 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

5、) (3) ( = t2 _ x)*quat( x = E )6.2 几种语法成分的四元式设计第6页，共41页，2022年，5月20日，5点49分，星期日 语句标号为转向语句提供转入语句标识，二者用标号相关联。. 转向语句与语句标号的四元式设计则有 i : S = q( lb _ _ i ) , quat(S)(1) 设有 转向语句： goto i 则有 goto i = q( gt _ _ i )【例6.2】 goto i ; i: x=(a+b)/c;则有四元式序列：(1) ( gt _ _ i )(11) ( = t2 _ x )(10) ( / t1 c t2)(8) ( lb _ _

6、 i )(9) ( + a b t1 )(2) 设有 标号语句： i : S 标号后面是语句自行练习一下！6.2 几种语法成分的四元式设计第7页，共41页，2022年，5月20日，5点49分，星期日. 条件语句的四元式设计(1) 文法：S - if (E) S1 else S2 (2) 语义结构：可选 E执行S1执行S2可选 falsetrue入口出口(3) 四元式结构： quat(E) q1 (if res(E) _ _ )quat(S1) q2 ( el _ _ _ )quat(S2) q3 ( ie _ _ _ )【注】 q1：当 res(E)=false 则转向S2入口四元式；q2：无

7、条件转向出口四元式；q3：条件语句出口四元式。可选6.2 几种语法成分的四元式设计第8页，共41页，2022年，5月20日，5点49分，星期日 中间代码设计示例：【例6.3】 if(ab) x=a+b; quat(E) q1 ( if res(E) _ _ )quat(S1) q2 ( el _ _ _ )quat(S2) q3 ( ie _ _ _ ) else y=a-b; 四元式序列： (1) ( while (E) S(2) 语义结构：(3) 四元式结构： E执行 S falsetrue入口出口q2 ( do res(E)_ _ ) quat(S)q3 ( we _ _ _ )q1(

8、wh _ _ _ )quat(E)【注】 q1：while 语句的入口四元式（提供转向E参照）；q2：当 res(E)=false 转向出口四元式；q3：while尾（兼循环转向 E ）四元式。q1四元式用作标识quat(E)的入口！6.2 几种语法成分的四元式设计第10页，共41页，2022年，5月20日，5点49分，星期日 中间代码设计示例(续1)：【例6.4】 四元式序列：(1) (wh _ _ _ )(2) ( a c t2 )(4) ( t1 t2 t3 )(5) ( do t3 _ _ )(6) ( + b c t4 )(7) ( / t4 2 t5 )(11) (we _ _ _

9、 )while (ac) x=(b+c)/2; a=a-1; quat(E)q1(wh _ _ _ )quat(S)q2(do res(E)_ _ )q3(we _ _ _ )(8) ( = t5 _ x )(9) ( - a 1 t6 )(10) ( = t6 _ a )自行练习！第11页，共41页，2022年，5月20日，5点49分，星期日6.3 语法制导翻译6.3.1 属性文法A=(G, V, E); 【定义】 属性文法是上下文无关文法在语义上的扩展，是一种接近形式化的语义描述方法，可定义为如下三元组：其中：G(文法)；V(属性集)；E(语义规则集)。 (1) 属性代表与文法符号相关的信

10、息，这里主要指语义信息(类型、种类、值和值地址)；文法产生式中的每个文法符号都附有若干个这样的属性。 (2) 属性可以进行计算和传递，语义规则就是在同一产生式中，相互关联的属性求值规则。 (3) 属性分两类（按属性求值规则区分）： 综合属性：其值由子女属性值来计算(自底向上求值)； 继承属性：其值由父兄属性值来计算(自顶向下求值)。说明第12页，共41页，2022年，5月20日，5点49分，星期日 属性文法构造示例【例6.5】 类型说明的属性文法 D - T v L L - ,v L | T - int | real | 设：X.type 为D - T v L | (v.type, L.typ

11、e) =T.type L - ,v L1 | (v.type, L1.type) =L.type T - int | T.type = int L - T - real | T.type = real 属性值已知类型说明文法G(D)：下述属性文法用于把类型值传递给相应变量； 文法符号 X 的类型属性；属性求值规则【注】可以看出，X.type 属性是继承属性。variable第13页，共41页，2022年，5月20日，5点49分，星期日 属性文法构造示例 (续1)：则类型说明 int a,b,c 的属性语法树：DT.int L.int , L.int, L.i

12、nt int(1) 属性传递路线如所示；(2) 由此可见，如果用此属性文法进行语法分析，再附加一些语义处理手段，那么，标识符a,b,c获得属性值int，同时填写符号表，是很容易办到的。D - T v L | (v.type, L.type)=T.type L - ,v L1 | (v.type, L1.type)=L.type T - int | T.type = int L - T - real | T.type = real 第14页，共41页，2022年，5月20日，5点49分，星期日 属性文法构造示例 (续2)：【例6.6】 算术表达式的属性文法 设：X.val 为文法符号 X 的值属

13、性；下述属性文法用于算术表达式的求值运算：E - E1 + T ; | E.val = E1.val + T.valT - T1 * F ; | T.val = T1.val * F.valE - T ; | E.val = T.valT - F ; | T.val = F.valF - ( E ) ; | F.val = E.valF - i ; | F.val = i.valE - E1 - T ; | E.val = E1.val - T.valT - T1 / F ; | T.val = T1.val / F.val【注】可以看出：X.val属性是综合属性。return第15页，共41

14、页，2022年，5月20日，5点49分，星期日 属性文法构造示例 (续3)： 根据算术表达式属性文法及其相应的属性求值规则， 2+4*(5-9/3)的属性语法树：E.10E1.2 + T.8 T.2 T.4 * F.2 F.2 F.4 ( E.2 ) 2 4 E.5 - T.3 T.5 T.9 / F.3 F.5 F.9 3 5 9属性传递、属性计算过程：按 最左推导或 最左归约第16页，共41页，2022年，5月20日，5点49分，星期日语法分析技术 属性翻译文法构造技术 + 语法制导翻译技术 【定义】语法制导翻译(syntax_directed translations)是在语法分析过程中

15、，随着分析(推导或归约)的逐步进展，每识别出一个语法结构，根据文法的每个规则所对应的语义子程序进行翻译的方法；核心技术是构造属性翻译文法 - 在原文法产生式中插入语义动作符号(翻译子程序)，借以指明属性文法中属性求值时机和顺序。 以算术表达式文法为例，探讨属性翻译文法的构造！ 通俗地说，所谓语法制导翻译技术，是指：第17页，共41页，2022年，5月20日，5点49分，星期日(2) GEQ() 表达式四元式生成函数:G(E)：E - T | E+TGEQ(+) | E-TGEQ(-) T - F | T*FGEQ(*) | T/FGEQ(/) F - iPUSH(i) | ( E ) 算术表达

16、式四元式属性翻译文法设计 假定：SEM(m) - 语义栈(属性传递、赋值场所)；(1) PUSH(i) 压栈函数(把当前 i 压入语义栈)；则：其中： QTq - 四元式区； t = NEWT; 申请临时变量函数； SEND(,SEMm-1,SEMm,t) POP;POP;PUSH(t)生成一个四元式送QTq语义栈次栈顶、栈顶第18页，共41页，2022年，5月20日，5点49分，星期日 算术表达式四元式属性翻译文法设计G(E)：E - T | E+TGEQ(+) | E-TGEQ(-) T - F | T*FGEQ(*) | T/FGEQ(/) F - i PUSH(i) | ( E ) 符

17、号串 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 push(a) *( b push(b) /c push(c) GEQ(/) -d push(d) GEQ(-) ) GEQ(*) +第19页，共41页，2022年，5月20日，5点49分，星期日 算术表达式四元式属性翻译文法设计 QTq SEMm 动作序列 a b c t2 PUSH(d) G

18、EQ(-) GEQ(/) GEQ(*) PUSH(c) PUSH(b) PUSH(a)执行过程 a a b a t1 d a b ca t1d(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(*) 第20页，共41页，2022年，5月20日，5点49分，星期日. 赋值语句四元式翻译文法： 6.3.3 各种语句四元式翻译文法设

19、计S - v PUSH(v) = E ASSI(=) ; ASSI(=) - 赋值函数； (1) SEND( =, SEMm, _ , SEMm-1 ); (2) POP;POP; . 标号、转向语句四元式翻译文法： S - i PUSH(i) : LABEL(i) S ; S - goto i GOTO(i) ; LABEL(i) - 标号函数； (1) SEND( lb, _ ,_ , SEMm ); (2) POP; GOTO(i) - 转向函数； (1) SEND( gt ,_ ,_ , i ); 第21页，共41页，2022年，5月20日，5点49分，星期日. 条件语句四元式翻译文法

20、： 6.3.3 各种语句四元式翻译文法设计(续1)S - if(R) IF(if) S; else EL(el) S IE(ie) IF(if) - if 函数； (1) SEND( if, SEMm, _ , _ ); (2) POP; IE(ie) - ifend 函数； (1) SEND( ie, _ ,_ ,_ ); EL(el) - else 函数； (1) SEND( el,_ ,_ ,_ ); R - E E GEQ() GEQ() - 表达式四元式生成函数； 其中的 为当前匹配的关系算符。需要回填第22页，共41页，2022年，5月20日，5点49分，星期日 属性翻译文法应用示

21、例【例6.7】 已知条件语句 if (a if ( R ) IF (if) S ; IE (ie) E EGEQ() apush(a) bpush(b)apush(a) = EASSI(=)E + TGEQ(+)T TF Fapush(a)TFF1push(1) if(ab)a=a+1 四元式翻译的动作序列：push(a) , push(b) , GEQ() , IF(if) , PUSH(a) push(a) , push(1) , GEQ(+) , ASSI(=) , IE(ie) 第23页，共41页，2022年，5月20日，5点49分，星期日 属性翻译文法应用示例(续1)根据以上四元式翻

22、译的动作序列，四元式生成过程：IF(if) push(a) push(b)push(a)push(1)GEQ(+)ASSI(=)IE(ie)push(a)GEQ() QTq SEMm 动作序列 a a b a b(1) ( a b t1) t1(2) (if t1 _ _ ) a a a a a1 a a 1(3) ( + a 1 t2) a t2 (4) ( = t2 _ a ) (5) (ie _ _ _ )push(a) , push(b) , GEQ( while WH(wh) (R) DO(do) S WE(we); WH(wh) - 循环头函数； (1) SEND( wh, _ ,

23、 _ , _ ); WE(we) - 循环尾(while end) 函数； (1) SEND( we,_ ,_ , _ ); DO(do) - DO 函数； (1) SEND( do, SEMm ,_ , _ ); 【注】文法中的 R 为 关系表达式（见条件语句四元式翻译文法）。 (2) POP ; 需要回填第25页，共41页，2022年，5月20日，5点49分，星期日6.4 语法制导翻译器的实现 语法制导翻译器的结构，可描述为：扩展的语法分析器 属性翻译文法+ 1.自顶向下属性翻译文法的要求：(1) 原文法应满足自顶向下分析要求(如 LL(1)文法)；(2) 属性是自顶向下可求值的；(3)

24、动作符号可插入到产生式右部任何位置。 2.自底向上属性翻译文法的要求：(1) 原文法应满足自底向上分析要求(如 LR( )文法)；(2) 属性是自底向上可求值的；(3) 动作符号只能位于产生式的最右端。其中第26页，共41页，2022年，5月20日，5点49分，星期日6.4 语法制导翻译器的实现(续1)6.4.1 递归子程序法四元式翻译器构造1. 设置语义栈：SEMm四元式区：QTq2. 属性翻译文法设计3.递归子程序的扩展 动作符号在哪，就在哪执行之； 主控程序( Z - E )功能增加：初始化和结果输出。E - T + TGEQ(+) | - TGEQ(-) T - F * FGEQ(*)

25、 | / FGEQ(/) F - iPUSH(i) | ( E )G1(E): 下面以算术表达式文法为例讲述三种简单实用的翻译器的设计问题。 E - T + T | - T T - F * F | / F F - i | ( E )第27页，共41页，2022年，5月20日，5点49分，星期日主程序 Z 开始 结束 #ENEXT(w)err0yn结果输出 初始化 R0 R2 入口出口NEXT(w)T +Tyn -nNEXT(w)TyGEQ(+)GEQ(-)子程序 E R3 R1Ri为返回地址6.4.1 递归子程序法四元式翻译器构造return第28页，共41页，2022年，5月20日，5点49

26、分，星期日 R5 入口出口NEXT(w)F *Fyn /nNEXT(w)FyGEQ(*)GEQ(/)子程序 T R6 R4入口出口 i (err1NEXT(w)err2NEXT(w)E )yyynnn子程序 FPUSH(i) R7Ri为返回地址6.4.1 递归子程序法四元式翻译器构造return第29页，共41页，2022年，5月20日，5点49分，星期日【例6.8】a*(b/c)# 四元式递归子程序翻译过程: QTqSEMm w 返回地址栈所在源程序栈ZER0 aTR1FR4a *Z E T R0R1 (Z E T FR0R1R5aa bZ E T FER0R1R5R7TR1FR4ab /Z

27、 E T F E TR0R1R5R7R1ab cZ E T F E TFR0R1R5R7R1R6abcZ E T F E TR0R1R5R7 R1)abc(1) (/ b,c,t1)at1)Z E T F ER0R1R5 R7)at1Z E T FR0R1R5 #at1Z E TR0R1(2) (* a,t1,t2)t2 #Z ER0 #t2ZOk!6.4.1 递归子程序法四元式翻译器构造主程序子程序E子程序T子程序F第30页，共41页，2022年，5月20日，5点49分，星期日6.4.2 LL(1)法四元式翻译器构造 2. LL(1)分析器的扩展 1. 设置语义栈：SEMm四元式区：QTq语

28、法栈：SYNn ;(2) 当动作符号位于栈顶时，执行之；(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 ) 第31页，共41页，2022年，5月20日，5点49分，星期日4. LL(1)分析表*/ ()TTFEE#-+i【例6.13】a+b*c# 四元式 LL(1)法翻译过程:SEMm QTq 操作w x SYNn#EaEPUSHR#ETTaPUSHRTF#EFaPUSHR

29、#ETPUSH(a)aaa#ETPUSH(a)+NEXT(w)a#ETT+aPUSHR#EE+PUSHRa#EGEQ(+)T+aNEXT(w)b#EGEQ(+)TTPUSHRa#EGEQ(+)TFFbPUSHRa接下页6.4.2 LL(1)法四元式翻译器构造第32页，共41页，2022年，5月20日，5点49分，星期日【例6.9】a+b*c# 四元式 LL(1)法翻译过程(续1):6.4.2 LL(1)法四元式翻译器构造 SEMm QTq 操作wx SYNn#EGEQ(+)TPUSH(b)bbbNEXT(w)a#EGEQ(+)TPUSH(b)*ab#EGEQ(+)T*TabPUSHR#EGEQ

30、(+)TGEQ(*)F*ab*NEXT(w)c#EGEQ(+)TGEQ(*)FabFPUSHR#EGEQ(+)TGEQ(*)cabPUSH(c) ccNEXT(w)#ab#EGEQ(+)TGEQ(*)PUSH(c)c#EGEQ(+)TGEQ(*)#abc(1) (*b,c,t1)# EGEQ(+) T#aT# EGEQ(+)#a t1(2) (+a,t1,t2)# Et2#E#t2ok接上页t1PUSHRPUSHR第33页，共41页，2022年，5月20日，5点49分，星期日6.4.3 LR()法四元式翻译器构造1. 设置2. 属性翻译文法设计语义栈：SEMm四元式区：QTq语法栈：SYNn

31、;Z-E 0E-E + TGEQ(+) | T T-T * FGEQ(*) | F F-iPUSH(i) | ( E ) 3. LR() 分析器的扩展 LR()分析表中的 r(i) 执行下述两种操作： 首先执行动作符号(翻译函数)； 然后执行归约操作(按产生式 i 归约)。动作符号一定在最右侧第34页，共41页，2022年，5月20日，5点49分，星期日 算术表达式句柄识别器的构造I1:Z E E E + TI4:E T T T * FI7:T F I9:F ( E) E E + T E T T T * F T F F (E) F iI8:F i I0:Z E E E + T E T T T

32、* F T F F (E) F iI5:T T * F F (E) F iI2:E E + T T T * F T F F (E) F iI10:F (E ) E E + TI11:F (E) I3:E E + T T T * F I6:T T*F ETiF(+*(ETFiTF(iF(i)+*第35页，共41页，2022年，5月20日，5点49分，星期日r(5)(9r(6）r(4）r(3）(9(9(9(r(5)11r(6）r(4）r(3）r(2）r(1）)r(5）r(6）r(4）r(3）r(2）r(1）ok#E10E1ET4T3T4TF*+iF7i80+21F7i823*5r(2）4F6i85r(3）r(3）r(3）6r(4）r(4）r(4）7r(5)r(5)r(5)11+210F7i89r(6）r(6）r(6）8r(1）*5Z-E 0E-E + TGEQ(+) | T T-T * FGEQ(*) | F F-i PUSH(i) | ( E ) r(i) 含义：(1) 执行动作符号；(2) 执行归约操作。SLR(1)分析表6.4.3 LR()法四元式翻译器构造第36页，共41页，2022年，5月20日，5点49分，星期日【例6.10】a*b+c# 四元式 S