《语法制导翻译 》PPT课件

《《语法制导翻译 》PPT课件》由会员分享，可在线阅读，更多相关《《语法制导翻译 》PPT课件（70页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 语法制导翻译语法制导翻译1程序设计语言中更重要的一个方面，是附着在语言结构上的语义语法表述的是语言的形式，或者说是语言的样子和结构语义揭示了程序本身的涵义、施加于语言结构上的限制或者要执行的动作“老鼠吃猫” 问题语法正确的句子，它的语义可能存在问题2语义分析的任务： 检查语言结构的语义是否正确执行所规定的语义动作如表达式的求值、符号表的填写、 中间代码的生成3语法制导翻译的基本思想： 对于文法:E E1+T E TT FF digitdigitlexval为digit的属性；为文法符号F、T、E对应的属性值将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号

2、，4当当digitdigit为常数时，为常数时， digit digit lexvallexval为为digitdigit在常数表中的入口在常数表中的入口当digit为标识符时， digitlexval为digit在符号表中的入口；F.valF.val、T.valT.val、E.val E.val 可以看作是中间可以看作是中间变量变量5E E1+T E val := E1 val+T valF digitF val := digitlexvalT FT val := F valE TE val := T val而属性的计算以而属性的计算以语义规则语义规则(semantic (semantic

3、rules)rules)的形式赋予由文法符号组成的的形式赋予由文法符号组成的产生式；产生式；在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理6换句话说是：为每一个产生式换句话说是：为每一个产生式配配上上语义规则并且在适当的时候语义规则并且在适当的时候执行执行这这些规则。些规则。即当归约（或推导）到某个产生式即当归约（或推导）到某个产生式时，除了按照产生式进行相应的代换时，除了按照产生式进行相应的代换之外之外(语法分析语法分析)， 还要按照产生式所对还要按照产生式所对应的语义规则执行相应的语义动作，应的语义规则执行相应的语义动作，如计算表达式、查填符号表、产生中

4、如计算表达式、查填符号表、产生中间代码间代码( (语义分析语义分析) )7语法制导翻译是目前最常用的语义分析技术语法分析语法分析建立语法分析树建立语法分析树语义分析语义分析-遍历语法分析树遍历语法分析树语法制导翻译语法制导翻译-建立与遍历同时完成建立与遍历同时完成8例1 台式计算器程序的语法制导定义 产生式 语义规则LEn print(Eval)E E1+T E val := E1 val+T valE T E val := T valT T1*F T val := T1 val*F valT F T val := F valF (E) F val := E valF digit F val

5、:= digitlexval 3*5 +4的分析过程1293*F5TFE+TF4ET3*5 +4的语法分析过程10digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln3*5 +4的语义分析过程11 5.1 语法制导定义(Syntax-directed definitions)语法制导定义也叫属性文法， 通过每一个产生式和一个语义规则集合相关联。 它是在上下文无关文法的基础上， 通过每个文法符号和一个属性集合相关联，语义规则用来计算与产生式

6、中出现的符号相关联的属性的值 。 912属性属性可以代表任何对象：字符串、数字、类型、内存单元或其它对象综合属性继承属性135.1.1 属性 1b是A属性， 在一个语法制导定义中， 规则可表示为：b= f（c1，c2，,ck）其中：f是一个函数，且满足下面两种情况之一： c1,c2,ck是中的文法符号的属性， 或者A的其它属性，则称b是A的综合属性； AP都有与之相关联的一套语义规则，14在两种情况下，都说属性b依赖于属性c1，c2，ck。2c1,c2,ck是A或中的任何文法 符号的属性,则称b是中的符号的 一个继承属性。 15 5.1.2 综合属性 综合属性从下到上包括自身，其属性可从后代和

7、自身的其它属性计算得到S-属性定义:只使用综合属性的只使用综合属性的语法制导定义语法制导定义。利用S-属性定义进行语义分析时,结点属性值的计算正好和自底向上分析建立分析树结点同步进行。16例1 台式计算器程序的S-属性定义 产生式 语义规则LEn print(Eval)E E1+T E val := E1 val+T valE T E val := T valT T1*F T val := T1 val*F valT F T val := F valF (E) F val := E valF digit F val := digitlexval 3*5 +4的分析过程173*F5TFE+TF4

8、ET3*5 +4的语法分析过程digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15Eval:=15digitlexval:=4Fval:=4Tval:=4Eval:=19nL1918digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln19 在分析树中为每个文法符号上加上它们的属性，则称为带注释的分析树，简称注释分析树综合属性值的计算方法 在建立每一个结点处使用语义规则来计算综合

9、属性值，即在 用哪个产生式进行归约后， 就执行那个产生式的s-属性定义计算属性的值，从叶结点到根结点进行计算 对于s-属性定义，通常使用自底向上的分析方法，205.1.3 继承属性 继承属性值是由此结点的父结点和或兄弟结点的某些属性值来决定的。 继承属性从上到下包括兄弟，也即继承属性从前辈和兄弟的属性计算得到21表2 带有继承属性的语法制导定义 产生式 语义规则 DTL L in:=T type T int T type :=integer T real T type :=real L L1,id L1 in :=L in addtype(id entry,L in) L id addtype

10、(id entry,L in)22练习：设AS为文法的综合属性集，AI为继承属性集，则下列语法制导定义中 PxQR R.c=1 Q u Q.a=3 产生式 语义规则 23 PyQR R.e=2 试求AS和AI24 解：由1知：Q.b,R.eAI 整理：AS=Q.a,R.d,R.f AI=Q.b,R.c,R.e由3知： R.cAI由4知： R.d,R.f AS由2知：Q.a=3AS255.2 语义规则语义规则通常有两种表现形式：语义规则也叫语义子程序或语义动作语法制导定义和翻译模式265.2.1 语法制导定义语法制导定义是关于语言翻译高层次规格说明，例：下面是将中缀表达式转化为后缀表达式的文法和

11、相应的语法制导定义 它隐藏了具体实现细节， 使用户不用显式地说明翻译发生的顺序27 产生式 语法制导定义 L E print(E.val) E E1+E2 E.val=E1.val|E2.val|+ E 语法制导定义 只考虑“做什么”，用抽象的属性表示文法符号所代表的语义28翻译模式也叫翻译方案翻译模式一个翻译模式是一个上下文无关文法， 其中被称为语义动作的程序段被嵌入到产生式的右部。一个翻译模式类似于语法制导定义，只是语义规则的计算顺序是显式给出的。29这是一种语法分析和语义动作交错的表示法，翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。 他表达在按深度优先遍历分析

12、树的过程中何时执行语义动作。30例2：一个简单的翻译模式（中缀变后缀） ETR Raddop T print(addop.lexeme)R1| Tnumprint(num.val) 313+5的语义翻译过程ERTPr33T+Pr+5RPr5结果：35+32翻译方案不仅要考虑“做什么”，还要考虑“怎么做”某种意义上说，语法制导定义类似于算法，而翻译方案更象程序33带有继承属性的翻译方案DTL in:=T typeL T int T type :=integerT real T type :=real L L1 in :=L in L1,idaddtype(id entry,L in) L id

13、addtype(id entry,L in) 例5 . 3 变量说明的类型定义 int a,b,c34DLreal,id3,id2id1句子real id1,id2,id3的带继承属性的分析树TT.type=realLLAdd(L.in)Add(L.in)Add(L.in)35例：文法G的产生式如下：S（L）S aL L,SL S1.试写出一个语法制导定义，输出配对括号个数2.写一个翻译方案，打印每个a的嵌套深度36解：S，L引入属性h产生式 语法制导定义S（L） S.h=L.h+1S a S.h=0S S print(S.h)37(aSS.h=0L,(aL.h=0SS.h=0LL.h=0)S

14、S.h=1LL.h=1)SS.h=2(a,(a)的分析过程38S，L引入属性d,翻译方案如下S S.d=0S.d=0 S S（ L.d=S.d+1L.d=S.d+1 L） S a print(s.d)print(s.d) L L1.d=L.dL1.d=L.d L1, S.d=L.dS.d=L.dS L S.d=L.dS.d=L.d S39SS.h=0S(L.d=1L)L.d=1L,S.d=1SS.d=1SPrint(1)a(L.d=2L)S.d=2SPrint(2)a(a,(a)的分析过程405.3 S-属性定义及其自底向上的计算 statevaltop 在分析栈中使用一个附加的域来存放综 合

15、属性值。 下图为一个带有综合属性值域的分析栈： Z Y Z 41 A b:=f(c1,c2,ck) A b X x Y y Z z 例：AXYZ Ab:=f(X x, Y y,Z z)ci(1 ik)是中符号的属性。其中：b是A的综合属性，综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。XY ZA42stateval.AA .btop定义式 A .b=f(X.x, Y.y, Z.z)(抽象) 变成valntop=f(valtop-2,valtop-1,valtop)valntop=f(valtop-2,valtop-1,valtop)（具体可执行代码）。归约后,分析栈为：在执

16、行代码段之前执行： ntop:=top-r+1执行代码段后执行： top:=ntop;其中:r是句柄的长度, ntop为归约后栈顶43例5.10 用LR分析器实现台式计算器产生式 代码段(和表对比）LEn printf(valntop)E E+T valntop:=valtop-2+valtopE TT T*F valntop:=valtop-2*valtopT FF (E) valntop:=valtop-1F digit44表5.5 翻译输入3*5+4n所做的移动输入 state val 使用的产生式3*5+4n - - *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T* 3- +4n T* 5 3-5 +4n T* F 3-5 F digit 45 +4n T 15 T T*F +4n E 15 E T 4n E+ 15- n E+4 15-4 n E+F 15-4 F digit n E+T 15-4 T F n E 19 E E+T En 19 - L 19 L En输入 state val 使用的产生式46总结：采用自底向上分析，