第5章 语法制导翻译1

第五章语法制导翻译及中间代码生成,5.1引言,在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码，然后再将其翻译为目标代码。优点：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件本章要讨论的中间代码生成，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。目前常见的中间语言有逆波兰表示、三元式、四元式等等。中间代码生成与语言的语义密切相关，目前采用语法制导翻译来描述语义。方法:对文法中的每个产生式都附加一个语义动作或语义子程序,语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。,5.1引言(续),这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。文法符号X的语义信息我们称之为语义属性或简称为属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。,文法符号及其语义属性,例如,文法GE:产生式语义子程序EE(1)+TE.Val=E(1).val+T.val;ETE.Val=T.Val;TdigitT.Val=digit;为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个语义信息栈,5.2属性文法与属性翻译文法,语法制导翻译方法的实质，就是根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）处理语句或子程序，对所要完成的功能进行描述。产生式的语义是由组成该产生式的文法符号的语义所决定的。将这些语义以“属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则，从而形成一种附带有语义属性的前后文无关文法，即属性文法。语义属性主要有两类：综合属性和继承属性,例5.1简单赋值语句文法的属性文法,Primtype:用于描述在语法树中的本节点以及后继结点的类型Posttype：用于描述当其结果被其他节点用作操作数时期望具有的类型,翻译文法（续）,翻译文法的作用是，在进行语法分析时，无论是用产生式进行推导还是进行归约，只要遇到其中带有语义动作的花括号，就要求编译系统自动执行花括号内指定的语义动作，在执行完该动作之后才继续进行下一步的语法分析。,例：ExprTermExprExpr+TermWriteCode(“+”);Expr|TermFactorTermTerm*FactorWriteCode(“*”);Term|FactoroperandWriteCode(yytext);|(Expr),递归下降分析中的翻译文法,若用递归下降法进行语法分析，则与非终结符号Expr相对应的递归程序可扩充为：,intEprim()if(CurrentToken=+)if(Term()WriteCode(“+”);if(Eprim()return1;elsereturn0;if(CurrentToken=)|CurrenToken=#)return1;elsereturn0;,表达式属性翻译文法,例5.2表达式属性翻译文法：Program|$1=$2=NewName();ExprFreeName($0);ProgramExprTermExprExpr+$1=$2=NewName();Termprintf(“+,%s,%s,%sn”,$0,$,$0);FreeName($0);Expr|TermFactorTermTerm*$1=$2=NewName();Factorprintf(“*,%s,%s,%sn”,$0,$,$0);FreeName($0);Term|FactorNumberprintf(“:=,%s,-,%sn”,yytext,$);|,5.3常见中间语言简介,5.3.1逆波兰表示,波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。特点:表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序，因而又称为无括号式。下面我们对照地给出一些表达式的两种表示：中缀表示后缀表示A+BAB+A+B*CABC*+(A+B)*(C+D)AB+CD+*x/yz-d*exyz/de*-(a=0b3)(exy)a0=b3exy,逆波兰式的特点,在两种表示中，运算对象出现的顺序相同；在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。由于后缀表示中的各个运算是按顺序执行的，因此，它的计值需从左到右依次扫视表达式中的各个符号，每遇一运算对象，就把它压入栈顶暂存起来；每遇一个二元（或一元）运算符时，就取出栈顶的两个（或一个）运算对象进行相应的运算，并用运算结果去替换栈顶的这两（或一）个运算对象；继续扫视余留的符号，直到扫视完整个表达式为止。当上述过程结束时，整个表达式的值将留于栈顶。,5.3.2四元式和三元式,四元式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。四元式是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)其中，op为一个二元(也可是一元或零元)运算符;arg1,arg2分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言的赋值语句的形式：result:=arg1oparg2,四元式的格式,需要指出的是，每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。例如，表达式A+B*C可写为序列T1:=B*CT2:=A+T1当op为一元、零元运算（如无条件转移）时，arg2甚至arg1应缺省，即result:=oparg1或opresult；对应的一般形式为：(op,arg1,-,result)或(op,-,-,result)。,三元式,为了节省临时变量的开销，有时也可采用一种三元式结构来作为中间代码，其一般形式为(i)(op,arg1,arg2)其中，(i)为三元式的编号，也代表了该式的运算结果；op,arg1,arg2的含义与四元式类似，区别在于arg可以是某三元式的序号，表示用该三元式的结果作为运算对象。例如，对于赋值语句a:=-b*(c+d)，若用三元式表示，则可写成(U_minus,b,-)(+,c,d)(*,)(:=,a)式中的运算符U_minus表示一元减运算。,翻译程序中使用的辅助函数,我们以算术表达式到三元式的翻译为例，说明如何为各产生式设计语义动作。为此，先介绍若干翻译过程中要使用的辅助函数：intLookUp(char*Name)以Name查符号表，若查到则返回相应登记项的序号(1),否则返回0。intEnter(char*Name)以Name为名字在符号表中登录新的一项,返回值为该项的序号。intEntry(char*Name)以Name为名字查、填符号表:intEntry(char*Name)inti=LookUp(Name);if(i)returni;elsereturnEnter(Name);,翻译程序中使用的辅助函数(续),intTrip(intop,intarg1,intarg2)根据给定的参数产生一个三元式(op,arg1,arg2)并将它送入三元式表中，其返回值为表中序号。为区分参数arg表示的是三元式还是变量，约定当arg0表示变量在符号表中登记项序号；arg=0表示参数为空。,三元式和四元式之异同,在产生式8中，终结符iden的属性是它的词文yytext，用$1表示。每个非终结符都有一个属性，代表以该符号为根的语法树的一个子树的运算结果，该属性的取值可以是整型数，或为一三元式的序号，或为符号表项的序号。比较三元式和四元式这两种表示方法可以看出，无论在一个三元式序列还是四元式序列中，各个三元式或四元式都是按相应表达式的实际运算顺序出现的。其次，对同一表达式而言，所需的三元式或四元式的个数一般是相同的。三元式比四元式更能节省存储空间,但不利于优化.可通过引入一些表格提高使用三元式的效率(略,见P200-201),5.4简单算术表达式和赋值语句的翻译,约定E中仅含简单变量;全部变量同类型;翻译时不做语义检查.辅助定义intNewTemp(void)产生临时变量的函数，每次调用都定义一个新的临时变量。返回值为该变量的编号。X.PLACE文法符号X的属性，其值为整型(0表示在符号表中序号,0表示临时变量编号)intGEN(intOp,intArg1,intArg2,intResult)根据所给实参产生一个四元式：(Op,Arg1,Arg2,Result)，且送入四元式表中，返回值为该四元式的序号。Arg1或Arg2为零时表示该参数缺省,赋值语句属性翻译文法,1.StatementAssignSt2.AssignStVariable:=ExprGEN(:=,$3.PLACE,0,$1.PLACE);3.ExprExpr+Expr$.PLACE=NewTemp();GEN(+,$1.PLACE,$3.PLACE,$.PLACE);4.|Expr*Expr$.PLACE=NewTemp();GEN(*,$1.PLACE,$3.PLACE,$.PLACE);5.|(Expr)$.PLACE=$2.PLACE;6.|identifier$.PLACE=Entry($1);7.Variableidentifier$.PLACE=Entry($1);,5.5布尔表达式的翻译,布尔表达式是布尔运算量和逻辑运算符按一定语法规则组成的式子。逻辑运算符通常有、三种（在某些语言中，还有（等价）及（蕴含）等等）；逻辑运算对象可以是逻辑值（True或False）、布尔变量、关系表达式以及由括号括起来的布尔表达式。不论是布尔变量还是布尔表达式，都只能取逻辑值True或False。在计算机内通常用1（或非零整数）表示真值（True），用0表示假值(False)。关系表达式是形如E1RopE2的式子，其中E1和E2为简单算术表达式，Rop为关系运算符（,=,=,）。若E1和E2之值使该关系式成立，则此关系表达式之值为True，否则为False。,布尔表达式的等价解释,为了方便起见，下面我们仅讨论由文法EEE|EE|E|(E)|i|iRopi(5.1)对于布尔表达式的计值和翻译，可采用类似算术表达式的方式来进行。例如，对于布尔表达式ABC，可翻译为：(,B,C,T1)(,A,T1,T2)但是，对于一个布尔表达式而言，我们的目的仅仅是为了判定它的真假值。因此，有时只需计算它的一个子表达式，便能确定整个布尔表达式的真假值。例如，对于AB，只要知道A为真，则无论B取何值，表达式的结果一定为真。可见，对于三种常见逻辑运算，可作如下等价的解释：AB(A)?B:0(5.2)AB(A)?1:B(5.3)A(A)?0:1(5.4),布尔表达式的出口,对于布尔表达式A（B（CD）)，其等价的表述是A？1：（B？（C？0：1）？1：D）：0）显然，采用此种结构可产生更为有效的中间代码。这里需假定原布尔表达式的计算过程中不含有任何的副作用。在上式的计算中，根据A、B、C、D的取值不同，计算的结果以及运算的中止点亦不同。例如，当A=1（真）时，结果为1且中止于左边第一个1处。这样中止的点我们称为该布尔表达式的出口，同时，把使布尔表达式取值为真的出口称为真出口，反之称为假出口。对一个布尔表达式而言，它至少有一个真出口和一个假出口（当然可以有多个）。在用于控制流程的布尔表达式E的计算中，这些出口分别指出当E值为真和假时，控制所应转向的目标（即某一四元式的序号）。,控制语句中的布尔表达式,我们来研究包含在控制语句ifEthenS1elseS2或whileEdoS中的布尔表达式E的翻译。在这类语句中，布尔表达式仅用于对程序流程进行控制。根据这两种语句的语义，我们可右图(a)和(b)所示的结构进行翻译。在图(a)中可知，E的真、假出口分别为语句S1和S2的入口四元式的序号。图(b)中，E的真出口为S的入口，假出口为整个while语句的出口,布尔表达式真假值的确定,一个布尔表达式E的真假值的确定，是在语法翻译过程中，根据(5.2)-(5.4)等价解释式逐步进行的。例如，对于布尔表达式E=E(1)E(2)若E(1)为真，则E必为真，故E(1)的真出口必是E的真出口(之一);若E(1)为假，则E的真假值取决于E(2)的真假值，此时，需对E(2)进行计算，由此可见，E(1)的假出口应为E(2)对应的四元式的序号(E(2)的入口)，同时,E(2)的真、假出口也是E的真、假出口。类似地，可确定E(1)E(2)、E及更复杂的表达式的真、假出口。,条件语句的翻译结果,在设计布尔表达式翻译算法（即编写语义动作）时，可定义和使用如下三类四元式：(jnz,A1,p)当A1为真(非零)时，转向第p四元式；(jrop,A1,A2,p)当关系A1ropA2成立时，转向第p四元式；(j,p)无条件转向第p四元式例如，对于条件语句ifABCthenS1elseS2经翻译后，可得四元式序列：,(1)(jnz,A,-,5)(2)(j,-,-,3)(3)(j,B,C,5)(4)(j,-,-,p+1)(5)S1相应的四元式序列(p)(j,-,-,q)(p+1)S2相应的四元式序列(q)其中，表达式A的真出口为5（也是整个表达式的真出口），假出口为3（即表达式BC的第一四元式）；BC的真、假出口也分别是整个表达式的真、假出口。,拉链与回填,在自底向上的语法制导翻译时,在产生一个(无)条件转移四元式时,它所要转向的那个四元式有时尚未产生，故无法立即产生一个完全的控制转移四元式。例如，在上例中，在产生第一个四元式时，由于语句S1的中间代码尚未产生，即A的真出口确切位置并不知道，故此时只能产生一个空缺转移目标的四元式(jnz,A,-,0),并将此四元式的序号(即1)作为语义信息存起来，待开始翻译S1时，再将S1的第一四元式的序号(即5)回填这个不完全的四元式。另外，在翻译过程中，常常会出现若干转移四元式转向同一目标，但此目标的具体位置又尚未确定的情况，此时我们可将这些四元式用拉链的办法将它们链接起来，用一指针指向链头，在确定了目标四元式的位置之后，再回填这个链。,布尔表达式的真假出口链,对于一个布尔表达式E来说，它应有两条链：真出口链(称为T链，记作TC)和假出口链(称为F链，记作FC)。它们就是非终结符Expr的两个属性Expr.TC及Expr.FC。例如，对于上述if语句中的布尔式E=AB0时,它给出本链的后继四元式的序号，Result=0时表示本四元式是链尾结点。,(1)(jnz,A,-,0)(2)(j,-,-,3)E.TC(3)(j,B,C,1)E.FC(4)(j,-,-,0),ABC的四元式序列及其TC链和FC链,文法的“拆分”,为便于实现布尔表达式的语法制导翻译，我们先改写文法，以便能在翻译过程中的适当时机获得所需的语义属性值。例如，可将文法(5.1)改写为：ExprExprExpr|ExprExpr|Expr|iden|idenRopiden|(Expr)ExprExprExprExpr(5.7)将文法进行“拆分”的目的:1.在翻译完运算符（）左侧的表达式后，能够及时获取其语义属性TC及FC2.完成用下一四元式序号（即运算符右侧表达式的第一四元式之序号）回填前一表达式的相应真（假）链TC（FC），3.将其另一链FC（TC）作为产生式左部符号的综合属性FC（TC）传播之。,语义变量及辅助语义函数,1.NXQ全局变量，用于指示所要产生的下一四元式的序号；2.GEN（）其意义同前,每次调用,NXQ+；3.intMerge(intp1,intp2)将链首“指针”分别为p1和p2的两条链合并为一条，并返回新链的链首“指针”（此处的“指针”实际上是四元式的序号，应为整型值）我们假定四元式是以一结构形式表示（存储）的：struct_QuadrupleintOp,arg1,arg2,Result;QuadrupleList;4.voidBackPatch(intp,intt)用四元式序号t回填