编译原理与技术

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

2、er 属性计算规则（语义规则）与产生式相关联的反映文法符号属性之间关系的“规则”2022-3-9编译原理与技术讲义4属性文法语法制导定义（文法属性语义规则）语义规则仅表明属性间“抽象”关系，不涉及具体翻译实现细节，如计算次序等。翻译方案（文法属性语义动作）语义规则即语义动作，可体现若干实现的细节。2022-3-9编译原理与技术讲义5e.g.1算术表达式的计算器 产生式 语法制导定义EE1 + E2 E.val := E1.val + E2.valEE1 * E2 E.val := E1.val * E2.valE( E1 ) E.val := E1.valEnumber E.val := nu

3、mber.lex_val2022-3-9编译原理与技术讲义6e.g.1算术表达式的计算器 产生式 翻译方案EE1 + E2 E.val := E1 .val + E2.val EE1 * E2 E.val := E1.val * E2.val E( E1 ) E.val := E1.val Enumber E.val := number.lex_val 2022-3-9编译原理与技术讲义7属性文法属性的分类若产生式AX1X2Xn，与之相关的属性计算规则b := f ( c1, c2, )如果属性b是产生式左部符号左部符号A的属性的属性则称其为A的的综合属性；综合属性；如果属性b是产生式右部符号

4、右部符号Xi的属性的属性则称其为Xi的继承属性；的继承属性；c1, c2, 一般是产生式右部其它符号的(综合)属性或A的继承属性； 固有属性：终结符仅有的属性。如number.lex_val。通常由词法程序提供。2022-3-9编译原理与技术讲义8A.bX1.c1X2.c2X综合属性A.b的计算A的继承属性AX1.c1X2.c2继承属性Xk.b的计算A的继承属性Xk.bX属性依赖图2022-3-9编译原理与技术讲义9e.g. 2 属性依赖图:345E. val = 23E. val = 3+E. val = 20number. lex_val = 3E. val = 4E. val = 5nu

5、mber. lex_val = 4number. lex_val = 52022-3-9编译原理与技术讲义10语义规则的计算方法分析树方法 为输入串建立分析树 由语义规则建立属性依赖图（没有属性循环依赖的） 对依赖图进行拓扑排序，得到属性计算次序 依次计算属性，得到“翻译”结果基于规则的方法 构造编译器时，事先对产生式的语义规则进行分析，得到属性计算次序忽略规则的方法 属性计算次序仅由分析方法限定。如S-属性定义可以在自下而上分析时，在归约前计算。如YACC中的语义动作。2022-3-9编译原理与技术讲义11e.g. 3 属性计算次序: 345E. val = 23E. val = 3+E.

6、val = 20number. lex_val = 3E. val = 4E. val = 5number. lex_val = 4number. lex_val = 5123456782022-3-9编译原理与技术讲义12S-属性定义语义规则仅包含综合属性计算（可以有固有属性出现）。适合自底向上计算e.g. 语法树语法树与分析树 语法树可看作分析树的浓缩。也称抽象语法树。而分析树可看成具体语法树。2022-3-9编译原理与技术讲义13 S if B-expr then S1 else S2语法树 分析树语法树 vs. 分析树if-then-elseB-exprS1S2Sif B-expr t

7、hen S1else S22022-3-9编译原理与技术讲义14 a := b* -c + b * -c 语法树 分析树语法树 vs. 分析树assigna+*bc*bcassignEEE+E*EbEEa赋值语句cE*EbEc算符2022-3-9编译原理与技术讲义15DAG（去除了公共子表达式的无环有向图）a := b* -c + b * -c语法树 vs. DAGassigna+*bc*bcassigna+*bc语法树DAG2022-3-9编译原理与技术讲义16e.g.4 构造表达式的语法树（DAG）产生式 语义规则EE1 + E2 E.nptr := mknode(+,E1.nptr, E

8、2.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.nptr, )Enumber E.nptr := mkleaf(NUM,number.lex_val)Eid E.nptr := mkleaf(ID,id.entry)2022-3-9编译原理与技术讲义17e.

9、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)建立表达式语法树的叶结点。建DAG也需检查是否已有相应结点。2022-3-9编译原理与技术讲义18e.g.4 构造表达式a+b*-4的属性结构树 E.nptrE.nptrE.n

10、ptr+E.nptrE.nptr*abE.nptr4ID aID bNUM4 -* + 2022-3-9编译原理与技术讲义19e.g.4 构造表达式a+b*-4的语法树（DAG） + ID a* ID b -NUM42022-3-9编译原理与技术讲义20L-属性定义如果产生式AX1X2Xn 的语义规则只计算1）A的综合属性，或者2）Xi的继承属性，且该属性仅依赖于产生式右部Xi的左边符号Xj（ji）的（综合）属性或A的继承属性；S-属性定义均为L-属性定义可按深度优先次序计算 一种自然的属性计算次序 在分析期间完成翻译。属性计算与结点建立有联系；适合于自顶向下和自底向上分析方法。2022-3-

11、9编译原理与技术讲义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;end2022-3-9编译原理与技术讲义22e.g.5 非L-属性定义的语法制导定义产生式语义规则ALML.i := l(A.i)M.i := m(L.s)A.s := f(M.s)AQRR.i := r(A

12、.i)Q.i := q(R.s)A.s := f(Q.s)2022-3-9编译原理与技术讲义23翻译方案中的动作语义动作可放在产生式右端任何位置；这也就显式地给出了动作的执行时刻。（可认为是在深度优先遍历中的执行时刻）e.g. 6将含有+和-运算的中缀表达式翻译为后缀形式：ET RR addop T print( addop.lex_val) R | T number print( number.lex_val) 2022-3-9编译原理与技术讲义24e.g. 6 中缀翻译为后缀 ：9-4+5ETR9print(9)-Tprint(-)R4print(4)+Tprint(+)5print(5)

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

14、 A2 A a print( A.in ) 2022-3-9编译原理与技术讲义27e.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)2022-3-9编译原理与技术讲义28e.g.8 类型说明的语法制导定义（0）属性传递DTLL，kL，jiint2022-3-9编译原理与技术讲义29e.g.8类型说明的语法制导定义（

15、1）改写上述类型声明文法，使得其中的T成为L的子结点（即产生式右部），可以避免继承属性的使用。修改后文法如下：DL Tint Treal LL1 , id LT id2022-3-9编译原理与技术讲义30e.g.8类型说明的语法制导定义（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.type2022-3-9编译原理与技术讲义31e.g.8类型说明

16、的语法制导定义（2）属性传递DTLL，kL，jiint2022-3-9编译原理与技术讲义32e.g.8 类型说明的语法制导定义（3）Pascal语言类型声明文法如下： DL : T Tint Treal LL1 , id Lid该声明文法的“问题”在于，L中声明的变量的类型T处于产生式中L的右边！若用继承属性L.in来传递类型信息T.type形成非L属性定义。从而无法在完成L分析同时将有关类型信息填入符号表！可以可以考虑将考虑将T作为作为L的子结点（通过修的子结点（通过修改文法）来改变这种情况改文法）来改变这种情况2022-3-9编译原理与技术讲义33e.g.8 类型说明的语法制导定义（4）

17、产生式语义规则 D id L addtype(id.entry,L.in)Tint T.type := integer Treal T.type := real L, id L1 L.in := L1.in addtype(id.entry, L1.in)L : T L.in := T.type2022-3-9编译原理与技术讲义34e.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)时

18、，该翻译方案输出什么？2022-3-9编译原理与技术讲义35S-属性定义的自底向上计算拓广分析栈，即添加属性栈，包含文法符号的综合属性。在归约实施前，右部各符号的综合属性（若有的话）已放在与符号位置对应的属性栈上，因此，可以先计算获得左部非终结符的综合属性。然后再归约，这时从分析栈中弹出句柄，（注意，此时改变栈顶注意，此时改变栈顶top即可即可）最后，将左部符号连同其属性放入由top指示的分析栈及属性栈的位置中。这种属性栈只能存放综合属性。回想YACC中如何做的？2022-3-9编译原理与技术讲义36如果AXYZ，相关语义规则如下：A.a := f(X.x,Y.y,Z.z)显然，X.x在Val

19、top-2Y.y在Valtop-1Z.z在ValtopA.a在Valntop ，ntop = top |句柄长度|+1Val ntop := f( valtop-2, Valtop-1, Valtop )属性栈与分析栈ZZ.zYY.yXX.x分析栈属性栈Valtopbottom2022-3-9编译原理与技术讲义37如果AB ，相关语义规则如下：A.a := B.b 显然，B.b在ValtopA.a在Valntop ，ntop = top 1+1 = top ,即归约前后栈顶top不变，也即Val ntop 和 Valtop对应属性栈同一个单元，所以，可以省略原语义规则对应的属性栈操作：所以，可

20、以省略原语义规则对应的属性栈操作：Valntop := Valtop属性栈与分析栈BB.b分析栈属性栈Valtopbottom2022-3-9编译原理与技术讲义38e.g.10 计算表达式的（栈）代码产生式语义规则代码段LE nPrint( E.val )Print( Valtop-1 )EE1+TE.val := E1.val + T.valValntop:=Valtop-2+ValtopETE.val := T.valTT1*FT.val := T1.val * F.valValntop:=Valtop-2*ValtopTFT.val := F.valF(E)F.val := E.valV

21、alntop:=Valtop-1FdigitF.val := digit.lex_val2022-3-9编译原理与技术讲义39如何在自底向上分析中计算继承属性？ 属性栈上仅能存放综合属性 能否将继承属性的引用转换成综合属性？分析栈中符号的继承属性 属性copy规则如果，AXY，有语义规则Y.i := X.s，翻译方案可写为： A X Y.i := X.s Y自底向上计算继承属性2022-3-9编译原理与技术讲义40自底向上计算继承属性 由属性copy规则可知，Y的继承属性Y.i和X.s在属性栈上同一位置。这样对属性Y.i的引用可以转化为对X.s的引用。若计算若计算Y的综合属性的综合属性Y.s时

22、需要引用时需要引用Y.i，则此时，则此时Y.i（即（即X.s）就紧邻在句柄下面；）就紧邻在句柄下面；如果如果Y的句柄形成前，的句柄形成前，它的某个右部符号它的某个右部符号需使用需使用Y.i，这时，这时，也可以直接使用也可以直接使用Y.i。（How to use?）bottomXX.s（Y.i）分析栈属性栈Valtop句柄（归约为Y）top句柄长句柄长2022-3-9编译原理与技术讲义41e.g.11 C声明的翻译方案 DT L.in := T.type L Tint T.type := integer Treal T.type := real L L1.in := L.in L1 , id a

23、ddtype(id.entry, L.in) Lid addtype(id.entry, L.in) 对于输入串：int p,q,r 分析过程如下：2022-3-9编译原理与技术讲义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就在句柄的下面！2022-3-9编译原理与技术讲义43e.g.11 C声明的“代码段”产生式 代码段（只含综合属性）DT L Tin

24、tvalntop:=integer Trealvalntop:=real L L1 , id addtype(valtop,valtop-3)Lid addtype(valtop,valtop-1)L的继承属性L.in2022-3-9编译原理与技术讲义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 。模拟继承属性

25、的计算bottomccABaAb分析栈1分析栈2top2022-3-9编译原理与技术讲义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.se.g.12 引入标记非终结符bottomAMaBAb分析栈1分析栈2topcc2022-3-9编译原理与技术讲义46产生式代码段S a A CS b A B M CC c valntop:= g(valtop-1)M valnt

26、op := valtop-1可否将M放在S a A C产生式中？M.i2022-3-9编译原理与技术讲义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和N2022-3-9编译原理与技术讲义48e.g.13 引入标记非终结符N 产生式 语义规则 S a A N C C.i := N.s N.i := A.s NN

27、.s := f(N.i)(其他产生式和语义规则不变）(代码段略）2022-3-9编译原理与技术讲义49产生式语义规则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.pse.g.14 文字排版的语法制导定义2022-3-9编译原理与技术讲义50S ： S.ht，综合属性；待排公式的整体高度B ：

28、B.ps，继承属性； 公式（文本）中字体“点”的大小 B.ht，综合属性；公式排版高度text ：text.h，文本高度max ：求两个排版公式的最大高度shrink(B) ：将点大小缩小为B的30disp(B1.ht，B2.ht)：向下调整B2的位置文字排版中的符号属性E1Val2022-3-9编译原理与技术讲义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(

29、B.ps) B2 B.ht := disp(B1.ht,B2.ht) B text B.ht := text.h B.ps 2022-3-9编译原理与技术讲义52文字排版中引入标记符号为了自底向上计算：B text B.ht := text.h B.ps 必须确定继承属性B.ps的（“属性栈”）位置。为此引入标记非终结符L、M和N及其属性，包括相应的空产生式和有关属性规则。这样B.ps即可在紧靠“句柄”text下方的位置上找到。(L的综合属性置为B.ps的初值)SL BBB1M B2BB1 sub N B2texttext.hLL.s=10分析栈属性栈topbottom2022-3-9编译原理

30、与技术讲义53S 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(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）2022-3-9编译原理与技术讲义54 产生式代码

31、段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 := 10M valntop := valtop-1N valntop := shrink( valtop-2 )2022-3-9编译原理与技术讲义55（L-属性定义）自顶向下翻译删除翻译方案中的左递归A A1Y A.a := g(A1.a, Y.y) A X A.a := f( X.x) 消除

32、左递归：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 /返回结果2022-3-9编译原理与技术讲义56输入串XY1Y2的翻译XA.a := f( X.x)A.a := g(f( X.x), y1.y)y1A.a := g(g(f( X.x), y1.y), y2.y)y2A.aXR.i := f(X.x)Y1R.i := g(f(X.x),Y1.y)Y2R.i := g(g(f(X.x),Y1.y), Y2.y)R.sR.sR.s2022-3-9编译原理与技术讲义57e.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 := mkl