1、2022-4-25北京电子科技学院12022-4-25北京电子科技学院2 语义分析的工作有:类型检查、控制流检查,一致性检查,作用域分析等。 可以在语法分析的基础上加上语义规则,直接产生机器语言或汇编语言形式的目标代码。但这种编译方式不利于优化和移植,目标代码质量不高。 现在的编译系统,一般都是将源程序先翻译为某种中间代码,然后再将中间代码翻译成目标代码。这样使得编译程序在逻辑结构上更简单,同时也为代码优化和移植创造了条件。第七章 语义分析及中间代码生成2022-4-25北京电子科技学院3 本章各种语句的代码生成将结合本章各种语句的代码生成将结合SPL代码生成的方式对照分析代码生成的方式对照分
2、析,开开展课堂讨论。展课堂讨论。2022-4-25北京电子科技学院4中间代码中间代码(Intermediate code)(Intermediate code)是源程是源程序的一种内部表示,不依赖目标机的结构,序的一种内部表示,不依赖目标机的结构,易于生成。易于生成。中间代码的几种形式:中间代码的几种形式:逆波兰式逆波兰式四元式四元式三元式三元式间接三元式间接三元式树树图。图。7.17.1中间代码中间代码2022-4-25北京电子科技学院5逆波兰式:逆波兰式:A B C D - * + E C D -N / +四元式:四元式: (1) ( - C D T1)(2) ( * B T1 T2)(3
3、) ( + A T2 T3)(4) ( - C D T4)(5) ( T4 N T5)(6) ( / E T5 T6)(7) ( + T3 T6 T7)例例 : A + B * ( C - D ) + E / ( C - D ) N 四元式是一个带有四个域的记四元式是一个带有四个域的记录结构,这四个域分别称为录结构,这四个域分别称为: op、arg1, arg2 及及result. op代表运算符。代表运算符。 语句语句x:y op z 可表示为可表示为(op,y,z,x)。= (op,y,z,T1) (:=,T1, ,x) 一目运算符的语句如:一目运算符的语句如:x:= -y 或者或者x:=
4、y 表示为表示为: (,y, ,x) 或或(:=,y, ,x) 条件和无条件转移语句将目标条件和无条件转移语句将目标标号置于标号置于result域中。域中。 (j, , ,标号标号)或或(jrop, , ,标号标号)。 2022-4-25北京电子科技学院6例例 : A + B * ( C - D ) + E / ( C - D ) N三元式:三元式:(1) ( - C D )(2) ( * B (1) )(3) ( + A (2) )(4) ( - C D )(5) ( (4) N )(6) ( / E (5) )(7) ( + (3) (6) ) 为了避免把临时变量填为了避免把临时变量填入到
5、符号表,可以通过入到符号表,可以通过计算这个临时变量值的计算这个临时变量值的语句的位置来引用这个语句的位置来引用这个临时变量。临时变量。 这样表示三地址代码的这样表示三地址代码的记录只需三个域:记录只需三个域:op 、argl和和 arg2 2022-4-25北京电子科技学院7间接三元式:间接三元式:间接三元式序列:间接三元式序列: 间接码表:间接码表:(1)(1)(2)(2)(3)(3)(1)(1)(4)(4)(5)(5)(6)(6)(1) ( - C D ) (2) ( * B (1) ) (3) ( + A (2) ) (4) ( (1) N ) (5) ( / E (4) ) (6)
6、( + (3) (5 ) ) 例例 : A + B * ( C - D ) + E / ( C - D ) N 为了便于代码优化处理,为了便于代码优化处理,有时不直接使用三元式有时不直接使用三元式表,而是另设一张指示表,而是另设一张指示器(称为间接码表),器(称为间接码表),它将按运算的先后顺序它将按运算的先后顺序列出有关三元式在三元列出有关三元式在三元表中的位置。表中的位置。 换句话说就是,用一张换句话说就是,用一张间接码表辅以三元式表间接码表辅以三元式表的办法来表示中间代码。的办法来表示中间代码。这种表示法称为间接三这种表示法称为间接三元式。元式。2022-4-25北京电子科技学院8四元式
7、与三元式和间接三元式作一些比较四元式与三元式和间接三元式作一些比较 四元式之间的联系是通过临时变量实现的。四元式之间的联系是通过临时变量实现的。这一点和三元式不同。要更动一张三元表是这一点和三元式不同。要更动一张三元表是很困难的,它意味着必须改变其中一系列指很困难的,它意味着必须改变其中一系列指示器的值。但要更动四元式表是很容易的,示器的值。但要更动四元式表是很容易的,因为调整四元式之间的相对位置并不意味着因为调整四元式之间的相对位置并不意味着必须改变其中一系列指示器的值。因此,当必须改变其中一系列指示器的值。因此,当需要对中间代码进行优化处理时,四元式比需要对中间代码进行优化处理时,四元式比
8、三元式要方便得多。三元式要方便得多。 对优化这一点而言,四元式和间接三元式同对优化这一点而言,四元式和间接三元式同样方便。样方便。2022-4-25北京电子科技学院9例例 : A + B * ( C - D ) + E / ( C - D ) N树树:+*AB-CD/EN-CD2022-4-25北京电子科技学院10DAG图表示图表示:例例 : A + B * ( C - D ) + E / ( C - D ) N+*AB-CD/EN2022-4-25北京电子科技学院11(1)语句:可执行语句:生成四元式不可执行语句(说明语句):填写符号表(2)翻译的要点:确定语句的目标代码结构确定中间代码形式
9、添加语义动作(3)数据结构:符号表、四元式表、临时变量表7.27.2语句的翻译语句的翻译2022-4-25北京电子科技学院121.1.简单算术表达式和赋值语句的四元式翻译简单算术表达式和赋值语句的四元式翻译文法文法:Sid:=E EE1+E2 |E1 *E2 |-E1|(E1)|id四元式形式四元式形式:(op,arg1,arg2,result) result:=arg1 op arg2语义属性语义属性:id.name表示表示id所代表的名字本身所代表的名字本身 E.place表示存放表示存放E值的变量名在符值的变量名在符号表的入口或整数码号表的入口或整数码(若此变量是一个临时变若此变量是一个
10、临时变量量);2022-4-25北京电子科技学院13函数:函数:newtemp,每次调用它都返回一个代表每次调用它都返回一个代表新临时变量名的整数码新临时变量名的整数码,临时变量名按产生的临时变量名按产生的顺序可想象为顺序可想象为T1,T2 Tn 。过程:过程:lookup(id.name)检查变量名是否在符检查变量名是否在符号表中。在,则返回地址;否,则返回号表中。在,则返回地址;否,则返回nil。 emit (op, arg1, arg2, result)将四元式放将四元式放入中间代码序列中。入中间代码序列中。2022-4-25北京电子科技学院14例:例:(1)S id:=E p:=loo
11、kup(id.name); if nil then emit(:=, E.place, , p) else error (2) EE1+E2 E.place:= newtemp; emit(+, E1.place, E2.place ,E.place) (3) EE1*E2 E.place:= newtemp; emit(*, E1.place, E2.place ,E.place) (4) E - E1 E.place:=newtemp; emit(,E1.PLACE, ,E.PLACE) (5) E( E1) E.place:= E1.place (6) Eid E.place:=newt
12、emp; P:=lookup(id.name); if P nil then E.place:=P else error2022-4-25北京电子科技学院15输入输入 栈栈 PLACE 四元式四元式A:=-B*(C*D):=-B*(C+D) id A-B*(C+D) id:= A_B*(C+D) id:=- A_ _*(C+D) id:=-id A_ _B*(C+D) id:=-E A_ _B (,B,_,T1)*(C+D) id:=E A_T1(C+D) id:=E* A_T1_C+D) id:=E*( A_T1_ _+D) id:=E*(id A_T1_ _C+D) id:=E*(E A_
13、T1_ _CD) id:=E*(E+ A_T1_ _C_) id:=E*(E+id A_T1_ _C_D) id:=E*(E+E A_T1_ _C _D ) id:=E*(E A_T1_ _ T2 (+,C,D,T2) id:=E*(E) A_T1_ _T2 _ id:=E*E A_T1_ T2 (* ,T1,T2,T3) id:=E A_T3 (:=,T3,_,A) S例例:自自下下而而上上分分析析时时赋赋值值句句的的翻翻译译步步骤骤2022-4-25北京电子科技学院16布尔表达式的基本作用:布尔表达式的基本作用:计算逻辑值计算逻辑值用作控制流语句用作控制流语句if-then、if-then
14、-else、while-do等之中的条件表达式等之中的条件表达式布尔表达式文法布尔表达式文法:EE and E|E or E | not E|(E)| i | i rop i rop为关系运算符为关系运算符()2.2.布尔表达式的翻译布尔表达式的翻译2022-4-25北京电子科技学院17布尔表达式的翻译:布尔表达式的翻译:第一种翻译法第一种翻译法,如同算术表达式一样如同算术表达式一样,一步不差,一步不差地从表达式各部分的值计算出整个表达式的值地从表达式各部分的值计算出整个表达式的值;例:例: 1 or (not 0 and 0)or 0 =1 or (1 and 0) or 0 =1 or 0
15、 or 0 =1 or 0 =1例例:A or B and C=D被翻译为如下四元式被翻译为如下四元式 OP ARG1 ARG2 RESULT = C D T1 and B T1 T2 or A T2 T32022-4-25北京电子科技学院18第二种翻译法第二种翻译法:采取某种优化措施。采取某种优化措施。例如,假定要计算例如,假定要计算A or B,如果计算出,如果计算出A的值的值为为1,B的值就无需再计算了。同理,在计算的值就无需再计算了。同理,在计算A and B时,若发现时,若发现A的值为的值为0,则,则B的值也无需的值也无需计算。计算。可以用可以用if-then-else结构来翻译布尔
16、表达式:结构来翻译布尔表达式:把把 A or B 解释成:解释成:if A then true else B把把 A and B 解释成:解释成:if A then B else false把把 not A 解释成:解释成:if A then false else true2022-4-25北京电子科技学院19布尔表达式的四元式翻译:布尔表达式的四元式翻译:EE1 or E2 E.place:=newtemp; emit(or, E1.place , E2.place ,E.place )EE1 and E2 E.place:=newtemp; emit(and, E1.place , E2.
17、place ,E.place )Enot E1 E.place:=newtemp; emit(not, E1.place , _ ,E.place )E(E1) E.place:= E1.place2022-4-25北京电子科技学院20Eid1 rop id2 E.place:=newtemp; emit(jrop, id1.place ,id2.place, nextstat+3 ); emit(:=, 0 , _,E.place); emit(j, _ ,_ , nextstat+2); emit(:=, 1 , _,E.place)Etrue E.place:=newtemp; emit
18、(:= , 1,_ ,E.place)Efalse E.place:=newtemp; emit(:= ,0,_ ,E.place)nextsta为为四元式序四元式序列号列号,每生每生成一条四成一条四元元式式,nextsta便加便加1。2022-4-25北京电子科技学院21例:例:ab or cd and efab or cd and ef的四元式:的四元式:100100: (j,a,b,103)(j,a,b,103)101: (:=,0,_,T101: (:=,0,_,T1 1) )102: (j ,_,_,104)102: (j ,_,_,104)103: (:=,1,_,T103: (:
19、=,1,_,T1 1) )104: (j,c,d,107)104: (j,c,d,107)105: (:=,0,_,T105: (:=,0,_,T2 2) )106: (j ,_,_,108)106: (j ,_,_,108)107107: (:=,1,_,T(:=,1,_,T2 2) )108: (j,e,f,111)108: (j,e,f,111)109: (:=,0,_,T109: (:=,0,_,T3 3) )110: (j ,_,_,112)110: (j ,_,_,112)111: (:=,1,_,T111: (:=,1,_,T3 3) )112: (and,T112: (and,
20、T2 2,T,T3 3 ,T,T4 4) )113: (or,T113: (or,T1 1,T,T4 4 ,T,T5 5) )2022-4-25北京电子科技学院22控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句控制语句 Sif E then S1 else S2条件表达式条件表达式E的的作用仅在于控制对作用仅在于控制对S1和和S2的选择,只要能的选择,只要能完成这一使命,完成这一使命,E的的值就无须最终保留在值就无须最终保留在某个临时单元之中。某个临时单元之中。因此,作为转移条件因此,作为转移条件的布尔式的布尔式E,赋予它,赋予它两种两种“出口出口”,一种,一种是是“真真”出口,
21、转向出口,转向S1;一是一是“假假”出口,出口,转向转向S2.E.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.falseif-then-else的代码结构2022-4-25北京电子科技学院23对于转移条件的布尔式对于转移条件的布尔式 E,翻译成仅含下述三种形翻译成仅含下述三种形式的四元式序列:式的四元式序列:v(jnz,a,_,p) 表示表示 if a goto p /(p=E.true)v(jrop,a,b,p) 表示表示if a rop b goto p v(j,_,_,p) 表示表示goto p /无
22、条件转向四元式无条件转向四元式p2022-4-25北京电子科技学院24例如:可把语句例如:可把语句 if A or BD then S1 else S2 翻译成如下的一串四元式:翻译成如下的一串四元式:(1) (jnz,A,_,5) A的真出口为的真出口为5(2) (j ,_,_,3) A的假出口为的假出口为3(3) (j ,B,D,5) BD的真出口为的真出口为5(4) (j,_,_,p+1) BD的假出口为的假出口为(p+1)(5)(关于(关于S1的四元式序列)的四元式序列) (p) (j ,_,_,q) 跳过跳过S2的代码段的代码段(p+1)(关于(关于S2的四元式序列)的四元式序列)
23、(q)2022-4-25北京电子科技学院25对于对于E=E1 or E2的形式:的形式:如果如果E1为真为真,则则E为真。即为真。即 E1的真出口就是的真出口就是E的的真出口真出口;如果如果E1为假,为假,必须计算必须计算E2。E1的假出的假出口是口是E2的第一个四元式序号,的第一个四元式序号,这时这时E2的真假出的真假出口就是口就是E的真假出口。的真假出口。例:例:ab or cf(1) if ab goto E.true(2) goto 3(3) if cf goto E.true(6) goto E.false E.true, E.false是是E的的继承属性继承属性, E.true是是
24、E为真时控制流转向的为真时控制流转向的标号标号; E.false是是E为假为假时控制流转向的标号时控制流转向的标号,函数函数newlabel返回新返回新的标号,将放在某个的标号,将放在某个四元式序列号前四元式序列号前.2022-4-25北京电子科技学院26产生式产生式语义语义规则EE1 or E2E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false E.code:=E1.code| gen(E1.false:)|E2.code控制流语句中的布尔表达式的翻译的控制流语句中的布尔表达式的翻译的基本思想基本思想
25、: 假定假定E 形如形如ad,则将生成如下的则将生成如下的E的代码:的代码: if ab goto E.true /(j, a, b, E.true) goto E.false /(j, _,_,E.false) 语语法法制制导导定定义义2022-4-25北京电子科技学院27产生式产生式语义语义规则EE1 and E2E1.true:= newlabel; E1.false:= E.false; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code gen(E1.true:) E2.code(接上页)(接上页)Enot E1 E1.true:=
26、 E.false; E1.false:= E.true; E.code:=E1.code 2022-4-25北京电子科技学院28产生式产生式语义规则Eid1 rop id2E.code:=gen(if id1.place rop.op id2.place goto E.true)| gen(goto E.false)Etrue E.code:=gen(goto E.true) Efalse E.code:=gen(goto E.false) E(E1) E1.true:= E.true; E1.false:= E.false; E.code:=E1.code (接上页)(接上页)函数函数gen
27、生成一个四元式生成一个四元式, E.code是是E的四元式序列的四元式序列。2022-4-25北京电子科技学院29表达式表达式 ab or cd and ef的中间代码翻译:的中间代码翻译:两遍扫描:1.构造语法树;2.按深度优先遍历翻译。假定整个条件表达式的真、假出口为假定整个条件表达式的真、假出口为LT和和LF,则:则:EEorEEandEabcdefL2: (5)if ef goto LT (6)goto LF .true=LT.false=LFLTL1LTLFL2LFLTLF(1)if ab goto LT(2)goto L1L1: (3)if cd goto L2 (4)goto L
28、F 问题:问题:LT、LF何时何时才能知道?才能知道?2022-4-25北京电子科技学院30上述四元式上述四元式(1)和和(5)(真出口真出口)、(4)和和(6) (假出口假出口)的转移地址并不能在四元式产生的同时得知。的转移地址并不能在四元式产生的同时得知。例如例如(1)和和(5)的转移地址是在整个布尔表达式产的转移地址是在整个布尔表达式产生完毕才能得知。因此要回填这个地址。生完毕才能得知。因此要回填这个地址。为了为了记录回填地址的四元式,常常采用记录回填地址的四元式,常常采用“拉链拉链”的的办法,把需要回填办法,把需要回填E.true的四元式拉成一条链,的四元式拉成一条链,把需要回填把需要
29、回填E.false的四元式拉成一条链的四元式拉成一条链,分别称分别称作作“真真”链和链和“假假”链。链。(p) (,0)(q)(,p)(r)(,q) 地址地址(r)是是E.true链头链头2022-4-25北京电子科技学院31例:例:(10)goto E.true(20)goto E.true(30)goto E.true拉链成:拉链成:(10)goto 0(20)goto (10)(30)goto (20)(30)是链头,是链头, (10)为链尾。为链尾。0是链尾标志。是链尾标志。又例:又例:goto 语句(前向转移,后向转移)语句(前向转移,后向转移)一遍扫描翻译一遍扫描翻译: 先产生暂时
30、没有填写目标标号的转移指令。先产生暂时没有填写目标标号的转移指令。 对于每一条这样的指令作适当的记录,对于每一条这样的指令作适当的记录, 一旦目标标号被确定下来,再将它一旦目标标号被确定下来,再将它“回填回填”到相应的指令中。到相应的指令中。2022-4-25北京电子科技学院32标号和转移语句: . goto L; . goto L; . goto L; .L: .拉链拉链返填返填goto nil.Lgoto .goto L: .2022-4-25北京电子科技学院33与拉链返填技术相关与拉链返填技术相关变量和函数:变量和函数:nextquad指示器指示器:指向下一个将要形成但尚未指向下一个将要
31、形成但尚未形成的四元式的地址形成的四元式的地址. nextquad初值初值为为1,每执每执行一次行一次emit之后之后, nextquad将将自动增加自动增加1.merge(p1,p2):/函数过程函数过程,把把p1,p2为链首的两条链为链首的两条链合并为一合并为一,返回链首返回链首p2(p1);POINTER PROCEDURE merge(p1,p2);IF p2=0 THEN merge:=p1 ELSEBEGIN p:=p2; WHILE 四元式四元式p的第四区段的内容不为的第四区段的内容不为0 DO P:=四元式四元式p的第四区段的内容的第四区段的内容; /找找p2尾把尾把p1填进四
32、元式填进四元式p的第四区段的第四区段; merge:=p2END2022-4-25北京电子科技学院34makelist(i):创建一个仅包含创建一个仅包含i的新表,的新表,i是四元是四元式数组的一个索引式数组的一个索引(下标下标),或说,或说i是四元式代码序是四元式代码序列的一个标号。列的一个标号。 backpatch(p,t):/过程过程”回填回填”,把把p所链接的每个四元式的第四区段都填为所链接的每个四元式的第四区段都填为t;PROCEDURE backpatch(p,t);BEGIN Q:=p; WHILE Q0 DO BEGIN q:=四元式四元式Q的第四区段的内容的第四区段的内容;
33、把把t填进四元式填进四元式Q的第四区段的第四区段; Q:=q END OF WHILEEND2022-4-25北京电子科技学院35自下而上分析中自下而上分析中使用回填翻译布尔表达式使用回填翻译布尔表达式 布尔表达式文法:布尔表达式文法: (1)EE1 or M E2 (2) |E1 and M E2 (3) |not E1 (4) |(E1) (5) |id1 rop id2 (6) |true (7) |false (8)M插入非终结符号插入非终结符号M是为了引入一个语义动作,是为了引入一个语义动作,以便在适当的时候获得即将产生的下一个四元以便在适当的时候获得即将产生的下一个四元式的序号。式
34、的序号。2022-4-25北京电子科技学院36使用一遍扫描的布尔表达式的翻译模式:使用一遍扫描的布尔表达式的翻译模式:/ M.quad记录记录E2代码序列的第一条四元式序号。代码序列的第一条四元式序号。 EE1 or M E2 backpatch(E1.falselist,M.quad); E.truelist:=merge(E1.truelist,E2.truelist); E.falselist:=E2.falselist EE1 and M E2 backpatch(E1.truelist,M.quad); E.truelist:=E2.truelist; E.falselist:=me
35、rge(E1.falselist,E2.falselist);2022-4-25北京电子科技学院37Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist E ( E ) E.truelist:= E1.truelist; E.falselist:=E1.falselistE id1 rop id2 E.truelist:= makelist(nextquad); E.falselist:= makelist(nextquad+1); emit(j rop.op,id1.place ,id2.place,0 ); emit(j, _
36、,_, 0 ); 2022-4-25北京电子科技学院38E true E.truelist:= makelist(nextquad); emit(j,_,_,0); E false E.falselist:= makelist(nextquad); emit(j,_,_,0); M M.quad:=nextquad / M.quad记录记录E2代码序列的第一条四元式序号。代码序列的第一条四元式序号。 2022-4-25北京电子科技学院39表达式表达式ab or cd and ef加了注释的分析树如图所示加了注释的分析树如图所示:E.t=100,104E.f=103,105E.t=100E.f=
37、101E.t=104E.f=103,105or M.q=102abE.t=102E.f=103E.t=104E.f=105andM.q=104cdef ( j,a,b,0 )(101) ( j ,_,_,0 )(102) ( j,c,d,0 )(103) ( j ,_,_,0 )(104) ( j,e,f,0 )(105) (106) ( j ,_,_,0 )(100) 1041022022-4-25北京电子科技学院40依次分析依次分析,得到如下四元式:得到如下四元式: 100 : if ab goto- 101 : goto- 102 :if cd goto- 103 : goto- 104
38、 : if ef goto- 105 : goto- 经过回填得到:经过回填得到: 100 : if ab goto 101 : goto l02 102 : if cd goio l04 103 : goto 104 : if ef goto 105 : goto 根据上述语义动作的描述,当整个表达式所相应的根据上述语义动作的描述,当整个表达式所相应的四元式都产生后,作为整个表达式的真、假出口仍没有四元式都产生后,作为整个表达式的真、假出口仍没有填上,他们分别由填上,他们分别由E.true和和E.false记录。记录。一旦整个布尔一旦整个布尔式的真假出口确定后,则可沿式的真假出口确定后,则可
39、沿“真真”,“假假”链为相应链为相应的四元式填上。例如的四元式填上。例如if-then-else语句,那么当分别扫描语句,那么当分别扫描到到then 和和else之后,便可回填真假出口。之后,便可回填真假出口。2022-4-25北京电子科技学院413.3.控制语句的翻译控制语句的翻译控制流语句文法:控制流语句文法: Sif E then S1 | if E then S1 else S2 | while E do S1 E.codeS1.codeE.true:.E.false:(a) if-thento E.trueto E.false代码结构代码结构:2022-4-25北京电子科技学院42E
40、.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.trueto E.false(b)if-then-elseE.codeS1.codeE.true:E.false:goto S.begin.S.begin:to E.falseto E.true(c )while-do2022-4-25北京电子科技学院43语法制导定义:产生式语义规则Sif E then S1E.true:=newlabel; E.false:=S.next; S1.next:=S.next S.code:=E.code| gen(E.true:)|S1.code
41、2022-4-25北京电子科技学院44产生式语义规则Sif E then S1else S2E.true:=newlabel; E.false:=newlabel; S1.next:=S.next; S2.next:=S.next; S.code:=E.code| gen(E.true:)|S1.code gen(gotoS.next)| gen(E.false:)|S2.code(接上页)2022-4-25北京电子科技学院45产生式语义规则Swhile E do S1S.begin:=newlabel; E.true:=newlabel; E.false:= S.next; S1.next:
42、=S.begin; S.code:=gen(S.begin: E.code gen(E.true:) S1.code gen(gotoS.begin)(接上页)2022-4-25北京电子科技学院46例:考虑如下语句 while ab do if cd then x:= yz else x:y-z 根据前面所述,生成代码如右: L1 : if ab goto L2 goto Lnext L2 : if cd goto L3 goto L4 L3 : T1:= yz x:T1 goto L1 L4 : T2:=y-z x:T2 goto L1 Lnext: 2022-4-25北京电子科技学院47文
43、法:(1)Sif E then S (2) | if E then S else S (3) | while E do S (4) | begin L end (5) | A (6)LL;S (7) |S S表示语句L表示语句表A为赋值语句E为一个布尔表达式常用语句的翻译常用语句的翻译2022-4-25北京电子科技学院48控制流语句的翻译模式:控制流语句的翻译模式:1.Sif E then M1 S1 N else M2 S2 backpatch( E.truelist,M1.quad); backpatch( E.falselist, M2.quad); S.nextlist:=merge(
44、S1.nextlist,N.nextlist, S2.nextlist)2.N N.nextlist:=makelist(nextquad); emit(j, _,_, 0 ) /当真语句段执行完后当真语句段执行完后,跳出跳出3.M M.quad:=nextquad 4.Sif E then M S1 backpatch( E.truelist,M.quad); S.nextlist:=merge(E.falselist,S1.nextlist)2022-4-25北京电子科技学院495.Swhile M1 E do M2 S1/M1处生成标号处生成标号S.begin,反填反填S1.nextli
45、st, M2处反填处反填E.truelist backpatch(S1.nextlist,M1.quad); backpatch(E.truelist,M2.quad); S.nextlist:=E.falselist; emit(j,_,_,M1.quad) 6.S begin L end S.nextlist:=L.nextlist7.S A S.nextlist:=makelist( )/初始化为空表初始化为空表8.LL1;M S backpatch(L1.nextlist,M.quad); L.nextlist:=S.nextlist 9.LS L.nextlist:=S.nextli
46、st 2022-4-25北京电子科技学院50翻译模式结构图:翻译模式结构图:Sif E then M1 S1 N else M2 S2to E.trueE.codeS1.codeE.true:S2.codeE.false:goto S.next.S.next:to E.falseM1处反填处反填E.truelistM2处反填处反填E.falselistN处处生成生成(j,_,_,S.next)先记录要回填的转移指令地址,在适当的先记录要回填的转移指令地址,在适当的时候进行回填,以便赋值和布尔表达式的求值时候进行回填,以便赋值和布尔表达式的求值得到合适的连接,以完成程序的控制流程得到合适的连接,
47、以完成程序的控制流程。2022-4-25北京电子科技学院51例例:用自底向上的分析法生成四元式代码用自底向上的分析法生成四元式代码,其中其中A1, A2和和A3 均表示赋值语句均表示赋值语句(假设各含假设各含10个四元式个四元式)。 if ab or cd and ef then A1 else A2; while ab do A3; 100: (j , a, b , 106 )101: (j , _, _, l02 )102: (j , c, d , 104 )103: (j , _, _, l17 )104: (j , e, f , 106 ) 105: (j , _, _, l17 )1
48、06 反填E.truelist (关于A1的四元式 )116: (j , _, _, l27 )117: 反填E.falselist (关于A2的四元式 ) 127: 反填S.nextlist (j , a, b , 129 )128: (j , _, _, l40 )129: 反填E.truelist (关于A3的四元式 ) 139: (j , _, _, l27 ) 140: 反填E.falselist2022-4-25北京电子科技学院52例:语句例:语句:while (AB) do if (CD) then X:=Y+Z 被翻译成如下一串四元式:被翻译成如下一串四元式:100 (j,A,B,102)101 (j ,_ ,_,107)102 (j ,C,D,104)103 (j ,_ ,_,100)104 (+ ,Y,Z, T )105 (:= ,T,_, X )106 (j ,_,_, 100)1072022-4-25北京电子科技学院53本章重点 了解各种中间代码形式,掌握四元式;了解各种中间代码形式,掌握四元式; 掌握拉链返填技术;掌握拉链返填技术; 掌握控制语句的四元式生成。掌握控制语句的四元式生成。 了解说明语句的处理和类型检查了解说明语句的处理和类型检查2022-4-25北京电子科技学院54P217#3,6,7