编译原理_第5章_第1节_语法制导翻译和中间代码生成

5.1概述任务：词法分析和语法分析的基础上，进一步分析其含义，为生成相应的目标代码做好准备或直接生成目标代码功能：（1）审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义（静态语义分析或静态审查）（2）如果静态语义正确，就执行真正的翻译，即要么生成中间代码(便于优化)，要么生成实际的目标代码语义分析及其功能5.1概述类型检查：每个操作是否遵循语言的类型系统控制流检查：控制流语句必须使控制转移到合法的地方一致性检查：在很多场合要求对象只能被定义一次，如枚举类型相关名字检查：同一名字必须出现两次或多次名字的作用域分析静态语义检查5.1概述复杂性介于源程序语言和机器语言的一种表示形式引入原因：快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。使编译程序结构在逻辑上更为简单明确，将与机器相关的某些实现细节置于代码生成阶段仔细处在中间代码一级进行优化工作使得代码优化比较容易实现。中间代码5.1.1翻译文法(TG)逆波兰表示法：一种把运算符写在运算量后面的表达式表示方法。a+bab+a+b*cabc*+(a+b)*cab+c*a+b*c#的处理过程：Read(a)Print(a)aRead(+)Read(b)Print(b)abRead(*)Read(c)Print(c)abcPrint(*)abc*Print(+)abc*+a@a+b@b*c@c@*@+Read(#)原文法：1.EE+T2.ET3.TT*F4.TF5.F(E)6.Fa7.Fb8.Fc增加动作描述后文法：1.EE+T@+2.ET3.TT*F@*4.TF5.F(E)6.Fa@a7.Fb@b8.Fc@cETT*FF*F(E)*F(E+T)*F(a+b)*cETT*F@*T*c@c@*F*c@c@*(E)*c@c@*(E+T@+)*c@c@*(E+F@+)*c@c@*(E+b@b@+)*c@c@*(a@a+b@b@+)*c@c@*产生式右部的动作描述5.1.1翻译文法(TG)5.1.1翻译文法(TG)翻译文法是一个上下文无关文法，在该文法中终极符号集由输入符号(即原来终极符)和动作符号组成。GT=(VN,VT,P,E)VN={E,T,F}VT={a,b,c,+,*,(,),@a,@b,@c,@+,@*}P={产生式}5.1.2属性翻译文法扩充翻译文法的概念，使非终极符号、终极符号、动作符号都包含属性值。这些属性代表与文法符号相关的信息，例如，文法符号的类型、值、符号表内容等。与这些属性相关的信息，称为值属性。值属性可以在语法分析过程中计算和传递，属性加工的过程即语义的处理过程(c↑3+c↑9)*(c↑2+c↑41)2.EE+T3.ET4.TT*F5.TF6.F(E)7.Fc1.SE@Answer(c↑3+c↑9)*(c↑2+c↑41)@Answer↓516SE@AnswerTT*FF(E)E+TTFc↑3Fc↑9(E)E+TTFc↑2Fc↑41F↑3T↑3E↑3F↑9T↑9E↑12F↑12T↑12F↑2T↑2E↑2F↑41T↑41E↑43F↑43T↑516E↑516综合属性2.EE+T3.ET4.TT*F5.TF6.F(E)7.Fc1.SE@Answer2.E↑pE↑q+T↑rp=q+r3.E↑pT↑qp=q4.T↑pT↑q*F↑rp=q*r5.T↑pF↑qp=q6.F↑p(E↑q)p=q7.F↑pc↑qp=q1.SE↑q@Answer↓rr=q5.1.2属性翻译文法一、综合属性如果一个结点的某一属性之值由子节点的属性值来计算，则称该属性为综合属性1.说明TypeV变量表2.变量表,V变量表3.变量表ε1.说明TypeV@Set-Type变量表2.变量表,V@Set-Type变量表3.变量表εSet-Type有两个参数：Set-Type(指针,类型)相应的动作符号：@Set-Type↓指针,类型inti,j,k5.1.2属性翻译文法二、继承属性若某一结点的某一属性之值由该结点的兄弟结点和（或）父节点的属性值来计算，则称该属性为继承属性1.说明TypeV@Set-Type变量表2.变量表,V@Set-Type变量表3.变量表εinti,j,k@Set-Type↓j,int@Set-Type↓i,int变量表↓int变量表↓int@Set-Type↓k,int变量表↓int继承属性5.1.2属性翻译文法说明Type↓intV↓i@Set-Type变量表，V↓j@Set-Type变量表，V↓k@Set-Type变量表ε二、继承属性1.说明TypeV@Set-Type变量表2.变量表,V@Set-Type变量表3.变量表ε1.说明Type↓tV↓p@Set-Type↓u,v变量表↓q2.变量表↓t,V↓p@Set-Type↓u,v变量表↓q3.变量表ε5.1.2属性翻译文法二、继承属性注：终结符只有综合属性，非终结符既有综合属性也有继承属性5.1.2属性翻译文法(1)每个VT,VN和动作符号都有一个与其相关的属性的有穷集，且每个属性都有一个值域。(2)每个VN和动作符号的属性可分为两类：继承属性或综合属性。三、属性翻译文法(3)继承属性求值规则：a.开始符号的每个继承属性具有指定的初始值；b.产生式右部的继承属性，用该产生式左部或同一右部的左边符号属性求得。(4)综合属性求值规则：a.输入符号的综合属性具有指定的初始值；b.产生式左部的综合属性，用该产生式左部或右部的某些符号属性求得；c.动作符号的综合属性，由该动作符号的其它属性值求得。5.1.2属性翻译文法语法制导翻译是在语法分析过程中，随着分析的进展，根据每个产生式对应的语义子程序进行翻译的一种办法。四、语法制导翻译(1)对每个文法符号X的各方面属性进行描述，如用X.Type,X.Cat,X.Val表示类型、种属、值。(2)对同一产生式中同一符号的多次出现，用上角标区别，如：EE(1)+E(2)。五、对语义动作描述的约定(3)每个产生式对应的语义动作写在该产生式的花括号内。EE(1)+E(2){E.Val=E(1).Val+E(2).Val}E0{E.Val=0}E1{E.Val=1}5.2.1后缀式后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1opE2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1E2op，其中E1和E2分别为E1和E2的后缀式。3.如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。5.2.1后缀式5.2.1逆波兰表示法•把表达式翻译成后缀式的语义规则描述产生式E→E(1)opE(2)E→(E(1))E→id语义动作E.code:=E(1).code||E(2).code||opE.code:=E(1).codeE.code:=id•E.code表示E后缀形式•op表示任意二元操作符•“||”表示后缀形式的连接。国防科技大学计算机系602教研室数组POST存放后缀式：k为下标，初值为1上述语义动作可实现为：产生式程序段E→E(1)opE(2){POST[k]:=op;k:=k+1}E→(E(1)){}E→i{POST[k]:=i;k:=k+1}例：输入串a+b+c的分析和翻译POST：12345E→E(1)opE(2)E.code:=E(1).code||E(2).code||opE→(E(1))E.code:=E(1).codeE→idE.code:=idab+c+…5.2.1逆波兰表示法用e表示给定中缀式，e为相应的逆波兰式e1θe2=e1e2θ(e)=ea=a中缀式转换为逆波兰表示：a*b+c*d=a*bc*d+=ab*cd*+=ab*cd*+e1θe2=e1e2θ(e)=ea=a5.2.1逆波兰表示法(a+b)*(c*d+e)=(a+b)(c*d+e)*=a+bc*d+e*=ab+c*de+*=ab+cd*e+*=ab+cd*e+*a≤b+c∧ad∨a+b≠e=a≤b+c∧ada+b≠e∨e1θe2=e1e2θ(e)=ea=a=a≤b+cad∧a+be≠∨=ab+c≤ad∧ab+e≠∨=abc+≤ad∧ab+e≠∨=abc+≤ad∧ab+e≠∨5.2.1逆波兰表示法(a+b)^(c*d)^e=(a+b)(c*d)^e)^=a+b(c*d)e^^=ab+c*de^^e1θe2=e1e2θ(e)=ea=a=ab+cd*e^^=ab+cd*e^^5.2.1逆波兰表示法5.2.1逆波兰表示法212+10*2121410140后缀式的计算：5.2.1逆波兰表示法e?x:yexyΨ后缀式的推广1：后缀式的推广2：Post[1:n]存放后缀式pj转移到Post[p]e1e2pj若e1e2，转移到Post[p]epjez若e=0，转移到Post[p]epjnz若e0，转移到Post[p]5.2.1逆波兰表示法x=exe=gotolljumpL为语句标号，运算符jump表示转到某个标号ife0thenxep1jezxp1:…e5jezx…12345ife=0thenxep1jezp2jp1:xp2:…ife0thenxelseyep1jezxp2jp1:yp2:…pj转移到Post[p]e1e2pj若e1e2，转移到Post[p]epjjez若e=0，转移到Post[p]epjjnz若e0，转移到Post[p]例：ifabthenx:=a+belsex:=a-babp1jxab-:=p2jp1:xab+:=p2:…abp1jezxab+:=p2jp1:xab-:=p2:…5.2.1逆波兰表示法pj转移到Post[p]e1e2p若e1e2，转移到Post[p]epjez若e=0，转移到Post[p]epjnz若e0，转移到Post[p]ife0thenxep1jezxp1:…ife=0thenxep1jezp2p1:xp2:…ife0thenxelseyep1jezxp2jp1:yp2:…例：begink:=10010:ifki+jthenbegink:=k-1goto10endelsek:=i*i-j*ji:=0j:=0endblock(1)(2)k100:=(5)10:(7)kij+addjnzkij+21jez(14)kk1-:=(19)7j(21)kii*jj*-:=(30)i0:=(33)j0:=(36)blockendepjnz若e0，转移到Post[p]5.2.1逆波兰表示法循环语句处理：fori:=atobsi:=a1:ifi=bthenbeginsi:=i+1goto1end5.2.1逆波兰表示法EE(1)OPE(2)E(E(1))Ei{E.Code=E(1).Code||E(2).Code||OP}{E.Code=E(1).Code}{E.Code=i}{Post[k]=OP;k=k+1}{}{Post[k]=i;k=k+1}(a+b)*ca(E+b)*cb(E+E)*c+(E)*cE*ccE