编译原理与技术.ppt

《编译原理与技术.ppt》由会员分享，可在线阅读，更多相关《编译原理与技术.ppt（62页珍藏版）》请在三一办公上搜索。

1、2023/9/28,1,编译原理与技术,语法制导翻译,2023/9/28,2,语法制导翻译,属性文法S-属性定义L-属性定义语法制导定义与翻译方案自底向上翻译S-属性定义自底向上计算自底向上计算继承属性自顶向下翻译,2023/9/28,3,属性文法,属性文法（Attributed Grammar）上下文无关文法+属性+属性计算规则 属性用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等。e.g.二义性表达式文法G，非终结符E有属性E.val（表达式的值）EE+E|E*E|(E)|number 属性计算规则（语义规则）与产生式相关联的反映文法符号属性之间关系的“规则”,2023/

2、9/28,4,属性文法语法制导定义（文法属性语义规则）语义规则仅表明属性间“抽象”关系，不涉及具体翻译实现细节，如计算次序等。翻译方案（文法属性语义动作）语义规则即语义动作，可体现若干实现的细节。,2023/9/28,5,算术表达式的计算器,产生式 语法制导定义EE1+E2 E.val:=E1.val+E2.valEE1*E2 E.val:=E1.val*E2.valE(E1)E.val:=E1.valEnumber E.val:=number.lex_val,2023/9/28,6,算术表达式的计算器,产生式 翻译方案EE1+E2 E.val:=E1.val+E2.val EE1*E2 E.

3、val:=E1.val*E2.val E(E1)E.val:=E1.val Enumber E.val:=number.lex_val,2023/9/28,7,属性文法,属性的分类若产生式AX1X2Xn，与之相关的属性计算规则b:=f(c1,c2,)如果属性b是产生式左部符号A的属性则称其为A的综合属性；如果属性b是产生式右部符号Xi的属性则称其为Xi的继承属性；c1,c2,一般是产生式右部其它符号的(综合)属性或A的继承属性；固有属性：终结符仅有的属性。如number.lex_val。通常由词法程序提供。,2023/9/28,8,A.b,X1.c1,X2.c2,X,综合属性A.b的计算,A的

4、继承属性,A,X1.c1,X2.c2,继承属性Xk.b的计算,A的继承属性,Xk.b,X,属性依赖图,2023/9/28,9,e.g.2 属性依赖图:345,E.val=23,E.val=3,+,E.val=20,number.lex_val=3,E.val=4,E.val=5,number.lex_val=4,number.lex_val=5,2023/9/28,10,语义规则的计算方法,分析树方法 为输入串建立分析树 由语义规则建立属性依赖图（没有属性循环依赖的）对依赖图进行拓扑排序，得到属性计算次序 依次计算属性，得到“翻译”结果基于规则的方法 构造编译器时，事先对产生式的语义规则进行分

5、析，得到属性计算次序忽略规则的方法 属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时，在归约前计算。如YACC中的语义动作。,2023/9/28,11,e.g.3 属性计算次序:345,E.val=23,E.val=3,+,E.val=20,number.lex_val=3,E.val=4,E.val=5,number.lex_val=4,number.lex_val=5,1,2,3,4,5,6,7,8,2023/9/28,12,S-属性定义,语义规则仅包含综合属性计算（可以有固有属性出现）。适合自底向上计算e.g.语法树语法树与分析树 语法树可看作分析树的浓缩。也称抽象语法树

6、。而分析树可看成具体语法树。,2023/9/28,13,S if B-expr then S1 else S2语法树 分析树,语法树 vs.分析树,if-then-else,B-expr,S1,S2,S,if,B-expr,then,S1,else,S2,2023/9/28,14,a:=b*-c+b*-c 语法树 分析树,语法树 vs.分析树,assign,a,+,*,b,c,*,b,c,assign,E,E,E,+,E,*,E,b,E,E,a,赋值语句,c,E,*,E,b,E,c,算符,2023/9/28,15,DAG（去除了公共子表达式的无环有向图）a:=b*-c+b*-c,语法树 vs.

7、DAG,assign,a,+,*,b,c,*,b,c,assign,a,+,*,b,c,语法树,DAG,2023/9/28,16,e.g.4 构造表达式的语法树（DAG）,产生式 语义规则EE1+E2 E.nptr:=mknode(+,E1.nptr,E2.nptr)EE1-E2 E.nptr:=mknode(-,E1.nptr,E2.nptr)EE1*E2 E.nptr:=mknode(*,E1.nptr,E2.nptr)EE1/E2 E.nptr:=mknode(/,E1.nptr,E2.nptr)E(E1)E.nptr:=E1.nptrE-E1 E.nptr:=mknode(,E1.np

8、tr,)Enumber E.nptr:=mkleaf(NUM,number.lex_val)Eid E.nptr:=mkleaf(ID,id.entry),2023/9/28,17,e.g.4 构造表达式的语法树（DAG）,E.nptr E的语法树（根结点指针）mknode(op,left,right)建立一个表达式语法树结点，它的运算符为op，左、右运算对象是left和right所指的语法树。如果建成DAG，则需要检查是否已存在相应内部结点op，其左右运算对象分别是left和right。若没有则新建一个。mkleaf(NUM,number.lex_val)mkleaf(ID,id.entry

9、)建立表达式语法树的叶结点。建DAG也需检查是否已有相应结点。,2023/9/28,18,e.g.4 构造表达式a+b*-4的属性结构树,E.nptr,E.nptr,E.nptr,+,E.nptr,E.nptr,*,a,b,E.nptr,4,2023/9/28,19,e.g.4 构造表达式a+b*-4的语法树（DAG）,2023/9/28,20,L-属性定义,如果产生式AX1X2Xn 的语义规则只计算1）A的综合属性，或者2）Xi的继承属性，且该属性仅依赖于产生式右部Xi的左边符号Xj（ji）的（综合）属性或A的继承属性；S-属性定义均为L-属性定义可按深度优先次序计算 一种自然的属性计算次序

10、 在分析期间完成翻译。属性计算与结点建立有联系；适合于自顶向下和自底向上分析方法。,2023/9/28,21,深度优先次序,procedure dfvisit(n:node)beginfor each child m of n,from left to right do begin evaluate inherited attributes of m;dfvisit(m);end;evaluate synthesized attributes of n;end,2023/9/28,22,e.g.5 非L-属性定义的语法制导定义,产生式语义规则ALML.i:=l(A.i)M.i:=m(L.s)A

11、.s:=f(M.s)AQRR.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s),2023/9/28,23,翻译方案中的动作,语义动作可放在产生式右端任何位置；这也就显式地给出了动作的执行时刻。（可认为是在深度优先遍历中的执行时刻）e.g.6将含有+和-运算的中缀表达式翻译为后缀形式：ET RR addop T print(addop.lex_val)R|T number print(number.lex_val),2023/9/28,24,e.g.6 中缀翻译为后缀：9-4+5,E,T,R,9,print(9),-,T,print(-),R,4,print(4),+,T,prin

12、t(+),5,print(5),R,1,2,3,4,5,2023/9/28,25,翻译方案中的动作,设计翻译方案时，必须保证动作所引用的属性值是可用的。只有综合综合属性时（S-属性定义），动作放在产生式末尾；若有继承属性时，动作的放置须保证：（产生式右部）符号的继承属性必须在此符号前计算；动作不要引用其右边符号的综合属性；左部非终结符的综合属性一般放在产生式末 尾（确保它引用的属性均已计算完且可用）,2023/9/28,26,e.g.7 翻译方案的书写,S A1 A2 A1.in:=1;A2.in:=2 A a print(A.in)改写为：S A1.in:=1 A1 A2.in:=2 A2

13、A a print(A.in),2023/9/28,27,e.g.8 类型说明的语法制导定义（0）,产生式语义规则 DT L L.in:=T.type Tint T.type:=integer Treal T.type:=real LL1,id L1.in:=L.in addtype(id.entry,L.in)Lid addtype(id.entry,L.in),2023/9/28,28,e.g.8 类型说明的语法制导定义（0）属性传递,D,T,L,L,，,k,L,，,j,i,int,2023/9/28,29,类型说明的语法制导定义（1）,改写上述类型声明文法，使得其中的T成为L的子结点（即

14、产生式右部），可以避免继承属性的使用。修改后文法如下：DL Tint Treal LL1,id LT id,2023/9/28,30,类型说明的语法制导定义（2）,产生式语义规则 D L Tint T.type:=integer Treal T.type:=real LL1,id L.in:=L1.in addtype(id.entry,L1.in)LT id addtype(id.entry,T.type);L.in:=T.type,2023/9/28,31,类型说明的语法制导定义（2）属性传递,D,T,L,L,，,k,L,，,j,i,int,2023/9/28,32,e.g.8 类型说明的

15、语法制导定义（3）,Pascal语言类型声明文法如下：DL:T Tint Treal LL1,id Lid,该声明文法的“问题”在于，L中声明的变量的类型T处于产生式中L的右边！若用继承属性L.in来传递类型信息T.type形成非L属性定义。从而无法在完成L分析同时将有关类型信息填入符号表！可以考虑将T作为L的子结点（通过修改文法）来改变这种情况,2023/9/28,33,e.g.8 类型说明的语法制导定义（4）,产生式语义规则 D id L addtype(id.entry,L.in)Tint T.type:=integer Treal T.type:=real L,id L1 L.in:=

16、L1.in addtype(id.entry,L1.in)L:T L.in:=T.type,2023/9/28,34,e.g.9 翻译方案的计算次序,EE+T print(“1”)ET print(“2”)TT*F print(“3”)TF print(“4”)F(E)print(“5”)Fid print(“6”)输入串是id*(id+id)时，该翻译方案输出什么？,2023/9/28,35,S-属性定义的自底向上计算,拓广分析栈，即添加属性栈，包含文法符号的综合属性。在归约实施前，右部各符号的综合属性（若有的话）已放在与符号位置对应的属性栈上，因此，可以先计算获得左部非终结符的综合属性。然

17、后再归约，这时从分析栈中弹出句柄，（注意，此时改变栈顶top即可）最后，将左部符号连同其属性放入由top指示的分析栈及属性栈的位置中。这种属性栈只能存放综合属性。回想YACC中如何做的？,2023/9/28,36,如果AXYZ，相关语义规则如下：A.a:=f(X.x,Y.y,Z.z)显然，X.x在Valtop-2Y.y在Valtop-1Z.z在ValtopA.a在Valntop，ntop=top|句柄长度|+1Val ntop:=f(valtop-2,Valtop-1,Valtop),属性栈与分析栈,2023/9/28,37,如果AB，相关语义规则如下：A.a:=B.b 显然，B.b在Valt

18、opA.a在Valntop，ntop=top 1+1=top,即归约前后栈顶top不变，也即Val ntop 和 Valtop对应属性栈同一个单元，所以，可以省略原语义规则对应的属性栈操作：Valntop:=Valtop,属性栈与分析栈,B,B.b,分析栈,属性栈Val,top,bottom,2023/9/28,38,e.g.10 计算表达式的（栈）代码,2023/9/28,39,如何在自底向上分析中计算继承属性？属性栈上仅能存放综合属性 能否将继承属性的引用转换成综合属性？分析栈中符号的继承属性 属性copy规则如果，AXY，有语义规则Y.i:=X.s，翻译方案可写为：A X Y.i:=X.

19、s Y,自底向上计算继承属性,2023/9/28,40,自底向上计算继承属性,由属性copy规则可知，Y的继承属性Y.i和X.s在属性栈上同一位置。这样对属性Y.i的引用可以转化为对X.s的引用。若计算Y的综合属性Y.s时需要引用Y.i，则此时Y.i（即X.s）就紧邻在句柄下面；如果Y的句柄形成前，它的某个右部符号需使用Y.i，这时，也可以直接使用Y.i。（How to use?）,top句柄长,2023/9/28,41,e.g.11 C声明的翻译方案,DT L.in:=T.type L Tint T.type:=integer Treal T.type:=real L L1.in:=L.in

20、 L1,id addtype(id.entry,L.in)Lid addtype(id.entry,L.in)对于输入串：int p,q,r 分析过程如下：,2023/9/28,42,输入串 分析栈 产生式 int p,q,r p,q,r intp,q,r T Tint,q,r Tp,q,r TL Lid q,r TL,r TL,q,r TL LL,id r TL,TL,r TL LL,id D DTL,注意：每次归约成L时，T与L的位置关系T就在句柄的下面！,2023/9/28,43,e.g.11 C声明的“代码段”,产生式 代码段（只含综合属性）DT L Tintvalntop:=inte

21、ger Trealvalntop:=real L L1,id addtype(valtop,valtop-3)Lid addtype(valtop,valtop-1),L的继承属性L.in,2023/9/28,44,问题1：继承属性的位置在构造编译器时不可预知（或不固定），如e.g.12 产生式语义规则S a A C C.i:=A.sS b A B CC.i:=A.sC cC.s:=g(C.i)用C c归约时，C.i的值可能在valtop-1或者在valtop-2的位置上。解决办法是考虑将其统一。引入标记非终结符 M和产生式M。,模拟继承属性的计算,bottom,c,c,A,B,a,A,b,分

22、析栈1,分析栈2,top,2023/9/28,45,产生式语义规则S a A CC.i:=A.sS b A B M CC.i:=M.sM.i:=A.sC cC.s:=g(C.i)M M.s:=M.i 引入M后，C.i 可从句柄c的下面(valtop-1)取得！属性传递：A.s M.i M.s C.i C.s,e.g.12 引入标记非终结符,bottom,A,M,a,B,A,b,分析栈1,分析栈2,top,c,c,2023/9/28,46,产生式代码段S a A CS b A B M CC c valntop:=g(valtop-1)M valntop:=valtop-1可否将M放在S a A

23、C产生式中？,M.i,2023/9/28,47,模拟继承属性的计算,问题2：语义规则不是简单的属性复写拷贝。e.g.13:将例12中的S a A C语义规则换为：产生式语义规则 S a A CC.i:=f(A.s)虽然在例12中引入了M使得“A.s”可在valtop-1处找到，但在S的两个产生式中C.i的取值方式不同，导致C.s的计算嘛这次可以考虑引入标记非终结符N和N,2023/9/28,48,e.g.13 引入标记非终结符N,产生式 语义规则 S a A N C C.i:=N.s N.i:=A.s NN.s:=f(N.i)(其他产生式和语义规则不变）(代码段略）,2023/9/28,49,

24、产生式语义规则SB B.ps:=10S.ht:=B.htBB1B2B1.ps:=B.psB2.ps:=B.ps B.ht:=max(B1.ht,B2.ht)BB1 sub B2 B1.ps:=B.psB2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)B text B.ht:=text.h B.ps,e.g.14 文字排版的语法制导定义,2023/9/28,50,S：S.ht，综合属性；待排公式的整体高度B：B.ps，继承属性；公式（文本）中字体“点”的大小 B.ht，综合属性；公式排版高度text：text.h，文本高度max：求两个排版公式的最大高度shri

25、nk(B)：将点大小缩小为B的30disp(B1.ht，B2.ht)：向下调整B2的位置,文字排版中的符号属性,E,1,Val,2023/9/28,51,文字排版的翻译方案（0）,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,2023/9/28,52,文字排版中引入标记符号,为了自底向上计算：B text

26、B.ht:=text.h B.ps 必须确定继承属性B.ps的（“属性栈”）位置。为此引入标记非终结符L、M和N及其属性，包括相应的空产生式和有关属性规则。这样B.ps即可在紧靠“句柄”text下方的位置上找到。(L的综合属性置为B.ps的初值)SL BBB1M B2BB1 sub N B2,text,text.h,L,L.s=10,分析栈,属性栈,top,bottom,2023/9/28,53,S L B.ps:=L.s L L.s:=10 B S.ht:=B.ht B B1.ps:=B.ps M M.s:=M.i B1 M.i:=B.ps M B2.ps:=M.s B2 B.ht:=max

27、(B1.ht,B2.ht)B B1.ps:=B.ps B1 sub N.i:=B.ps N N.s:=shrink(N.i)N B2.ps:=N.s B2 B.ht:=disp(B1.ht,B2.ht)B text B.ht:=text.h B.ps,文字排版的翻译方案（1）,2023/9/28,54,产生式代码段S L B valntop:=valtop BB1 M B2 valntop:=max(valtop-2,valtop)BB1 sub N B2 valntop:=disp(valtop-3,valtop)B text valntop:=valtopvaltop-1L valntop

28、:=10M valntop:=valtop-1N valntop:=shrink(valtop-2),2023/9/28,55,（L-属性定义）自顶向下翻译,删除翻译方案中的左递归A A1Y A.a:=g(A1.a,Y.y)A X A.a:=f(X.x)消除左递归：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/返回结果,2023/9/28,56,输入串XY1Y2的翻译,X,A.a:=f(X.x),A.a:=g(f(X.x),y1.y),y1,A.a:=g(g(f(X.x),y1.y

29、),y2.y),y2,A.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),R.s,R.s,R.s,2023/9/28,57,e.g.15 删除翻译方案中左递归,EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr)EE1-T E.nptr:=mknode(-,E1.nptr,T.nptr)ET E.nptr:=T.nptr T(E)T.nptr:=E.nptr Tnum T.nptr:=mkleaf(NUM,num.val)Tid T.nptr:=mkleaf(ID,id.entr

30、y),2023/9/28,58,删除左递归后：引入非终结符RE T R.i:=T.nptr R E.nptr:=R.s R+T R1.i:=mknode(+,R.i,T.nptr)/”建树“R1 R.s:=R1.s R-T R1.i:=mknode(-,R.i,T.nptr)R1 R.s:=R1.s R R.s:=R.i/返回最终语法树（其余略）,2023/9/28,59,（递归下降）预测翻译器的设计,为每个非终结符A构造用于分析和属性计算的函数（注意，在递归下降的语法分析中构造的仅是过程），这样的函数构成如下：参数：符号A的继承属性 返回值：符号A的综合属性（记录）局部变量：A的产生式中每个

31、符号的属性均有对应的局部量（A的继承属性除外）函数体形式为：（类似递归分析过程）根据输入符号决定产生式的选择；对每个可能选择的产生式从左自右分析并计算属性（执行语义动作）,2023/9/28,60,对每个可能选择的产生式从左自右分析并计算属性（执行语义动作）：（1）终结符X，将X.x保存在相应的局部量中（如果有的话），调用match(X);（2）非终结符B，产生赋值 c:=B(b1,b2,bn)，c和bi分别是B的综合属性和继承属性对应的局部变量；（3）语义动作，将代码直接拷贝到函数体中，而其中属性出现改为局部量的引用；（4）函数结尾：return A的综合属性。,2023/9/28,61,e

32、.g.16 递归翻译函数,R+T R1.i:=mknode(+,R.i,T.nptr)R1 R.s:=R1.s R-T R1.i:=mknode(-,R.i,T.nptr)R1 R.s:=R1.s R R.s:=R.i,2023/9/28,62,node_ptr R(node_ptr i)node_ptr nptr,i1,s1,s;/符号属性对应的局部量if(lookhead=+)/R+T Rmatch(+);nptr=T();i1=mknode(+,i,nptr);/语义动作s1=R(i1);s=s1;/语义动作else if/R-T Relse s=i;/R 语义动作return s;非终结符R的递归翻译函数,