语法制导翻译

1、第五章第五章 语法制导翻译语法制导翻译2程序设计语言中更重要的一个方面，是附着在语言结构上的语义语法表述的是语言的形式，或者说是语言的样子和结构语义揭示了程序本身的涵义、施加于语言结构上的限制或者要执行的动作“老鼠吃猫” 问题语法正确的句子，它的语义可能存在问题3语义分析的任务： 检查语言结构的语义是否正确执行所规定的语义动作如表达式的求值、符号表的填写、 中间代码的生成4中间代码生成与语言的语义密切相关，而语义的形式化描述是十分困难的。语法制导翻译：这种模式实际上是对上下文无关文法的一种扩充。5语法制导翻译的基本思想： 对于文法:E E1+T E TT FF ididlexval为id的属性

2、；F.val、T.val、E.val为文法符号F、T、E对应的属性值将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号，6当当idid为常数时，为常数时， idid lexvallexval为为idid在常数在常数表中的入口表中的入口当id为标识符时， idlexval为id在符号表中的入口；F.valF.val、T.valT.val、E.valE.val 可以看作是中间可以看作是中间变量变量7E E1+T E val := E1 val+T valF idF val := idlexvalT FT val := F valE TE val := T val而属性的计算

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

4、义动作，应的语义规则执行相应的语义动作，如计算表达式、查填符号表、产生中如计算表达式、查填符号表、产生中间代码间代码( (语义分析语义分析) )9语法制导翻译是目前最常用的语义分析技术语法分析语法分析建立语法分析树建立语法分析树语义分析语义分析-遍历语法分析树遍历语法分析树语法制导翻译语法制导翻译-建立与遍历同时完成建立与遍历同时完成10例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

5、valF (E) F val := E valF id F val := idlexval 3*5 +4的分析过程12113*F5TFE+TF4ET3*5 +4的语法分析过程12idlexval:=3Fval:=3Tval:=3idlexval:=5Fval:=5Tval:=15*Eval:=15+idlexval:=4Fval:=4Tval:=4Eval:=19Ln3*5 +4的语义分析过程13 5.1 语法制导定义(Syntax-directed definitions)语法制导定义也叫属性文法，9 在文法产生式右部适当的位置上插入语义规则而得到的新文法称为属性文法。14 通过每一个产生式

6、和一个语义规则集合相关联。它是在上下文无关文法的基础上， 通过每个文法符号和一个属性集合相关联， 语义规则用来计算与产生式中出现的符号相关联的属性的值 。 915属性属性可以代表任何对象：字符串、数字、类型、内存单元或其它对象综合属性继承属性165.1.1 属性 1b是A属性， 在一个语法制导定义中， 规则可表示为：b= f（c1，c2，,ck）其中：f是一个函数，且满足下面两种情况之一： c1,c2,ck是中的文法符号的属性， 或者A的其它属性，则称b是A的综合属性； AP都有与之相关联的一套语义规则，17在两种情况下，都说属性b依赖于属性c1，c2，ck。2c1,c2,ck是A或中的任何文

7、法 符号的属性,则称b是中的符号的 一个继承属性。 18 5.1.2 综合属性 综合属性从下到上包括自身，其属性可从后代和自身的其它属性计算得到S-属性定义:只使用综合属性的只使用综合属性的语法制导定义语法制导定义。利用S-属性定义进行语义分析时,结点属性值的计算正好和自底向上分析建立分析树结点同步进行。19例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

8、:= E valF id F val := idlexval 3*5 +4的分析过程203*F5TFE+TF4ET3*5 +4的语法分析过程idlexval:=3Fval:=3Tval:=3idlexval:=5Fval:=5Tval:=15Eval:=15idlexval:=4Fval:=4Tval:=4Eval:=19nL1921idlexval:=3Fval:=3Tval:=3idlexval:=5Fval:=5Tval:=15*Eval:=15+idlexval:=4Fval:=4Tval:=4Eval:=19Ln22 在分析树中为每个文法符号上加上它们的属性，则称为带注释的分析树，简

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

10、=L in addtype(id entry,L in) L id addtype(id entry,L in)25练习：设AS为文法的综合属性集，AI为继承属性集，则下列语法制导定义中 PxQR Q.b=R.d R.c=1 R.e=Q.a Q u Q.a=3 产生式 语义规则 26 PyQR Q.b=R.f R.c=Q.a R.e=2 Rv R.d=R.c R.f=R.e 试求AS和AI27 解：由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=3AS285.2 语义规则语义规则通常有

11、两种表现形式：语义规则也叫语义子程序或语义动作语法制导定义和翻译模式295.2.1 语法制导定义语法制导定义是关于语言翻译高层次规格说明，例：下面是将中缀表达式转化为后缀表达式的文法和相应的语法制导定义 它隐藏了具体实现细节， 使用户不用显式地说明翻译发生的顺序30 产生式 语法制导定义 L E print(E.val) E E1+E2 E.val=E1.val|E2.val|+ E id E.val=id.lexval语法制导定义 只考虑“做什么”，用抽象的属性表示文法符号所代表的语义31翻译模式也叫翻译方案5.2.2翻译模式一个翻译模式是一个上下文无关文法， 其中被称为语义动作的程序段被嵌

12、入到产生式的右部。一个翻译模式类似于语法制导定义，只是语义规则的计算顺序是显式给出的。32这是一种语法分析和语义动作交错的表示法，翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。 他表达在按深度优先遍历分析树的过程中何时执行语义动作.33例2： ETE E+ T E| Tid 一个简单的翻译模式（中缀变后缀） ETE E+ T print(+.lexeme)E| Tidprint(id.val) 343+5的语义翻译过程EETPr33T+Pr+5EPr5结果：35+35翻译方案不仅要考虑“做什么”，还要考虑“怎么做”某种意义上说，语法制导定义类似于算法，而翻译方案更象程

13、序36带有继承属性L.in的翻译方案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 addtype(id entry,L in) 例5 . 3 变量说明的类型定义 int a,b,c37DL.in=T.typeLrealL1.in=L.in,id3L1.in=L.in,id2id1句子real id1,id2,id3的带继承属性的分析树TT.type=realLLAdd(L.in)Add(L.in)Add(L.in)38例：文法G

14、的产生式如下：S（L）S aL L,SL S1.试写出一个语法制导定义，输出配对括号个数2.写一个翻译方案，打印每个a的嵌套深度39解：1.为S，L引入属性h产生式 语法制导定义S（L） S a L L1,S L S S S S.h=0S.h=L.h+1L.h=L1.h+S.hL.h=S.hPrint(S.h)40(aSS.h=0L,(aL.h=0SS.h=0LL.h=0)SS.h=1LL.h=1)SS.h=2(a,(a)的分析过程412.为S，L引入属性d,翻译方案如下S S S（L） S a L L1, SL SS.dS.d=0 =0 S S L.dL.d=S.d+1 =S.d+1 L )

15、L )print(S.dS.d) )L1.d=L.dL1.d=L.d L1,L1,S.d=L.dS.d=L.d S SS.d=L.dS.d=L.d S S42SS.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)的分析过程435.3 S-属性定义及其自底向上的计算 statevaltop 在分析栈中使用一个附加的域来存放综 合属性值。 下图为一个带有综合属性值域的分析栈： Z Y Z Z.val Y.val Z.val 44 A b:=f(c1,c2,ck) A b X x Y y Z z 例：AXYZ

16、Ab:=f(X x, Y y,Z z)ci(1 ik)是中符号的属性。其中：b是A的综合属性，综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。XY ZA45stateval.AA .btop定义式 A .b=f(X.x, Y.y, Z.z)(抽象) 变成valntopvalntop=f(valtop-2,valtop-1,valtop)=f(valtop-2,valtop-1,valtop)（具体可执行代码）。归约后,分析栈为：在执行代码段之前执行： ntop:=top-r+1执行代码段后执行： top:=ntop;其中:r是句柄的长度, ntop为归约后栈顶46例5.10

17、用LR分析器实现台式计算器产生式 代码段(和表5.1对比）LEn printf(valntop)E E+T valntop:=valtop-2+valtopE TT T*F valntop:=valtop-2*valtopT FF (E) valntop:=valtop-1F id47表5.5 翻译输入3*5+4n所做的移动输入 state val 使用的产生式3*5+4n - - *5+4n 3 3 *5+4n F 3 Fid *5+4n T 3 TF 5+4n T* 3- +4n T* 5 3-5 +4n T* F 3-5 F id 48 +4n T 15 T T*F +4n E 15 E

18、 T 4n E+ 15- n E+4 15-4 n E+F 15-4 F id n E+T 15-4 T F n E 19 E E+T En 19 - L 19 L En输入 state val 使用的产生式49总结：采用自底向上分析， 例如LR分析，首先给出S-属性定义， 然后,把S-属性定义变成可执行的代码段, 这就构成了翻译程序。 象一座建筑, 语法分析是构架， 归约处有一个“挂钩”, 语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。 这样，随着语法分析的进行， 归约后调用相应的语义子程序, 50 在这种分析模式中， 语法分析是主动的， 语义分析是从动的， 语法分析制导着语义分析5

19、15.4 L-属性定义 一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，在语法分析过程中进行语义分析和翻译，属 性的计算顺序受到语法分析建立分析树结点顺序的限制。它适应多种自底向上和自顶向下的翻译方法。 52 一个语法制导定义是L- L-属性定义属性定义，5.4.1 L-属性定义每一个S-属性定义都是L-属性定义。如果AX1X2XnP, 或是Xj(1j n)的一个继承属性，1、产生式中Xj的左边符号X1,X2，Xj-1 的属性； 2A的继承属性。 其每一个语义规则中的每一个属性都是一个综合属性，这个继承属性仅依赖于 53例.一个简单的翻译模式 ETR Raddop T print(a

20、ddop.lexeme)R1| Tnumprint(num.val) 9 5 2 +它是输入表达式9-5+2的后缀式。把语义动作看成终结符号， 输入9-5+2,其分析树如图， 当按深度优先遍历它，执行遍历中访问的语义动作， 将输出：54ET9TPt(9)RPt(-)Pt(+)R-5Pt(5)+T2Pt(2)R 9-5+2的带语义动作的分析树55设计翻译模式（根据语法制导定义） TT1*F Tval:=T1 val*F val TT1*F Tval:=T1 val*F val1. 只需要综合属性的情况：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：条件：语

21、法制导定义是L-属性定义，保证语义动作不会引用还没有计算的属性值。56产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。一个动作不能引用这个动作右边符号的综合属性。 产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。 2. 既有综合属性又有继承属性计算这种属性的动作通常可放在产生式右端的未尾.57下面的翻译模式不满足要求： SA1A2 A1in:=1; A2 in:=2 A a print(A in) SA2A1aPr(A.in)A1.in=1,A2.in=2end58如果改正一下，就满足L-属性文法的要求： SA1in:=1; A2 in:=2A1A2

22、A a print(A in) SA2A1aPr(A1.in)A1.in=1,A2.in=259 5.5 自顶向下的翻译-用翻译模式构造自顶向下翻译。 5.5.1 从翻译模式中消除左递归对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。60 EE1+T E val:=E1val+T val E E1-T E val:=E1 val-T val E T E.val:=T val T (E) T val:=E val T num T val:=num val 图5.13 带左递归的文法的翻译模式61ETR9-TR15+TR12ETRRTR1R-T

23、R1RT（ E ）Tnum62ETR.i=T.valRE.val=R.s9t.val=9-TR1.i=R.i-T.valR1R.s=R1.s5T.val=5+TR1.i=R.i+T.valR1R.s=R1.s2T.val=2R.s=R.i63 ET Ri:=T val RE val:=R s R TR1i:=R.i+T. val R1R. s:=R1 s R- TR1 i:=R i-Tval R1R s:=R1 s RR s:=R i T（ E ） T val:=E.val Tnum T val:=num val 经过转换的带有右递归文法的翻译模式676964ETR.i=T.valRE.val=R.s9t.val=9-TR1.i=R.i-T.valR1R.s=R1.s5T.val=5+TR1.i=R.i+T.valR1R.s=R1.s2T