编译原理6-4.1-L属性文法-翻译模式PPT学习课件

1、第六章 属性文法和语法制导翻译,6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S-属性文法的自下而上计算 6.4 L-属性文法和自顶向下翻译 6.5 自下而上计算继承属性,6.4 L-属性文法和自顶向下翻译,6.4.1 翻译模式 6.4.2 自顶向下翻译 6.4.3 递归下降翻译器的设计,L-属性文法,L-属性文法可通过一次遍历就计算出所有属性值。 诸如LL(1)这种自上而下分析方法的分析过程，从概念上说可以看成是深度优先建立语法树的过程 我们可以在自上而下语法分析的同时实现L-属性文法的计算。,L-属性文法,一个属性文法称为 L-属性文法 如果对于每个产生式 AX1X2Xn， 其

2、每个语义规则中的每个属性或者是综合属性， 或者是Xj(1=j= n)的一个继承属性 , 且这个继承属性仅依赖于： (1) 产生式Xj的左边符号X1，X2，Xj-l的属性 (2) A的继承属性 S-属性文法一定是L-属性文法,L-属性文法的例子 6.1 节 表6.1 表6.2,表6.7 非L-属性文法的例子,因为 Q.i 依赖于右部符号R的综合属性R.s,6.4.1 翻译摸式,翻译模式（Translation schemes） 一种适合语法制导翻译的另一种描述形式。 在翻译模式中，和文法符号相关的属性和语义规则（语义动作），用花括号括起来，插入到产生式右部的合适位置上。,R addop T R,

3、 print( addop.lexme) R,ET R R addop T print( addop.lexme) R | T num print( num. lexme) ,例: 将含有+和-运算的中缀表达式翻译为后缀形式,如 表达式 9-+2 后缀表示为 9 - 2 +,翻译模式给出了使用语义规则进行计算的次序,这样就可把某些实现细节表示出来。,图6.10 9+2 的说明动作的语法分析树,E,T,R,9,print(9),T,print(),R,5,print(5),+,T,print(+),2,print(2),R,1,2,3,4,5,把语义动作看作是终结符号 按深度优先次序遍历分析树，

4、即得到,9,5,2,ET R R addop T print( addop.lexme) R | T num print( num. lexme) ,参考输出后缀式的属性文法,例如，假设有下面的产生式和语义规则： T T1* F T. val := T1.val * F. val 建立翻译模式： T T1* F T. val := T1. val * F. val,只需要综合属性时, 可以这样建立翻译模式: 为每一个语义规则建立一个包含赋值的动作, 并把这个动作放在相应的产生式右边的末尾。,如果既有综合属性又有继承属性，在建立翻译模式时就必须满足三个条件 (1)产生式右边的符号的继承属性必须在

5、这个符号以前的动作中计算出来。 (2)一个动作不能引用这个动作右边的符号的综合属性。 (3)产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,下面的翻译模式不满足上述三个条件中的第一个条件: (1)产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 SA1 A2 A1. in:=1; A2. in:=2 Aa print(A. in) ,可以改为 S A1. in:1 A1 A2. in:=2 A2,print(A.in),1,print(A.in),2,A1. in:1; A2. in:=2,3,该属性还没

6、有定义,S A1. in:1 A1 A2. in:=2 A2,print(A.in),1,print(A.in),S,A,a,A,a,2,A2. in:=2,3,A1. in:1,4,例: 给定一个L-属性文法, 建立一个满足上述三个条件的翻译模式。,基于数学格式语言EQN 给定输人E sub 1 .Val EQN把E，1和.val分别按不同的大小放在相关的位置上，如图所示。,图6.11 盒子的语法制导安放,非终结符B(表示盒子)代表一个公式， 产生式BBB 代表两个盒子并置， BB1 sub B2 代表B2的大小比B1的小,并且放在下角标的位置,表6.8 盒子大小和高度的属性文法,使B2.p

7、s减少30%,把盒子B2向下放置,继承属性ps影响 公式的高度,综合属性B.ht代表 B的高度,查表获得,S B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,图6.12 从表6.8构造出的翻译模式,为文法 G:S ( L ) | a L L , S | S 写一个翻译方案

8、，它输出每个a的嵌套深度 例如:对于( a , ( a , a) ) ，输出的结果是 1 2 2,S S. depth := 0 S S L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth := L. depth L1 , S. depth := L. depth S L S. depth := L. depth S,补充例1,S,(,L,),L,S,S S. depth := 0 S S L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth :

9、= L. depth L1 , S. depth := L. depth S L S. depth := L. depth S,( a , ( a , a) ),S,a,(,L,),L,S,S,a,a,0,1,1,1,1,1,2,2,2,2,2,2,为文法 G:S ( L ) | a L L , S | S 写一个翻译方案,打印出每个a在句子中是第几个字符 例如,当句子是 ( a , ( a , ( a , a ) , (a) ) )时， 打印的结果是 2 5 8 10 14,补充例2,S S. in := 0 S S L. in := S. in + 1 ( L ) S. out := L.

10、 out + 1 S a S. out := S. in + 1; print (S. out) L L1. in := L. in L1 , S. in := L1. out + 1 S L. out := S. out L S. in := L. in S L. out := S. out ,L. in := S. in + 1,S. out := L. out + 1 ,L1. in := L. in ,S. in := L1. out + 1 ,L. out := S. out ,S. in := L. in ,L. out := S. out ,S. out := S. in + 1; print (S. out) ,S. out := S. in + 1; print (S. out) ,S,(,L,),L,S,S,a,a,S.in=0,S S. in := 0 S S L. in := S. in + 1 ( L ) S. out := L. out + 1 S a S. out := S. in + 1; prin