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

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),a,Read(+),Read(b),Print(b),ab,Read(*),Read(c),Print(c),abc,Print(*),abc*,Print(+),abc*+,aa+bb*cc*+,Read(#),原文法：,1.EE+T,2.ET,3.TT*F,4.TF,5.F(E),6.Fa,7.Fb,8.Fc,增加动作描述后文法：,1.EE+T+,2.ET,3.TT*F*,4.TF,5.F(E),6.Faa,7.Fbb,8.Fcc,ETT*FF*F(E)*F(E+T)*F(a+b)*c,ETT*F*T*cc*F*cc*(E)*cc*(E+T+)*cc*(E+F+)*cc*(E+bb+)*cc*(aa+bb+)*cc*,产生式右部的动作描述,5.1.1 翻译文法(TG),5.1.1 翻译文法(TG),翻译文法是一个上下文无关文法，在该文法中终极符号集由输入符号(即原来终极符)和动作符号组成。,GT=(VN,VT,P,E)VN=E,T,FVT=a,b,c,+,*,(,),a,b,c,+,*P=产生式,属性翻译文法,扩充翻译文法的概念，使非终极符号、终极符号、动作符号都包含属性值。这些属性代表与文法符号相关的信息，例如，文法符号的类型、值、符号表内容等。与这些属性相关的信息，称为值属性。值属性可以在语法分析过程中计算和传递，属性加工的过程即语义的处理过程,(c3+c9)*(c2+c41),2.EE+T,3.ET,4.TT*F,5.TF,6.F(E),7.Fc,1.SEAnswer,(c3+c9)*(c2+c41),Answer516,F3,T3,E3,F9,T9,E12,F12,T12,F2,T2,E2,F41,T41,E43,F43,T516,E516,综合属性,2.EE+T,3.ET,4.TT*F,5.TF,6.F(E),7.Fc,1.SEAnswer,2.EpEq+Tr p=q+r,3.EpTqp=q,4.TpTq*Fr p=q*r,5.TpFqp=q,6.Fp(Eq)p=q,7.Fpcqp=q,1.SEqAnswerr r=q,属性翻译文法,一、综合属性,如果一个结点的某一属性之值由子节点的属性值来计算，则称该属性为综合属性,1.说明Type V 变量表,2.变量表,V 变量表,3.变量表,1.说明Type V Set-Type 变量表,2.变量表,V Set-Type 变量表,3.变量表,Set-Type有两个参数：Set-Type(指针,类型)相应的动作符号：Set-Type 指针,类型,int i,j,k,属性翻译文法,二、继承属性,若某一结点的某一属性之值由该结点的兄弟结点和（或）父节点的属性值来计算，则称该属性为继承属性,1.说明Type V Set-Type 变量表,2.变量表,V Set-Type 变量表,3.变量表,int i,j,k,Set-Typej,int,Set-Typei,int,变量表int,变量表int,Set-Typek,int,变量表int,继承属性,属性翻译文法,二、继承属性,1.说明Type V Set-Type 变量表,2.变量表,V Set-Type 变量表,3.变量表,1.说明Typet Vp Set-Typeu,v 变量表q,2.变量表t,Vp Set-Typeu,v 变量表q,3.变量表,属性翻译文法,二、继承属性,注：终结符只有综合属性，非终结符既有综合属性也有继承属性,属性翻译文法,(1)每个VT,VN和动作符号都有一个与其相关的属性的有穷集，且每个属性都有一个值域。,(2)每个VN和动作符号的属性可分为两类：继承属性或综合属性。,三、属性翻译文法,(3)继承属性求值规则：开始符号的每个继承属性具有指定的初始值；产生式右部的继承属性，用该产生式左部或同一右部的左边符号属性求得。,(4)综合属性求值规则：输入符号的综合属性具有指定的初始值；产生式左部的综合属性，用该产生式左部或右部的某些符号属性求得；动作符号的综合属性，由该动作符号的其它属性值求得。,属性翻译文法,语法制导翻译是在语法分析过程中，随着分析的进展，根据每个产生式对应的语义子程序进行翻译的一种办法。,四、语法制导翻译,(1)对每个文法符号X的各方面属性进行描述，如用X.Type,X.Cat,X.Val表示类型、种属、值。,(2)对同一产生式中同一符号的多次出现，用上角标区别，如：EE(1)+E(2)。,五、对语义动作描述的约定,(3)每个产生式对应的语义动作写在该产生式的花括号内。,EE(1)+E(2)E.Val=E(1).Val+E(2).ValE0E.Val=0E1E.Val=1,5.2.1 后缀式,后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。3.如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。,逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。,5.2.1 后缀式,5.2.1 逆波兰表示法,把表达式翻译成后缀式的语义规则描述,产生式EE(1)op E(2)E(E(1)Eid,语义动作E.code:=E(1).code|E(2).code|opE.code:=E(1).codeE.code:=id,E.code表示E后缀形式op表示任意二元操作符“|”表示后缀形式的连接。,国防科技大学计算机系602教研室,数组POST存放后缀式：k为下标，初值为1上述语义动作可实现为：产生式程序段EE(1)op E(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1例：输入串a+b+c的分析和翻译POST：1 2 3 4 5,EE(1)op E(2)E.code:=E(1).code|E(2).code|opE(E(1)E.code:=E(1).codeEidE.code:=id,a,b,+,c,+,5.2.1 逆波兰表示法,用e表示给定中缀式，为相应的逆波兰式=a,中缀式转换为逆波兰表示：,=+,=*+,=ab*cd*+,=a,5.2.1 逆波兰表示法,=*,=*,=+*,=ab+*e+*,=ab+cd*e+*,da+be,=d,=a,=d,=+e,=a+adab+e,=abc+adab+e,5.2.1 逆波兰表示法,=,=,=+,=a,=ab+*e,=ab+cd*e,5.2.1 逆波兰表示法,5.2.1 逆波兰表示法,212+10*,2,12,14,10,140,后缀式的计算：,5.2.1 逆波兰表示法,e?x:y exy,后缀式的推广1：,后缀式的推广2：,Post1:n存放后缀式,p j 转移到Postp,e1 e2 p j 若e1e2，转移到Postp,e p j ez若e=0，转移到Postp,e p j nz若e0，转移到Postp,5.2.1 逆波兰表示法,x=e=,goto ll jump L为语句标号，运算符jump表示转到某个标号,if e0 then x e p1 j ez x p1:,if e=0 then xe p1 j ez p2 j p1:x p2:,if e0 then x else ye p1 j ez x p2 j p1:y p2:,p j 转移到Postp,e1 e2 p j 若e1e2，转移到Postp,e pj j ez 若e=0，转移到Postp,e pj j nz 若e0，转移到Postp,例：if ab then x:=a+b else x:=a-b,a b p1 j x a b-:=p2 j p1:x a b+:=p2:,a b p1 jez x a b+:=p2 j p1:x a b-:=p2:,5.2.1 逆波兰表示法,p j转移到Postp,e1 e2 p 若e1e2，转移到Postp,e p jez若e=0，转移到Postp,e p jnz若e0，转移到Postp,if e0 then x e p1 j ez x p1:,if e=0 then xe p1 j ez p2 p1:x p2:,if e0 then x else ye p1 j ez x p2 j p1:y p2:,例：begin k:=10010:if ki+j then begin k:=k-1 goto 10 endelse k:=i*i-j*j i:=0 j:=0end,block,(1),(2),k 100:=,(5),10:,(7),k i j+add jnz,k i j+21 jez,(14),k k 1-:=,(19),7 j,(21),k i i*j j*-:=,(30),i 0:=,(33),j 0:=,(36),blockend,e p jnz若e0，转移到Postp,5.2.1 逆波兰表示法,循环语句处理：for i:=a to b s,i:=a1:if i=b then begin s i:=i+1 goto 1 end,5.2.1 逆波兰表示法,EE(1)OP E(2),E(E(1),Ei,E.Code=E(1).Code|E(2).Code|OP,E.Code=E(1).Code,E.Code=i,Postk=OP;k=k+1,Postk=i;k=k+1,(a+b)*c,a,(E+b)*c,b,(E+E)*c,+,(E)*c,E*c,c,E*E,*,E,语法制导生成后缀式：,5.2.2 三元式表示法,(OP,Arg1,Arg2),运算符,运算量或指示器,例：A+B*C,(1)(*,B,C),(2)(+,A,(1),5.2.2 三元式表示法,例1：ABxy+1(x0B)D,(1)(+,y,1),(2)(,x,(1),(3)(,B,(2),(4)(,A,(3),(5)(,x,0),(6)(,(5),B),(7)(,(6),D),(8)(,(4),(7),5.2.2 三元式表示法,例2：x=a*b+c/d,(1)(*,a,b),(2)(/,c,d),(3)(+,(1),(2),(4)(=,x,(3),5.2.3 四元式表示法,(OP,Arg1,Arg2,Result),运算符,运算量,运算结果,5.2.3 四元式表示法,A=-B*(C+D),注释,(1)单目运算符，一律使用ARG1。,(2)临时变量：a.与用户自定义变量名一样看待；,b.用某种整数编码代替。,