天津大学编译原理讲义-Part6属性文法和语法制导翻译.ppt

L-属性定义的语法制导翻译 设计L属性定义的语法制导翻译需要注意以下几点： 基本设计原则：当某个动作引用一个属性时，这个属性是可用的。也就是说，一个动作不会引起一个没有计算出来的属性。 只有综合属性时 为每一个语义规则建立一个赋值动作，并把该动作放在产生式右部的末尾 T→T1*F T.val := T1.val ×F.val T→T1*F {T.val := T1.val ×F.val} L-属性定义的语法制导翻译 同时存在综合属性和继承属性时： 产生式右部符号的继承属性必须在这个符号以前的动作中计算出来 一个动作不能引用该动作右部符号的综合属性 产生式左部非终结符的综合属性只有在其引用的所有属性值都计算出来以后才能计算。计算该属性的动作通常放在产生式右部的末尾。 下面的翻译模式不符合上面的定义： S→A1A2 {A1.in := 1; A2.in := 2} A→a {print(A.in)} 按深度优先遍历时，要打印第二个产生式里的继承属性A.in时，该属性还没有被定义。 L-属性文法举例 产生式 语义规则 S→B B.ps := 10 S.ht := B.ht B→B1B2 B1.ps := B.ps B2.ps := B.ps B.ht := max(B1.ht, B2.ht) B→ B1 sub B2 B1.ps := B.ps B2.ps := shrink(B.ps) B.ht := disp(B1.ht, B2.ht) B→text B.ht := text.h ×B.ps S→{B.ps := 10} B {S.ht := B.ht} B→{B1.ps := B.ps} B1 {B2.ps := B.ps} B2 {B.ht := max(B1.ht, B2.ht)} B→ {B1.ps := B.ps} B1 sub {B2.ps := shrink(B.ps)} B2 {B.ht := disp(B1.ht, B2.ht)} B→text {B.ht := text.h ×B.ps} L-属性文法的自顶向下翻译 在预测分析的过程中实现L-属性文法 为了明显的看出动作和属性计算发生的属性，我们使用翻译模式而不是属性文法。 为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。 将前面讲过的方法扩充，从翻译模式中消除左递归（LL(1)文法构造的步骤），这种方法也适用于带有综合属性的翻译模式。 举例 E→E1+T {E.val := E1.val + 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} E→T {R.i := T.val} R {E.val := R.s} R→+ T {R1.i := R.i + T.val} R1 {R.s := R1.s} R→- T {R1.i := R.i - T.val} R1 {R.s := R1.s} R→ε {R.s := R.i} T→( E ) {T.val := E.val} T→num {T.val := num.val} 9-5+2 R - T num R ε E T num R + T num val=9 val=9 i=9 val=5 val=5 i=4 val=2 val=2 i=6 s=6 val=6 一个符号继承属性必须由出现这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来之后才能计算 消除左递归的一般方法 假设有如下的翻译模式 A→A1Y {A.a := g(A1.a, Y.y)} A→X {A.a := f(X.x)} 每个文法符号都有综合属性，g和f是任意函数。 文法可以转换为： A→XR R→YR | ε 考虑语义动作，变为： A→X {R.i := f(X.x)} R {A.a := R.s} R→Y {R1.i := g(R.i, Y.y)} R1 {R.s :=