编译原理综述.ppt

《编译原理综述.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.1概述5.1.1翻译文法文法用于描述构成语言的全部句子的集合。翻译文法是在文法的基础上增加翻译功能，一边进行语法分析，一边进行翻译。例，设计一个处理器，其输入为中缀表达式，输出为后缀表达式。例，中缀式a+b*c，后缀式abc*+。输入序列是:a+b*c处理器的输入输出活动是:RD(a)PT(a)RD(+)RD(b)PT(b)RD(*)RD(c)PT(c)PT(*)PT(+)用输入符号本身代表输入操作，用@开始的符号串代表输出操作:a@a+b@b*c@c@*@+输出结果是:abc*+@称为动作符号标记，由@开始的符号串称为一个动作符号。由文法

2、构造翻译文法:1.EE+T2.ET3.TT*F4.TF5.F(E)6.Fa7.Fb8.Fc1.EE+T@+2.ET3.TT*F@*4.TF5.F(E)6.Fa@a7.Fb@b8.Fc@c结论:通过输入文法推导产生出某个输入序列通过翻译文法的推导，便可得到相应的活动序列例，句型(a+b)*c输入文法的最左推导:ETT*FF*F(E)*F(E+T)*F(a+b)*c*翻译文法的最左推导:ETT*F@*F*F@*(E)*F@*(a@a+b@b@+)*c@c@**ab+c*定义:翻译文法是一个上下文

3、无关文法。在该文法中终结符号集由输入符号(即原来终结符)和动作符号组成。例，上述文法:GT=(VN,VT,P,E)VN={E,T,F}VT={a,b,c,+,*,(,),@a,@b,@c,@+,@*}P={产生式}在此文法中，(语义动作)仅仅是输出该动作符号的动作标记符@后面的符号串。这里,该翻译文法是符号串翻译文法。5.1.2属性翻译文法翻译文法中的符号，包括非终结符，终结符和动作符号都是有穷集合中的符号，都没有值的概念。扩充翻译文法的概念，即让符号包含值部分。符号所具有的值部分称符号的属性。(1)将符号的属性与语法树的节点联系起来，输入和输

4、出值之间的关系可以通过产生式来表示。例，设有一词法分析程序能够输出下列单词符号：(,),+,*,c考虑设计一个语法分析程序，它接受上述符号组成的算术表达式，并输出这个表达式的值。翻译文法是:1.SE@ANSWER5.TF2.EE+T6.F(E)3.ET7.Fc4.TT*F1.综合属性语法树为例，输入序列：(C↑3+C↑9)*(C↑2+C↑41)“↑数字串”表示该符号的值部分接受:输出:显然,语法树中的非终结符E,T,F的每次出现都是表示该输入表达式的一个子表达式，其值部分应是其子表达式的计算结果。例，产生式:FcTF则F的值部

5、分等于c的值部分，T的值部分等于F的值部分。计算表达式的实际过程是:先分别计算各子表达式的值，再计算父表达式的值，直到求得整个表达值。表示属性计算的语法树(2)为了形式地表示上述表达式的求值过程，可以将产生式改写，对出现在每一个产生式中的每一个值赋以一个不同的名字，而后使用这些名字说明各产生式中各符号的值部分之间的关系(求值规则)。例，计算表达式值的符号串翻译文法可改写为：SE↑q@ANSWER↓rr=qE↑pE↑q+T↑rp=q+rE↑pT↑qp=qT↑pT↑q*F↑rp=q*rT↑pF↑qp=qF↑p(E↑q)p=qF↑pc↑

6、qp=q产生式左部符号的属性值是通过计算右部符号的属性值得来的。在语法树中，每个非终结符的属性值都是由它下面的那些符号(子结点)来确定。这种可通过自底向上进行求值的属性，称综合属性。继承属性例，(说明句)文法:说明TYPEV变量表变量表，V变量表变量表εintegera,b,c翻译文法:说明TYPEV@SET-TYPE变量表变量表,V@SET-TYPE变量表变量表ε动作符号@SET-TYPE调用过程SET-TYPE，把TYPE的值(类型)填到各个变量在符号表中的项的类型域中。动作符号@SET-TYPE的值部分有两个属性:@SET-T

7、YPE↓变量,类型变量表的类型值，这可采用自上向下传递方法求得来自产生式左部变量表属性值。翻译文法变成:说明TYPE↓tV↓p@SET-TYPE↓p1,t1变量表↓t2t1=t2=t,p1=p2.变量表↓t，V↓p@SET-TYPE↓p1,t1变量表↓t2t1=t2=t,p1=p3.变量表ε产生式右部的符号的属性值，是由其左部符号或同一右部的其左部的符号的属性值求得的.这种求值规则求得的属性称继承属性。符号串TYPE↓REALV↓1,V↓2,V↓3的语法树说明TYPE↓REALV↓1@SET-TYPE↓1,REAL变量表↓REAL变量表↓

8、REAL@SET-TYPE↓2,REALV↓2,变量表↓REAL@SET-TYPE↓3,REALV↓3,3.属性翻译文法定义:属性翻译文法是带有下列说