编译原理-刘善梅-第7章 语义分析和中间代码产生6ppt课件

1、编译原理第七章第七章 语义分析和中间代码产生语义分析和中间代码产生第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n中间语言中间语言n赋值语句的翻译赋值语句的翻译n布尔表达式的翻译布尔表达式的翻译n控制语句的翻译控制语句的翻译n过程调用的处理过程调用的处理 第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n静态语义检查静态语义检查n类型检查类型检查n控制流检查控制流检查n一致性检查一致性检查 n相关名字检查相关名字检查n名字的作用域分析名字的作用域分析 第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n静态语义检查和中间代码产生在编译程静态语义检查和中间代码产生在

2、编译程序中的地位：序中的地位：语法分语法分析器析器中间代码中间代码产生器产生器静态检静态检查器查器中间代码中间代码优化器优化器n中间语言中间语言n独立于机器独立于机器n复杂性界于源语言和目标语言之间复杂性界于源语言和目标语言之间n引入中间语言的好处：引入中间语言的好处：n便于进行与机器无关的代码优化工作便于进行与机器无关的代码优化工作 n易于移植易于移植n使编译程序的结构在逻辑上更为简单明确使编译程序的结构在逻辑上更为简单明确 源语言源语言程序程序目标语目标语言程序言程序中间语中间语言程序言程序CompilerFront EndCompilerBack Endn常用的中间语言：常用的中间语言：

3、n后缀式，又叫逆波兰表示后缀式，又叫逆波兰表示n图表示：图表示： DAG图、抽象语法树图、抽象语法树n三地址代码三地址代码n三元式三元式n四元式四元式n间接三元式间接三元式7.1 中间语言中间语言 7.1.1 7.1.1 后缀式后缀式 n后缀式表示法：后缀式表示法：Lukasiewicz发明的一种表示发明的一种表示表达式的方法，又称逆波兰表示法。表达式的方法，又称逆波兰表示法。n一个表达式一个表达式E的后缀形式可以如下定义：的后缀形式可以如下定义：n1. 如果如果E是一个变量或常量，则是一个变量或常量，则E的后缀式是的后缀式是E自身。自身。n2. 如果如果E是是E1 op E2形式的表达式，其

4、中形式的表达式，其中op是任何二元操作符，则是任何二元操作符，则E的后缀式为的后缀式为E1 E2 op，其中，其中E1 和和E2 分别为分别为E1 和和E2的后缀式。的后缀式。n3. 如果如果E是是(E1)形式的表达式，则形式的表达式，则E1 的后缀的后缀式就是式就是E的后缀式。的后缀式。n逆波兰表示法不用括号。只要知道每个逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。端进行扫描，都能对它进行唯一分解。n后缀式的计算后缀式的计算n用一个栈实现。用一个栈实现。n一般的计算过程是：自左至右扫描后缀一般的计算过

5、程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰式，每碰到运算量就把它推进栈。每碰到到k目运算符就把它作用于栈顶的目运算符就把它作用于栈顶的k个项，个项，并用运算结果代替这并用运算结果代替这k个项。个项。把表达式翻译成后缀式的语义规则描述把表达式翻译成后缀式的语义规则描述 产生式产生式EE(1)op E(2)E (E(1)Eid语义规则语义规则E.code:= E(1).code | E(2).code |opE.code:= E(1).codeE.code:=id E.code表示表示E后缀形式后缀形式 op表示任意二元操作符表示任意二元操作符 “|”表示后缀形式的连接。表示后缀形式

6、的连接。7.1.2 图表示法图表示法n图表示法图表示法nDAGn抽象语法树抽象语法树 7.1.2 图表示法图表示法 a+a*(b-c)+(b-c)*d的的DAG+*abd*-ca有两个父结点（有两个父结点（+，*）；）；表达式表达式b-c也有两个父结点；也有两个父结点； a:=b*(-c)+b*(-c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc抽象语法树对应的代码：抽象语法树对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*bum

7、inusc抽象语法树抽象语法树*buminusc a:=b*(-c)+b*(-c)的抽象语法树对应的代码的抽象语法树对应的代码DAG对应的代码：对应的代码： T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG a:=b*(-c)+b*(-c)的的DAG对应的代码对应的代码抽象语法树对应的代码：抽象语法树对应的代码： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T57.1.3 三地址代码三地址代码 n三地址代码三地址代码nx:=y op z /*每个语句的右边只能有一个运每个语句的右边只能有一个运算符算符*

8、/n三地址代码可以看成是抽象语法树或三地址代码可以看成是抽象语法树或DAG的的一种线性表示一种线性表示 a:=b*(-c)+b*(-c)的图表示法的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc相应于相应于 a:=b*(-c)+b*(-c)抽象语法树与抽象语法树与DAG的三地址码的三地址码 T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5对于抽象语法树的代码对于抽象语法树的代码对于对于DAG的代码的代码三地址语句的种类

9、三地址语句的种类 nx:=y op z nx:=op y nx:=y ngoto L nif x relop y goto L或或if a goto Ln传参传参param x和转子和转子call p,n，以及返回语句，以及返回语句return ynx:=yi及及xi:=y的索引赋值的索引赋值nx:=&y, x:=*y和和*x:=y的地址和指针赋值的地址和指针赋值n编译程序中，三地址语句的具体实现可以用记编译程序中，三地址语句的具体实现可以用记录来表示，记录中包含运算符和操作数的域。录来表示，记录中包含运算符和操作数的域。n通常有三种表示方法：通常有三种表示方法：n四元式四元式 op,

10、 arg1, arg2, resultn三元式三元式 op, arg1, arg2n间接三元式间接三元式 间接码表间接码表+三元式表三元式表四元式需要利用较多的临时单元四元式需要利用较多的临时单元, ,四元式之四元式之 间间 的联系通的联系通过临时变量实现。过临时变量实现。中间代码优化处理时，四元式比三元式方便的多中间代码优化处理时，四元式比三元式方便的多, ,间接三间接三元式与四元式同样方便，两种实现方式需要的存储空间元式与四元式同样方便，两种实现方式需要的存储空间大体相同。大体相同。三地址语句的具体实现三地址语句的具体实现n四元式四元式n一个带有四个域的记录结构，这四个域一个带有四个域的记

11、录结构，这四个域分别称为分别称为op, arg1, arg2及及resultnoparg1arg2resultn(0)uminuscT1n(1)*bT1T2n(2)uminuscT3n(3)*bT3T4n(4)+T2T4T5n(5):=T5a 23 对于语句a:=b*-c+b*-c 的四元式表示 三地址语句的四元式表示 (- , c , , t1) (* , b , t1 , t2) (- , c , , t3) (* , b , t1 , t4) (+ ,t2 , t4 , t5) (= , t5 , ,a)1、 x=y op z2、 x=op y3、goto L4、if x rop y g

12、oto L5、x=y6、parm x call p,n 7、x=yi xi=y8、x=&y x=*y（op , y , z , x)（op , y , , x)（j , , , L)(jrop ,x ,y , L)(= , y , ,x)三地址语句的具体实现三地址语句的具体实现n三元式三元式 n通过计算临时变量值的语句的位置来引通过计算临时变量值的语句的位置来引用这个临时变量用这个临时变量n三个域：三个域：op、arg1和和arg2noparg1arg2n(0)uminuscn(1)*b(0)n(2)uminuscn(3)*b(2)n(4)+(1)(3)n(5)assigna(4)三地

13、址语句的具体实现三地址语句的具体实现nxi:=y nop arg1 arg2 n(0) = x i n(1) assign (0) ynx:=yinop arg1 arg2n(0) = y in(1) assign x (0)三地址语句的具体实现三地址语句的具体实现n间接三元式间接三元式 n为了便于优化，用为了便于优化，用 三元式表三元式表+间接码表间接码表 表示中间代码表示中间代码n间接码表间接码表:一张指示器表，按运算的先后一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位次序列出有关三元式在三元式表中的位置。置。n优点优点: 方便优化，节省空间方便优化，节省空间n例如，语句例如

14、，语句nX:=(A+B)*C;nY:=D(A+B)n的间接三元式表示如下表所示。的间接三元式表示如下表所示。间接代码间接代码 (1) (2) (3) (1) (4) (5)三元式表三元式表 OPARG1 ARG2(1)+AB(2)*(1) C(3):=X(2)(4)D(1)(5):=Y(4)小结小结n常用的中间语言常用的中间语言n 后缀式，逆波兰表示后缀式，逆波兰表示n 图表示：图表示：DAG，抽象语法树，抽象语法树n 三地址代码：三元式、四元式、间接三元三地址代码：三元式、四元式、间接三元式式第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n中间语言中间语言n赋值语句的翻译赋值语句

15、的翻译n布尔表达式的翻译布尔表达式的翻译n控制语句的翻译控制语句的翻译n过程调用的处理过程调用的处理 赋值语句的翻译赋值语句的翻译 1.简单算术表达式及赋值语句简单算术表达式及赋值语句 id:=E对表达式对表达式E求值并置于变量求值并置于变量T中中id.place=Tn非终结符号非终结符号S有综合属性有综合属性S.code，它代表，它代表赋值语句赋值语句S的三地址代码。的三地址代码。n非终结符号非终结符号E有如下两个属性：有如下两个属性：nE.place表示存放表示存放E值的单元的名字。值的单元的名字。nE.code表示对表示对E求值的三地址语句序列。求值的三地址语句序列。n函数函数newte

16、mp的功能是，每次调用它时，的功能是，每次调用它时，将返回一个不同临时变量名字将返回一个不同临时变量名字,如如T1,T2,。为赋值语句生成三地址代码的为赋值语句生成三地址代码的S-属性文法定义属性文法定义 产生式产生式语义规则语义规则Sid:=ES.code:=E.code | gen(id.place := E.place)EE1+E2E.place:=newtemp; E.code:=E1.code | E2.code | gen(E.place := E1.place + E2.place)EE1*E2E.place:=newtemp; E.code:=E1.code | E2.code

17、 | gen(E.place := E1.place * E2.place)E-E1E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place)E (E1)E.place:=E1.place; E.code:=E1.codeEid E.place:=id.place; E.code= 产生赋值语句三地址代码的翻译模式产生赋值语句三地址代码的翻译模式 Sid:=E p:=lookup(); if pnil thenemit(p := E.place) else error EE1+E2 E.place:=ne

18、wtemp; emit(E.place := E1.place + E2.place)EE1*E2 E.place:=newtemp; emit(E.place := E 1.place * E 2.place)Sid:=E S.code:=E.code | gen(id.place := E.place)E E1+E2 E.place:=newtemp; E.code:=E1.code | E2.code |gen(E.place := E1.place + E2.place)E E1*E2 E.place:=newtemp; E.code:=E1.code | E2.code | gen(

19、E.place := E1.place * E2.place)产生赋值语句三地址代码的翻译模式产生赋值语句三地址代码的翻译模式 E-E1 E.place:=newtemp; emit(E.place:= uminusE 1.place)E(E1) E.place:=E1.placeEid p:=lookup(); if pnil then E.place:=p else error E-E1 E.place:=newtemp; E.code:=E1.code | gen(E.place := uminus E1.place)E (E1) E.place:=E1.place; E.

20、code:=E1.codeEid E.place:=id.place; E.code= 2. 数组元素的引用数组元素的引用n数组元素地址的计算：数组元素地址的计算：nX:=Ai1,i2， ,ik+YnAi1,i2， ,ik=X+Y 赋值语句的翻译赋值语句的翻译 n设设A为为1维数组，每个元素宽度为维数组，每个元素宽度为w， low为下界，为下界，base为为A的第一个元素的第一个元素;n则则A(i)这个元素的相对地址为：这个元素的相对地址为：base+（i-low）wn上式可整理为：上式可整理为：iw+（base-loww）可变部分可变部分不变部分不变部分n设设A为为2维数组，按行存放，每个元

21、素宽度为维数组，按行存放，每个元素宽度为w， lowi 为第为第i维维 的下界，的下界， ni 为第为第i维维 可取值的个数；可取值的个数；base为为A的第一个元素的相对地址；的第一个元素的相对地址；n则则A(i1,i2)这个元素的相对地址为：这个元素的相对地址为：nbase+（i1-low1）n2 +i2-low2）wn上式可整理为：上式可整理为： n（i1 n2+i2) w+base-( (low1 n2）+low2)w ）可变部分可变部分不变部分不变部分A1,1A1,2A1,3A2,1A2,2A2,3n设设A为为n维数组，按行存放，每个元素宽度为维数组，按行存放，每个元素宽度为w，nl

22、owi 为第为第i维维 的下界，的下界，upi 为第为第i维维 的上界的上界nni 为第为第i维维 可取值的个数（可取值的个数（ ni = upi - lowi +1）nbase为为A的第一个元素相对地址的第一个元素相对地址 n元素元素Ai1,i2,ik相对地址公式相对地址公式 n(i1 n2+i2)n3+i3)nk+ik)w +nbase-(low1 n2+low2)n3+low3)nk+lowk)w nC= base-(low1 n2+low2)n3+low3)nk+lowk)w 可变部分可变部分不变部分不变部分nid出现的地方也允许下面产生式中的出现的地方也允许下面产生式中的L出现出现

23、nL id Elist | idnElistElist,E | E n为了便于处理，文法改写为为了便于处理，文法改写为n LElist | id nElistElist, E | id E (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w产生带数组元素引用的赋值语句基础文法产生带数组元素引用的赋值语句基础文法(1) SL:=E(2) EE+E(3) E(E)(4) EL(5) LElist (6) Lid(7) Elist Elist, E(8) Elistid En引入下列语义变量或语义过程属性）引入下列语义变量或语义

24、过程属性）:nElist.ndim ：下标个数计数器，即维数：下标个数计数器，即维数nElist.place ：表示临时变量，用来临时：表示临时变量，用来临时存放已形成的存放已形成的Elist中的下标表达式计算出中的下标表达式计算出来的值来的值.n Elist. array：记录数组名：记录数组名 nlimit(array，j) ：函数过程，它给出数组：函数过程，它给出数组array的第的第j维的长度维的长度(i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)wn每个代表变量的非终结符每个代表变量的非终结符L有两个属性：有两个

25、属性：nL.place：n若若L为简单变量为简单变量i, 指变量指变量i的符号表入口的符号表入口 n若若L为下标变量，指存放不变部分的为下标变量，指存放不变部分的 临时变临时变量的整数码量的整数码 nL.offset ：n若若L为简单变量，为简单变量，null，n若若L为下标变量，指存放可变部分的临时变为下标变量，指存放可变部分的临时变量的整数码量的整数码 (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w带数组元素引用的赋值语句翻译模式带数组元素引用的赋值语句翻译模式(1) SL:=E if L.offset=null

26、then /*L是简单变量是简单变量*/emit(L.place := E.place) else emit( L.place L.offset := E.place) (2) EE1 +E2 E.place:=newtemp; emit(E.place := E 1.place + E 2.place)(i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w(3) E(E1)E.place:=E1.place(4) EL if L.offset=null then E.place:=L.place else begin E.p

27、lace:=newtemp; emit(E.place := L.place L.offset ) end 带数组元素引用的赋值语句翻译模式带数组元素引用的赋值语句翻译模式Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lowk)w(8) Elistid E Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place A i1,i2,ik ( (i1 n2+i2)n3+i3)nk+ik)w +base-(low1 n2+low2)n3+low3)nk+lo

28、wk)w(7) Elist Elist1, E t:=newtemp;m:=Elist1.ndim+1;emit(t := Elist1.place * limit(Elist1.array,m) );emit(t := t + E.place); Elist.array:= Elist1.array;Elist.place:=t;Elist.ndim:=m Ai1,i2,ik (i1 n2+i2)n3+i3)nk+ik) w +base-(low1 n2+low2)n3+low3)nk+lowk)w(5) LElist L.place:=newtemp; emit(L.place := El

29、ist.array C); L.offset:=newtemp; emit(L.offset := w * Elist.place) (6) Lid L.place:=id.place; L.offset:=null 类型转换类型转换n用用E.type表示非终结符表示非终结符E的类型属性的类型属性 n对应产生式对应产生式EE1 op E2的语义动作中关于的语义动作中关于E.type的语义规则可定义为：的语义规则可定义为：n if E1.type=integer andE2.type=integern E.type:=integern else E.type:=real n算符区分为整型算符算符

30、区分为整型算符int op和实型算符和实型算符real op，nx:=yi*jn 其中其中x、y为实型；为实型；i、j为整型。这个赋值为整型。这个赋值句产生的三地址代码为：句产生的三地址代码为：n T1:=i int* jn T3:=inttoreal T1n T2:=y real+ T3n x:=T2 关于产生式关于产生式EE1 E2 的语义动作的语义动作 E.place:=newtemp; if E1.type=integer and E2.type=integer then begin emit (E.place := E 1.place int+ E 2.place); E.type:

31、=integer end else if E1.type=real and E2.type=real then begin emit (E.place := E 1.place real+ E 2.place); E.type:=real endelse if E1.type=integer and E2.type=real then beginu:=newtemp;emit (u := inttoreal E 1.place);emit (E.place := u real+ E 2.palce);E.type:=realendelse if E1.type=real and E2.type

32、=integer then beginu:=newtemp;emit (u := inttoreal E 2.place);emit (E.place := E 1.place real+ u);E.type:=realend else E.type:=type_error小结小结n赋值语句的翻译赋值语句的翻译n简单算术表达式及赋值语句简单算术表达式及赋值语句n数组元素的引用数组元素的引用n产生有关类型转换的指令产生有关类型转换的指令第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n中间语言中间语言n赋值语句的翻译赋值语句的翻译n布尔表达式的翻译布尔表达式的翻译n控制语句的翻译控制语

33、句的翻译n过程调用的处理过程调用的处理 布尔表达式的翻译布尔表达式的翻译n布尔表达式的两个基本作用布尔表达式的两个基本作用:n用于逻辑演算用于逻辑演算,计算逻辑值计算逻辑值;n用于控制语句的条件式用于控制语句的条件式.n产生布尔表达式的文法产生布尔表达式的文法:n EE or E | E andE | not E | (E) | i relop i | in计算布尔表达式通常采用两种方法计算布尔表达式通常采用两种方法:n1. 如同计算算术表达式一样如同计算算术表达式一样,一步步算一步步算n 1 or (not 0 and 0) or 0n =1 or (1 and 0) or 0n =1 or

34、 0 or 0n =1 or 0n =1n2. 采用某种优化措施采用某种优化措施n 把把A or B解释成解释成 if A then true else Bn 把把A and B解释成解释成 if A then B else falsen 把把not A解释成解释成 if A then false else true两种不同的翻译方法两种不同的翻译方法:第一种翻译法：数值表示法第一种翻译法：数值表示法 A or B and C=D翻译成翻译成(1) (=, C, D, T1)(2) (and, B, T1, T2)(3) (or, A, T2, T3)第二种翻译法适合于作为条件表达式的布第二种

35、翻译法适合于作为条件表达式的布尔表达式使用尔表达式使用.1 数值表示法数值表示法 na or b and not c 翻译成翻译成nT1:=not cnT2:=b and T1nT3:=a or T1n关系表达式关系表达式ab 可等价地写成可等价地写成nif ab then 1 else 0 ，翻译成三地址语句，翻译成三地址语句序列序列n 100: if ab goto 103n101: T:=0n102: goto 104n103: T:=1n104:产生布尔表达式的三地址代码的数值表示产生布尔表达式的三地址代码的数值表示法翻译模式法翻译模式n过程过程emit将三地址代码送到输出文件中将三地

36、址代码送到输出文件中nnextstat给出输出序列中下一条三地址语句的给出输出序列中下一条三地址语句的地址索引地址索引n每产生一条三地址语句后，过程每产生一条三地址语句后，过程emit便把便把nextstat加加1 产生布尔表达式的三地址代码的数值表示产生布尔表达式的三地址代码的数值表示法翻译模式法翻译模式 EE1 or E2 E.place:=newtemp; emit(E.place := E 1.place or E2.place)EE1 and E2 E.place:=newtemp; emit(E.place := E 1.place and E2.place)Enot E1 E.p

37、lace:=newtemp; emit(E.place := not E 1.place)E(E1) E.place:=E1.place产生布尔表达式的三地址代码的数值表示法产生布尔表达式的三地址代码的数值表示法翻译模式翻译模式 Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop. op id2. place goto nextstat+3);emit(E.place := 0);emit(goto nextstat+2);emit(E.place:= 1) Eid E.place:=id.place ab 翻译成翻译成100:if

38、ab goto 103101:T:=0102:goto 104103:T:=1104:布尔表达式布尔表达式ab or cd and ef的翻译结果的翻译结果 100:if ab goto 103101:T1:=0102:goto 104103:T1:=1104:if cd goto 107105:T2:=0106:goto 108107: T2:=1108: if ec or b c goto L2 “真出口真出口 ngoto L1nL1:if bc or b c goto L2 “真出口真出口 goto L1L1:if bc or b c goto L2 “真出口真出口 goto L1L1:

39、if bd goto L2 “真出口真出口 goto L3 “假出口假出口 L2:(关于关于S1的三地址代码序列的三地址代码序列)goto LnextL3:(关于关于S2的三地址代码序列的三地址代码序列)考虑如下表达式：考虑如下表达式： ab or cd and ef产生式产生式语义规则语义规则 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true) | gen(goto E.false) EE1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.t

40、rue; E2.false:=E.false; E.code:=E1.code |gen(E1.false :) | E2.code EE1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code | gen(E1.true :) | E2.code考虑如下表达式：考虑如下表达式： ab or cd and ef假定整个表达式的真假出口已分别置为假定整个表达式的真假出口已分别置为Ltrue和和Lfalse，则按以上属性定义将生成如下的代码：，则按以上属性定义

41、将生成如下的代码：if ab goto Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto Lfalse控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译n两遍扫描两遍扫描n为给定的输入串构造一棵语法树；为给定的输入串构造一棵语法树；n对语法树进行深度优先遍历，进行语义规对语法树进行深度优先遍历，进行语义规则中规定的翻译。则中规定的翻译。n一遍扫描一遍扫描n 在自底向上的语法分析过程中生成布尔在自底向上的语法分析过程中生成布尔表达式的三地址代码表达式的三地址代码考虑如下表达式：考虑如下表达式： ab or cd and

42、 ef假定整个表达式的真假出口已分别置为假定整个表达式的真假出口已分别置为Ltrue和和Lfalseoror EabEEandand cdE efE两遍扫描实现布尔表达式的翻译两遍扫描实现布尔表达式的翻译 EE or E | E andE | not E | (E) | i relop i | ioror EabEEandand cdE efE产生式产生式语义规则语义规则 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true) | gen(goto E.false) EE1 or E2 E1.true:=E

43、.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code |gen(E1.false :) | E2.code EE1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code | gen(E1.true :) | E2.codeif ab goto Ltruegoto L1if cd goto L2goto Lfalse if ef goto Ltruegot

44、o Lfalse(Ltrue, Lfalse)(Ltrue, L1)(Ltrue, Lfalse)(L2, Lfalse)(Ltrue, Lfalse)L1:L2:一遍扫描实现布尔表达式的翻译一遍扫描实现布尔表达式的翻译n采用四元式形式采用四元式形式n把四元式存入一个数组中，数组下标就代表四元把四元式存入一个数组中，数组下标就代表四元式的标号式的标号n商定商定 n四元式四元式(jnz, a, -, p) 表示表示 if a goto p n四元式四元式(jrop, x, y, p)表示表示 if x rop y goto pn四元式四元式(j, -, -, p) 表示表示 goto p一遍扫描

45、实现布尔表达式的翻译一遍扫描实现布尔表达式的翻译ab or cd100: (j, a, b, ?)101: (j, -, -, 102) 102: (j, c, d, ?)103:(j, -, -, ?) 104: 110:n主要问题：主要问题：n产生跳转指令四元式时，它的转移地址无法立产生跳转指令四元式时，它的转移地址无法立即知道即知道n需要以后扫描到特定位置时才能回过头来确定需要以后扫描到特定位置时才能回过头来确定n把这个未完成的四元式地址作为把这个未完成的四元式地址作为E的语义值保的语义值保存存,待机待机回填回填。n为非终结符为非终结符E赋予两个综合属性赋予两个综合属性E.truelis

46、t和和E.falselist。它们分别记录布尔表达式。它们分别记录布尔表达式E所应的所应的四元式中需回填四元式中需回填“真真”、“假出口的四元式的标假出口的四元式的标号所构成的链表号所构成的链表 n例如例如:假定假定E的四元式中需要回填的四元式中需要回填真真出口的出口的p，q，r三个四元式，则三个四元式，则E.truelist为下列链为下列链:n(p) (x， x，x，0)nn(q) (x，x，x，p)nn(r) (x，x，x，q)链尾：链尾：0为链末标志为链末标志E. truelist =r，r为链首为链首n为了处理为了处理E.truelist和和E.falselist ，引入下列，引入下列

47、语义变量和过程语义变量和过程:n变量变量nextquad，它指向下一条将要产生但尚，它指向下一条将要产生但尚未形成的四元式的地址未形成的四元式的地址(标号标号)。nextquad的的初值为初值为1，每当执行一次，每当执行一次emit之后，之后，nextquad将自动增将自动增1。n函数函数makelist(i)，它将创建一个仅含，它将创建一个仅含i的新链的新链表，其中表，其中i是四元式数组的一个下标是四元式数组的一个下标(标号标号)；函；函数返回指向这个链的指针。数返回指向这个链的指针。n函数函数merge(p1,p2)，把以，把以p1和和p2为链首的两为链首的两条链合并为一，作为函数值，回送

48、合并后的链条链合并为一，作为函数值，回送合并后的链首。首。n过程过程backpatch(p, t)，其功能是完成，其功能是完成“回填回填”，把把p所链接的每个四元式的第四区段都填为所链接的每个四元式的第四区段都填为t。n例如例如:过程过程backpatch(p, t)，其功能是完成，其功能是完成“回回填填”，把，把p所链接的每个四元式的第四区段都填所链接的每个四元式的第四区段都填为为t。n(r) (x， x，x，t)nn(q) (x，x，x，t)nn(p) (x，x，x，t)链尾链尾p布尔表达式的文法布尔表达式的文法(1) E E1 or M E2(2) | E1 and M E2(3)| n

49、ot E1(4)| (E1)(5)| id1 relop id2(6)| id(7)M布尔表达式的翻译模式布尔表达式的翻译模式 (7) M M.quad:=nextquad (1) EE1 or M E2(2) | E1 and M E2布尔表达式的翻译模式布尔表达式的翻译模式 (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,

50、M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) E1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.falseE1.codeTo E. falseTo E1. trueE2.codeTo E.trueTo E.false布尔表达式的翻译模式布尔表达式的翻译模式 (3) Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist(4) E(E1) E.truelist:=E1.true

51、list; E.falselist:=E1. falselist布尔表达式的翻译模式布尔表达式的翻译模式 (5) Eid1 relop id2 E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) (6) Eid E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(jnz , id .place , ,0

52、)； emit( j, -, -, 0) 布尔表达式的翻译模式布尔表达式的翻译模式 n作为整个布尔表达式的作为整个布尔表达式的真真假假出口出口(转移转移目标目标)仍待回填仍待回填.(5) Eid1 relop id2 E.truelist:=makelist(nextquad) E.falselist:=makelist(nextquad+1); emit(j relop.op , id 1.place , id 2.place,0); emit(j, , , 0) (7) M M.quad:=nextquad 100: (j, a, b, 0)101: (j, -, -, 0) 102: (

53、j, c, d, 0)103:(j, -, -,0) 104: (j, e, f, 0)105: (j, -, -,0) abE(100,101)oror M(102)andand M(104)efE(104, 105) c dE(102, 103) ab or cd and ef c dEororandand abE(100,101) M(102) M(104)efE(104, 105)(102, 103)(1) EE1 or M E2 backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist);

54、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) 100: (j, a, b, 0)101: (j, -, -, 0) 102: (j, c, d, 0)103:(j, -, -,0) 104: (j, e, f, 0)105: (j, -, -,0) E104(104，105,103)E(104，100,105.103)102103100ab or cd

55、 and ef 100 (j, a, b, 0)101 (j, -, -, 102)102 (j, c, d, 104)103 (j, -, -, 0)104 (j, e, f, 100) truelist105 (j, -, -, 103) falselist 小结小结n布尔表达式的翻译布尔表达式的翻译n 数值表示法数值表示法n作为条件控制的布尔表达式翻译作为条件控制的布尔表达式翻译n 一遍扫描的翻译模式一遍扫描的翻译模式第七章第七章 语义分析和中间代码产生语义分析和中间代码产生n中间语言中间语言n赋值语句的翻译赋值语句的翻译n布尔表达式的翻译布尔表达式的翻译n控制语句的翻译控制语句的翻译n

56、过程调用的处理过程调用的处理 7.5 控制语句的翻译控制语句的翻译 n考虑下列产生式所定义的语句考虑下列产生式所定义的语句n S if E then S1n | if E then S1 else S2n | while E do S1n其中其中E为布尔表达式。为布尔表达式。利用属性文法定义语义利用属性文法定义语义设计一遍扫描的翻译模式设计一遍扫描的翻译模式nif-then语句语句nS if E then S1E.codeS1.codeTo E.trueTo E.falseE.true:E.false:if-then语句的属性文法语句的属性文法 产生式产生式语义规则语义规则 Sif E the

57、n S1 E.true:=newlabel; E.flase:=S.next; S1.next:=S.next S.code:=E.code | gen(E.true :) | S1.codeE.codeS1.codeTo E.trueTo E.falseE.true:E.false:nif-then-else语句语句nS if E then S1 else S2E.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:if-then-else语句的属性文法语句的属性文法 产生式产生式 语义规则语义规则Sif

58、E then S1 else S2 E.true:=newlabel; E.false:=newlabel; S1.next:=S.next S2.next:=S.next; S.code:=E.code | gen(E.true :) | S1.code | gen(goto S.next) | gen(E.false :) | S2.codeE.codeS1.codeS2.codeTo E.trueTo E.falsegoto S.nextS.nextE.true:E.false:nwhile-do语句语句nS while E do S1 E.codeS1.codeTo E.trueTo

59、E.falsegoto S.beginS.begin:E.true:E.false:while-do语句的属性文法语句的属性文法 产生式产生式语义规则语义规则Swhile E do S1S.begin:=newlabel; E.true:=newlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin :) | E.code | gen(E.true :) | S1.code | gen(goto S.begin)E.codeS1.codeTo E.trueTo E.falsegoto S.beginS.begin:E.true

60、:E.false:考虑如下语句考虑如下语句 :while ab doif cd thenx:=y+z else x:=y-zn生成下列代码：生成下列代码： nL1:if ab goto L2ngoto LnextnL2:if cd goto L3ngoto L4nL3:T1:=y+znx:=T1ngoto L1nL4:T2:=y-znx:=T2ngoto L1nLnext:一遍扫描翻译控制流语句一遍扫描翻译控制流语句 n考虑下列产生式所定义的语句考虑下列产生式所定义的语句:n(1) Sif E then Sn(2) | if E then S else Sn(3)| while E do Sn(4) | be