《语义分析iii》ppt课件

资源描述

《《语义分析iii》ppt课件》由会员分享，可在线阅读，更多相关《《语义分析iii》ppt课件（29页珍藏版）》请在金锄头文库上搜索。

1、编译原理和技术,大连理工软件学院胡彦 ,4.3 L属性定义的自上而下计算,S属性定义的计算边分析边计算分析完毕，属性也计算完毕问题：继承属性是否可以采用边分析边计算的方式进行？,边分析边计算，使得语法和语义的计算都在一遍处理完毕，而不需要为语义分析而单独进行一遍编译分析,4.3 L属性定义的自上而下计算,属性计算与分析方法之间的关系属性的计算次序受分析方法所限定的分析树结点建立次序的限制。分析树的结点是自左向右生成。所以，仅当属性信息是自左向右流动时，才有可能在分析的同时完成属性计算。,4.3 L属性定义的自上而下计算,4.3.1 L属性定义如果每个产生式A X1 X2 X

2、n 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，1 j n, 但它仅依赖：该产生式中Xj左边符号X1, X2, , Xj-1的属性； A的继承属性。 S属性定义属于L属性定义。,4.3 L属性定义的自上而下计算,L属性定义的例子：变量类型声明的语法制导定义,4.3 L属性定义的自上而下计算,int id1, id2, id3的分析树的依赖图 D TL L.in := T.type,4.3 L属性定义的自上而下计算,对于L属性定义，与S属性的一个最本质区别在于 S属性定义中，只要将产生式作为一个整体看待即可，语义规则可以视为是附着在整个产生式上 L属性定义则不一样，它跟属性

3、所属的符号在产生式中的位置有关系为了对L属性定义进行翻译，必须提一下一个概念翻译方案,4.3 L属性定义的自上而下计算,4.3.2 翻译方案语义动作（语义规则）插入到产生式右部的任何地方，以表达动作的执行时刻。 ABC,4.3 L属性定义的自上而下计算,4.3.2 翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是8 5 + 2 。 E T R R addop T print (addop.lexeme) R1 | T num print (num.val) E T R num print (8) R numprint (8) addop Tprint

4、 (+)R numprint(8) addop numprint(5)print (+)R print(8)print(5)print(+) addop Tprint() R print(8)print(5)print(+)print(2)print(),4.3 L属性定义的自上而下计算,L属性定义的翻译方案的三条限制：产生式右部符号的继承属性必须在先于这个符号的动作中计算 A-Xy.in=x.sYZ = OK A-XYY.in=x.sZ = ERROR 一个动作不能引用该动作右边符号的综合属性左部非终结符的综合属性只能在它所依赖的所有属性都计算完后才能计算,4.3 L属性定义的自上而下计

5、算,例数学排版语言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text,4.3 L属性定义的自上而下计算,例数学排版语言EQN E sub 1 .val,4.3 L属性定义的自上而下计算,例数学排版语言EQN 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 te

6、xt B.ht := text.h B.ps ,4.3 L属性定义的自上而下计算,4.3.3 预测翻译器的设计目标：为文法计算其中的L属性值方法：把预测分析器的构造方法推广到翻译方案的实现产生式R +TR | 的分析过程 procedure R; begin if lookahead = + then begin match ( + ); T; R end else begin /* 什么也不做 */ end end,4.3 L属性定义的自上而下计算,例左递归的消除引起继承属性,4.3 L属性定义的自上而下计算,E T R.i := T.nptr T + T + T + R E.npt

7、r := R.s R + T R1.i := mknode ( +, R.i, T.nptr) R1 R.s := R1.s R R.s := R.i T F W.i := F.nptr W T.nptr := W.s W * F W1.i := mknode ( *, W.i, F.nptr) W1 W.s := W1.s W W.s := W.i ,消除左递归后文法,R,R,R,T.nptr,？,4.3 L属性定义的自上而下计算,function R (i :syntax_tree_node ) :syntax_tree_node; var nptr , i1, s1, s : synta

8、x_tree_node; addoplexeme : char; begin if lookahead = + then begin /* 产生式 R +T R */ addoplexeme := lexval; match( + ); nptr := T; i1 := mknode(addoplexme, i , nptr) ; s1 := R (i1 ); s : = s1 end else s := i; /* 产生式 R */ return s end;,R + T R1.i := mknode ( +, R.i, T.nptr) R1 R.s := R1.s,产生式R +TR | 的

10、算,4.3.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D L : T T integer | char L L, id | id 改成从右向左归约 D id L L , id L | : T T integer | char,4.3 L属性定义的自上而下计算,D id L addtype (id. entry, L. type) L , id L1 L. type := L1. Type; addtype (id. entry, L1. type) L : T L. type := T. type T integer T. type := integer

11、T real T. type := real,4.4 L属性的自下而上计算,L属性的自上而下计算与自上而下的语法分析的过程是一致的但是，自上而下分析能够处理的文法局限于LL(1) 为了为更为一般的文法计算L属性，需要研究自下而上的L属性计算方法,4.4 L属性的自下而上计算,L属性自下而上计算需要解决的问题：,栈 state val,top,AX Y Z.i = X.x Z,一个状态（文法符号）对应一个综合属性，该属性的值一般在处理完该文法符号之后得到。那么在Z还没有开始处理前，继承属性Z.i 就没有对应的val条目供其使用！,解决办法：在栈上消除继承属性,4.4 L属性的自下而上计算,4.

12、4.1 删除翻译方案中嵌入的动作问题自下而上的分析中，语义动作的执行是在使用产生式对句柄进行归约的时候但是，L属性定义的继承属性的计算需要嵌在产生式右部不同的地方问题的解决方案：通过改写文法，使得所有嵌入在产生式中间的动作变换成只在产生式的最右端出现,4.4 L属性的自下而上计算,4.4.1 删除翻译方案中嵌入的动作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端。 E T R R + T M R1 |

13、T N R1 | T num print (num.val) M print (+) N print (),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性所依赖的属性在分析栈上的位置能静态确定例 int p, q, r D T L.in := T.type L T int T. type := integer T real T. type := real L L1.in := L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性,每

14、个L结点上L.in = T.type,L id addtype (id.entry, L.in ),L L1.in := L.in L1, id addtype (id.entry, L.in ),L L1.in := L.in L1, id addtype (id.entry, L.in ),4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,所依赖的属性在分析栈上的位置不能静态确定 S aAC C.i := A.s S bABC C.i := A.s C c C.s := g(C.i) 增加标记非终结符 S aAC C.i := A.s S bABMC M.i := A.s; C.i := M.s C c C.s := g(C.i) M M.s := M.i,

展开阅读全文