编译技术 张莉第一部分-基础篇 电子教案-第9章-语法制导翻译技术.ppt

《编译技术 张莉第一部分-基础篇 电子教案-第9章-语法制导翻译技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章语法制导翻译技术翻译文法(TG)和语法制导翻译属性翻译文法(ATG)自顶向下语法制导翻译翻译文法的自顶向下语法制导翻译属性文法的自顶向下语法制导翻译自底向上的语法制导翻译（自学）9.0本章导言词法分析，语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，能够很容易地将其分析器构造出来。本章要介绍的是语义分析和代码生成技术。程序语言的语义形式化描述目前有三种基本描述方法，即：操作语义指称语义公理语义9.1翻译文法和语法制导翻译有上下无关文法G[E]:1.E→E+T4.T→F2.E→T5.F→(E)3.T→T*

2、F6.F→i此文法是一个中缀算术表达式文法翻译的任务是:中缀表达式逆波兰表示a+b*cabc*+假如翻译任务是要将中缀表达式简单变换为波兰后缀表示，只需在上述文法中插入相应的动作符号。1.E→E+T@+4.T→F2.E→T5.F→(E)3.T→T*F@*6.F→i@i其中：@+,@*,@i为动作符号。@为动作符号标记，后面为字符串。在本例中，其对应语义子程序的功能是要输出打印动作符号标记后面的字符串。所以，产生式1：E→E+T@+的语义是分析E,+和T，输出+产生式6：F→i@i的语义是分析i，输出i1.E→E+T4.T→F2.E→T5.F→(E)3.T→T*F6.F→i

3、下面给出输入文法和翻译文法的概念：输入文法：未插入动作符号时的文法。由输入文法可以通过推导产生输入序列。翻译文法：插入动作符号的文法。由翻译文法可以通过推导产生活动序列。输入序列动作序列用相应的翻译文法推导，可得：ETT*F@*F*F@*(E)*F@*(E+T@+)*F@*例：(i+i)*i可以用输入文法推导：ETT*FF*F(E)*F(E+T)*F(i+i)*i*(i@i+i@i@+)*i@i@**1.E→E+T@+4.T→F2.E→T5.F→(E)3.T→T*F@*6.F→i@i1.E→E+T4.T→F2.E→T5.F→(E)3.T→T*F6.

4、F→i定义9.1翻译文法是上下文无关文法，其终结符号集由输入符号和动作符号组成。由翻译文法所产生的终结符号串称为活动序列。活动序列：由翻译文法推导出的符号串，由终结符和动作符号组成。●从活动序列中，抽去动作符号，则得输入序列（i+i)*i●从活动序列中，抽去输入序列，则得动作序列，执行动作序列，则完成翻译任务：@i@i@+@i@*ii+i*(i@i+i@i@+)*i@i@*上例题中的翻译文法为：GT=(Vn,Vt,P,E)Vn={E,T,F}Vt={i,+,*,(,),@+,@*,@i}P={E→E+T@+,E→T,T→T*F@*,T→F,F→(E),F→i@i}符号串

5、翻译文法：若插入文法中的动作符号对应的语义子程序是输出动作符号标记@后的字符串的文法。语法导制翻译：按翻译文法进行的翻译。给定一输入符号串，根据翻译文法获得翻译该符号串的动作序列，并执行该序列所规定的动作的过程。语法导制翻译的实现方法：翻译文法所定义的翻译是由输入序列和动作序列组成的对偶集。在文法的适当位置插入语义动作符号，当按文法分析到动作符号时就调用相应的语义子程序，完成翻译任务。如：(i+i)*i,@i@i@+@i@*→ii＋i*i+i*i@i@i@i@*@+因此，给定一个翻译文法，就给定了一个对偶集。9.2属性翻译文法在翻译文法的基础上，可以进一步定义属性文法，翻

6、译文法中的符号，包括终结符、非终结符和动作符号均可带有属性，这样能更好的描述和实现编译过程。属性可以分为两种：综合属性继承属性9.2.1综合属性基本操作数带有属性的表达式文法G[E]1.E→E+F4.T→F2.E→T5.F→(E)3.T→T*F6.F→iC此文法能够产生如下的输入序列：（i3＋i9)*i2其中↑C是综合属性符号，↑为综合属性标记，c为属性变量或者属性值。根据给定的文法，可写出该输入序列的语法树自底向上的属性计算ET*TFF(E)E+TTFi3i2Fi9ET*TFF(E)E+TTFi3i2Fi9所以，用表示属性计算是自底向上的，称为综合

7、属性。3393912121222424说明：p,q,r为属性变量名。属性变量名局部于每个产生式，也可使用不同的名字。为了形式地表示上述表达式的属性求值过程，可以改写上述文法：产生式求值规则1.Ep4Eq5+Tr2p4:=q5+r2;2.Ep3Tq4p3:=q4;3.Tp2Tq3*Fr1p2:=q3*r1;4.Tp2Fq2p2:=q2;5.Fp1(Eq1)p1:=q1;6.Fp1iq1p1:=q1;求值规则：综合属性是自右向左，自底向上求值。考虑下列文法：G[<说明>]：1.<说