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

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

2、是L-attributed。,编译原理,4,SDD vs. SDT,语义规则 语义动作,E E1 + T E.val := E1 .val + T.val ,编译原理,5,SDD vs. SDT,语义规则 语义动作,E E1 + T print(+); ,编译原理,6,5.4.1 后缀SDT,自底向上分析S属性文法。 A X Y Z语义动作,编译原理,7,编译原理,8,5.4.2后缀SDT的语法分析实现,A X Y Z,X Y Z,X.x Y.y Z.z,top,文法符号,综合属性,编译原理,9,例5.15 显式操作语法分析栈,编译原理,10,3*5 n的分析计算过程,digit,3,top,

3、编译原理,11,3*5 n的分析计算过程,F,3,top,编译原理,12,3*5 n的分析计算过程,T,3,*,digit,5,top,编译原理,13,3*5 n的分析计算过程,T,3,*,F,5,top,编译原理,14,3*5 n的分析计算过程,T,15,top,编译原理,15,3*5 n的分析计算过程,E,15,top,编译原理,16,3*5 n的分析计算过程,E,15,n,top,编译原理,17,3*5 n的分析计算过程,L,15,top,编译原理,18,5.4.3 产生式内部带语义动作的SDT,B X a Y LR：归约出X之后立即执行动作a LL：试图展开Y之前执行动作a,编译原理,

4、19,例，中缀到后缀转换的SDD,编译原理,20,例，中缀到后缀转换的SDT,L E n E E1+ T print(+) E T T T1* F print(*) T F F (E) F digit print(digit.lexval),编译原理,21,例5.16 翻译为前缀表达式,L E n E print(+) E1+ T E T T print(*) T1* F T F F (E) F digit print(digit.lexval),Not all SDTs can be implemented during parsing: Not a LR Grammar ?,编译原理,22

5、,嵌入动作的分析树：3*5+4,编译原理,23,5.4.4 从SDT中删除左递归,例5.17 带左递归的文法的翻译模式。 E E1 + T print(+); E T 转换为： E TR R + print(+); R R ,编译原理,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.

6、a, Y.y) A X A.a := f (X.x) ,编译原理,26,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 ,编译原理,27,5.4.5 L属性定义的SDT,确定语义动作的执行时机 如何将语义动作嵌入产生式右部的适当位置？,编译原理,28,1. 只有综合属性的情况：将计算综合属性的语义规则作为产生式右边末尾的动作。例如：,原则：,产生式 语义规则 T T1 * F T.val := T1.val * F.val,产生式 语义动作 T T1 * F T.val :

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

8、)。,编译原理,31,E,1,.val,上图可以用命令：E sub 1.val 描述。,例5.18数学排版语言的翻译模式片断。,a,i,上图可以用命令：a sub i sub j 描述。,j,编译原理,32,例5.18数学排版语言的翻译模式。,综合属性： ht ：描述height dp ：描述depth 继承属性ps：point size，设定字体大小。 Assume ps = 10。 下标的大小按比例缩小，位置下降。,编译原理,33,图5-25 盒子的大小和高度的语法制导定义,编译原理,34,S B BB B sub B B sub 1 E sub 1,E,1,B1.ht,max(B1.ht

9、, 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 B B B1B2 B B1 sub B2 B (B) | text,结合性：右结合 优先级：sub高于并置,S B B T B1 | T T F sub T1 | F F (B) | tex

10、t,编译原理,37,例5.19,S while (C) S1,C.code S1.code goto L1 .,C.true:,C.false:,to C.true,to C.false,while语句,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 | C.code | label | L2 | S1.code,S while ( L1 = newlabel();

11、L2 = newlabel(); C.false = S.next;C.true = L2; C) S1.next = L1; S1 S.code = label | L1 | C.code | label | L2 | S1.code ,编译原理,39,5.5 实现L属性定义的翻译,建立注释语法分析树 构造语法分析树，加入动作，按照前序顺序执行 使用递归下降的语法分析器，在预测分析的过程中实现L属性定义。,编译原理,40,例5.20,编译原理,41,例5.22,编译原理,42,编译原理,43,5.5.1 从翻译模式中消除左递归,例5.14 带左递归的文法的翻译模式。 S-属性定义 E E1

12、+ T E.val := E1.val + T.val E E1 - T E.val := E1.val - T.val E T E.val := T.val T (E) T.val := E.val T num T.val := num.val,编译原理,44,经过转换的带有右递归文法的翻译模式,E T R.i := T.val R E.val := R.s R + T R1.i := R.i + T.val R1 R.s := R1.s R R.s := R.i T ( E ) T.val := E.val T num T.val := num.val,编译原理,45,表达式9-5+2的计

13、算,编译原理,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.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,+,-,id to ent

14、ry for a,num 4,id to entry for c,图5.29 使用继承属性构造 a - 4 + c 的语法树,id,i R s,T nptr,+,i R s,num,T nptr,-,i R s,E.nptr,T nptr,id,编译原理,48,5.5.2 预测翻译器的设计算法5.1 预测语法制导翻译器的构造,输入: 语法制导翻译模式, 其基础文法适于预测分析 输出: 语法制导翻译器 方法: 修改预测分析器的结构。 1. 为每个非终结符号A构造一个函数， A的每个继承属性对应函数的一个参数， A的综合属性对应函数的返回值(假定A只有一个综合属性)，并为出现在A的产生式中的文法符

15、号的每个属性定义一个局部变量； 2. A函数的代码根据当前的输入决定使用哪一个产生式；,编译原理,49,3. 与每个产生式有关的代码如下： 1) 对于带有综合属性x的单词符号X，把x的值保存在为X.x声明的变量中，产生匹配X的调用，并继续输入； 2) 对于非终结符号B，产生一个赋值语句c:=B(b1,b2,bk), b1,b2,bk 是代表B的继承属性的变量，c是代表B的综合属性的变量； 3) 对于每个动作，将其代码拷贝到分析器，把对属性的引用改为对相应的局部变量的引用。,算法5.1 预测语法制导翻译器的构造,编译原理,50,例5.16,图5.28中的文法是LL(1)文法，适于自顶向下的分析。

16、 从文法中非终结符号的属性，可以得到函数E，R和T的参数和返回值的类型。由于E和T没有继承属性，所以它们不含有参数。,编译原理,51,把两个R产生式结合起来, 新的产生式用符号addop 代表+和-： R addop T R1.i = mknode(addop.lexeme, R.i, T.nptr) R1 R.s = R1.s R R.s = R.i,编译原理,52,R的翻译器代码基于产生式 R addop T R |的语法分析过程：,编译原理,53,编译原理,54,5.5.4 L属性的自底向上,S-属性的自底向上计算 综合属性在归约时执行计算动作 L-属性的自底向上计算 语义动作不在最右内

17、嵌的语义动作 继承属性的计算关键问题 解决方法引入标记,编译原理,55,删除嵌入在翻译模式中的动作,语义动作如何执行 希望在归约时执行 所有的动作都出现在产生式的末尾 可以采用在翻译模式中插入标记非终结符号的方法。,A B.i = f(A.i) B C 改写为： A M B C M 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 R R + T print(+) R1 | - T print(-) R1 | T num print(num.val),编译原理,57,分析栈中的继承属性,继承属性的值无非有两种来源 一开始就存在 来自综合属性，经过复制 来自综合属性，经过计算,编译原理,58,D T type in L int 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.t