大三下编译最终作业lect5-attribute

1、2011年春季学期编译技术第5章语导翻翻译译Syntax-Directed Translation.语导翻译概述5.1 属性文法5.2 翻译模式5.3 自顶向下翻译5.4 自底向上翻译2.语导翻译概述在语法分析完成之后，一般还需要把输入的源代码翻译为一种目标表示形式。n语导翻译（syntax-directed translation）指的是编译器在分析过程中执行的工作n 首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码n 文法符号的属性可以描述文法符号的语义例如，一个变量文法符号的属性可以有变量的类型，层次，地址等。表达式的属性有类型，值等。n 通过对属性值的计算完成翻译任务3语

2、义动作（semantic action）分析器中添加一些代码分析器的语法动作一起配合执行。n 语法动作：指的是分析过程中的移进和归约n 语义动作：每个产生式都关联一些代码序列， 当该产生式被应用的时候会执行相应的代码。n 对于代码序列中可以做什么并没有强加的限制这里的代码通常是和分析器一起进行编译的可以用于打印消息，停止分析活动，或者是处理编译器的数据结构4语义值（Semantic Value）1. . .n每个符号都对应一个（或多个）语义值。n 在自底向上分析中，X1. . .Xn的语义值是已知的，这样语义动作会为A计算一个语义值。n 在自顶向下分析中，A的值是已知的，而在该产生式被应用之后

3、才能够知道X1. . .Xn的值。n 终结符号的语义值通过词法得到。n 非终结符号的语义值通过产生式对应的语义动作来计算。ttribute)5n 继承属性(InheritedAttribute)n 在分析树中，一个结点的综合属性值是从其子结点的属性值计算出来的；而一个结点的继承属性值是由该结点兄弟结点和父结点的属性值计算出来的。语义翻译的实现紧跟着语法分析的进展n 每识别出一个语法结构，就会对它的语义进行分析和翻译。6综合属性示例 （表达式文法）语法继承属性示例A xA | x语法语义值计算符号串中每个 x 的位置8."AX1X2Xn ÎP都有与之相关联的若干个属性定义规则

4、，属性定义规则一般形式为= f(c1, c2f是一个函数，而且k)1c是A的一个属性并且c1, c2, , ck是A的继承属性或是某个Xi的属性，称c为A的综合属性。或2c是某个符号Xi的属性并且c1, c2, , ck是A或Xj的属性，称c为Xi的一个继承属性。在两种情况下，都说属性 c 依赖于属性 c1, , ck。Ø属性定义规则也可以是过程（void型函数）调用，此时称为A的虚综合属性。9台式计算器属性文法定义10产生式属性定义规则L®Enprint (E.val)E ®E1+TE.val := E1.val + T.valE ®TE.val :=

5、 T.valF ®(E)F.val := E.valF ®integerF.val := integer.lexval 3*5+4n的计算过程T×val:=15T×val:=3*分析树各结点属性的计算可以自下而上地完成11digit×lexval:=5F×val:=3LE×val:=19digit×lexval:=3F×val:=5F×val:=4i i ×l xl =4T×val:=4E×val:=15+n带有继承属性 .的属性文法定义12产生式属性定义规则D&#

6、174;TLL.in:=T ®intT.type :=integerT ®realT.type :=realL ®L1, idL1.in :=L.in EnterID(, L.in)L ®idEnterID (, L.in)real id1, id2, id3的计算过程DTLin 564 typereal,in 7id3 3 nameL8in 9L10,id22 name 属性编号代表计算顺序。(编号6/8/10对应动作EnterID) 顺序并不唯一。id1131 name属性求值n 有向边：若结点m表示的属性值依赖于结点n的

7、属性值，则有从n到m的有向边。n 若依赖图中无环，则存在一个拓扑排序，它就是属性值的计算顺序。14抽象语法树 （Abstract Syntax Tree) 产生式 S if B then S1 else S2 的语法树if-then-else |BS1S2 赋值语句的语法树assignmentvariableexpression在语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。15具体语法树 vs. 抽象语法树具体语法树 （分析树）16.v抽象语法树具体语法树抽象语法树（AST）建立表达式的语法树的属性文法建立表达式的语法树使用的函数:1. mknode (op, left, r

8、ight) 建立一个运算符号结点, 标号是op, 两个域left和right指向运算分量结点的指针。2. mkleaf (id, name) 建立一个标识符结点, 由标号id标识, 一个域entry指向标识符符号表中相应的项。3. mkleaf (num, val) 建立一个常数结点, 标号为num, 域val用于存放常数的值。上述函数都会返回新建立结点的指针。18例：a-4+c的语法树idto entrycidto entry a19num4+建立语法树的属性文法定义产生式语义规则E ® E1+T E ® E1-TE ® T T ® (E)T 

9、4; idT ® numE.nptr:=mknode('+',E1.nptr,T.nptr) E.nptr:=mknode('-',E1.nptr,T.nptr) E.nptr:=T.nptrT.nptr:=E.nptrT.nptr:=mkleaf(id,) T.nptr:=mkleaf(num,num.val)20例：a-4+c的语法树的构造过程idto entrycidto entry a21+num4例：+*dabc22表达式 a *-c)+(b-c)*d 的DAGS-属性文法中使用一个附加的域来存放 合属性析栈statevalto

10、p23.ZZ.z.YY.y综合属性的计算"A®ab := f(c1,c2,ck)b是A的综合属性, ci(1£ i£k)是a中符号的属性。综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。A®XYZA.a:=f(X.x, Y.y, Z.z)A.aX.xZ.z24stateval定义式 A.a:=f(X.x, Y.y, Z.z)（抽象）变成valnewtop:=f(valtop-2,valtop-1,valtop)（具体可执行代码）。在执行代码段之前执行： newtop:=top-r+1top:=newtop;执行代码段后执行：r

11、是句柄的长度.25top.statevaltopYY.yZZ.z.AA.a例：用26产生式代码段L®EnE ®E+TE ®TT ®T*F T ®FF ®(E)F ®digitprintf (valnewtop) valnewtop:=valtop-2+valtopval newto:=val to -2 *val tovalnewtop:=valtop-127输入stackval使用的产生式* +4n-*5+4n33*5+4nF3F®digit*5+4nT3T®F 5+4nT*3-+4nT*53-5+4n

12、T*F3-5F ®digit翻译输入 *所做的移动 翻译输入3*5+4n所做的移动（续）T® T*FE® T+4n+4n4nnn nT E E+E+4E+F E+T151515-15-415-415-4F ® digitT® F®+En19 -L® EnL1928L-属性文法一个属性文法是L-属性文法, 如果"AX1X2XnÎP, 其每一个属性定义规则中的每一个属性或是一个综合属性，或是Xj (1£j £ n)的一个继承属性， 并且这个继承属性仅依赖于1. 产生式中Xj的左边符号X1，

13、X2，Xj-1的属性; 和2. A的继承属性。29 每一个S-属性文法都是L-属性文法。 L-属性定义可用于按深度优先顺序来计算。非L-属性文法的例子上表的属性文法定义不是L-属性文法。文法符号Q的继承属性依赖于它右边文法符号R的属性。30产生式属性定义规则A®LML.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s).i:=r(A.i)A ®.i:=q(R.s)A.s:=f(Q.s).对属性文法的扩充一种便于译模式翻译的形式。n 把其中的属性定义规则改为计算属性值的规则（或称语义动作）用花括号 括起来，它们可入到产生式右部的任何合适的位置上。n 这是一种语法分

14、析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。n 翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。n 原来的不含语义动作的文法称作是基础文法。31例：一个简单的翻译模式(只包含+/-操作的表达式)ETRRaddop T print(addop.lexeme) R1|Tnum print(num.val)把语义动作看成终结符号，输入9-5+2, 其分析树见下页，当按深度优先遍历它，执行遍历中访问的语义动作，将输出9 5 - 2 +它是输入表达式9-5+2的后缀式。32 9-5+2的带语义动作的分析树 ERT-R9RT+Te5233Pt(&

15、#180;2´)Pt(´5´)Pt(´+´)Pt(´-´)Pt(´9´)翻译模式的设计需要保证语义动作性值。分情况考虑：还没有计算的属1. 只需要综合属性的情况：n 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：T®T1*F 所需动作: T.val:=T1.val * F.valT®T1*F T.val:=T1.val * F.val 34翻译模式的设计2.既有综合属性又有继承属性：n 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来

16、。n 一个动作不能性。这个动作右边符号的综合属n 产生式左边非终结符号的综合属性只有在它所的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。35不正确的翻译模式36可以改成如下的形式：S ® A1.in:=1 A1 A2.in:=2 A2A ®a print(A.in) 下面的翻译模式不满足要求：S ®A1A2 A1.in:=1;A2.in:=2A ®a print(A.in) 如何构造语义动作集合？造合适的语义动作集合要深入理解在给定分析技术（自顶向下或自底向上）中推导的过程。要想书写清晰而简洁的语义动作，通常需要对文法进

17、行重新构造，以帮助在合适的地方来计算语义值。在最初获得了适合自顶向下或自底向上分析的文法之后，往往在编译器构造的这个阶段还是会对文法进行修改以提供对语义动作的支持。37.自顶向下的翻译n 首先要从翻译模式中消除左递归n 对于一个翻译模式，若采用自顶向下分析， 必须消除左递归和提取左公因子，在改写基础文法时考虑属性值的计算38左递归文法翻译模式的转换例把带左递归的文法的翻译模式转换成不带左递归的文法的翻译模式。39E ® E1+T E.val := E1.val + T.val E ® E1-T E.val := E1.val - T.val E ® T E.val

18、 := T.val T ® (E) T.val := E.val T ® num T.val := num.val带左递归的文法的翻译模式 经过转换的不带有左递归文法的翻译模式40ET R.i := T.val R E.val := R.s R+T R1.i := R.i +T.val R1= R1.s R-T1.i := R.i - T.val R1 R.s := R1.s R R.s := R.i T (E) T.val := E.val Tnum T.val := num.val E ×val=6R ×i=9 ; R ×s= 6T

19、5;val=9R ×i=4;R ×s= 6T ×val=59T ×val=2R × i=6;+5R ×s= 6 表达式9-5+2的计算 2e41左递归翻译模式的一般化及消除左递归的翻译模式左递归翻译模式AXRRY R.i := f (X.x) A.a := R.s AA1Y A.a := g (A1.a, Y.y) R1.i :=R.i, Y.yAX A.a := f (X.x) R1 R.s := R1.s R R.s := R.i n 假设每一个文法符号都有一个综合属性， 用相应的小写字母表示，g 和 f 是任意函数n 经过转换的

20、翻译模式中使用了R的继承属性 i和综合属性 s。42Y2Y1X43含左递归的文法A.a = f X.xA.a = g ( f (X.x), Y1.y)A.a = g ( g ( f (X.x),Y1 .y),Y2 .y)输入：XY1Y2XY1 R2.s := R3.s Y2 不含左递归的文法44R3.s := R3.iR3.i = g ( g ( f(X ×x),Y1×y),Y2 ×y)R2.i = g ( f(X.x),Y1.y)R1.s := R2.sR1.i = f (X.x)A.a := R1.sA例：45建立表达式语法树的翻译模式：E®E1+T

21、E.nptr := mknode(´+´, E1.nptr, T.nptr) E®E1-TE.nptr := mknode(´-´, E1.nptr, T.nptr)E®TE.nptr :=T.nptr从翻译模式中消除左递归，变成下面的翻译模式。消除左递归之后的翻译模式：46E TR.i := T.nptrRE.nptr := R.s R +TR1.= mknode ' ',. , T.nptr) R1 R.s := R1 .sR -TR1 .i := mknode ('-', R.i, T.nptr)

22、 R1 R .s := R1 .sR R .s := R .iT (E)T.nptr := E.nptrT idT.nptr := mkleaf id, T num T.nptr := mkleaf (num, num.val)使用继承属性构造语法树EnptrTidRTiRnptr-nptr+TiRsnumididto entry for cidto entry for a47num4-+a- 4+c翻译器的设计算法:语导翻译器的建立输入：一个基础文法是 LL(1) 文法的翻译模式。输出：一个语导翻译器的代码。方法：在分析器中加入语义动作代码。（1）"AÎVN

23、, 建立一个可递归调用的函数A。为A的每一个继承属性都设置一个形式参数，函数的返回值是A的综合属性值。为A产生式涉及的每个属性值设一个局部变量。（2）函数A的代码要根据当前的输入符号来决定使用哪一个产生式。48（3） 与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、非终结符号还是语义动作， 分别是：（a）对于带有综合属性x的单词符号X，x存放在相应的局部变量中。编写一个match(X)。（b）对于BÎVN，编写一个赋值语句c := B (b1, b2, ，bk)其中， b1, b2, ，bk是B的继承属性，c是存放B的综合属性值的局部变量。（c）对于每个动作，把动作的代码

24、抄进翻译器中，用存放属性值的变量来代替对属性值的每一次。（d）编写返回A综合属性值的语句。9自顶向下的翻译器代码示例例：构造简单表达式语法树的翻译模式RaddopTR1.i := mknode (addop.lexeme,R.irR1RR.s := R1.sR.s := R.i50翻译程序:相应的syntax-tree-node* Rsntax-tree-node* Ri )syntax-tree-node*Tnptr, *R1i, *R1s, *Rs;char addoplexeme;if(lookahead = addop)/*产生式Raddop T R*/addoplexeme = le

25、xval; match (addop);Tnptr = T();/* T 是一个函数 */R1i = mknode addo R1s = R (R1i);Rs = R1s ;lexemeRirelse Rs = Ri; /*产生式R®e*/ return (Rs);51RaddopT R1.i := mknode (addop.lexeme, R.i, T.nptr) R1 R.s := R1.sR R.s := R.i例：表达式文法的翻译器(生成AST)52含左递归的翻译模式：EE1+T E.nptr := mknode (+, E1.nptr, T.nptr)ETE.nptr :

26、= T.nptr TT1*F T.nptr := mknode (*, T1.nptr, F.nptr)TF T.nptr := F.nptr F(E) F.nptr := E.nptr Fid F.nptr := mkleaf (ID, ) Fnum F.nptr := mkleaf (NUM, num.val)转换：不含左递归的翻译模式53ET R.i := T. nptr R E.nptr := R.sR +T R1.i := mknode (+, R.i, T.nptr) R1 R.s := R1.s R R.s := R.i T F P.i := F. nptr P T

27、. nptr :=P.sP *F1.i := mknode * P.i, F.nptr) P1 P.s := P1.s P P.s := P.i F(E) F. nptr := E.nptr Fid F.nptr := mkleaf (ID, ) Fnum F.nptr := mkleaf (NUM, num.val) 54typedef node structchar d;struct node *left,*right; BType;typedef BType* Pointer;Pointer FE( )Pointer R_i, T_nptr, E_nptr, R_s; T_

28、nptr = FT( );R_i = T_nptr;R_s = FR(R_i); E_nptr = R_s;return E_nptr;翻译程序ETR.i := T. n trR E.nptr := R.sRTR1 R1.i := mknode (, R.i, T.nptr) = R1.s R R.s := R.i 55Pointer FR(Pointer R_i)Pointer R1_i,T_nptr,R_s,R1_s; if(lookahead = )match();T_nptr = FT( );R1_i = mknode(R_i, T_nptr);R1_s = FR(R1_i);R_s

29、= R1_s; return R_s;elseR_s = R_i; return R_s;56F(E) F. nptr := E.nptr Fid F.nptr := mkleaf (ID, ) Pointer FF( )Fnum F.nptr := mkleaf (NUM, num.val)Pointer F_nptr,E_nptr; int num_val,id_name; if(lookahead=()match(); E_nptr = FE( ); match(); F_nptr = E_nptr;return F_nptr;else if(lookahead=id)id

30、_name = lex_val; match(id); F_nptr = mkleaf (ID,id_name); return F_n trelse if(lookahead=num)num_val = lex_val; match(num); F_nptr = mkleaf (NUM,num_val); return F_nptr;else error(“(, id or num expected !”);.自底向上翻译了便于翻译程序的设计底向上翻译通常要求动作都放在产生式之后，以便在用该产生式归约时执行这些动作。对于翻译模式中嵌入在产生式中间的动作，应当通过等价变换把它们移到产生式之后。

31、符和产生式这样简单的方法来实现。57例1：算术表达式58算术表达式后缀式翻译模式的等价变换LEnETRRTMR1|M print(+) TFPP*FNP1|Nprint(*) F(E)Fnum print( num.val) LEnETRRT print(+) R1 | TFPP*F print(*) P1 | F(E)Fnum print( num.val) 例 2： SFOR i :=E1 TO E2 DO S1 FOR语句的中间代码形式：59E1.code （表达式E1的中间代码）i. place := E1.place;E2.code （表达式E2的中间代码）loop:if i.pla

32、ce > E2.place goto out;S1.code （语句S1的中间代码）i. place := Succ(i.place); （计算i的后继）goto loop;例2：语句的翻译模式SFOR i :=E1 TO E2 DO S1SFOR i :=E1 Gen(i.place, := , E1.place) TOE2 loop :=nextstmt;Gen(if, i.place, >, E2.place, goto) DO S1 backpatch(S1.nextlist, nextstmt);Gen (i.place, :=, Succ(i.place); S.nextlist:=loop;Gen (goto, loop)60 nextstmt的值是将要产生的中间代码语句的地址； 函数Gen的功能是产生相应的中间代码语句，如调用Gen(i.place,:=, E1.place)能够产生语句i.place:= E