6hh第8章语法制导翻译和中间代码生成

第8章语法制导翻译和中间代码生成8.1属性文法8.2中间代码的形式8.3语法制导翻译概论8.4简单赋值语句的翻译8.5布尔表达式的翻译8.6控制语句的翻译8.7说明语句的翻译8.8数组和结构的翻译源程序经词法分析、语法分析后,还需进行语义分析,即审查每个语法成分的静态语义。如果静态语义正确,则生成与之等效的中间代码或目标代码。直接生成目标代码的优点是编译时间短且无需中间代码到目标代码的翻译;生成中间代码的优点是使编译结构在逻辑上更简单明确、代码优化更易实现。语义检查:静态语义检查和动态语义检查。前者在编译阶段进行;后者在运行阶段进行。静态语义检查涉及以下几个方面:(1)类型检查:如操作数类型是否相容(2)控制流检查:用以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case;break语句需寻找包含它的最小switch、while或for语句。(3)一致性检查:如在相同作用域中标识符只能说明一次、case标号不能相同等。(4)相关名字检查。有时同一名字必须出现多次。如Ada程序中,循环或程序块可以有一个名字,出现在这些结构的开头和结尾,编译程序必须检查确认这两个地方用的名字是相同的。(5)名字的作用域分析。由于语义是上下文有关的,故语义的形式化描述很困难。目前较常见的是利用属性文法作为语义描述工具,并采用语法制导翻译法对语法成分进行翻译。语法制导翻译法就是为每个产生式配上一个翻译子程序(也称语义子程序或语义动作),并在语法分析的同时执行这些子程序。语义动作规定生成中间代码应做哪些基本动作。在语法分析过程中,当一个产生式用于归约时,相应的语义子程序被启动,完成既定翻译任务。语法制导翻译分为自下而上和自上而下两类,下面介绍自下而上语法制导翻译。假定有一个自下而上的LR分析器,把其能力扩大,使它在归约的同时调用相应的语义子程序进行翻译。语义子程序执行后,有些结果需作为产生式左部符号的语义值暂存,以后引用。故分析栈需扩充以存放三类信息:状态、文法符号及语义值。栈顶#X1…Xks0s1…skX1.val…Xk.val扩充后的分析栈如下图所示:扩充总控程序,使其在完成语法分析的同时也完成语义分析,即进行归约时调用相应的语义子程序。算术表达式文法及语义动作:(0)S'→E{printval[TOP]}(1)E→E(1)+E(2){val[TOP]=val[TOP]+val[TOP+2]}(2)E→E(1)*E(2){val[TOP]=val[TOP]*val[TOP+2]}(3)E→(E(1)){val[TOP]=val[TOP+1]}(4)E→i{val[TOP]=lexval}(注:lexval为i的整型内部值)例给出算术表达式7+9*5#的语义分析过程E·val=52E·val=7E·val=45+7E·val=9*E·val=595表达式7+9*5#的语法树及各结点值表8.1表达式7+9*5#的语义分析过程步骤状态栈符号栈语义栈输入串下一动作10#_7+9*5#s3203#7__+9*5#r4301#E_7+9*5#s44014#E+_7_9*5#s350143#E+9_7__*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*5_7_9__#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc8.1属性文法文法的属性是指与文法符号的类型和值等有关的一些信息。例如,判断变量X的类型是否匹配,要用X的数据类型描述;判断变量X是否存在,要用X的存储位置描述;对X的运算,则要用X的值描述。故语义分析需引入X的属性,如X.type、X.place、X.val。文法符号的属性可分为两类:继承属性:由父结点的属性计算得到,即沿语法树自上向下传递信息。综合属性:由子结点的属性计算得到,即沿语法树自下向上传递信息。属性文法是指在文法中增加了属性,它包含一个CFG文法和一系列语义规则,这些语义规则附在文法的每个产生式上。语法制导翻译是指在语法分析过程中,完成附加在产生式上的语义规则描述的动作。例简单算术表达式求值的语义描述:产生式语义规则(0) S→Eprint(E.val)(1) E→E(1)+TE.val=E(1).val+T.val(2) E→TE.val=T.val(3) T→T(1)*FT.val=T(1).val*F.val(4) T→F(1)T.val=T(1).val(5) F→(E)F.val=E.val(6) F→iF.val=i.lexval每个非终结符都有一个属性val,它由其右部符号的val值计算,为综合属性。与S→E关联的是函数print(E.val),S在语义规则中没有出现,理解为S的属性是空的或虚的。例说明语句中各变量类型信息的语义规则。说明语句文法:G[D]:D→intL|floatLL→L,id|id产生式语义规则(1)D→TLL.in=T.type(2)T→intT.type=int(3)T→floatT.type=float(4)L→L(1),idL(1).in=L.in;addtype(id.entry,L.in)(5)L→idaddtype(id.entry,L.in)T有一个综合属性T.type,值为int或float;L有一个继承属性L.in,值由T.type决定;属性L.in被确定后将随语法树的逐步生成而传递到下边有关结点。例如,输入串inta,b的属性传递情况:DTLintL(1),id2id18.2.1抽象语法树抽象语法树是一种较流行的中间语言表示形式。在抽象语法树中,每个叶结点表示常量或变量这样的运算对象,而内部结点表示运算符。抽象语法树不同于语法树,它展示了一个操作过程并同时描述了源程序的层次结构。8.2中间代码的形式例如,赋值语句x=a+b的抽象语法树如图(a),其普通语法树如图(b)所示:assignx+ab(a)抽象语法树SVE=xEE+ab(b)普通语法树说明:语法规则中包含的某些符号可能起标点符号作用,也可能起解释作用。例如,赋值语句S→V=E中,赋值号仅起标点符号作用,其目的是把V与E分开。再如,条件语句S→if(e)S1;elseS2中,if和else起注释作用,说明当e为真时执行S1,否则执行S2;而“;”仅起标点符号作用。当把语法规则的本质部分抽象出来、把非本质部分去掉后,便得抽象语法规则。赋值语句和条件语句的抽象语法规则为:(1)赋值语句:左部表达式(2)条件语句:表达式语句1语句2这种去掉不必要信息的做法可以获得高效的中间表示。assignx+a*bc(a)抽象语法树SVE=xEE+EE*abc(b)普通语法树例如,赋值语句x=a+b*c的抽象语法树如图(a)所示,其普通语法树如图(b)所示:上述普通语法树的结点为14个,而抽象语法树的结点为7个且每个内部结点最多只有两个分支。因此,赋值语句或表达式可表示为一棵二叉树。对于含多元运算的语法成分,其抽象语法树为一棵多叉树,但可转为二叉树。抽象语法树的优点:结构紧凑、容易构造、结点数较少。逆波兰表示法是由波兰科学家提出的一种表达式表示方法,这种方法把运算量写在前、把运算符写在后,又称后缀表示法。8.2.2逆波兰表示法1.表达式E的逆波兰表示(1)若E是变量或常数,则E的后缀表示为E;(2)若E为E1opE2,则后缀表示为E1E2op,其中E1,E2分别为E1,E2的后缀表示。若op为一元运算,则视E1和E1为空。(3)若E为(E1)形式,则后缀表示即为E1,其中E1为E1的后缀表示。在逆波兰表示中,操作数的出现顺序与原来一致,而把运算符按运算先后顺序放在相应操作数后。逆波兰表示不需要用括号规定运算顺序,便于用栈实现计值。计值过程:自左至右扫描后缀表达式,遇到运算量就把它入栈,遇到K目运算符就把它作用于栈顶的K个运算量,并用运算结果取代栈顶的K个运算量。2.程序语句的逆波兰表示为了用逆波兰式表示一些控制语句,定义转移操作如下:(1)BL:转向某标号(2)BT:条件为真时转移(3)BF:条件为假时转移(4)BR:无条件转移部分程序语句的逆波兰表示如下:(1)赋值语句左部=表达式的逆波兰表示为左部表达式=例如,x=a+b*c的逆波兰式为xabc*+=(2)GOTO语句GOTO语句标号的逆波兰表示为语句标号BL其中,BL为单目后缀运算符。(3)条件语句BR表示无条件转移的单目后缀运算符。例如,顺序号BR其中,顺序号表示逆波兰式中单词符号的顺序号(即第几个单词)。BT和BF表示条件转移双目后缀运算符。例如,当布尔式e为真时转移表示为:e的逆波兰式顺序号BT当布尔式e为假时转移表示为:e的逆波兰式顺序号BF若用BF和BR,则if(e)S1;elseS2的逆波兰式:e的逆波兰式顺序号1BF//顺序号1为S2第1单词S1的逆波兰式//e为真时执行S1顺序号2BR//S2后第1个单词S2的逆波兰式例如,if(mn)k=i+1;elsek=i−1的逆波兰式表示为:(1) mn(4) 13BF(6) ki1+=(11)18BR(13)ki1−=(18)…把逆波兰式写在一行上:mn13BFki1+=18BRki1−=(4)循环语句循环语句不能直接用逆波兰表示,需展开为等价的条件语句再用逆波兰表示。例如,for(i=m;i=n;i++)S转换为:i=m;10:if(i=n){S;i=i+1;gotol0}1.三地址代码的一般形式x=yopz其中x,y,z为操作数,op为操作符。8.2.3三地址代码由于三地址语句只含一个运算符,故由多个运算符组成的表达式需要用三地址语句序列表示。例如,表达式x+y*z的三地址代码:t1=y*z;t2=x+t12.三地址语句的种类常用的三地址语句有8种:(1)x=yopz,其中op为二元运算符;(2)x=opy,其中op为一元运算符;(3)x=y,将y的值赋给x;(4)无条件转移语句gotoL;(5)条件转移语句ifxropygotoL;(6)变址赋值语句x=y[i]表示把从地址y开始的第i个单元中的值赋给x;x[i]=y表示把y的值赋给从地址x开始的第i个地址单元。(7)过程调用语句parX和callP,n。过程调用语句P(X1,X2,…,Xn)可用下述三地址代码表示:parX1…parXncallP,n过程返回语句为returny其中y为返回值。(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=yopz(op,y,z,x)x=−y(minus,y,_,x)x=y(=,y,_,x)parx1(par,x1,_,_)callP,n(call,_,_,P)gotoL(j,_,_,L)ifxropygotoL(jrop,x,y,L)例如,赋值语句a=b*(c+d)的四元式:①(+,c,d,t1)②(*,b,t1,t2)③(=,t2,_,a)约定:一元运算符使用arg1;若op为算术或逻辑运算符,则result为一个新引进的临时变量,用于存放运算结果。可见,四元式之间的联系通过临时变量实现。(2)三元式三元式是具有三个域的记录结构:(op,arg1,arg2)其中op为操作符,arg1和arg2既可指向有关名字在符号表中的登记项或临时变量,也可指向三元式表中的某个三元式。例如,赋值语句a=(b+c)*(b+c