语义分析和中间代码生成.pptx

,第二级,第三级,第四级,第五级,第,4,章 语义分析和中间代码生成,4.1,概 述,4.1.1,语义分析的概念,一个源程序经过词法分析、语法分析之后，表明该源程序在书写上是正确的，并且符合程序语言所规定的语法。但是语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接下来的工作是语义分析，即审查每个语法成分的静态语义。如果静态语义正确，则生成与该语言成分等效的中间代码，或者直接生成目标代码。,直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的翻译，而中间代码的优点是使编译结构在逻辑上更为简单明确，特别是使目标代码的优化比较容易实现。,如同在进行词法分析、语法分析的同时也进行着词法检查、语法检查一样，在语义分析时也必然要进行语义检查。动态语义检查需要生成相应的目标代码，它是在运行时进行的；静态语义检查是在编译时完成的，它涉及以下几个方面：,(1),类型检查，如参与运算的操作数其类型应相容。,(2),控制流检查，用以保证控制语句有合法的转向点。如,C,语言中不允许,goto,语句转入,case,语句流；,break,语句需寻找包含它的最小,switch,、,while,或,for,语句方可找到转向点，否则出错。,(3),一致性检查，如在相同作用域中标识符只能说明一次、,case,语句的标号不能相同等。,语义分析阶段只产生中间代码而不生成目标代码的方法使编译程序的开发变得较为容易，但语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述。由于语义是上下文有关的，因此语义的形式化描述是非常困难的，目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。,4.1.2,语法制导翻译方法,语法制导翻译的方法就是为每个产生式配上一个翻译子程序,(,称语义动作或语义子程序,),，并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中，当一个产生式获得匹配,(,对于自上而下分析,),或用于归约,(,对于自下而上分析,),时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。,语法制导翻译分为自下而上语法制导翻译和自上而下语法制导翻译，我们重点介绍自下而上语法制导翻译。,假定有一个自下而上的,LR,分析器，我们可以把这个,LR,分析器的能力加以扩大，使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作；每个产生式的语义子程序执行之后，某些结果,(,语义信息,),必须作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。,此外，原,LR,分析器的分析栈也加以扩充，以便能够存放与文法符号相对应的语义值。这样，分析栈可以存放三类信息：分析状态、文法符号及文法符号对应的语义值。扩充后的分析栈如图,41,所示。,作为一个例子，我们考虑下面的文法及语义动作所执行的程序：,产生式 语义动作,(0)SE print valTOP,(1)EE,(1),+E,(2),valTOP=valTOP+valTOP+2,(2)EE,(1),*E,(2),valTOP=valTOP*valTOP+2,(3)E(E,(1),)valTOP=valTOP+1,(4)Ei valTOP=lexval(,注：,lexval,为,i,的整型内部值,),这个文法的,LR,分析表见表,3.20,。,我们扩充分析栈工作的总控程序功能，使其在完成语法分析的同时也能完成语义分析工作,(,这时的语法分析栈已成为语义分析栈,),；即在用某一个规则进行归约之后，调用相应的语义子程序完成与所用产生式相应的语义动作，并将每次工作后的语义值保存在扩充后的“语义值”栈中。图,42,表示算术表达式,7,9*5#,的语法树及各结点值，而表,4.1,则给出了根据表,3.20,用,LR,语法制导翻译方法得到的该表达式的语义分析和计值过程。,图,41,扩充后的,LR,分析栈,图,42,语法制导翻译计算表达式,7,9*5#,的语法树,表,4.1,表达式,7,9*5#,的语义分析和计值过程,步骤,状态栈,符号栈,语义栈,输入串,主要动作,1,0,#,_,7,9*5#,s,3,2,03,#7,_ _,9*5#,r,4,3,01,#E,_7,9*5#,s,4,4,014,#E+,_7_,9*5#,s,3,5,0143,#E+9,_7_ _,*5#,r,4,6,0147,#E+E,_7_9,*5#,s,5,7,01475,#E+E*,_7_9_,5#,s,3,8,014753,#E+E*5,_7_9_ _,#,r,4,9,014758,#E+E*E,_7_9_5,#,r,2,10,0147,#E+E,_7_45,#,r,1,11,01,#E,_52,#,acc,4.2,属 性 文 法,4.2.1,文法的属性,属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。随着编译的进展，对语法分析产生的语法树进行语义分析，且分析的结果用中间代码描述出来。对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号,X,，该,X,可以是终结符或非终结符。根据语义处理的需要，在用产生式,AX,进行归约或推导时，应能准确而恰当地表达文法符号,X,在归约或推导时的不同特征。,例如，判断变量,X,的类型是否匹配，要用,X,的数据类型来描述；判断变量,X,是否存在，要用,X,的存储位置来描述；而对,X,的运算，则要用,X,的值来描述；因此，语义分析阶段引入,X,的属性，如,X.type,、,X.place,、,X.val,等来分别描述变量,X,的类型、存储位置以及值等不同的特征。,文法符号的属性可分为继承属性与综合属性两类。,继承属性用于“自上而下”传递信息。继承属性由相应语法树中结点的父结点属性计算得到，即沿语法树向下传递，由根结点到分枝,(,子,),结点，它反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序语言上下文的结构关系。,综合属性用于“自下而上”传递信息。综合属性由相应语法分析树中结点的分枝结点,(,即子结点,),属性计算得到，其传递方向与继承属性相反，即沿语法分析树向上传递，从分枝结点到根结点。,4.2.2,属性文法,属性文法是一种适用于定义语义的特殊文法，即在语言的文法中增加了属性的文法，它将文法符号的语义以“属性”的形式附加到各个文法的符号上,(,如上述与变量,X,相关联的属性,X.type,、,X.place,和,X.val,等,),，再根据产生式所包含的含义，给出每个文法符号属性的求值规则，从而形成一种带有语义属性的上下文无关文法，即属性文法。属性文法也是一种翻译文法，属性有助于更详细地指定文法中的代码生成动作。,例如，简单算术表达式求值的属性文法如下：,产生式 语义规则,(1)SE print(E.val),(2)EE,(1),+T,E.val=E,(1),.val+T.val,(3)ET E.val=T.val,(4)TT,(1),*FT.val=T,(1),.val*F.val,(5)TT,(1),T.val=T,(1),.val,(6)F(E)F.val=E.val,(7)Fi F.val=i.lexval,上面的一组产生式中，每一个非终结符都有一个属性,val,来表示整型值，如,E.val,表示,E,的整型值，而,i.lexval,则表示,i,的整型内部值。与产生式关联的每一个语义规则的左部符号,E,、,T,、,F,等的属性值的计算由其各自相应的右部符号决定，这种属性也称为综合属性。与产生式,SE,关联的语义规则是一个函数,print(E.val),，其功能是打印,E,产生式的值。,S,在语义规则中没有出现，可以理解为其属性是一个虚属性。,我们再举一例说明属性文法。一简单变量类型说明的文法,GD,如下：,GD,：,Dint Lfloat L,LL,idid,其对应的属性文法为：,产生式语义规则,(1)DTLL.in=T.type,(2)Tint,T.type=int,(3)TfloatT.type=float,(4)LL,(1),，,idL,(1),.in=L.in;addtype(id.entry,L.in),(5)Lidaddtype(id.entry,L.in),注意到与文法,GD,相应的说明语句形式可为,int id,1,，,id,2,，,id,n,或者,float id,1,，,id,2,，,id,n,非终结符,T,有一个综合属性,type,，其值为,int,或,float,。语义规则,L.in=T.type,表示,L.in,的属性值由相应说明语句指定的类型,T.type,决定；属性,L.in,被确定后将随语法树的逐步生成而传递到下边的有关结点使用，这种结点属性称为继承属性。由此可见，标识符的类型可以通过继承属性的复写规则来传递。例如，对输入串,int a,b,，根据上述的语义规则，可在其生成的语法树中看到用“”表示的属性传递情况，如图,43,所示。,图,43,属性信息传递情况示意,4.3,几种常见的中间语言,4.3.1,抽象语法树,抽象语法树也称图表示，是一种较为流行的中间语言表示形式。在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。抽象语法树不同于前述的语法树，它展示了一个操作过程并同时描述了源程序的层次结构。,注意，语法规则中包含的某些符号可能起标点符号作用也可能起解释作用。如赋值语句语法规则：,SV=e,其中的赋值号“,=”,仅起标点符号作用，其目的是把,V,与,e,分开；而条件语句语法规则：,Sif(e)S,1,;else S,2,其中的保留字符号,if,和,else,起注释作用，说明当布尔表达式,e,为真时执行,S,1,，否则执行,S,2,；而“；”仅起标点符号作用。可以看出，上述语句的本质部分是,V,、,e,和,S,i,。当把语法规则中本质部分抽象出来而将非本质部分去掉后，便得到抽象语法规则。这种去掉不必要信息的做法可以获得高效的源程序中间表示。上述语句的抽象语法规则为：,(1),赋值语句：左部 表达式,(2),条件语句：表达式 语句,1,语句,2,与抽象语法相对应的语法树称为抽象语法树或抽象树，如赋值语句,x=ab*c,的抽象语法树如图,44(a),所示，而图,44(b),则是该赋值语句的普通语法树。,图,44 x=ab*c,的语法树,抽象语法树的一个显著特点是结构紧凑，容易构造且结点数较少。图,44(b),所示的普通语法树的结点为,14,个；而图,44(a),所示的抽象语法树的结点仅有,7,个，且每个内部结点最多只有两个分支，因此可以将每个赋值语句或表达式表示为一棵二叉树。对于含有多元运算的更为复杂的语法成分，相应的抽象语法树则为一棵多叉树，但我们总可以将其转变为一棵二叉树。,4.3.2,逆波兰表示法,逆波兰表示法是波兰逻辑学家卢卡西维奇,(Lukasiewicz),发明的一种表示表达式的方法，这种表示法把运算量,(,操作数,),写在前面，把运算符写在后面，因而又称后缀表示法。例如，把,a+b,写成,ab+,，把,a*(b+c),写成,abc+*,。,1,表达式的逆波兰表示,表达式,E,的后缀表示的递归定义如下：,(1),如果,E,是变量或常数，则,E,的后缀表示即,E,自身。,(2),如果,E,为,E,1,op E,2,形式，则它的后缀表示为,E,1,E,2,op,；其中,op,是二元运算符，而,E,1,、,E,2,分别又是,E,1,和,E,2,的后缀表示。若,op,为一元运算符，则视,E,1,和,E,1,为空。,(3),如果,E,为,(E,1,),形式，则,E,1,的后缀表示即为,E,的后缀表示。,上述递归定义的实质是：后缀表示中，操作数出现的顺序与原来一致，而运算符则按运算先后的顺序放入相应的操作数之后,(,即运算符先后的顺序发生了变化,),。这种表示已不再需要用括号来规定运算的顺序了。后缀表示中的计值用栈实现非常方便。一般的计值过程是自左至右扫描后缀表达式，每碰到运算量就把它推进栈，每碰到,K,目运算符就把它作用于栈顶的,K,个运算量，并用运算的结果,(,即一个运算量,),来取代栈顶的,K,个运算量。,2,程序语句的逆波兰表示,为了用逆波兰式表示一些控制语句，我们定义转移操作如下：,(1)BL,：转向某标号；,(2)BT,：条件为真时转移；,(3)BF,：条件为假时转移；,(4)BR,：无条件转移。,部分程序语句的逆波兰表示如下：,(1),赋值语句。赋值语句“,=”,的逆波兰表示为,=,例如，赋值语句“,x=a+b*c”,可按逆波兰式写为“,xabc*+=”,。,(2)GOTO,语句。转向语句“,GOTO”,的逆波兰表示为,BL,其中，“,BL”,为单目后缀运算符，“,”,则为,BL,的一个运算分量。,(3),条件语句。,BR,表示无条件转移单目后缀运算符。例如，“,BR”,表示无条件转移到“,”,处，这里的顺序号是,BR,的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号,(,即第几个单词,),，它不同于,GOTO,语句中的语句标号。,BT,和,BF,表示按条件转移的两个双目后缀运算符。例如：,BT,BF,分别表示当,e,为真或假时转移到顺序号处；其中，布尔表达式,e,的逆波兰式和顺序号是两个特殊的运算分量。若使用,BT,和,BF,两个运算符，则条件语句,if(e)S,1,;else S,2,的逆波兰式为：,BF,/*e,为假则转,S,2,的第一个单词的顺序号*,/,/*e,为真则执行,S,1,*/,BR,/*S,1,执行结束后无条件转出该条件语句*,/,(3),条件语句。,BR,表示无条件转移单目后缀运算符。例如，“,BR”,表示无条件转移到“,”,处，这里的顺序号是,BR,的一个特殊运算分量，用来表示逆波兰式中单词符号的顺序号,(,即第几个单词,),，它不同于,GOTO,语句中的语句标号。,BT,和,BF,表示按条件转移的两个双目后缀运算符。例如：,BT,BF,例如，条件语句,if(mn)k=i+1,；,else k=i1,的逆波兰式表示为,(1),(18),为单词编号,),：,(1)mn,(4)13BF,(6)ki1+=,(11)18BR,(13)ki1=,(18)if,语句的后继语句,此逆波兰式也可写在一行上，即,mn13BFki1+=18BRki1=,(4),循环语句。,for,循环语句为：,for(i=m,；,i=n,；,i+)S,；其中，,i,为循环控制变量，,m,为初值，,n,为终值，,S,为循环体。循环语句不能直接用逆波兰表示，因而将其展开为等价的条件语句后再用逆波兰表示，即,i=m,；,10,：,if(i=n),S,；,i=i+1,；,goto l0,4.3.3,三地址代码,1,三地址代码的形式,三地址代码语句的一般形式为,x=y op z,其中，,x,、,y,和,z,为名字、常量或编译时产生的临时变量；,op,为运算符，如定点运算符、浮点算符和逻辑运算符等。三地址代码的每条语句通常包含三个地址，两个用来存放运算对象，,一个用来存放运算结果。在实际实现中，用户定义的名字将由指向符号表中该名字项的指针所取代。由于三地址语句只含有一个运算符，因此多个运算符组成的表达式必须用三地址语句序列来表示，如表达式,x+y*z,的三地址代码为：,t,1,=y*z,t,2,=x+t,1,其中，,t,1,和,t,2,是编译时产生的临时变量。三地址代码是语法树的一种线性表示，如图,44(a),所示的语法树用三地址代码表示为：,t,1,=b*c,t,2,=a t,1,x=t,2,2,三地址语句的种类,作为中间语言的三地址语句非常类似于汇编代码，它可以有符号标号和各种控制流语句。常用的三地址语句有以下几种：,(1)x=y op z,形式的赋值语句，其中,op,为二目的算术运算符或逻辑运算符。,(2)x=op y,形式的赋值语句，其中,op,为一目运算符，如一目减,uminus,、逻辑否定,not,、移位运算符以及将定点数转换成浮点数的类型转换符。,(3)x=y,形式的赋值语句，将,y,的值赋给,。,(4),无条件转移语句,goto L,，即下一个将被执行的语句是标号为,L,的语句。,(5),条件转移语句,if x rop y goto L,，其中,rop,为关系运算符，如,、,、,=,等。若,x,和,y,满足关系,rop,就转去执行标号为,L,的语句，否则继续按顺序执行本语句的下一条语句。,(6),过程调用语句,par X,和,call P,n,。源程序中的过程调用语句,P(X,1,、,X,2,、,，,X,n,),可用下列三地址代码表示：,par X,1,par X,2,par X,n,call P,n,其中，整数,n,为实参个数。,过程返回语句为,return y,，其中,y,为过程返回值。,(7),变址赋值语句,x=yi,，其中,x,、,y,、,i,均代表数据对象，表示把从地址,y,开始的第,i,个地址单元中的值赋给,x,。,xi=y,则表示把,y,的值赋给从地址,x,开始的第,i,个地址单元。,(8),地址和指针赋值语句,x=&y,表示将,y,的地址赋给,x,，,y,可以是一个名字或一个临时变量，而,x,是指针名或临时变量；,x=*y,表示将,y,所指示的地址单元中的内容,(,值,),赋给,x,，,y,是一个指针或临时变量；*,x=y,表示指将,x,所指对象的值置为,y,的值。,3,三地址代码的具体实现,三地址代码是中间代码的一种抽象形式。在编译程序中，三地址代码语言的具体实现通常有三种表示方法：四元式、三元式和间接三元式。,1),四元式,四元式是具有四个域的记录结构，这四个域为,(op,，,arg1,，,arg2,，,result),其中，,op,为运算符；,arg1,、,arg2,及,result,为指针，它们可指向有关名字在符号表中的登记项或一临时变量,(,也可空缺,),。常用的三地址语句与相应的四元式对应如下：,x=y op z,对应,(op,y,z,x),x=y,对应,(uminus,y,_,x),x=y,对应,(=,y,_,x),par x1,对应,(par,x1,_,_),call P,对应,(call,_,_,P),goto L,对应,(j,_,_,L),if x rop y goto L,对应,(jrop,x,y,L),例如，赋值语句,a=b*(c+d),相应的四元式代码为：,(+,c,d,t,1,),(*,b,t,1,t,2,),(=,t,2,_,a),我们约定：凡只需一个运算量的算符一律使用,arg1,。此外，注意这样一个规则：如果,op,是一个算术或逻辑运算符，则,result,总是一个新引进的临时变量，它用来存放运算结果。由上例也可看出，四元式出现的顺序与表达式计值的顺序是一致的，四元式之间的联系是通过临时变量实现的。四元式由于其表示更接近程序设计的习惯而成为一种普遍采用的中间代码形式。,2),三元式,三元式是具有三个域的记录结构，这三个域为,(op,，,arg1,，,arg2),其中，,op,为运算符；,arg1,、,arg2,既可指向有关名字在符号表中的登记项或临时变量，也可以指向三元式表中的某一个三元式。例如，相应于赋值语句,a=(b+c)*(b+c),的三元式代码为：,(+,b,c),(+,b,c),(*,),(=,a,),上述三元式表示的结果与的结果相乘。由上例可知，三元式出现的先后顺序和表达式各部分的计值顺序是一致的。,3),间接三元式,在三元式代码表的基础上另设一张表，该表按运算的次序列出相应三元式在三元式表中的位置，这张表称为间接码表。三元式表只记录不同的三元式语句，而间接码表则表示由这些语句组成的运算次序。例如，赋值语句,a=(b+c)*(b+c),对应的三元式表与间接码表为：,三元式表：,(+,b,c),(*,),(=,a,),间接码表：,在三元式表示中，每个语句的位置同时有两个作用：一是可作为该三元式的结果被其它三元式引用；二是三元式位置顺序即为运算顺序。在代码优化阶段，需要调整三元式的运算顺序时会遇到困难，这是因为三元式中的,arg1,、,arg2,也可以是指向某些三元式位置的指针，当这些三元式的位置顺序发生变化时，含有指向这些三元式位置指针的相关三元式也需随之改变指针值。因此，变动一张三元式表是很困难的。,对四元式来说，引用另一语句的结果可以通过引用该语句的,result(,通常是一个临时变量,),来实现，而间接三元式则通过间接码表来描述语句的运算次序。这两种方法都不存在语句位置同时具有两种功能的现象，代码调整时要做的改动只是局部的，因此，当需要对中间代码表进行优化处理时，四元式与间接三元式都比三元式方便得多。,4.4,表达式及赋值语句的翻译,4.4.1,简单算术表达式和赋值语句的翻译,简单算术表达式是一种仅含简单变量的算术表达式；简单变量是指普通变量和常数，但不含数组元素及结构引用等复合型数据结构。简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四元式形式，这些翻译方法稍加修改也可用于产生三元式或间接三元式。,考虑以下文法,GA,：,Ai=E,EE+EE*EE(E)i,在此，非终结符,A,代表“赋值句”。文法,GA,虽然是一个二义文法，但通过确定运算符的结合性及规定运算符的优先级就可避免二义性的发生。,为了实现由表达式到四元式的翻译，需要给文法加上语义子程序，以便在进行归约的同时执行对应的语义子程序。语义子程序所涉及的语义变量、语义过程及函数说明如下：,(1),对非终结符,E,定义语义变量,E.place,，即用,E.place,表示存放,E,值的变量名在符号表中的入口地址或临时变量名的整数码。,(2),定义语义函数,newtemp(),，即每次调用,newtemp(),时都将回送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为,T,1,、,T,2,、,。,(3),定义语义过程,emit(op,arg1,arg2,result),emit,的功能是产生一个四元式并填入四元式表中。,(4),定义语义函数,lookup(i.name),，其功能是审查,i.name,是否出现在符号表中，是则返回,i.name,在符号表的入口指针，否则返回,NULL,。,使用上述语义变量、过程和函数，可写出文法,GA,中的每一个产生式的语义子程序。,(1)Ai=E p=lookup(i.name);,if(p=NULL)error();,else emit(=,E.place,_,P);,(2)EE,(1),+E,(2),E.place=newtemp();,emit(+,E,(1),.place,E,(2),.place,E.place);,(3)EE,(1),*E,(2),E.place=newtemp();,emit(*,E,(1),.place,E,(2),.place,E.place);,(4)EE,(1),E.place=newtemp();,emit(uminus,E,(1),.place,_,E.place);,(5)E(E,(1),)E.place=E,(1),.place;,(6)Ei,p=lookup(i.name);if(p!=NULL)E.place=p;,/*,另一种表示为,E.place=entry(i)*/,else error();,例,4.1,试分析赋值语句,X=B*(C+D),的语法制导翻译过程。,解答,赋值语句,X=B*(C+D),的语法制导翻译过程如表,4.2,所示,(,加工分析过程参考表,4.1),。,表,4.2,赋值语句,X=B*(C+D),的翻译过程,输入串,归约产生式,符号栈,语义栈,(place),四元式,X=B*(C+D)#,#,_,=B*(C+D)#,(6),#i,_X,B*(C+D)#,#i=,_X_,B*(C+D)#,#i=,_X_ _,*(C+D)#,(6),#i=i,_X_ _B,*(C+D)#,(4),#i=E,_X_ _B,(uminus,B,_,T,1,),*(C+D)#,#i=E,_X_T,1,(C+D)#,#i=E*,_X_T,1,_,C+D)#,#i=E*(,_X_T,1,_ _,+D)#,(6),#i=E*(i,_X_T,1,_ _C,+D)#,#i=E*(E,_X_T,1,_ _C,D)#,#i=E*(E+,_X_T,1,_ _C_,)#,(6),#i=E*(E+i,_X_T,1,_ _C,_,D,)#,(2),#i=E*(E+E,_X_T,1,_ _C,_,D,(+,C,D,T,2,),)#,#i=E*(E,_X_T,1,_ _T,2,#,(5),#i=E*(E),_X_T,1,_ _T,2,_,#,(3),#i=E*E,_X_T,1,_T,2,(*,T,1,T,2,T,3,),#,(1),#i=E,_X_T,3,(=,T,3,_,X),#,#A,_X,4.4.2,布尔表达式的翻译,在程序语言中，布尔表达式一般由运算符与运算对象组成。布尔表达式的运算符为布尔运算符，即、，或为,not,、,and,和,or(,注：,C,语言中为！、,&,和,|),，其运算对象为布尔变量，也可为常量或关系表达式。关系表达式的运算对象为算术表达式，其运算符为关系运算符,、,=,、,等。关系运算符的优先级相同但不得结合，其运算优先级低于任何算术运算符。布尔运算符的运算顺序一般为、，且和服从左结合，,布尔算符的运算优先级低于任何关系运算符,(,注意，此处的运算优先级约定不同于,C,语言,),。此外，对布尔运算、关系运算、算术运算的运算对象的类型可不区分布尔型或算术型，假定不同类型的变换工作将在需要时强制执行。为简单起见，我们遵循以上运算约定讨论下述文法,GE,生成的布尔表达式：,GE,：,EEEEEE(E)ii rop i,另一种方法是根据布尔运算的特点实施某种优化，即不必一步一步地计算布尔表达式中所有运算对象的值，而是省略不影响运算结果的运算。例如，在计算,AB,时，若计算出的,A,值为,1,，则,B,值就无需再计算了；因为不管,B,的结果是什么，,AB,的值都为,1,。同理，在计算,AB,时若发现,A,值为,0,，则,B,值也无需计算，,AB,的值一定为,0,。,在后面的论述中，我们假定函数过程的工作不出现上述的副作用情况。,如何确定一个表达式的真假出口呢？考虑表达式,E,(1),E,(2),，若,E,(1),为真，则立即知道,E,也为真，因此，,E,(1),的真出口也就是整个,E,的真出口；若,E,(1),为假，则,E,(2),必须被计值，此时,E,(2),的第一个四元式就是,E,(1),的假出口。当然，,E,(2),的真假出口也就是整个,E,的真假出口。类似的考虑适用于对,E,(1),E,(2),的翻译。我们将,E,(1),E,(2),和,E,(1),E,(2),的翻译用图,45,表示，而对形如,E,(1),的表达式则只需调换,E,(1),的真假出口就可得到该表达式,E,的真假出口。,图,45 E,(1),E,(2),和,E,(1),E,(2),的翻译图,(a)E,(1),E,(2),；,(b)E,(1),E,(2),在自下而上的分析过程中，一个布尔式的真假出口往往不能在产生四元式的同时就填上，我们只好把这种未完成的四元式的地址,(,编号,),作为,E,的语义值暂存起来，待到整个表达式的四元式产生完毕之后，再来填写这个未填入的转移目标。,对于每个非终结符,E,，我们需要为它赋予两个语义值,E.tc,和,E.fc,，以分别记录,E,所对应的四元式需要回填“真”、“假”出口的四元式地址所构成的链。这是因为在翻译过程中，常常会出现若干转移四元式转向同一个目标但目标位置又未确定的情况，此时可用“拉链”的方法将这些四元式链接起来，待获得转移目标的四元式地址时再进行返填。例如，假定,E,的四元式需要回填“真”出口的有,p,、,q,、,r,这三个四元式，则它们可链接成如图,46,所示的一条真值链,(,记作,tc),。,图,46,拉链法链接四元式示意,为了处理,E.tc,和,E.fc,这两项语义值，我们需要引入如下的语义变量和函数：,(1)nxq,：始终指向下一条将要产生的四元式的地址,(,序号,),，其初值为,1,。每当执行一次,emit,语句后，,nxq,自动增,1,。,(2)merge(p,1,p,2,),：把以,p,1,和,p,2,为链首的两条链合并为一条以,p,2,为链首的链,(,即返回链首值,p,2,),。,(3)Backpatch(p,t),：把链首,p,所链接的每个四元式的第四区段,(,即,result),都改写为地址,t,。,merge(),函数如下：,merge(p,1,，,p,2,),if(p,2,=0)return(p,1,);,else,p=p,2,;,while(,四元式,p,的第四区段内容不为,0),p=,四元式,p,的第四区段内容；,把,p,1,填进四元式,p,的第四区段；,return(p,2,);,Backpatch(),函数如下：,Backpatch(p,t),Q=p;,while(Q!=0),q=,四元式,Q,的第四区段内容；,把,t,填进四元式,Q,的第四区段；,Q=q;,为了便于实现布尔表达式的语法制导翻译，并在扫描到“”与“”时能及时回填一些已经确定了的待填转移目标，我们将前述文法,GE,改写为下面的文法,GE,，以利于编制相应的语义子程序：,GE,：,EE,A,EE,B,EE(E)ii rop i,E,A,E,E,B,E,这时，文法,GE,的每个产生式和相应的语义子程序如下：,(1)Ei E.tc=nxq;E.fc=nxq+1;,emit(jnz,entry(i),_,0);,emit(j,_,_,0);,(2)Ei,(1),rop i,(2),E.tc=nxq;E.fc=nxq+1;,emit(jrop,entry(i,(1),),entry(i,(2),),0);,emit(j,_,_,0);,(3)E(E,(1),)E.tc=E,(1),.tc;E.fc=E,(1),.fc;,(4)EE,(1),E.tc=E,(1),.fc;E.fc=E,(1),.tc;,(5)E,A,E,(1),Backpatch(E,(1),.tc,nxq);,E,A,.fc=E,(1),.fc;,(6)EE,A,E,(2),E.tc=E,(2),.tc;,E.fc=merge(E,A,.fc,，,E,(2),.fc);,(7)E,B,E,(1),Backpatch(E,(1),.fc,，,nxq);,E,B,.tc=E,(1),.tc;,(8)EE,B,E,(2),E.fc=E,(2),.fc;,E.tc=merge(E,B,.tc,，,E,(2),.tc);,例,4.2,试给出布尔表达式,abcd,作为控制条件的四元式中间代码。,解答,设四元式序号从,100,开始，则布尔表达式,abcd,的分析过程如图,47,所示。,图,47,表达式,abcd,分析示意,即：,100(jnz,，,a,，,_,，,102),101(j,，,_,，,_,，,104),102(jnz,，,b,，,_,，,106),103(j,，,_,，,_,，,104),104(j,，,c,，,d,，,106),105(j,，,_,，,_,，,q),T:106,F:q,当然，我们也可以通过图,48,的分析得到上述四元式序列。,由例,4.2,可知，每一个布尔变量,a,都对应一真一假两个四元式，并且格式是固定的，即,(jnz,，,a,，,_,，,0),/*a,为布尔变量*,/,(j,，,_,，,_,，,0),而每一个关系表达式同样对应一真一假两个四元式，其格式也是固定的，即,(jrop,，,X,，,Y,，,0),/*X,、,Y,为关系运算符两侧的变量或值*,/,(j,，,_,，,_,，,0),图,48 abcd,的翻译图,4.5,控制语句的翻译,在源程序中，控制语句用于实现程序流程的控制。一般程序流程控制可分为下面三种基本结构：,(1),顺序结构，一般用复合语句实现；,(2),选择结构，用,if,和,case,等语句实现；,(3),循环结构，用,for,、,while,、,do(,即,repeat),等语句实现。,4.5.1,条件语句,if,的翻译,1,条件语句,if,的代码结构,我们按下面的条件语句,if,的模式进行讨论：,if(E)S,1,;else S,2,条件语句,if(E);else S,2,中布尔表达式,E,的作用仅在于控制对,S,1,和,S,2,的选择，因此可将作为转移条件的布尔式,E,赋予两种“出口”：一是“真”出口，出向,S,1,；一是“假”出口，出向,S,2,。于是，条件语句可以翻译成如图,49,所示的代码结构。,图,49,条件语句,if(E)S,1,;else S,2,的代码结构,我们知道，非终结符,E,具有两项语义值,E.tc,和,E.fc,，它们分别指出了尚待回填真假出口的四元式串。,E,的“真”出口只有在扫描完布尔表达式,E,后的“,)”,时才能知道，而它的“假”出口则需要处理过,S,1,之后并且到,else,时才能明确。这就是说，必须把,E.fc,的值传下去，以便到达相应的,else,时才进行回填。,S,1,语句执行完就意味着整个,if-else,语句也已执行完毕，因此，,在,S,1,的编码之后应产生一条无条件转移指令，这条转移指令将导致程序控制离开整个,if-else,语句。但是，在完成,S,2,的翻译之前，这条无条件转移指令的转移目标是不知道的，甚至在翻译完,S,2,之后仍无法确定，这种情形是由语句的嵌套性所引起的。例如下面的语句：,if(E,1,)if(E,2,)S,1,;else S,2,;else S,3,在,S,1,代码之后的那条无条件转移指令不仅应跨越,S,2,，而且应跨越,S,3,。这也就是说，转移目标的确定和语句所处的环境密切相关。,2,条件语句,if,的文法和语义子程序的设计,条件语句,if,的文法,GS,如下：,GS,：,Sif(E)S,(1),Sif(E)S,(1),;else S,(2),为了在扫描条件语句过程中不失时机地处理和回填有关信息，可将,GS,改写为如下的,GS,：,GS,：,(1)SCS,(1),(2)Cif(E),(3)ST,p,S,(2),(4)T,P,CS,(1),;else,根据程序语言的处理顺序，首先用产生式,(2)Cif(E),进行归约，这时,E,的真出口即为,E,所生成四元式序列后的下一个地址。因此，将“,)”,后的第一个四元式地址回填至,E,的真出口，,E,的假出口地址则作为待填信息放在,C,的语义变量,C.chain,中，即：,Cif(E)Backpatch(E.tc,nxq);,C.chain=E.fc;,接下来用产生式,(1)SCS,(1),继续向上归约。这时已经处理到,Sif(E)S,(1),，由于归约时,E,的真出口已经处理，而,E,的假出口,(,即语句,S,的出口,),同时是语句,S,(1),的出口，,但此时语句,S,的出口地址未定，故将,C.chain,和,S,(1),.chain,一起作为,S,的待填信息链用函数,merge,链在一起保留在,S,的语义值,S.chain,中，即有,SCS,(1),S.chain=merge(C.chain,S,(1),.chain),如果此时条件语句为不含,else,的条件句，则在产生式,(1),、,(2),归约为,S,后即可以用下一个将要产生的四元式地址,(,即,S,的出口地址,),来回填,S,的出口地址链,(,即,S.chain),；如果此时条件语句为,if-else,形式，则继续用产生式,(4)T,P,CS,(1),;else,归约。,用,T,p,CS,(1),;else,