第5章语法制导翻译技术和中间代码生成090504

11编译原理2020年2月5日S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理符号表管理22编译原理2020年2月5日第5章语法制导翻译技术和中间代码生成1.要求明确语义分析的任务2.明确属性文法和语法制导翻译的含义3.明确自底向上和自顶向下语法制导翻译的区别和特点4.明确生成中间代码的目的，中间代码的几种形式教学目标33编译原理2020年2月5日•属性文法•语法制导翻译法的基本思想•常见的中间代码•各种不同语法结构的语法制导翻译技术教学内容44编译原理2020年2月5日词法分析，语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。本章要介绍的是语义分析和中间代码生成技术。程序语言中间代码目标代码翻译翻译55编译原理2020年2月5日根据语义规则对识别出的各种语法成分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。第一，审查每个语法结构的静态语义，即检查语法结构合法的程序是否真正有意义。也称静态语义检查。（类型检查、控制流的检查、一致性检查、相关名字的检查）第二，如果静态语义正确，语义处理则要执行真正的翻译，要么生成中间代码，要么生成实际的目标代码。（说明性语句：填符号表；可执行性语句：生成中间代码）语义分析的任务66编译原理2020年2月5日①类型检查。②控制流检查，确保控制语句有合法的转向点。例如，C语言中的break语句使控制跳离包括该语句的最小的switch，while或for语句。如果不存在包括它的这样的语句，则应报错。静态语义检查77编译原理2020年2月5日静态语义检查③一致性检查。很多情况下要求对象只能被定义一次。例如，Ｃ语言中规定一个标识符在同一作用域中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等。④相关名字检查。有的语言中有时规定，同一名字必须出现两次或多次。例如，Ada语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。88编译原理2020年2月5日附加了一组属性和运算（语义）规则的文法5.2属性文法文法符号X的属性t常用X.t来表示•语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关•不同的产生式对应不同的语义规则•不同的分析目标也对应不同的语义规则1.属性的表示2.语义规则的表示语义信息语义之间的关系静态语义检查、符号表操作、代码生成及打印各种错误信息99编译原理2020年2月5日属性文法•属性文法的形式定义：•AG：AG=（G，V，E）•G:上下文无关文法;•V:属性的有穷集合;每一个属性与某一个文法符号相关联；用文法符号·属性表示•E:表示属性的断言或谓词的有穷集合(语义规则);每一个断言与文法的某个产生式相关联)•属性:综合属性(自下而上传递信息)、继承属性（自上而下传递信息)1010编译原理2020年2月5日•非终结符E、T及F都有一个综合属性val,符号i有一个综合属性。•某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现语义规则EE1+TETTT1*FTFF(E)FiE.val=E1.val+T.valE.val=T.valT.val=T1.valF.valT.val=F.valF.val=E.valF.val=i.lexval产生式例5.11111编译原理2020年2月5日语法制导翻译的过程语法制导翻译：将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。1212编译原理2020年2月5日语法制导翻译分为两种处理方法：（1）自底向上语法制导翻译：对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。（2）自顶向下语法制导翻译：在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。1313编译原理2020年2月5日语法制导定义对每个产生式编制一个语义子程序在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译综合属性继承属性自底向上传递信息自顶向下（自左向右）传递信息1414编译原理2020年2月5日属性翻译文法的应用综合属性与自下而上定值每个非终结符的属性值都是根据位于其下面那些符号的属性值来确定的，即按一种自下而上的方式来确定的。继承属性和自上而下定值非终结符的属性值或者根据其上层非终结符的属性来确定或者根据产生式右部其它符号的属性来确定。这种属性值是根据自上而下方式确定的。1515编译原理2020年2月5日•print(E.val)打印由E产生的算术表达式的值，可认为这条规则定义了L的一个虚属性。LEEE1+TETTT1*FTFF(E)Fiprint(E.val)E.val=E1.val+T.valE.val=T.valT.val=T1.valF.valT.val=F.valF.val=E.valF.val=i.lexval例5.２综合属性语义规则产生式1616编译原理2020年2月5日LE.val=14nT.val=12E.val=2T.val=2F.val=2i.lexval=2T.val=3+*F.val=3F.val=4i.lexval=4i.lexval=3•一个结点的综合属性值是其子结点的某些属性来决定的２+3*4的注释分析树通常使用自底向上的分析方法•在每个结点处使用语义规则来计算综合属性值•当一个产生式获得匹配时，就调用相应的语义子程序•从叶结点到根结点进行计算只含有综合属性的语法制导定义称为S属性定义1717编译原理2020年2月5日S属性定义与自底向上翻译•LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算•LR分析器增加属性值（语义）栈1）为文法的每条规则设计相应的语义子程序；2）增加一个语义信息栈；3）在语法分析的同时做语义处理：即在用某一个产生式进行规约的同时，调用相应的语义子程序完成所用规则的语义动作，并将每次动作后的值保存在语义栈中翻译步骤计算表达式2+3*5状态ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5G[E]：1E→E+T2E→T3T→T*F4T→F5F→(E)6F→ii+i*i表达式2+3*5的归约过程步骤状态栈语义栈符号栈输入串动作00_$2+3*5$S5105__$2+3*5$r6203_2$F+3*5$r4302_2$T+3*5$r2401_2$E+3*5$S65016_2_$E+3*5$S560165_2__$E+3*5$r6步骤状态栈语义栈符号栈输入串动作70163_2_3$E+F*5$r480169_2_3$E+T*5$S7901697_2_3_$E+T*5$S510016975_2_3__$E+T*5$r61101697(10)_2_3_5$E+T*F$r3120169_2_15$E+T$r11301_17$E$acc注意•句柄归约在先，语义动作调用在后•归约时，栈内句柄各符号的语义信息与句柄及同时出栈，整个句柄所表示的语义信息则赋给相应产生式左部非终结符号的语义变量，并让该非终结符号及语义信息同时入栈2323编译原理2020年2月5日生成中间代码的目的(1)便于优化(2)便于移植(3)逻辑结构清晰常见的中间代码形式：后缀式三地址代码（四元式、三元式和间接三元式）图形（抽象语法树、有向无环图）中间代码：一种介于源语言和目标语言之间的中间语言形式5.３中间代码2424编译原理2020年2月5日中缀表示后缀表示a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特点1、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值后缀式2525编译原理2020年2月5日分别给出下列表达式的后缀表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)-(a+b*c)3.a=c∧b=d4.a≤b+c∧ad∨a+b≠ea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=∧abc+≤ad∧ab+e≠∨2626编译原理2020年2月5日逆波兰表示法（后缀式）特点：运算符直接写在其运算对象之后。•不再有括号•运算对象出现的次序未变•求值过程简单，宜于用栈实现后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。2727编译原理2020年2月5日三地址代码１．种类（1）x=yopz形式的赋值语句，其中op是二元运算符。（2）x=opy形式的赋值语句，其中op是一元运算符。（3）x=y形式的赋值语句。（4）无条件转移语句gotoL，表示下一个要执行的语句是标号为L的语句。（5）条件转移语句ifxropygotoL中，rop为关系运算符，如果x和y满足关系rop，就转而执行标号为L的语句，否则顺序执行下一个语句。2828编译原理2020年2月5日（6）过程调用语句paramx和callp,n。源程序中的过程调用语句p(x1，x2，…，xn)可以产生如下的三地址代码：paramx1paramx2…paramxncallp,n其中n为实参个数。过程返回语句形如returny，其中y为过程返回的一个值。2929编译原理2020年2月5日（7）变址赋值：x=y[i]，把从y开始的第i个存储单元的值赋给x。x[i]=y，把y的值赋给x开始的第i个存储单元。其中，x，y和i都代表数据对象。（8）地址和指针赋值：x=&y，把y的地址赋给x。x=y，把y指示的地址单元中的内容赋给x。x=y，把x指向的存储单元的值置为y。3030编译原理2020年2月5日2．具体实现四元式操作符操作数1操作数2结果结果：通常是由编译引进的临时变量例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一,XT1,T2,T3,T4为临时变量，由四元式优化比较方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T43131编译原理2020年2月5日操作符左操作符数右操作数表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三个三元式中的操作数(1)(2)表示第(1)和第(2)条三元式的计算结果。三元式3232编译原理2020年2月5日例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)不便于代码优化：删除某些三元式后可能需作一系列的修改三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)间接三元式执行顺序(1)(2)(3)(4)(1)(5)三元式的执行次序用另一张表表示,优化时三元式可以不变，仅仅改变其执行顺序表3333编译原理2020年2月5日图形表示法•无循环有向图(DirectedAcyclicGraph，简称DAG)–对表达式中的每个子表达式，DAG中都有一个结点–一个内部结点代表一个操作符，它的孩子代表操作数–在一个DAG中代表公共子表达式的结点具有多个父结点3434编译原理2020年2月5日例：x=y+yz+yz抽象语法树图形表示有向无环图=x++yyzyz－=x++yyz－(a