程序设计语言编译原理第三版第7章-课件.ppt

1、1第七章语义分析和中间代码产生第七章语义分析和中间代码产生优化器优化器语法分析器语法分析器静态检查器静态检查器中间代码产生器中间代码产生器中间代码中间代码 一般情况下，在词法分析程序和语法分析程序对源程序的语法结一般情况下，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，构进行分析之后，要么要么，由语法分析程序直接调用相应的语义子程序进行语义处理；，由语法分析程序直接调用相应的语义子程序进行语义处理；要么要么，首先生成语法树或该结构的某种表示，再进行语义处理。，首先生成语法树或该结构的某种表示，再进行语义处理。2语义处理分两步：语义处理分两步：1.1.静态语义分析，即验证语法结构合

2、法的程序是否真正有意义。静态语义分析，即验证语法结构合法的程序是否真正有意义。2.2.若静态语义正确，语义处理则要执行真正的翻译。若静态语义正确，语义处理则要执行真正的翻译。即即要么要么生成程序的一种中间表示形式（中间代码），生成程序的一种中间表示形式（中间代码），要么要么生成实际的目标代码。生成实际的目标代码。静态语义检查包括：静态语义检查包括：（1 1）类型检查；）类型检查；（2 2）控制流检查；）控制流检查；（3 3）一致性检查；）一致性检查；（4 4）相关名字检查。）相关名字检查。第七章语义分析和中间代码产生第七章语义分析和中间代码产生3中间代码：中间代码：即中间语言，独立于机器的，复

3、杂性介于源即中间语言，独立于机器的，复杂性介于源语言和机器语言之间的一种表示形式。语言和机器语言之间的一种表示形式。采用中间语言的好处：采用中间语言的好处：第七章语义分析和中间代码产生第七章语义分析和中间代码产生（1 1）便于进行与机器无关的代码优化工作；）便于进行与机器无关的代码优化工作；（2 2）使编译程序改变目标机更容易；）使编译程序改变目标机更容易；（3 3）使编译程序的结构在逻辑上更为简单明确。）使编译程序的结构在逻辑上更为简单明确。4 7.1 7.1 中间语言中间语言 7.2 7.2 说明语句说明语句 7.3 7.3 赋值语句的翻译赋值语句的翻译 7.4 7.4 布尔表达式的翻译布

4、尔表达式的翻译 7.5 7.5 控制语句的翻译控制语句的翻译 7.6 7.6 过程调用的处理（略）过程调用的处理（略）7.7 7.7 类型检查类型检查 （略）（略）第七章语义分析和中间代码产生第七章语义分析和中间代码产生57.7.中间语言中间语言中间语言形式：中间语言形式：后缀式三地址代码 图表示法三元式三元式 四元式四元式 间接三元式间接三元式DAGDAG抽象语法树抽象语法树6一、后缀式一、后缀式逆波兰式：逆波兰式：规则规则：7.7.中间语言中间语言(1)E(1)E常量变量：常量变量：后缀式为后缀式为E E本身本身(2)E(2)EE E1 1 op E op E2 2：E E1 1 E E2

5、 2 op(3)E(3)E(E(E1 1)：(E(E1 1)(4)E(4)Eop Eop E1 1：E E1 1 op op77.7.中间语言中间语言例子：例子：a a*(b+c)(b+c)(a+b)(a+b)*(c+d)(c+d)abc+abc+*x+yza0(8+z)3x+yza0(8+z)3ab+cd+ab+cd+*xy+za08z+3xy+za08z+38二、图表示法二、图表示法1.DAG(1.DAG(无循环有向图无循环有向图)与抽象语法树对比与抽象语法树对比 相同点相同点:对表达式中的每个子表达式，它们都有一个结对表达式中的每个子表达式，它们都有一个结 点，一个内部结点代表一个操作符

6、，它的孩子点，一个内部结点代表一个操作符，它的孩子 代表操作数；代表操作数；不同点不同点:在一个在一个DAGDAG中代表公共子表达式的结点具有多个中代表公共子表达式的结点具有多个 父结点，而在一棵抽象语法树中公共子表达式父结点，而在一棵抽象语法树中公共子表达式 被表示为重复的子树。被表示为重复的子树。7.7.中间语言中间语言9例子：例子：如图所示，为如图所示，为a+aa+a*(b-c)+(b-c)(b-c)+(b-c)*d d的的DAGDAG +*d a-b c7.7.中间语言中间语言102.2.抽象语法树抽象语法树例子：例子：(1)a:=b*-c+b*-c的图表示法的图表示法assign a

7、+*b uminus b uminus c c语法树语法树assign a+*b uminus cDAGDAG7.7.中间语言中间语言11(2)a:=b*-c+b*-c 的抽象语法树的两种表示法的抽象语法树的两种表示法assignida +*idbuminusidc *uminusidcidbidbIdcuminus1*02idbidcuminus5*46+37idaassign980123456789107.7.中间语言中间语言12三、三地址代码三、三地址代码1.1.三地址代码三地址代码:下面一般形式的语句构成的序列下面一般形式的语句构成的序列:x:=y op zx:=y op zT T1

8、1:=y:=y*z,Tz,T2 2:=x+T:=x+T1 1称为三地址代码的原因称为三地址代码的原因:每条语句通常包含三个地址每条语句通常包含三个地址,两个用来表示操作数两个用来表示操作数,一一个用来存放结果。个用来存放结果。7.7.中间语言中间语言具体实现具体实现:用记录表示用记录表示,其中包含其中包含运算符运算符和和操作数操作数的域。的域。x,y,z:x,y,z:名字名字,常数常数,编译时产生的临时变量编译时产生的临时变量 op:op:运算符号运算符号(如定点运算符如定点运算符,浮点运算符浮点运算符,逻辑运算符等逻辑运算符等)132.2.四元式：四元式：带有四个域的记录结构带有四个域的记录

9、结构 内容均是指针内容均是指针,指向有关名字的符号表入口指向有关名字的符号表入口7.7.中间语言中间语言(op(op，arg1arg1，arg2arg2，result)result)147.7.中间语言中间语言例子例子:三地址语句三地址语句a:=ba:=b*-c+b-c+b*-c-c的四元式表示的四元式表示 四元式表示四元式表示Oparg1arg2result(0)(1)(2)(3)(4)(5)uminus*uminus*+:=cbcbT1T2T1T3T4T1T2T3T4T5a153.3.三元式：三元式：为了避免把临时变量填入符号表为了避免把临时变量填入符号表,可通过计算该临可通过计算该临时变

10、量值的语句的位置来引用该临时变量。时变量值的语句的位置来引用该临时变量。或是指向符号表的指针或是指向符号表的指针对程序中的名字而言对程序中的名字而言或是指向三元式表的指针或是指向三元式表的指针对临时变量而言对临时变量而言7.7.中间语言中间语言（op，arg1，arg2）16oparg1arg2(0)(1)(2)(3)(4)(5)uminus*umins*+assigncbcb(1)a(0)(2)(3)(4)7.7.中间语言中间语言例子例子:三地址语句三地址语句a:=b*-c+b*-c的三元式表示的三元式表示 174.4.间接三元式：间接三元式：便于代码优化处理便于代码优化处理方法：方法：间接

11、码表间接码表+三元式表三元式表按运算的先后顺序列出有关三元式在三元表中的位置按运算的先后顺序列出有关三元式在三元表中的位置oparg1arg2(1)(2)(3)(4)(5)+*:=:=A(1)XDYBC(2)(1)(1)例例:语句语句X:=(A+B)X:=(A+B)*C;Y:=D(A+B)C;Y:=D(A+B)的间接三元式表示如下所示的间接三元式表示如下所示:间接代码间接代码(1)(1)(2)(2)(3)(3)(1)(1)(4)(4)(5)(5)三元式表三元式表7.7.中间语言中间语言187.2 7.2 说明语句说明语句编译过程中编译过程中,对对“说明语句说明语句”要做的工作要做的工作:对一个

12、过程或分程序的一系列说明语句对一个过程或分程序的一系列说明语句,考察时考察时:(1)(1)需要需要为局部于该过程的名字分配存储空间为局部于该过程的名字分配存储空间;(2)(2)对每个局部名字对每个局部名字,都都需在符号表中建立相应的表项需在符号表中建立相应的表项,并填入有关的信息并填入有关的信息如类型、在存储器中的相对地址如类型、在存储器中的相对地址 等。等。19一、过程中的说明语句一、过程中的说明语句1.1.产生产生“说明语句说明语句”的文法：的文法：PDDD;DDid:T TintegerTrealTarraynum of T1TT17.2 7.2 说明语句说明语句202.处理方式：处理方

13、式：处理第一条说明语句处理第一条说明语句之前之前，先置，先置offset为为0 0，以后每次，以后每次遇到一个遇到一个新的名字新的名字，则，则:(1)(1)将该名字填入符号表中将该名字填入符号表中,(2)(2)置相对地址为当前置相对地址为当前offset之值之值，(3)(3)使使offset加上该名字所表示的数据对象的域宽加上该名字所表示的数据对象的域宽。7.2 7.2 说明语句说明语句213.相应的翻译模式：相应的翻译模式：7.2 说明语句说明语句PDDD;DDid:T TintegerTrealTarraynum of T1TT1 offset:=0 enter(id.name,T.typ

14、e,offset);offset:=offset+t.width T.type:=integer;T.width:=4 T.type:=real;T.width:=8 T.type:=array(num.val,T1.type);T.width:=num.valT1.width T.type:=pointer(T1.type);T.width:=4 22说明说明:(1)offset:全程变量全程变量,代表变量在过程数据区中的相对地址代表变量在过程数据区中的相对地址,用来跟踪下一个可用的相对地址的位置用来跟踪下一个可用的相对地址的位置.7.2 7.2 说明语句说明语句(2)enter(name,

15、type,offset):把名字把名字name符号表符号表,并给出此名字的类型并给出此名字的类型type及在及在过程数据区中的相对地址过程数据区中的相对地址offset.(3)综合属性综合属性:T.type名字的类型名字的类型;T.width名字的域宽名字的域宽(即该类型名字所占用即该类型名字所占用 的存储单元个数的存储单元个数)23二、保留作用域信息二、保留作用域信息1.1.嵌套过程中的说明语句嵌套过程中的说明语句7.2 7.2 说明语句说明语句(1)(1)相应的文法相应的文法:PD DD;D|id:T|proc id;D;S(2)(2)程序举例程序举例:247.2 说明语句说明语句2.含嵌

16、套说明的翻译模式：含嵌套说明的翻译模式：PM D addwidth(top(tblptr),top(offset);pop(tblptr);pop(offset)M t:=mktable(nil);push(t,tblptr);push(0,offset)D D1;D2D proc id;N D1;S t:=top(tblptr);addwidth(t,top(offset);pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)N t:=mktable(top(tblptr);push(t,tblptr);push(0,offset)

17、D id:T enter(top(tblptr),id.name,T.type,top(offset);top(offset):=top(offset)+T.width 25(1)(1)语义规则中的操作语义规则中的操作:7.2 7.2 说明语句说明语句2.2.含嵌套说明的翻译模式：含嵌套说明的翻译模式：Mktable(previous):创建一张新符号表创建一张新符号表,并返回指向新表的一个指针并返回指向新表的一个指针;Enter(table,name,type,offset):在指针在指针tabletable指示的符号表中为名字指示的符号表中为名字namename建立一个新顶建立一个新顶,并

18、并把类型把类型typetype、相对地址、相对地址offsetoffset填入到该项中填入到该项中;267.2 7.2 说明语句说明语句(1)(1)语义规则中的操作语义规则中的操作:Enterproc(table,name,newtable):在指针在指针table指示的符号表中为名字指示的符号表中为名字name的过程建立一个的过程建立一个新顶。参数新顶。参数newtable指向过程指向过程name的符号表。的符号表。Addwidth(table,width):在指针在指针table指示的符号表表头中记录下该表中所有名字占指示的符号表表头中记录下该表中所有名字占用的总宽度用的总宽度;27(2)

19、(2)栈栈:tblptr:存放指向符号表的指针存放指向符号表的指针,栈顶为指向当前正在处理过栈顶为指向当前正在处理过 程的符号表指针程的符号表指针.offset:存放变量在数据区中的相对地址存放变量在数据区中的相对地址,栈顶为当前正在处栈顶为当前正在处 理过程的下一个变量的相对地址。理过程的下一个变量的相对地址。(3)top():取当前栈顶元素取当前栈顶元素 push(a,B):将将a a推进推进B B栈栈顶栈栈顶 pop(A):将将A A栈栈顶元素出栈栈栈顶元素出栈7.2 7.2 说明语句说明语句287.3 7.3 赋值语句的翻译赋值语句的翻译一、简单算术表达式及赋值语句一、简单算术表达式及

20、赋值语句1.1.产生产生“赋值语句赋值语句”三地址代码的翻译模式三地址代码的翻译模式:Sid:=E p:=lookup(id.name);if pnil then emit(p:=E.place)else error EE1+E2 E.place:=newtemp;emit(E.place:=E1.place+E2.place)EE1*E2 E.place:=newtemp;emit(E.place:=E1.place*E2.place)E-E1 E.place:=newtemp;emit(E.place:=uminusE1.place)E(E1)E.place:=E1.placeEid p:

21、=lookup(id.name);if pnil then E.place:=p else error292.说明说明:id.nameidid所代表的名字本身所代表的名字本身lookup(id.name)检查符号表中是否存在相应检查符号表中是否存在相应此名字的入口此名字的入口nil:返回一个该表项的指针返回一个该表项的指针 =nil:未找到未找到 emit()将生成的三地址语句发送到输出文件中将生成的三地址语句发送到输出文件中E.place存放存放E E值的名字值的名字newtemp产生产生“临时变量临时变量”7.3 7.3 赋值语句的翻译赋值语句的翻译303.例题：例题：写出下列代码段中表达

22、式的翻译制导过写出下列代码段中表达式的翻译制导过 程及其所产生的四元式程及其所产生的四元式beginInteger：B、C、D、X;X:=-B*(C+D);endOparg1arg2result(1)(2)(3)(4)+*:=T1 1T3 3T2 2T1 1T2 2T3 3符号表符号表四元式四元式7.3 7.3 赋值语句的翻译赋值语句的翻译31 已归约串已归约串PLACEPLACE输入串输入串语义动作语义动作#X:=-B X:=-B*(C+D)#(C+D)#X#X X X :=-B :=-B*(C+D)#(C+D)#X:=#X:=X_ X_-B-B*(C+D)#(C+D)#X:=-#X:=-X

23、_ X_ B B*(C+D)#(C+D)#X:=-B#X:=-B X_B X_B *(C+D)#(C+D)#X:=-E#X:=-E X_B X_B *(C+D)#E.place:=p=(C+D)#E.place:=p=#X:=E#X:=E1 1 X_T X_T1 1 *(C+D)#E(C+D)#E1 1.place:=newtemp=T.place:=newtemp=T1 1;生成四元式生成四元式(1)(1)#X:=E#X:=E*(C(C X_T X_T1 1_C_C +D)#+D)#X:=E#X:=E*(E1(E1X_TX_T1 1_C +D)#E_C +D)#E1 1.place:=p=.

24、place:=p=32 已归约串已归约串 PLACEPLACE 输入串输入串 语义动作语义动作#X:=E#X:=E*(E1+D X_T(E1+D X_T1 1_C_D_C_D)#)#X:=E#X:=E*(E1+E2 X_T(E1+E2 X_T1 1_C_D_C_D)#)#E E2 2.place:=p=.place:=p=#X:=E#X:=E*(E3(E3X_TX_T1 1_T_T2 2)#)#EE3 3.place:=newtemp=T.place:=newtemp=T2 2;生成四元式生成四元式(2)(2)#X:=E#X:=E*(E3)X_T(E3)X_T1 1_T_T2 2_ _#X:=

25、E#X:=E*E4 X_TE4 X_T1 1_T_T2 2#E4.place=E3.place=T#E4.place=E3.place=T2 2#X:=E5#X:=E5X_TX_T3 3#E5.place=T#E5.place=T3 3;生成四元式生成四元式(3)(3)#S#S#p:=lookup(X.name);#p:=lookup(X.name);生成四元式生成四元式(4)(4)33二、数组元素的引用二、数组元素的引用1.1.数组元素在存储器中的存放数组元素在存储器中的存放:7.3 7.3 赋值语句的翻译赋值语句的翻译一维数组地址一维数组地址:二维数组地址二维数组地址:Ai 的地址的地址=

26、base+(i-low)*w =i*w+(base-low*w)Ai1,i2 的地址的地址 =base+(i1 low1)*n2+i1-low2)*w =(i1*n2)+i2)*w+(base (low1*n2)+low2)*w)347.3 7.3 赋值语句的翻译赋值语句的翻译1.1.数组元素在存储器中的存放数组元素在存储器中的存放:二、数组元素的引用二、数组元素的引用k维数组地址维数组地址:C=(low1 n2+low2)n3+low3)nk+lowk)*w变量部分：变量部分：（(i1 n2+i2）n3+i3）)nm+i m e1=i1,em=em-1*n m+imA i1,i2,ik 的地

27、址的地址=（i1 n2+i2）n3+i3）)nk+ik)*w +base (low1 n2+low2)n3+low3)nk+lowk)*w 35改写产生式的原因：改写产生式的原因：使我们在整个下标表达式串使我们在整个下标表达式串Elist的翻译过程中随时都的翻译过程中随时都能知道符号表中相应于数组名字能知道符号表中相应于数组名字id的符号表入口的符号表入口,从而随时从而随时能了解登记在符号表中的有关数组能了解登记在符号表中的有关数组id的全部信息。的全部信息。2.2.产生数组元素的产生式：产生数组元素的产生式：LidElist|idLElist|idElistElist,E|E ElistEl

28、ist,E|idE7.3 7.3 赋值语句的翻译赋值语句的翻译363.数组元素的翻译模式：数组元素的翻译模式：A.文法文法:(1)SL:=E (2)EE+E (3)E(E)(4)EL (5)LElist (6)Lid (7)ElistElist,E (8)Elistid E7.3 7.3 赋值语句的翻译赋值语句的翻译37B.B.说明说明:id.placeid的符号表入口的符号表入口.E.place存放存放E的名字的名字/值值.L.offset =null,L为为简单名字简单名字;null,L为为数组元素引用数组元素引用,存放临时变量的值存放临时变量的值.(变量部分的值变量部分的值)L.plac

29、e L简单名字简单名字,则指向符号表中相应此名字表项的则指向符号表中相应此名字表项的 指针指针,即此名字的符号表入口即此名字的符号表入口.L数组引用数组引用,则则L.place存放临时变量的值存放临时变量的值.(常量部分的值常量部分的值)7.3 赋值语句的翻译赋值语句的翻译387.3 赋值语句的翻译赋值语句的翻译B.B.说明说明:Elist.array用来记录用来记录指向符号表中相应数组名字指向符号表中相应数组名字 表项的指针表项的指针数组变量的符号表入口数组变量的符号表入口 Elist.place表示临时变量表示临时变量,用来临时存放由用来临时存放由Elist中的中的 下标表达式计算出的值下

30、标表达式计算出的值。Elist.ndim记录记录Elist中的下标表达式的个数中的下标表达式的个数,即即 维数维数。Limit(array,j)返回返回nj,即由即由array所指示的数组的所指示的数组的 第第j j维长度维长度。397.3 7.3 赋值语句的翻译赋值语句的翻译C.C.翻译模式翻译模式 (1)S L:=E if L.offset=null then emit(L.place:=E.place)else emit(L.place L.offset :=E.place)(2)E E1+E2 E.place:=newtemp;Emit(E.place:=E1.place+E2.pla

31、ce)(3)E (E1)E.place:=E1.place 407.3 7.3 赋值语句的翻译赋值语句的翻译 (4)EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp;emit(E.place:=L.place L.offset)end (5)L Elist L.place:=newtemp;emit(L.place:=Elist.array-C);L.offset:=newtemp;emit(L.offset:=w*Elist.place)(6)Lid L.place:=id.place;L.offset

32、:=null 417.3 7.3 赋值语句的翻译赋值语句的翻译 (7)Elist Elist1,E t:=newtemp;m:=Elist1.ndim+1;emit(t:=Elist1.place*limit(Elist1.array,m);emit(t:=t+t.place)Elist.array:=Elist1.array;Elist.place:=t;Elist.ndim:=m (8)Elist id E Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place 424.举例举例已知已知:A为为1020的数组的数组,即即n1=10,

33、n2=20,设设w=4,x:=A y,zx:=Ay,z 其相应的三地址语句序列如下其相应的三地址语句序列如下:(1)T1:=y*20(2)T1:=T1+z(3)T2:=A-84(4)T3:=4*T1(5)T4:=T2T3(6)x:=T47.3 7.3 赋值语句的翻译赋值语句的翻译437.4 7.4 布尔表达式的翻译布尔表达式的翻译前言前言:2.2.布尔表达式的组成及形式布尔表达式的组成及形式 组成组成:布尔运算符号、布尔变量、关系表达式布尔运算符号、布尔变量、关系表达式 and,or,not (,)形式形式:E E1 1 relop E relop E2 21.1.布尔表达式的两个基本作用布尔

34、表达式的两个基本作用 (1)(1)用来计算逻辑值用来计算逻辑值 (2)(2)用作控制流语句的条件表达式用作控制流语句的条件表达式447.4 布尔表达式的翻译布尔表达式的翻译3.产生布尔表达式的文法产生布尔表达式的文法:EE or EEE and EEnot EE(E)Eid relop idEid45一、数值表示法一、数值表示法1.1.计算布尔表达式值的两种方法：计算布尔表达式值的两种方法：7.4 7.4 布尔表达式的翻译布尔表达式的翻译(1)(1)逐步计算逐步计算(与算术表达式计算类似与算术表达式计算类似)例：例：1 or (not 0 and 0)or 01 or (not 0 and 0

35、)or 0 =1 or (1 and 0)or 0 =1 or (1 and 0)or 0 =1 or 0 or 0 =1 or 0 or 0 =1 or 0 =1 or 0 =1 =1(2)(2)采取某种优化措施采取某种优化措施 A or BA or B if A then T else Bif A then T else B A and BA and Bif A then B else Fif A then B else F not Anot A if A then F elseTif A then F elseT462.2.采取采取“逐步计算法逐步计算法”计算布尔表达计算布尔表达式式7.

36、4 7.4 布尔表达式的翻译布尔表达式的翻译(2)关系式关系式a b if ab then 1 else 0分析分析:(1)布尔式布尔式a or b and not c T1:=not c T2:=b and T1 T3:=a or T2 100:if ab goto 103 101:T:=0 102:goto 104 103:T:=1 104:473.布尔表达式布尔表达式“逐步计算法逐步计算法”的翻译模式：的翻译模式：Emit():过程过程,将产生的三地址代码送到输出文件中将产生的三地址代码送到输出文件中.Nextstat:给出输出序列中给出输出序列中下一条三地址语句的地址索引下一条三地址语

37、句的地址索引,每产生一条三地址语句后每产生一条三地址语句后,过程过程emit将将nextstat加加1 1.7.4 布尔表达式的翻译布尔表达式的翻译48关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式:EE1 or E2 E.place:=newtemp;emit(E.place:=E1.placeorE2.place)EE1 and E2 E.place:=newtemp;emit(E.place:=E1.placeandE2.place)Enot E1 E.place:=newtemp;emit(E.place:=notE1.place)E(E)E.place:=E

38、1.placeEid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place gotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1);Eid E.place:=id.place 494.举例：举例：ab or cd and ef7.4 布尔表达式的翻译布尔表达式的翻译 100:if ab goto 103 101:T1:=0 102:goto 104 103:T1:=1 104:if cd goto 107 105:T2:=0 106:

39、goto 108 107:T2:=1 108:if ec or bc goto L2goto L1 L1:if bd goto L2goto L3 L2:关于关于S S1 1的三地址代码的三地址代码goto Lnext L3:关于关于S S2 2的三地址代码的三地址代码 Lnext:7.4 7.4 布尔表达式的翻译布尔表达式的翻译553.产生布尔表达式三地址代码的语义规则产生布尔表达式三地址代码的语义规则 课本课本188188页表页表7.7 7.7 注意：注意：利用表利用表7.7中的语义规则翻译的中的语义规则翻译的最容易方法最容易方法是经过是经过 两遍扫描。两遍扫描。（1）为给定的输入串构造一

40、颗语法树；）为给定的输入串构造一颗语法树；（2）对语法树进行深度优先遍历，进行语义规则中）对语法树进行深度优先遍历，进行语义规则中 规定的翻译。规定的翻译。564.4.实现一遍扫描翻译实现一遍扫描翻译 (1)(1)三地址代码表示三地址代码表示 四元式四元式 (jnz,a,p)if a goto p (jrop,x,y,p)if x rop y goto p (j,p)goto p(2)(2)一遍扫描的主要问题：一遍扫描的主要问题：当生成某些转移语句时我们可能还不知道该语句将要转当生成某些转移语句时我们可能还不知道该语句将要转移到的标号究竟是什么？移到的标号究竟是什么？问题的解决：问题的解决：在

41、生成形式分支的跳转指令时暂时不确定跳转在生成形式分支的跳转指令时暂时不确定跳转 目标，而建立一个链表，把转向这个目标的跳目标，而建立一个链表，把转向这个目标的跳 转指令的标号键入这个链表。一旦目标确定之转指令的标号键入这个链表。一旦目标确定之 后再把它填入有关的跳转指令中。后再把它填入有关的跳转指令中。回填技术回填技术E.truelist-E.falselist:分别记录布尔表达式分别记录布尔表达式E E所对应的四元式中需回填所对应的四元式中需回填“真真”、“假假”出口的出口的四元式标号所构成的链表四元式标号所构成的链表。57变量变量nextquad指向下一条将要产生但尚未形成的四元式的指向下

42、一条将要产生但尚未形成的四元式的 地址地址,初值为初值为1,1,执行一次执行一次emit后后,自动加自动加1.1.函数函数makelist(i)将将创建一个仅含创建一个仅含i的新链表的新链表，其中，其中i是四元式是四元式 数组的一个下标，函数数组的一个下标，函数返回指向这个链的指针返回指向这个链的指针。函数函数merge(p1,p2)把链首为把链首为p1和和p2的两条链合并为一的两条链合并为一,作为作为 函数值函数值,回送合并后的链首回送合并后的链首.过程过程backpatch(p,t)功能是功能是完成完成“回填回填”,把把p所链接的每个所链接的每个 四元式的第四个区段都填为四元式的第四个区段

43、都填为t.（3）变量和过程变量和过程58（4）翻译模式翻译模式:课本课本190190页页7.4 布尔表达式的翻译布尔表达式的翻译(1)EE1 or M E2 backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist(2)EE1 and M E2 backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)(3)Enot

44、 E1 E.truelist:=E1.falselist;E.falselist:=E1.truelist (4)E(E1)E.truelist:=E1.truelist;E.falselist:=E1.falselist 59(5)Eid1 relop id2 E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jrelop.op,id1.place,id2.place,0);emit(j,-，-，0)7.4 布尔表达式的翻译布尔表达式的翻译(6)Eid E.truelist:=makelist(next

45、quad);E.falselist:=makelist(nextquad+1);emit(jnz,id.place,-,0);emit(j,-，-，0)(7)E M.quad:=nextquad;605.例题：例题：课本课本190190页例题页例题7.47.4 ab or cd and ef7.4 布尔表达式的翻译布尔表达式的翻译翻译结果：翻译结果：100 (j,a,b,0)101 (j,-,-,102)102 (j,c,d,104)103 (j,-,-,0)104 (j L1:if ab goto L2 goto Lnext L2:if cd goto L3 goto L4 L3:T1:=y

46、+z X:=T1 goto L1 L4:T2:=y-z X:=T2 goto L1 Lnext647.5 控制语句的翻译控制语句的翻译2.一遍扫描产生中间代码的翻译模式一遍扫描产生中间代码的翻译模式课本课本195-196 S if E then S if E then S else S while E do S begin L end A L L;SS分析：分析：L.nextlist指向一个转移指令链表指向一个转移指令链表 S.nextlist指向一个转移指令链表指向一个转移指令链表转移指令链表：转移指令链表：未填写目标标号而在以后需要回填的转移指未填写目标标号而在以后需要回填的转移指 令的链

47、。令的链。657.5 控制语句的翻译控制语句的翻译（1）S if E then M1 S1 N else M2 S2 backpatch(E.truelist,M1.quad);backpatch(E.falselist,M2.quad);S.nextlist:=merge(S1.nextlist,N.nextlist,S2.nextlist)N N：产生跳过：产生跳过S2S2的无条件跳转指令。的无条件跳转指令。（2）N N.nextlist:=makelist(nextquad);emit(j,)（3）M M.quad:=nextquad (4)S if E then M S1 backpa

48、tch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,S1.nextlist)667.5 控制语句的翻译控制语句的翻译(5)S while M1 E do M2 S1 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.nextlist (7)S A S.nextlist:=makelist()(8)L L1;M S backpatc

49、h(L1.nextlist,M.quad);L.nextlist:=S.nextlist (9)L S L.nextlist:=S.nextlist 677.5 控制语句的翻译控制语句的翻译例例7.6 按照上述的语义动作，加上前述关于赋值句和布尔按照上述的语义动作，加上前述关于赋值句和布尔表达式的翻译法，采用一遍扫描翻译语句表达式的翻译法，采用一遍扫描翻译语句.课本课本196页页 While (ab)do if(cd)then x:=y+z；翻译结果：翻译结果：100 (j,a,b,102)101 (j,-,-,0)False102 (j,c,d,104)103 (j,-,-,100)104 (+,y,z,T)105 (:=,T,-,x)106 (j,-,-,100)