第五章语法制导翻译(2)

1、1第五章第五章 语法制导翻译语法制导翻译5.4 5.5编译原理25.4 语法制导的翻译模式语法制导的翻译模式(Translation Scheme)q语法制导翻译（SDT）是SDD的实现。q语法制导翻译模式（SDT）是拓广的CFG， 在文法中嵌入语义动作，语义动作写在花括号“”里，可以出现在产生式右部适当位置。q当归约出产生式右部的某个非终结符号后，就执行紧接在该非终结符号右边的语义动作。编译原理3q任何SDT可以通过先建立语法分析树，然后前序遍历执行语义动作。q但是，我们希望SDT能够在语法分析的同时进行，无需构造好分析树。这里讨论两类：基础文法是LR，SDD是S-attributed；基础

2、文法是LL，SDD是L-attributed。编译原理4SDD vs. SDTq语义规则q语义动作产产 生生 式式 语语 义义 规规 则则 E E1 + T E.val := E1 .val + T.val E E1 + T E.val := E1 .val + T.val 编译原理5SDD vs. SDTq语义规则q语义动作产产 生生 式式 语语 义义 规规 则则 E E1 + T E.code := E1 . code | T. code | + E E1 + T print(+); 编译原理65.4.1 后缀后缀SDTq自底向上分析S属性文法。A X Y Z语义动作编译原理7 L E n

3、 print (E.val); E E1 + T E.val := E1 .val + T.val; E T E.val := T.val; T T1 * F T.val := T1.val F.val ; T F T.val := F.val; F (E) F.val := E.val; F digit F.val := digit.lexval; 编译原理85.4.2后缀后缀SDT的语法分析实现的语法分析实现qA X Y ZX Y Z X.x Y.y Z.ztop文法符号综合属性编译原理9 例例5.15 显式操作语法分析栈显式操作语法分析栈 L E n print (stacktop-1.

4、val); top = top -1; E E1 + T stacktop-2.val = stacktop-2 .val + stacktop.val; top = top -2; E T T T1 * F stacktop-2.val = stacktop-2 .val stacktop.val; top = top -2; T F F (E) stacktop-2.val = stacktop-1 .val ； top = top -2; F digit 编译原理103*5 n的分析计算过程的分析计算过程digit3top编译原理113*5 n的分析计算过程的分析计算过程F3top编译原

5、理123*5 n的分析计算过程的分析计算过程T3* digit5top编译原理133*5 n的分析计算过程的分析计算过程T3* F5top编译原理143*5 n的分析计算过程的分析计算过程T15 top编译原理153*5 n的分析计算过程的分析计算过程E15 top编译原理163*5 n的分析计算过程的分析计算过程E15n top编译原理173*5 n的分析计算过程的分析计算过程L15 top编译原理185.4.3 产生式内部带语义动作的产生式内部带语义动作的SDTqB X a Y LR：归约出X之后立即执行动作aLL：试图展开Y之前执行动作a编译原理19例，中缀到后缀转换的例，中缀到后缀转换

6、的SDD Production Semantic Ruleexpr expr1 + term expr.t := expr1.t | term.t | +expr expr1 term expr.t := expr1.t | term.t | -expr term expr.t := term.tterm 0 term.t := 0term 1 term.t := 1. .term 9 term.t := 9编译原理20 例，中缀到后缀转换的例，中缀到后缀转换的SDTL E nE E1+ T print(+) E TT T1* F print(*) T FF (E)F digit print(

7、digit.lexval)编译原理21 例例5.16 翻译为翻译为前缀前缀表达式表达式L E nE print(+) E1+ TE TT print(*) T1* FT FF (E)F digit print(digit.lexval)Not all SDTs can be implemented during parsing:Not a LR Grammar?编译原理22嵌入动作的分析树：嵌入动作的分析树：3*5+4编译原理235.4.4 从从SDT中删除左递归中删除左递归q例5.17 带左递归的文法的翻译模式。E E1 + T print(+); E T转换为：E TRR + print(

8、+); RR 编译原理24 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 例：一个一般化的例子例：一个一般化的例子编译原理25 A A1Y A.a := g (A1.a, Y.y) A X A.a := f (X.x) Y1XY2AAA.a = g ( g ( f (X.x), Y1.y), Y2.y).a = g ( f (X.x), Y1.y).a = f (X.

9、x).y.y.x编译原理26A 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 AXRY1RY2R.i=g ( g ( f (X.x), Y1.y), Y2.y).i = g ( f (X.x), Y1.y) .y.i = f (X.x).y.xa sss编译原理275.4.5 L属性定义的属性定义的SDTq确定语义动作的执行时机q如何将语义动作嵌入产生式右部的适当位置？编译原理281. 只有综合属性综合属性的情况：将计算综合属性的语义规则作为产生式右边末尾的动作。例如：原则：

10、原则： 产生式 语义规则 T T1 * F T.val := T1.val * F.val 产生式 语义动作 T T1 * F T.val := T1.val * F.val编译原理292. 同时存在综合属性和继承属性，建立翻译模式的必要条件：产生式右部符号的继承属性必须在这个符号以前的动作中计算出来；一个动作不能引用该动作右边符号的综合属性；产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可以放在产生式右端的末尾。编译原理30例：例：翻译模式 S A1A2 A1.in := 1; A2.in := 2 A a print(A.in)不符合条

11、件(1)。 若改写成 S A1.in := 1; A2.in := 2 A1A2 A a print(A.in)则就符合条件(1)。编译原理31E1.val上图可以用命令：E sub 1.val 描述。例5.18数学排版语言的翻译模式片断。数学排版语言的翻译模式片断。ai上图可以用命令：a sub i sub j 描述。j编译原理32例5.18数学排版语言的翻译模式。数学排版语言的翻译模式。q综合属性：ht ：描述heightdp ：描述depthq 继承属性ps：point size，设定字体大小。 Assume ps = 10。 下标的大小按比例缩小，位置下降。编译原理33图图5-25 盒

12、子的大小和高度的语法制导定义盒子的大小和高度的语法制导定义编译原理34S B BB B sub B B sub 1 E sub 1E1B1.htmax(B1.ht, B2.ht 0.25 * B.ps )E sub 1的推导过程的推导过程(忽略二义性问题)max(B1.dp, B2.dp + 0.25 * B.ps) 非终结符号 B (表示Box)代表一个公式。 产生式 B B1B2 代表两个方框的并置。 B B1 sub B2 代表一个布局，其中 B2 是比 B1 小一号的方框， B2 是 B1 的下标。编译原理35翻译模式翻译模式编译原理36如何消除二义性如何消除二义性?S BB B1B2

13、B B1 sub B2B (B) | text结合性：右结合优先级：sub高于并置S BB T B1 | TT F sub T1 | FF (B) | text编译原理37例例5.19 qS while (C) S1C.codeS1.codegoto L1.C.true:C.false:to C.trueto C.falsewhile语句L1:L2:编译原理38 产生式 语义规则S while (C) S1 L1 = newlabel();L2 = newlabel();S1.next = L1;C.false = S.next;C.true = L2; S.code = label | L1

14、 | C.code | label | L2 | S1.code S while ( L1 = newlabel(); L2 = newlabel(); C.false = S.next;C.true = L2;C) S1.next = L1;S1 S.code = label | L1 | C.code | label | L2 | S1.code 编译原理395.5 实现实现L属性定义的翻译属性定义的翻译q建立注释语法分析树q构造语法分析树，加入动作，按照前序顺序执行q使用递归下降的语法分析器，在预测分析的过程中实现L属性定义。编译原理40例例5.20编译原理41例例5.22编译原理42编

15、译原理435.5.1 从翻译模式中消除左递归从翻译模式中消除左递归例5.14 带左递归的文法的翻译模式。S-属性定义E E1 + T E.val := E1.val + T.valE E1 - T E.val := E1.val - T.valE T E.val := T.valT (E) T.val := E.valT num T.val := num.val编译原理44经过转换的带有右递归文法的翻译模式经过转换的带有右递归文法的翻译模式E T R.i := T.val R E.val := R.sR + T R1.i := R.i + T.val R1 R.s := R1.s R R.s

16、:= R.iT ( E ) T.val := E.valT num T.val := num.val编译原理45表达式表达式9-5+2的计算的计算E valT.val=9num.val=9i = 9 R s-T.val=5num.val=5i = 4 R s+ +T.val=2i = 6 R snum.val=2编译原理46例5.15 转换后的构造语法树的翻译模式E 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.

17、nptr) R1 R.s := R1.s R R.s := R.i T ( E ) T.nptr := E.nptr T id T.nptr :=mkleaf(id, id.entry) T num T.nptr :=mkleaf(num, num.val) 编译原理47+-idto entry for anum 4idto entry for c图图5.29 使用继承属性构造使用继承属性构造 a - 4 + c 的语法树的语法树 idi R sT nptr+i R snumT nptr-i R sE.nptrT nptrid编译原理485.5.2 预测翻译器的设计预测翻译器的设计算法算法5.

18、1 预测语法制导翻译器的构造预测语法制导翻译器的构造输入输入: 语法制导翻译模式语法制导翻译模式, 其基础文法适于预测分析其基础文法适于预测分析输出输出: 语法制导翻译器语法制导翻译器方法方法: 修改预测分析器的结构。修改预测分析器的结构。1. 为每个非终结符号A构造一个函数， A的每个继承属性对应函数的一个参数， A的综合属性对应函数的返回值(假定A只有一个综合属性)，并为出现在A的产生式中的文法符号的每个属性定义一个局部变量；2. A函数的代码根据当前的输入决定使用哪一个产生式；编译原理493. 与每个产生式有关的代码如下：1) 对于带有综合属性x的单词符号X，把x的值保存在为X.x声明的

19、变量中，产生匹配X的调用，并继续输入；2) 对于非终结符号B，产生一个赋值语句c:=B(b1,b2,bk), b1,b2,bk 是代表B的继承属性的变量，c是代表B的综合属性的变量；3) 对于每个动作，将其代码拷贝到分析器，把对属性的引用改为对相应的局部变量的引用。算法算法5.1 预测语法制导翻译器的构造预测语法制导翻译器的构造编译原理50例例5.16 q图5.28中的文法是LL(1)文法，适于自顶向下的分析。q从文法中非终结符号的属性，可以得到函数E，R和T的参数和返回值的类型。由于E和T没有继承属性，所以它们不含有参数。 编译原理51把两个R产生式结合起来, 新的产生式用符号addop代表

20、+和-：R addopT R1.i = mknode(addop.lexeme, R.i, T.nptr) R1 R.s = R1.sR R.s = R.i编译原理52R的翻译器代码基于的翻译器代码基于产生式产生式 R addop T R | 的语法分析过程：的语法分析过程：编译原理53编译原理545.5.4 L属性的自底向上属性的自底向上qS-属性的自底向上计算综合属性在归约时执行计算动作qL-属性的自底向上计算语义动作不在最右内嵌的语义动作继承属性的计算关键问题解决方法引入标记标记编译原理55删除嵌入在翻译模式中的动作删除嵌入在翻译模式中的动作q语义动作如何执行希望在归约时执行所有的动作都

21、出现在产生式的末尾q可以采用在翻译模式中插入标记非终结符号的方法。A B.i = f(A.i) B C改写为：A M B CM M.i = A.i; M.s = f(M.i) 编译原理56例：引入标记非终结符号例：引入标记非终结符号M,N，改写翻译模式：，改写翻译模式：E T RR + T M R | - T N R | T numprint(num.val) M print(+) N print(-) E T RR + T print(+) R1 | - T print(-) R1 | T num print(num.val)编译原理57分析栈中的继承属性分析栈中的继承属性q继承属性的值无非

22、有两种来源一开始就存在来自综合属性，经过复制来自综合属性，经过计算编译原理58 DT type in Lint in L , x in L , q p 图5.32 在每一个L结点L.in = T.type继承属性来自综合属性，其值由复写规则决定，继承属性来自综合属性，其值由复写规则决定，且继承属性的位置固定的情形。且继承属性的位置固定的情形。编译原理59翻译模式翻译模式D T L.in := T.type L T int T.type = integerT realT.type = realL L1 .in := L.in L1 , id addtype(id.entry, L.in) L i

23、d addtype(id.entry, L.in) 复写规则编译原理60图图5.33 当当L的右边符号被归约时，的右边符号被归约时，T正好在其右边的符号的正好在其右边的符号的下面下面输入 state 使用的产生式 real p, q, r p,q,r p,q,r ,q,r ,q,r q,r ,r ,r r - real T Tp TL TL, TL,q TL TL, TL,r TL D Treal Lid LL,id LL,id DTL 编译原理61图图5.34 T.type的值在的值在L.in处被使用处被使用产生式 代码段 D TL; T int T real L L,id L id Val

24、ntop := integer Valntop := real Addtype(valtop, valtop-3 Addtype(valtop, valtop-1 属性T.type在栈中的位置相对于栈顶是事先知道的。因此，可以用栈中的属性值T.type代替L.in。编译原理62模拟继承属性的计算模拟继承属性的计算q这两种情况如何处理？继承属性的存放位置不能事先预知继承属性需要通过计算得到编译原理63一个不能预知属性值在栈中所放位置的例子一个不能预知属性值在栈中所放位置的例子考虑下面SDD： 产生式 语义规则 S aAC C.i := A.s S bABC C.i := A.s C c C.s

25、:= g(C.i)属性C.i通过一个复写规则来继承属性A.s 的值。 Sa A C s i Sb A B C s i编译原理64一个不能预知属性值在栈中所放位置的例子一个不能预知属性值在栈中所放位置的例子考虑下面翻译模式：S aA C.i := A.s C S bAB C.i := A.s C C c C.s := g(C.i)属性C.i通过一个复写规则来继承属性A.s 的值。 Sa A C s i Sb A B C s i编译原理65通过标记非终结符通过标记非终结符M复写属性的值复写属性的值 产生式 语义规则 S aAC C.i := A.s S bABMC M.i :=A.s; C.i :

26、= M.s C c C.s := g(C.i) M M.s := M.i Sb A B C s i (a)原产生式 Sb A B M C s i s i (b) 依赖关系编译原理66cAb_A.s.topcMBAa_M.sB.sA.s.top通过标记非终结符M复写属性的值，预知属性值在栈中所放位置编译原理67标记非终结符也可以用来模拟不是复写规则的语标记非终结符也可以用来模拟不是复写规则的语义规则义规则例如，例如，产生式语义规则 S a A C C.i := f(A.s)此时，决定C.i的规则不是复写规则， C.i值尚未在val栈中形成。这个问题仍然可以使用标记非终结符号来解决：产生式语义规则

27、 S a A N C N.i := A.s; C.i := N.s N N.s := f(N.i)编译原理68cSiCiNsAsacAaC.sA.s.topcNAaC.sN.sA.s.top编译原理69例例5.19 使用三个标记非终结符使用三个标记非终结符所有继承属性都由复写规则赋值。编译原理70编译原理71图图5.37 语法制导定义的实现语法制导定义的实现产生式 代码段SKBK stackntop.ps = 10;BB1 L B2 stackntop.ht = max(stacktop-2.ht, stacktop.ht);stackntop.dp = max(stacktop-2.dp,

28、stacktop.dp);L stackntop.ps = stacktop-1.psBB1 sub M B2 stackntop.ht = max(stacktop-3.ht, stacktop.ht stacktop-4.ps * 0.25); stackntop.dp = max(stacktop-3.dp, stacktop.dp stacktop-4.dp * 0.25); M stackntop.ps = stacktop-2.ps * 0.70B ( N B1 ) stackntop.ht = stacktop-1.ht;stackntop.dp = stacktop-1.dp;

29、N stackntop.ps = stacktop-1.psBtext stackntop.ht = getHeight(stacktop-1.ps, stacktop.lexval);stackntop.dp = getDepth(stacktop-1.ps, stacktop.编译原理72Esub1.val的分析树的分析树SKtext.val BMsubBtextE text1BBBL 编译原理73Esub1.val的注释分析树的注释分析树SKtext.val BMsubBtextE text1BBBL s=10pspsipshth=E.hsps hth=1.hi编译原理74Esub1.v

30、al的注释分析树的注释分析树SKtext.val BMsubBtextE text1BBBL s=10h=E.hhtishthtishththtpspspspspsh=1.hh=.val.h编译原理75引进标记非终结符号对基础文法的影响引进标记非终结符号对基础文法的影响q基础文法是LL(1)文法没有影响，修改后的文法仍将保持LL(1)文法。因为每个标记非终结符号是唯一的，而且只有唯一一个的产生式q基础文法是LR(1)文法q引入标记非终结符号可能使修改后的文法变成非LR(1)文法编译原理76 例例5.16 翻译为前缀表达式翻译为前缀表达式L E nE print(+) E1+ TE TT print(*) T1