编译原理第八章—语法制导翻译.pptVIP

L－属性文法和自顶向下翻译 LL（1）这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现L属性文法的计算。 消除左递归： E→E addop T | T T→num 变为 E→TR R→addop T R|ε T→num （消除左递归）2+3-5的语法树 LL（1）分析: E→TR R→addop T R|ε T→num E R T T + 2 T - 3 R R 5 ? 说明语义动作的语法树 E R T Print’+’ + 2 T - 3 R R 5 ? print’2’ T print’3’ print’5’ Print’-’ E→TRR→addop T {print(addop. Lexeme)} R1|εT→num {print(num.val)} 补充：左递归翻译模式的转换 左递归翻译模式 A→A1Y｛A.a:=g(A1.a,Y.y)} A→X ｛A.a:=f(X.x)} 每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。 消除左递归，文法转换成 A→X R R→Y R|ε 补充：左递归翻译模式的转换 再考虑语义动作，翻译模式变为： A→X ｛R?i:=f(X ? x)} R ｛A. ? a:=R. ? s} R→Y ｛R1 ? i:=g（R ? i,Y ? y）} R1 ｛R ? s:=R1 ? s} R→ε ｛R ? s:=R ? i} 其中，使用R的继承属性i和综合属性s。 翻译模式1和翻译模式2的结果是一样的。 A→A1Y {A.a: = g(A1。a, Y.y)} A→X {A.a: = f(X.x)} A.a=g(g(f(X.x),Y1.y),Y2.y) A.a=g(f(X.x),Y1.y) Y2 A.a=f(X.x) Y1 X A A Y A Y X A→X{R.i: = f(X.x)} R→Y {R1.i: = g((R.i),Y.y)}  R {A.a: =R.s} R1{R.s: = R1.s} A→XR R→YR｜ε A X R Y1 R Y2 R ? A X R.i=f(X.x) Y1 R.i=g(f(X.x),Y1.y) Y2 R.i=g(g(f(X.x),Y1.y),Y2.y) ? L-属性文法 L-属性文法的定义和翻译模式 L-属性文法在自上而下分析中的实现 L-属性文法在自下而上分析中的实现 自下而上的分析中实现L-属性文法 两种方法 从翻译模式中去掉嵌入在产生式中间的动作 用综合属性代替继承属性 一、从翻译模式中去掉嵌入在产生式中间的动作转换方法:引入新的非终结符N和产生式N→ ε,把嵌入在产生式中间的动作用非终结符N代替,并把这个动作放在产生式后面. 例: E→T R R→ + T {print (‘+’) } R1 R→- T {print (‘-’) } R1 R→ε T→num {print (num.val) } 文法变换后,接受的语言相同. E→T R R→ + T M R1 R→- T N R1 R→ε T→num {print (num.val) } M→ε {print (‘+’) } N→ε {print (‘-’) } 目的:使所有嵌入的动作都出现在产生式的末尾,可以自下而上处理继承属性. 二、用综合属性代替继承属性 有时，改变基础文法可能避免继承属性。例如，一个Pascal的说明由一标识符序列后跟类型组成，如, m, n: integer。这样的说明的文法可由下面形式的产生式构成 D→L：T T→integer|char