语义分析和中间代码的产生.ppt

语义分析和中间代码的产生,编译技术之七,主讲,鲁 斌,2,在词法分析和语法分析之后，编译程序要进行静态语义检查和翻译 静态语义检查通常包括： 类型检查 控制流检查 一致性检查 相关名字检查 翻译为中间语言的好处： 便于进行与机器无关的代码优化 使编译程序改变目标机更容易 使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰,3,1 中间语言,掌握几种中间语言的基本结构 逆波兰表示 图表示法（DAG 和抽象语法树） 三地址代码（四元式、三元式、间接三元式）,4,1.1 后缀式,后缀式表示法又称逆波兰表示法，把运算量（操作数）写在前面，把算符写在后面（后缀） 一个表达式的后缀式可以如下定义： 如果E是一个变量或常量，则E的后缀式是E自身 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为 E1 E2 op,这里E1和E2分别为E1和E2的后缀式 如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式,5,例如：a+b可以写成 (a+b)*c可以写成 abc+*代表 ab+cd+*代表 把表达式翻译成后缀式的语义规则描述：,ab+,ab+c*,a*(b+c),(a+b)*(c+d),6,1.2 图表示法,图表示法包括DAG与抽象语法树 无循环有向图（Directed Acyclic Graph , 简称 DAG)与抽象语法树一样，对于表达式中的每个子表达式，DAG图中都有一个结点。一个内部结点代表一个操作符，它的孩子代表操作数 两者不同的是，在DAG图中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树,7,例如：赋值语句a:=b*-c+b*-c的抽象语法树和DAG图如下：,assign,+,a,*,uminus,b,c,*,uminus,b,c,抽象语法树,assign,+,a,*,uminus,b,c,DAG,8,产生赋值语句抽象语法树的属性文法,9,赋值语句：a:=b*-c+b*-c 后缀式：a b c uminus * b c uminus * + assign,assign,+,*,uminus,id a,id c,id b,*,uminus,id c,id b,id b,id c,unimus 1,* 0 2,id b,id c,unimus 5,* 4 6,+ 3 7,id a,assign 9 8,.,0,1,2,3,4,5,6,7,8,9,10,10,1.3 三地址代码,三地址代码是由下面一般形式的语句构成的序列: X := y op z 其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等。每个语句的右边只能有一个运算符,11,例如：赋值语句a:=b*-c+b*-c的抽象语法树如下：,assign,+,a,*,uminus,b,c,*,uminus,b,c,抽象语法树,三地址代码 t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ： t5,12,例如：赋值语句a:=b*-c+b*-c的DAG图如下：,assign,+,a,*,uminus,b,c,DAG,三地址代码 t1： -c t2： b*t1 t5： t2+t2 a ： t5,13,三地址语句的种类,（1）赋值语句 x：y op z，op为二目算术算 符或逻辑算符; （2）赋值语句 x：op y ，op为一目算符， 如一目减uminus、逻辑非not、移位算符 及转换算符; （3）复制语句 x：y; （4）无条件转移语句goto L; （5）条件转移语句 if x relop y goto L，关系运 算符号relop（ ，=，= 等等）;,14,（6）过程调用语句 param x 和 call p, n ; 过程返回语句 return y; （7）索引赋值 x:=yi 及 xi :=y ; （8）地址和指针赋值 x：y，x：* y 和 * x：y。,15,产生赋值语句三地址代码的属性文法,16,E.place表示存放E值的名字 E.code表示对E求值的三地址语句序列 newtemp是个函数，对它的调用将产生一个新的临时变量 三地址语句序列是语法树的线性表示，用临时变量代替语法树中的结点 实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地址语句序列置入code属性之中,17,三地址代码的具体实现,四元式 op, arg1, arg2, result 三元式 op, arg1, arg2 间接三元式 间接码表+三元式表 四元式需要利用较多的临时单元,四元式之间的联系通过临时变量实现 中间代码优化处理时，四元式比三元式方便的多,间接三元式与四元式同样方便，两种实现方式需要的存储空间大体相同,18,语句a:=b*-c+b*-c 的四元式表示：,(0) (1) (2) (3) (4) (5),uminus * uminus * + assign,c b c b t2 t5,arg1,t1 t3 t4,arg2,result,t1 t2 t3 t4 t5 a,op,19,(0) (1) (2) (3) (4) (5),uminus * uminus * + assign,c b c b （1） a,arg1,(0) (2) (3) (4),arg2,op,数：三元式中使用指向三元式语句的指针。,语句a:=b*-c+b*-c 的三元式表示：,20,语句 X:=(A+B)*C; Y:=D(A+B),的间接三元式表示：,间接代码,(1) (2) (3) (1) (4) (5),注：语句的移动仅改变左边的语句表,21,2 说明语句,当考察一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间 对每个局部名字，我们将在符号表中建立相应的表项，并填入相应的信息，如类型、在存储器中的相对地址等 相对地址是指对静态数据区基地址的一个偏移量,22,2.1 过程中的说明语句,在C、Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把他们安排在一块数据区中 需要一个全程变量如offset来跟踪下一个可用的相对地址的位置,23,计算说明语句中名字的类型和相对地址,24,第一条产生式及其语义动作可写为： P offset:=0 D 进一步用产生式的标记非终结符号，改写产生式，以便语义动作均出现整个产生似的右边： PMD M offset:= 0 ,25,2.2 保留作用域信息,当遇到一个嵌入的过程说明时,则应当暂停包围此过程的外围过程说明语句的处理 这种方法可以通过加入下面语言把有关语义动作来说明 PD DD;D|id:T | proc id ;D ;S T有两个属性type和width. 假定对于上式的语言的每个过程都有一张独立的符号表，可用链表实现 当碰到过程说明Dproc id; D1 ;S 时，便创建一张新的符号表，并且把在D1中的所有说明项都填入此符号表内 新表有一个指针指向刚好包围该嵌入过程的外围过程的符号表，由id表示的过程名字作为该外围过程的局部名字 要告诉enter在哪个符号表填入一项,26,程序结构,一组嵌套过程，每个过程说明的局部名字建立一个符号表，所有正在翻译过程的符号表组成整个源程序的符号表 翻译时，为每一个过程维持一个符号表,27,sort a,x,readarray i a,exchange x,a,quicksort k,v,partition i,j a,v,i,j,28,nil,header,a,x,readarray,exchange,quicksort,header,header,header,k,v,partition,header,i,j,sort,readarray,exchange,quicksort,partition,i,to readarray,to exchange,嵌套过程的符号表,29,进入过程partition，quicksort过程的编译并未结束，活动记录的设计和符号表的建立尚未完成，因此，要把quicksort过程使用的table和offset保存于栈中 使用两个栈，分别保存刚编译过程的符号表table和offset的值,30,PMD addwidth(top(tblptr),top(offset); pop(tblptr); pop(offset) M t:=mktable（nil）； push(t,tblptr); push(0,offset) DD1；D2 Dproc id; N D1；S t:top（tblptr); addwidth(t,top(offset); pop（tblptr）；pop（offset); enterproc(top（tblptr），，t),处理嵌套过程中的说明语句,31,D id: T enter(top(tblptr),,T.type, top(offset); top(offset）：= top(offset) T.width N t ：mktable(top（tblptr)； push(t，tblptr）；push（0，offset) 如下操作： 1. mktable( previous）创建一张新符号表 2. enter（table，name，type，offset）插入表项 3. addwidth（table，width）记录总域宽 4. enterproc（table,name, newtable） 建立过程新表项,32,上述翻译模式给出了如何在一遍扫描中对数据进行处理，它使用了一个栈tblptr保存各外层过程的符号指针 对前例符号表，当处理过程partition中的说明语句时，栈tblptr中将包括指向sort,quicksort及partition的符号表的指针 指向当前符号表的指针在栈顶。另一个栈offset存放各嵌套过程的当前相对地址。Offset 的栈顶元素为当前被处理过程的下一个局部名字的相对地址 对于 ABC action A 所有关于非终结符号B,C的语义动作均已先于Action A完成。因此，将先做与标记非终结符号M相应的语义动作,33,M的语义动作把栈tblptr初始化为仅含最外层作用域的符号表的指针，由mktable(nil)创建符号表，并把符号表的指针返回给t；同时还把相对地址0压入栈offset中 当出现一个过程说明时，非终结符N起着类似的作用，其语义动作使用mktable(top(tblptr)来创建一个新符号表，参数top(tblptr)为指向刚好包围此嵌套过程的外围过程符号表的指针。把指向新表的指针压入栈tblptr的栈顶，同时把相对地址0压入offset栈顶,34,每遇到一个变量说明id:T，就把id填入在当前符号表中。这时栈tnlptr保持不变，而栈offset的栈顶值增加T.width 当开始执行产生式Dproc id; N D1;S右边的语义动作时，由D1产生的所有名字占用的总宽度便是offset的栈顶值，它由过程addwidth记录下来；同时，栈tblptr及其offset的栈顶项值被弹出，返回外层过程中的说明语句继续处理。并在此时把过程的名字id填入到其外围过程的符号表中,35,2.3 纪录中的域名,除了基本类型、指针和数组外，下述产生式使非终结符号T产生纪录类型： Trecord D end 为记录中的域名建立一张符号表的翻译模式 T record LD end T.type:=record（top（tblptr)； T.width:top(offset)； pop（tblptr); pop(offset) L t:=mktable(nil); push(t,tblptr); push(0,offset) ,36,3 赋值语句的翻译,赋值语句中的表达式的类型可以是整型、实型、数组和纪录 作为翻译赋值语句为三地址代码的一部分，我们将讨论如何在符号表中查找名字及如何存取数组和纪录的元素,37,3.1 简单算术表达式及赋值语句,lookup() 检查是否在符号表中存在相应此名字的表项 采用最近嵌套作用域规则查找非局部名字时，lookup过程先通过top(tblptr)指针在当前符号表中查找名字为name的表项 若找到，返回有关信息 若未找到，lookup就利用当前符号表表头的指针找到该符号表的外围符号表，然后在那里查找名字为name的表项，直到所有外围过程的符号表中均无此name表项，则lookup返回nil，表明查找失败,38,Sid:=E p:=lookup(); 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 -E E.place:=newtemp; emit(E.place := uminusE1.place,产生赋值语句三地址代码的翻译模式,39,E(E1) E.place:=E1.place Eid p:=lookup(); if pnil then E.place:=p else error lookup()= id.entry nil emit 将生成的三地址代码送到输出文件上。 语义动作应包括类型分析，文法符号应有类型属性，在类型分析的基础上，进行相容和赋值相容检查，生成类型转换的三地址代码,40,3.2 数组元素的引用,现在讨论数组元素的表达式和赋值语句的翻译问题 若数组A的元素存放在一片连续单元里，则可以较容易的访问数组的每个元素 假定数组的每个元素的宽度为w，则一维数组Ai 这个元素的起始地址为： base + (i low)*w （） 其中low为数组下标的下界， 并且base是分配给数组的相对地址，即base为A的第一个元素Alow的相对地址。()式可以整理为： i*w + (base low*w) 其中：i*w 是随数组下标变量而变化的部分 （base low*w)是在数组中不变化的常数记为C,41,对于二维数组情况尤其应注意： 若二维数组A按行存放，则可用如下公式计算Ai1,i2的相对地址： base + ( i1 low1)*n2 + i2 low2) *w 其中，low1、low2分别为i1、i2的下界；n2是i2可取值的个数。即若high2为i2的上界，则n2=high2 low2 +1. 假定i1,i2是编译时唯一尚未知道的值，我们可以重写上述表达式为： ( (i1*n2) + i2) *w +( base ( (low1 *n2) + low2) *w) 后一项子表达式( base ( (low1 *n2) + low2) *w )的值是可以在编译时确定的，为常数。前一子项随i1, i2 而改变是一个变数。 特别是当low=1时有：V=(i1*n2+i2)*w C= base (n2+1)*w 应该牢记。 对于多维数组，可得计算元素Ai1, i2, , ik相对地址公式： ( (i1n2 + i2) n3 + i3) nk+ ik)*w+base ( (low1n2 + low2) n3 + low3) nk+ lowk)*w,42,ai1,i2,in的地址 =常量部分C +变量部分V x:=ai1,i2的三地址代码结构： t1 := V t2 := C t3 := t2t1 x := t3 计算动态数组元素地址的公式与在固定长度数组情况下是同样的，只是上、下界在编译时是未知的,43,要生成数组的引用代码，其主要问题是把常数C和变数V 的计算与数组引用的文法联系起来 把数组元素引用加入到赋值语句中 Lid Elist | id ElistElist, E | E 为语句处理上的方便改写为： LElist | id Elist Elist, E | id E,44,Elist.ndim：记录Elist中的下标表达式的个数，即维数 函数limit（array，j）：返回nj ，即由array所指示的数组的第j维长度 Elist.place：临时变量，用来临时存放由Elist中的下标表达式计算出来的值 Elist.array：用来纪录指向符号表中相应数组名字表项的指针,45,一个Elist可以产生一个k-维数组引用Ai1,i2,ik的前m维下标，并将生成计算下面式子的三地址代码 （ ( ( i1*n2 +i2)n3)nm + im 利用如下的递归公式进行计算： e1 = i1, em = em-1* nm + im 于是 当m=k时将ek乘以元素的宽度w便可计算出数组元素地址的变量部分 描述L的左值（即地址）用两个属性L.place和L.offset 如果L仅为一个简单名字，L.place就为指向符号表中相应此名字表项的指针，而offset为null，表示这个左值是一个简单名字而非数组的引用,46,访问数组元素的翻译模式,给定文法： （1）SL：E （2）EEE （3）E（E） （4）EL （5) LElist （6）Lid （7）ElistElist，E （8）Elistid E,47,相应语义动作 若L是一个简单的名字，将生成一般的赋值； 若L为数组元素引用，则生成对L所指示地址的索引赋值 1SL ：E if L. offsetnull then emit(L.place ： E.place) else emit（L.placeL.offset：= E. Place） 2EE1E2 E.place：newtemp; emit（E.place： E1placeE2.place）,48,3E（E1） E.place ：E1.place 使用索引来获得地址L.placeL.offset 的内容： 4 EL if L.offsetnull then E.place:L.place * L是简单变量 */ else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end,49,5 LElist L.place:=newtemp; emit（L.place:=Elist.array C) （low1*n2low2）n3low3） *nk lowk） * w ）； L.offset:=newtemp; emit（L.offset:=w*Elist.place) 一个空的offset表示一个简单的名字： 6 Lid L.place:=id.place;L.offset:=null,50,应用递归公式扫描下一个下标表达式 7ElistElist1,E t：newtemp; m： Elist1ndim1； emit（t := Elist1.place * limit(Elist1.array,m)； emit（t ：= t E.place）； Elist.array：Elist1.array; Elist.place：=t; Elist.ndim：m 8 ElistidE Elist.place:=E.place; Elist.ndim:=1; Elist.array：id.place,51,数组的类型信息： VAR a:ARRAY 110,120 OF real; 符号表中的信息可组织如下：,a 偏移量 类型,名字表,信息向量,C=84 low1=1 high1=10 n1=10 low2=1 high2=20 n2=20 基类型,Real 标准类型 8,52,例7.1 设A为一个10*20的数组，即n1= 10, n2=20,并设w4，数组第一个元素为A1，1 。 则有， (low1*n2)low2)*w =(1*20 1）*484 对赋值语句x:= Ay,z的带注释的分析树如图所示,53,带注释的语法树：其中每个变量，用其名字代替id.place.,54,该赋值语句在由底向上的分析中被翻译成如下三地址语句序列： T1：= y*20 T1：= T1z T2：= A-84 T3: = 4*T1 T4：= T2T3 x : = T4 注意：20、84、4都是编译中引入的常量,55,在前面关于算术表达式和赋值语句的翻译中，我们假定所有的id 都是同一类型的 实际上，在表达式中可能出现各种类型的变量或常量 所以编译程序必须做到：或者拒绝接受某种混合运算，或者产生有关类型转换的指令,56,3.3 纪录中域的引用,编译器将记录的域的类型和相对地址保存在相应域名的符号表表项之中，可以把用在符号表中查找名字的程序同样用来查找域名。 例如：表达式：pinfo1 变量P是一个指向某个记录类型的指针，info 为其中一个算术型类型的域名 编译程序内部把 p表示为：pointer(record(t)，域名info将可以在t所指向的符号表中查找,57,4 布尔表达式的翻译,布尔表达式有两个基本作用 用作计算逻辑值 用作控制流语句的条件表达式 如if-then、if-then-else和 while-do等的条件表达式 布尔表达式是用布尔运算符号（and、 or、not )作用到布尔变量或关系表达式上而组成的 关系表达式形如E1 relop E2, 其中E1和E2是算术表达式，relop为关系运算符 （ =, , =, ）,58,考虑由下列文法产生的布尔表达式： EE or E | E and E | not E | (E) | id relop id |id 用relop的属性relop.op来确定relop所指的六种关系中的哪一个 假定or和and 是左结合的，规定or 的优先级最低，其次是and, not的优先级最高。,59,翻译布尔表达式的方法,表示一个布尔表达式的值 方法一：用数值表示真和假，从而对布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算 方法二：通过程序的控制流，即用程序中控制转移到达的位置来表示布尔表达式的值 方法二用于翻译控制流语句中的布尔表达式尤其方便,60,4.1 数值表示法,用1表示真，0表示假来实现布尔表达式的翻译 布尔表达式：a or b and not c翻译成三地址代码序列： 100 ： t1:=not c 101 ： t2:=b and t1 102 ： t3:=a or t1 一个形如 ab的关系表达式可等价的写成: if ab then 1 else 0 并将它翻译成如下三地址语句序列： 100 if ab goto 103 101 T:=0 102 goto 104 103 T:= 1 104,61,布尔表达式的数值表示法的翻译模式,EE1 or E2 E.place:=newtemp; emit(E.place:=E1.placeor E2.place) EE1 and E2 E.place:=newtemp; emit(E.place:=E1.placeand E2.place) Enot E1 E.place:=newtemp; emit(E.place:= not E1.place) Eid1 relop id2 E.place:=newtemp; emit(if id1.place relop.op id2.placegoto nextstat+3); emit(E.place:= 0); emit(gotonextstat+2); emit(E.place:= 1) Eid E.place:=id.place,62,例7.2：生成布尔表达式ab or cd and ef的三地址代码,100：if ab goto 103 101：T1:=0 102：goto 104 103：T1:= 1 104：if cd goto 107 105：T2:=0 106：goto 108,107：T2:= 1 108：if ef goto 111 109：T3:=0 110：goto 112 111：T3:= 1 112：T4:=T2 and T3 113：T5:=T1 or T4,63,4.2 作为条件控制的布尔式翻译,出现在条件语句： if E then S1 else S2 （） 中的布尔表达式E，它的作用仅在于控制对S1和S2的选择 作为转移条件的布尔式 E，可以赋予它两种“出口” “真”出口，出向S1 “假”出口，出向S2 语句（）可翻译成如下图的形式。,64,对于作为转移条件的布尔式，可以把它翻译成为一串跳转指令 如：可把语句 If ac or bc goto L2 Goto L1 L1: if bd goto L2 goto L3 L2: (关于S1的三地址代码序列) goto Lnext L3: (关于S2的三地址代码序列) Lnext:,65,用符号标号标识一条三地址语句，每次调用函数newlabel后都返回一个新的符号标号 E.true是E为真时的控制流转向的标号，E.false是E为假时控制流转向的标号 基本思想: 假定E 形如ad,则将生成如下的E的代码： if ab goto E.true goto E.false,66,产生式,语义规则,EE1 or E2,E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false E.code:=E1.code| gen(E1.false:)|E2.code,产生布尔表达式三地址代码的语义规则,67,EE1 and E2,E1.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:= E.false; E1.false:= E.true; E.code:=E1.code,68,Eid1 relop id2,E.code:=gen(if id1.place relop.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的true和false属性都是继承属性,E(E1),E1.true:= E.true; E1.false:= E.false; E.code:=E1.code,69,例7.3：表达式 ab or cd and ef 真假出口分别为Ltrue和Lfalse，可翻译成如下的三地址代码： If ab goto Ltrue Goto L1 L1: if cd goto L2 goto Lfalse L2: if ef goto Ltrue goto Lfalse,70,使用回填翻译布尔表达式,两遍扫描 从给定的输入构造出一棵语法树 对语法树按深度优先遍历，来进行定义中给出的翻译 一遍扫描 先产生暂时没有填写目标标号的转移指令 对于每一条这样的指令作适当的记录 一旦目标标号被确定下来，再将它“回填”到相应的指令中 假设实现三地址代码时采用四元式形式实现，并且假定： (jnz , a ,- , p ) 表示 if a goto p (jrop, x , y, p ) 表示 if x rop y goto p (j , -, - , p ) 表示 goto p,71,布尔表达式文法： （1）EE1 or M E2 （2） |E1 and M E2 （3） |not E1 （4） |(E1) （5） |id1 relop id2 （6） |true （7） |false （8）M 插入非终结符号M是为了引入一个语义动作，以便在适当时候获得即将产生的下一个四元式的索引，或说四元式的标号,72,翻译模式用到如下三个函数： makelist(i)：创建一个仅包含i的新表，i是四元式数组的一个索引（下标），或说i是四元式代码序列的一个标号 merge(p1，p2)：连接由指针p1和p2指向的两个表并且返回一个指向连接后的表的指针 backpatch(p，i)：把i作为目标标号回填到p所指向的表中的每一个转移指令中去 此处的“表”都是为“反填”所拉的链,73,EE1 OR ME2 backpatch(E1.falselist,M.quad); E.truelist:=merge(E1.truelist,E2.truelist); E.falselist:=E2.falselist EE1 AND ME2 backpatch(E1.truelist,M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist);,使用一遍扫描的布尔表达式的翻译模式,74,Enot E1 E.truelist:=E1.falselist; E.falselist:=E1.truelist E ( E1 ) E.truelist:= E1.truelist; E.falselist:=E1.falselist E id1 relop id2 E.truelist:= makelist(nextquad); E.falselist:= makelist(nextquad+1); emit(j relop.op , id1.place , id2.place , 0); emit(j,-,-,0) M M.quad:=nextquad ,75,例7.4 重新考虑表达式ab or cd and ef 一棵作了注释的分析树如下图所示：,E.t=100,104 E.f=103,105,E.t=100 E.f=101,E.t=104 E.f=103,105,or,M.q=102,a,b,E.t=102 E.f=103,E.t=104 E.f=105,and,M.q=104,c,e,d,f,76,依次分析，得到如下四元式： 100 ： (j,a,b,0) 101 ： (j,-,-,0) 102 ： (j,c,d,0) 103 ： (j,-,-,0) 104 ： (j,e,f,0) 105 ： (j,-,-,0),经过回填得到： 100 ： (j,a,b,0) 101 ： (j,-,-,102) 102 ： (j,c,d,104) 103 ： (j,-,-,0) 104 ： (j,e,f,0) 105 ： (j,-,-,0),当知道了条件为真时和条件为假时分别应做哪些事时就可以进行回填,77,7.5 控制语句的翻译,7.5.1 控制流语句 7.5.2 标号和goto语句 7.5.3 CASE语句的翻译,78,文法： Sif E then S1 | if E then S1 else S2 | while E do S1,E.code,S1.code,E.true:,.,E.false:,(a) if-then,to E.true,to E.false,代码结构：,7.5.1 控制流语句,79,E.code,S1.code,E.true:,S2.code,E.false:,goto S.next,.,S.next:,to E.true,to E.false,(b)if-then-else,E.code,S1.code,E.true:,E.false:,goto S.begin,.,S.begin:,to E.false,to E.true,(c )while-do,80,产生式,语义规则,Sif E then S1,E.true:=newlabel; E.false:=S.next; S1.next:=S.next S.code:=E.code| gen(E.true:)|S1.code,控制流语句的属性文法,81,Sif 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(gotoS.next)| gen(E.false:)|S2.code,82,Swhile E do S1,S.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(gotoS.begin),83,例7.5 考虑如下语句： 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:=yz x：t2 goto L1 Lnext：,84,文法： （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为一个布尔表达式,使用回填翻译控制流语句,85,(1) Sif E then M1 S1 N else M2 S2,E.code,S1.code,E.true:,S2.code,E.false:,goto S.next,.,S.next:,to E.true,to E.false,M1处反填E.truelist M2处反填E.falselist N处生成goto S.next,控制流语句的翻译模式,86,backpatch( E.truelist,M1.quad); backpatch(E.falselist,M2.quad); S.nextlist:=merge(S1.nextlist,N.nextlist, S2.nextlist) (2) N N.nextlist:=makelist(nextquad); emit(j,-,-,-) (3) M M.quad:=nextquad; (4) Sif E then M S1 backpatch( E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist),87,(5) Swhile M1 E do M2 S1 M1处生成标号S.begin ，反填S1.nextlist。 M2处反填E.truelist。 S.nextlist:=E.falselist 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( ),88,先记录要回填的转移指令地址，在适当的时候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序的控制流程 例7.6 使用自底向上的分析法生成四元式目标 代码，其中A1，A2和A3 均表示赋值语句。 if ab or cd and ef then A1 else A2； while ab do A3,(8) LL1;M S backpatch(L1.nextlist,M.quad); L.nextlist:=S.nextlist (9) LS L.nextlist:=S.nextlist