编译原理第7章课件

编译原理,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,*,页,单击此处编辑母版标题样式,语义分析和中间代码产生,第七章 语义分析和中间代码生成,第七章 语义分析和中间代码生成,紧接在词法分析和语法分析之后，编译程序要做的工作就是进行静态语义检查和翻译。,静态语义检查,(1),类型检查,。如果操作符作用于不相容的操作数，编译程序必须报告出错信息。,(2),控制流检查,。控制流语句必须使控制转移到合法的地方。,(3),一致性检查,。在很多场合要求对象只能被定义一次。,(4),相关名字检查,。,其它如名字的作用域分析等。,紧接在词法分析和语法分析之后，编译程序要做的工作就是进行静态,使用中间语言的好处,(1),便于进行与机器无关的代码优化工作；,(2),使编译程序改变目标机更容易；,(3),使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰。,使用中间语言的好处,编译原理第7章课件,本章内容目录,中间语言,后缀式,图表示法,三地址代码,说明语句,过程中的说明谙旬,保留作用域信息,记录中的域名,赋值语句的翻译,简单算术表达式及赋值语句,数组元素的引用,布尔表达式的翻译,数值表示法,作为条件控制的布尔式翻译,控制语句的翻译,本章内容目录中间语言赋值语句的翻译,中间语言,几种常见的中间语言形式,后缀式,三地址代码,（包括三元式、四元式、间接三元式）,DAG,图表示,中间语言 几种常见的中间语言形式,后缀式,后缀式表示法又称,逆波兰表示法,。,这种表示法是把运算量（操作数）写在前面，把算符写在后面（后缀）。,例如，把,a,十,b,写成,ab,，把,a*b,写成,ab*,。,后缀式 后缀式表示法又称逆波兰表示法。,一个表达式,E,的后缀形式,(1),如果,E,是一个变量或常量，则,E,的后缀式是,E,自身。,(2),如果,E,是,E1 op E2,形式的表达式，这里,op,是任何二元操作符，则,E,的后缀式为,E1,E2op,，这里,E1,和,E2,分别为,E1,和,E2,的后缀式。,(3),如果,E,是（,E1,）形式的表达式，则,E1,的后缀式就是,E,的后缀式。,后缀式表示法用不着使用括号。根据运算量和算符出现的先后位置，以及每个算符的目数，就完全决定了一个表达式的分解。,一个表达式E的后缀形式(1)如果E是一个变量或常量，则E的后,只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它正确进行唯一分解。,只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都,图表示法,包括,DAG,与抽象语法树,无循环有向图,（,Directed Acycli Graph,简称,DAG,）。,与抽象语法树一样，对表达式中的每个子表达式，,DAG,中都有一个结点。一,个内部结点代表一个操作符,，它的孩子代表操作数。,与抽象语法树不同的是，在一个,DAG,中代公,共子表达式的结点具有多个父结点,，而在一棵抽象语法树中公共子表达式被表示为重复的子树。,图表示法 包括DAG与抽象语法树,例如，表达式,a+a*(b-c)+(b-c),*,d,例如，表达式 a+a*(b-c)+(b-c)*d,例如，表达式,a+a*(b-c)+(b-c),*,d,例如，表达式 a+a*(b-c)+(b-c)*d,编译原理第7章课件,编译原理第7章课件,后缀式即是,对抽象语法树,的,后续遍历序列,例：上图中的抽象语法树的后缀式是：,a b c uminus * b c uminu *+ assign,抽象语法树的边没有显式地出现在后缀式中，这些边可以根据结点出现的次序及表示操作符的结点要求操作数的个数还原出来。,后缀式即是对抽象语法树的后续遍历序列,编译原理第7章课件,编译原理第7章课件,三地址代码,三地址代码是由下面一般形式的语句构成的序列：,x,：,= y op z,其中,x,y,z,为,名字、常数,或编译时产生的,临时变量,；,op,代表,运算符号,如定点运算符、浮点运算符、逻辑运算符等等。每个语句的右边只能有一个运算符。,例如，源语言表达式,x,y*z,可以被翻译为如下语句序列：,T1,：,y*z,T2,：,x,T1,其中，,Tl,，,T2,为编译时产生的临时变量。,三地址代码 三地址代码是由下面一般形式的语句构成的序列：,三地址代码可以看成是抽象语法树或,DAG,的一种线性表示。,三地址代码可以看成是抽象语法树或DAG的一种线性表示。,三地址语句,类似于汇编语言代码,。语句可以带有符号标号，而且存在各种控制流语句。符号标号代表存放中间代码的数组中三地址代码语句的下标。,下面列出所使用的三地址语句的种类。,（,1),形如,x:,y op z,的赋值语句，其中,op,为二元算术算符或逻辑算符。,(2),形如,x:,op y,的赎值语句，其中,op,为一元算符，如一元减,ununus,逻辑非,not,移位算符及转换算符（如将定点数转换成浮点数）。,(3),形如,x:=y,的复制语句，它将,y,的值赋给,x,。,(4),形如,goto L,的无条件转移语句，即下一条将被执行的语句是带标号,L,的三地址语句。,三地址语句类似于汇编语言代码。语句可以带有符号标号，而且存在,(5),形如,if x relop y goto L,或,if a goto L,的条件转移语句。,第一种形式语句施用关系运算符号,relop,（如，,=,等等）于,x,和,y,若,x,与,y,满足关系,relop,那么下面就执行带标号,L,的语句，否则下面就继续执行,if,语句之后的语句。,第二种形式的语句中，,a,为布尔变量或常量，若,a,为真，则执行带标号,L,的语句，否则执行后一条语句。,(6),用于过程调用的语句,param x,和,call p, n,以及返回语句,return y.,源程序中的过程调用语句,P(xl,，,x2,，,，,xn,）通常产生如下的三地址代码：,param x1,param x2,param xn,call p,n,其中,n,表示实参个数。过程返回语句,retum y,中,y,为过程返回的一个值。,(5)形如 if x relop y goto L 或,(7),形如,x:= yi,及,xi:=y,的索引赋值。前者把相对于地址,y,的后面第,i,个单元里的值赋给,x,。后者把,y,的值赋给相对于地址,x,后面的第,i,个单元。,（,8,）形如,x:=&y, x:=*y,和*,x:=y,的地址和指针赋值。其中第一个赋值语句把,y,的地址赋给,x,。假定,y,是个名字，或者是一个临时变量，代表一个具有左值的表达式，例如,Ai,j,；并且,x,是一个指针名字或临时变量。也就是说,x,的右值将被赋予对象,y,的左值。第二个 赋值语句,x:=*y,，假定,y,是一个指针或者是一个其右值为地址的临时变量。此语句执行的结果是把,y,所指示的地址单元里存放的内容赋给,x.,第三个赋值语句*,x:=y,将把,x,所指向的对象的右值赋给,y,的右值。,(7)形如x:= yi 及 xi:=y 的,在设计中间代码形式时，运算符的选择是非常重要的。,显然，,算符种类应足以用来实现源语言中的运算,。,一个小型算符集合较易于在新的目标机器上实现。,然而，用局限的指令集合会使某些源语言运算表示成中间形式时代码加长，从而需要在目标代码生成时做较多的工作以获得高效的代码。,在设计中间代码形式时，运算符的选择是非常重要的。,生成三地址代码时，,临时变量的名字,对应,抽象语法树的内部结点。,对于产生式,E,E1,E2,的左端的非终结符号,E,而言，它的经过计算得出的值往往放到一个新的临时变量,T,中。,一般说来，赋值语句,id:=E,的三地址代码包括：,对表达式,E,求值并置于变量,T,中，然后进行赋值,id. place:=T.,如果一个表达式,仅有一单个标识符,，例如,Y,则,由,Y,自身保留表达式的值。,生成三地址代码时，临时变量的名字对应抽象语法树的内部结点。,下表是为赋值语句生成三地址代码的,S-,属性文法定义。,如给定输入,a: = b*-c+b*-c,。,非终结符号,S,有,综合属性,S. code,它代表赋值,语句,S,的三地址代码,。,非终结符号,E,有如下两个属性：,（,1) E.place,表示存放,E,值的名字,；,(2) E.code,表示对,E,求值的,三地址语句序列,。,函数,newtemp,的功能是，,每次调用它时，将返回一个不同临时变量名字,，如,T1,，,T2,，,。为了方便，我们在表使用,gen(x,：,y +,z),表示生成三地址语句,x:=y,十,z,.,代替,x,y,或,z,出现的表达式在传递给,gen,时求值，用单引号括起来的运算符或操作数将保留引号里字面的符号。,下表是为赋值语句生成三地址代码的S-属性文法定义。,编译原理第7章课件,三地址语句可看成中间代码的一种抽象形式。,编译程序中，三地址代码语句的具体,实现可以用记录表示,，记录中包含表示运算符和操作数的域。,通常有三种表示方法：,四元式、三元式、间接三元式,。,三地址语句可看成中间代码的一种抽象形式。,四元式,一个四元式是一个带有,四个域的记录结构,，这四个域分别称为,op,、,arg1, arg2,及,result.,域,op,包含一个代表,运算符,的内部码。,三地址语句,x:,y op z,可表示为：将,y,置于,argl,域，置于,arg2,域，,x,置于,result,域，：为算符。,带有,一元运算符,的语句如：,x:= -y,或者,x:=y,的表示中不用,arg2.,而像,param,这样的运算符仅使用,argl,域。,条件和无条件转移语句将,目标标号置于,result,域中,。,四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为,三元式,为了避免把临时变量填入到符号表，可以通过,计算这个临时变量值的语句的位置,来引用这个临时变量。,这样表示三地址代码的记录只需三个域：,op,、,argl,和,arg2,三元式 为了避免把临时变量填入到符号表，可以通过计算这个临时,编译原理第7章课件,间接三元式,为了便于代码优化处理，有时不直接使用三元式表，而是另,设一张指示器（称为间接码表），,它将按,运算的先后顺序列出有关三元式在三元表中的位置,。,换句话说就是，用一张间接码表辅以三元式表的办法来表示中间代码。这种表示法称为间接三元式。,间接三元式 为了便于代码优化处理，有时不直接使用三元式表，而,例如，语句,X:=,（,A,B,）*,C,；,Y:=D,（,A,B),的间接三元式表示如表所示。,例如，语句,四元式与三元式和间接三元式作一些比较,四元式之间的联系是通过临时变量实现的。这一点和三元式不同。要更动一张三元表是很困难的，它意味着必须改变其中一系列指示器的值。但要更动四元式表是很容易的，因为调整四元式之间的相对位置并不意味着必须改变其中一系列指示器的值。因此，当需要对中间代码进行优化处理时，四元式比三元式要方便得多。,对优化这一点而言，四元式和间接三元式同样方便。,四元式与三元式和间接三元式作一些比较 四元式之间的联系是通过,说明语句,当考查一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。,对,每个局部名字,，我们都将在,符号表,中,建立相应的表项,，并填入有关的信息如类型、在存储器中的相对地址等。,相对地址是指对,静态数据区基址,或,活动记录中局部数据区基址的一个偏移量,。,说明语句 当考查一个过程或分程序的一系列说明语句时，便可为局,当产生中间代码地址时，对目标机一些情况做到心中有数是有好处的。,例如，假定在一个以字节编址的目标机上，整数必须存放在,4,的倍数的地址单元，那么，计算地址时就应以,4,的倍数增加。,当产生中间代码地址时，对目标机一些情况做到心中有数是有好处的,过程中的说明语句,在,C, Pascal,及,FORTRAN,等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把它们安排在一所数据区中。,从而需要一个,全程变量如,offset,来跟踪下一个可用的相对地址的位置。,过程中的说明语句 在C, Pascal及FORTRAN等语言,在下图关于说明语句的翻译模式中，非终结符号,P,产生一系列形如,id,：,T,的说明语句。,在处理第一条说明语句之前，先置,offset,为,0,，以后每次遇到一个新的名字，便将该,名字填入符号表中并置相对地址为当前,offset,之值,，,然后使,offset,加上该名字所表示的数据对象的域宽,。,在下图关于说明语句的翻译模式中，非终结符号P产生一系列形如i,编译原理第7章课件,过程,enter(name, type, offset,）用来把名字,name,填入到符号表中，并给出此名字的类型,type,及在过程数据区中的相对地址,offset,。,非终结符号,T,有两个,综合属性,T. type,和,T. width,，分别表示名字的类型和名字的域宽（即该类型名字所占用的存储单元个数）。,在图中,假定整数类型域宽为,4,；实数域宽为,8;,一个数组的域宽可以通过把数组元素数目与一个元素的域宽相乘获得；每个指针类型的域宽假定为,4.,过程enter(name, type, offset）用来把,如果把图中的第一条产生式及其语义动作写在一行，则对,offset,赋初值更明显，如下式所示：,P,offset:=0,D,（,7,1,）,前面曾谈到产生,的标记非终结符号，可以用它来重新改写上述产生式以便语义动作均出现在整个产生式的右边。,我们可采用标记非终结符号,M,来重写式（,7.1,）：,P,M D,M,offset:=0,如果把图中的第一条产生式及其语义动作写在一行，则对offse,保留作用域信息,允许,嵌套过程的语言,，对于每一个过程，其中局部名字的相对地址计算可以采用图,7.6,的方法。,而当遇到一个,嵌入的过程说明,时，则应当,暂停包围此过程的外围过程说明语句的处理,。这种方法可以通过加入到如下的语言把有关语义动作来说明。,P,D,D,D; D,|,id,：,T,|,proc id,：,D,；,S (7,2),由于我们当前的目标是考虑说明语句，因而对其中产生语句的非终结符号,S,及产生类型的非终结符号,T,的产生式我们没有给出。与图,7.6,中相同,T,有两个综合属性,type,和,width,。,保留作用域信息 允许嵌套过程的语言，对于每一个过程，其中局部,假定对于式,(7,2),的语言的每一个,过程都有一张独立的符号表,。这种符号表可用链表实现。当碰到过程说明,D,proc id,；,D,；,S,时，便,创建一张新的符号表,，并且把在,D,，中的所有说明项都填入此符号表内。,新表有一个,指针,指向,刚好包围该嵌入过程的外围过程的符号表,，由,id,表示的过程名字作为该外围过程的局,部名字,。,对图,7.6,处理变量说明的唯一修改是，要告诉,enter,在哪个符号表填入一项。,假定对于式(72)的语言的每一个过程都有一张独立的符号表。,在下面的语义规则中用到如下操作。,(1) mktable(previous),创建一张新符号表，并返回指向新表的一个指针。参数,previous,指向一张先前创建的符号表，譬如刚好包围嵌入过程的外围过程符号表。指针,previous,之值放在新符号表表头，表头中还可存放一些其它信息如过程嵌套深度等等。我们也可以按过程被说明的顺序对过程编号，并把这一编号填入表头。,(2) enter(table,，,name,，,type, offset,）在指针,table,指示的符号表中为名字,name,建立一个新项，并把类型,type,、相对地址,offset,填入到该项中。,(3) addwidth(table,width),在指针,table,指示的符号表表头中记录下该表中所有名字占用的总宽度。,(4) enterpcoc(table,，,name,，,newtable,）在指针,table,指示的符号表中为名字为,name,的过程建立一个新项。参数,newtable,指向过程,name,的符号表。,在下面的语义规则中用到如下操作。,在下图中的翻译模式给出了如何在一遍扫描中对数据进行处理，它使用了一个栈,tblptr,保存各外层过程的符号表指针。,当处理过程,partition,中的说明语句时，栈,tblprt,中将包括指向,sort, quicksort R partition,的符号表的指针。指向当前符号表的指针在栈顶。,另一个栈,offset,存放各嵌套过程的当前相对地址。,offset,的栈顶元素为当前被处理过程的下一个局部名字的相对地址。,在下图中的翻译模式给出了如何在一遍扫描中对数据进行处理，它使,编译原理第7章课件,编译原理第7章课件,编译原理第7章课件,记录中的域名,除了基本类型、指针和数组外，下述产生式使非终结符号,T,产生记录类型：,T,record D end,当遇到保留字,record,时，与标记非终结符号,L,相应的语义动作为记录中的各域名创建一张新的记录符号表。把指向该表的指针压人栈,tblptr,中，并把相对地址。压入栈,offset,中。,记录中的域名 除了基本类型、指针和数组外，下述产生式使非终结,编译原理第7章课件,赋值语句的翻译,赋值语句中的表达式的类型可以是整型、实型、数组和记录。,作为翻译赋值语句为三地址代码的一个部分，将讨论如何在符号表中查找名字及如何存取数组和记录的元素。,赋值语句的翻译 赋值语句中的表达式的类型可以是整型、实型、数,简单算术表达式及赋值语句,属性,id. name,表示,id,所代表的名字本身。,过程,lookup(id.nam,）检查是否在符号表中存在相应此名字的入口。如果有，则返回一个指向该表项的指针，否则，返回,nil,表示没有找到。,在语义动作中，调用过程,emit,将生成的三地址语句发送到输出文件中,简单算术表达式及赋值语句 属性id. name表示id所代表,假定赋值语句出现在如下文法形成的上下文环境中：,P,MD,M,D,D;D,|,id:T,|,proc id; N D;S,N,如果把这些产生式加到下面文法中，非终结符,P,就变为开始符号。,假定赋值语句出现在如下文法形成的上下文环境中：,编译原理第7章课件,数组元素的引用,现在讨论包含数组元素的表达式和赋值句的翻译问题。,数组在存储器中的存放方式决定了数组元素的地址计算法，从而也决定了应该产生什么样的中间代码。,数组元素的引用 现在讨论包含数组元素的表达式和赋值句的翻译问,若数组,A,的元素存放在一片连续单元里，则可以较容易地访问数组的每个元素。假设数组,A,每个元素宽度为,w,，则,Ai,这个元素的起始地址为,base+(i-low)*w,其中,: low,为数组下标的下界,base,是分配给数组的相对地址，即,base,为,A,的第一个元素,Alow,的相对地址。,变形整理得：,i*w,（,base,一,low * w),其中子表达式,C=base-low * w,可以在处理数组说明时计算出来。,我们假定,C,值存放在符号表中数组,A,的对应项中，则,Ai,相对地址可由,i*w,十,C,计算出来,.,若数组A的元素存放在一片连续单元里，则可以较容易地访问数组的,二维数组可以按行或按列存放。,若二维数组,A,按行存放，则可用如下公式计算,A il,，,i2 ,的相对地址：,base,（,i1-low1,）,*n2,i1-low2,）,*w,可以重写上述表达式为,(i1 * n2),i2)*w,(base-(low1 *n2),low2)*w),后一项子表达式,(base-,（,(low1* n2)+low,*,w2) *w),的值是可以在编译时确定的,.,二维数组可以按行或按列存放。,如果在文法中,id,出现的地方允许下面产生式中,L,出现，则可把数组元素引用加入到赋值语句中。,L,idElist| id,ElistElist,E|E,改写上述产生式为,L,Elist,|,id,Elist,Elist,，,E,|,id,E,如果在文法中id出现的地方允许下面产生式中L出现，则可把数组,Elist. ndim,记录,Elist,中的下标表达式的个数，即维数。,函数,limit( array ,j),返回,nj,即由,array,所指示的数组的第,j,维长度。最后,Elist. place,表示临时变量，用来临时存放由,Elist,中的下标表达式计算出来的值。,一个,Elist,可以产生一个,k-,维数组引用,Ai1,i2,ik,的前,m,维下标，并将生成计算下面式子的三地址代码：,（,（,(i1n2,i2) n3,i3) .,）,nm+im,利用如下的递归公式进行计算：,e1=i1,，,em,em-1*nm+im,于是，当,m=k,时将,ek,乘以元素域宽,w,便可计算出式中的第一个子项。,Elist. ndim记录Elist中的下标表达式的个数，即,下面考虑在赋值语句中加入数组元素之后的翻译模式，我们将把语义动作加入到如下文法中：,（,1,）,S,L:=E,(2,）,E,E,E,(3,）,E,（,E),(4,）,E,L,(5,）,L,Elist,(6) L,id,(7) Elist,Elist,，,E,(8,）,Elist,idE,下面考虑在赋值语句中加入数组元素之后的翻译模式，我们将把语义,在语义动作中由,emit,过程产生三地址代码。,若,L,是一个简单的名字，将生成一般的赋值；,否则，若,L,为数组元素引用，则生成对,L,所指示地址的索引赋值。,在语义动作中由emit过程产生三地址代码。,例：设,A,为一个,10*20,的数组，即,n1,10,，,n2=20,，并设,w,4,。对赋值语句,x,：,=Ay,，,z,的带注释的语法分析树见图,7.12.,该赋值语句被翻译成如下三地址语句序列：,T1:=y*20,T1:=T1+z,T2:=A-84,T3:=4*T1,T4:=T2T3,X:=T4,例：设A为一个10*20的数组，即n110，n2=20，并,编译原理第7章课件,布尔表达式的翻译,在程序设计语言中，布尔表达式有两个基本的作用：一个是用作计算逻辑值；另一个是用作控制流语句如,if - then, if then-else,和,while-do,等之中的条件表达式。,布尔表达式是用布尔运算符号（,and,，,or,，,not,）作用到布尔变量或关系表达式上而组成的。,关系表达式形如,E1relop E2,，其中,E1,和,E2,是算术表达式，,relop,为关系运算符（，,=,）。,考虑由下列文法产生的布尔表达式：,E,E or E,|,E and E,|,not E,|,（,E),|,id relop id,|,id,布尔表达式的翻译 在程序设计语言中，布尔表达式有两个基本的作,计算布尔表达式的值通常有两种办法。,一是如同计算算术表达式一样，一步不差地从表达式各部分的值计算出整个表达式的值。,另一种计算法是采取某种优化措施,:,把,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 true,计算布尔表达式的值通常有两种办法。,数值表示法,布尔表达式将从左到右按类似算术表达式的求值方法来计算。,例如，对于布尔表达式：,a or b and not c,将被翻译成如下三地址序列：,T1,：,not c,T2,：,=b and T1,T3,：,=a or T2,数值表示法 布尔表达式将从左到右按类似算术表达式的求值方法来,一个形如,a,b,的关系表达式可等价地写成,if a,b then 1 else 0,，并可将它翻译成如下三地址语句序列（我们假定语句序号从,100,开始）：,100: if a,b goto 103,101,：,T:=0,102: goto 104,103,：,T:,1,104:,一个形如ab的关系表达式可等价地写成,编译原理第7章课件,编译原理第7章课件,作为条件控制的布尔式翻译,出现在条件语句,if E then S1 else Sz2,中的布尔表达式,E,，它的作用仅在于控制对,S1,和,S2,的选择。只要能够完成这一使命，,E,的值就无须最终保留在某个临时单元之中。,因此，作为转移条件的布尔式,E,，我们可以赋予它两种“出口”。一是“真”出口，出向,S1,；一是“假”出口，出向,S2,。,作为条件控制的布尔式翻译 出现在条件语句,编译原理第7章课件,编译原理第7章课件,例,7,3,考虑如下表达式：,a,b or c,d and e,f,假定整个表达式的真假出口已分别置为,Ltrue,和,Lfalse,，则按表,7.7,的定义将生成如下的代码：,if a,b goto Ltrue,goto L1,L1,：,if c,d goto L2,goto Lfalse,L2,：,if e,f goto Ltrun,goto Lfalse,自然，这里的代码是未优化的，有冗余的指令。,例7 3考虑如下表达式：,下面讨论如何通过一遍扫描来产生布尔表达式的代码。,为了便于讨论，我们假设下面在实现三地址代码时，采用四元式形式实现。,把四元式存入一个数组中，数组下标就代表四元式的标号。,四元式,(jnz,a,-,p),表示,if a goto p,四元式,(jmp,x,y,p),表示,if x rop y goto p,四元式,(j,-,-,p),表示,goto p,下面讨论如何通过一遍扫描来产生布尔表达式的代码。,通过一遍扫描来产生布尔表达式和控制流语句的代码的主要问题在于，当生成某些转移语句时我们可能还不知道该语句将要转移到的标号究竟是什么。为了解决这个问题，我们可以在生成形式分支的跳转指令时暂时不确定跳转目标，而建立一个链表，把转向这个目标的跳转指令的标号键人这个链表。一旦目标确定之后再把它填人有关的跳转指令中。这种技术称为回填。,通过一遍扫描来产生布尔表达式和控制流语句的代码的主要问题在于,为非终结符,E,赋予两个综合属性,E,truelist,和,E,falselist,。,它们分别记录布尔表达式,E,所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表。,具体实现时，我们可以借助于需要回填的跳转四元式的第四区段来构造这种链,为非终结符E赋予两个综合属性Etruelist和Efal,（,1),变量,nextquad,它指向下一条将要产生但尚未形式的四元式的地址（标号）。,nextquad,的初值为,1,，每当执行一次,emit,之后，,nextquad,将自动增,1.,(2),函数,makelist(i),，它将创建一个仅含,i,的新链表，其中,i,是四元式数组的一个下标（标号）；函数返回指向这个链的指针。,(3),函数,merge(p1.p2),把以,p1 fn p2,为链首的两条链合并为一，作为函数值，回送合并后的链首。,(4),过程,backpatch(p, t),，其功能是完成“回填”，把,p,所链接的每个四元式的第四区段都填为,t.,（1)变量nextquad,它指向下一条将要产生但尚未形式的,现在，我们来构造一个翻译模式，使之能在自底向上的分析过程中生成布尔表达式的四元式代码。,我们在文法中插入了标记非终结符,M,，以便在适当的时候执行一个语义动作，记下下一个将要产生的四元式标号。我们使用的文法如下：,（,1,）,E,E1 or ME2,(2,）,|,E,1 and M E2,(3),|,not E1,(4),|,(E1,）,(5),|,id1 relop id2,(6),|,id,(7) M,现在，我们来构造一个翻译模式，使之能在自底向上的分析过程中生,例,7.4,重新考虑表达式,a,b or c,d and e,f.,一棵作了注释的分析树如图,7,16,所示。语义动作是在对树的深度优先遍历中完成的。由于所有的语义动作均出现在产生式的右端的终点，因而它们可以在自下而上的语法分析中随着对产生式的归约来完成。,按照上面所考虑的一些思想，构造出布尔表达式的翻译模式如下(如书,P190,),例7.4 重新考虑表达式按照上面所考虑的一些思想，构造出布,编译原理第7章课件,100 (j,，,a, b, 0),101,（,j,，,-,，,-,，,0),102 (j,，,c,，,d,，,104),103,（,j,，,-,，,-,，,0),104 (j,，,e, f, 0),105,（,i,，,-,，,-,，,0),100 (j,，,a, b, 0),101,（,j,，,-,，,-,，,102),102 (j,，,c, d, 104),103,（,i,，,-,，,-,，,0),104 (i,，,e, f, 0),105,（,i,，,-,，,-,，,0),100 (j，a, b, 0)100 (j，a, b,控制语句的翻译,控制流语句,if - then,，,if then-else, while-do,文法如下：,S,if E then S1,|,if E then S1 else S2,|,while E do S1,其中,E,为布尔表达式。,控制语句的翻译控制流语句,编译原理第7章课件,编译原理第7章课件,例,7.5,考虑如下语句,while ab do,if cd then x:=y+z,else x:=y-z,根据上述属性文法和赋值语句的翻译模式，将生成下列代码,L1: if ab goto L2,goto Lnext,L2: if cd goto L3,goto L4,L3: T1:=y+z;,x:=T1,goto L1,L4: T2:=y-z,x:=T2,goto L1,Lnext:,例7.5 考虑如下语句,例,7.6,按照上述的语义动作，加上前述关于赋值句和布尔表达式的翻译法，语句,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),107,例7.6 按照上述的语义动作，加上前述关于赋值句和布尔表达式,