编译原理与技术 语法制导翻译

1、2021-6-13编译原理与技术讲义1 编译原理与技术 语法制导翻译 2021-6-13编译原理与技术讲义2 语法制导翻译 属性文法 ls-属性定义 ll-属性定义 l语法制导定义与翻译方案 自底向上翻译 ls-属性定义自底向上计算 l自底向上计算继承属性 自顶向下翻译 2021-6-13编译原理与技术讲义3 属性文法 属性文法（attributed grammar） 上下文无关文法上下文无关文法+属性属性+属性计算规则属性计算规则 属性用来描述文法符号的语义特征，如 常量的“值”、变量的类型和存储位置等。 e.g. 二义性表达式文法g，非终结符e有属性e.val （表达式的值） ee + e

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

3、e1 ) e.val := e1.val enumber e.val := number.lex_val 2021-6-13编译原理与技术讲义6 e.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 2021-6-13编译原理与技术讲义7 属性文法 属性的分类 若产生式ax1x2xn，与之相关的属性计算规则 b := f ( c1, c2, ) 如果属性

4、b是产生式左部符号左部符号a的属性的属性则称其为a 的的综合属性；综合属性； 如果属性b是产生式右部符号右部符号xi的属性的属性则称其为 xi的继承属性；的继承属性； c1, c2, 一般是产生式右部其它符号的(综合)属 性或a的继承属性； 固有属性：终结符仅有的属性。如 number.lex_val。通常由词法程序提供。 2021-6-13编译原理与技术讲义8 a.b x1.c1x2.c2x 综合属性a.b的计算 a的继承属性 a x1.c1x2.c2 继承属性xk.b的计算 a的继承属性 xk.bx 属性依赖图 2021-6-13编译原理与技术讲义9 e.g. 2 属性依赖图:345 e.

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

6、分析时，在归约前计算。如yacc中的语义动作。 2021-6-13编译原理与技术讲义11 e.g. 3 属性计算次序: 345 e. val = 23 e. val = 3 + e. val = 20 number. lex_val = 3e. val = 4e. val = 5 number. lex_val = 4number. lex_val = 5 1 2 3 4 5 6 7 8 2021-6-13编译原理与技术讲义12 s-属性定义 语义规则仅包含综合属性计算（可以有固有 属性出现）。 适合自底向上计算 e.g. 语法树 语法树与分析树 语法树可看作分析树的浓缩。也称抽象语法 树。而

7、分析树可看成具体语法树。 2021-6-13编译原理与技术讲义13 s if b-expr then s1 else s2 语法树 分析树 语法树 vs. 分析树 if-then-else b-exprs1s2 s if b-expr then s1else s2 2021-6-13编译原理与技术讲义14 a := b* -c + b * -c 语法树 分析树 语法树 vs. 分析树 assign a+ * b c * b c assigne ee+ e*e b e e a 赋值语句 c e*e b e c 算符 2021-6-13编译原理与技术讲义15 dag（去除了公共子表达式的无环有向图

8、） a := b* -c + b * -c 语法树 vs. dag assign a+ * b c * b c assign a+ * b c 语法树dag 2021-6-13编译原理与技术讲义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.n

9、ptr, e2.nptr) e( e1 ) e.nptr := e1.nptr e - e1 e.nptr := mknode(,e1.nptr, ) enumber e.nptr := mkleaf(num,number.lex_val) eid e.nptr := mkleaf(id,id.entry) 2021-6-13编译原理与技术讲义17 e.g.4 构造表达式的语法树（dag） e.nptr e的语法树（根结点指针） mknode(op, left, right)建立一个表达式语法 树结点，它的运算符为op，左、右运算对象 是left和right所指的语法树。如果建成dag， 则需

10、要检查是否已存在相应内部结点op，其 左右运算对象分别是left和right。若没有则新 建一个。 mkleaf(num,number.lex_val) mkleaf(id,id.entry) 建立表达式语法树的叶结点。建dag也需检 查是否已有相应结点。 2021-6-13编译原理与技术讲义18 e.g.4 构造表达式a+b*-4的属性结构树 e.nptr e.nptre.nptr+ e.nptre.nptr* a b e.nptr 4 id a id b num4 - * + 2021-6-13编译原理与技术讲义19 e.g.4 构造表达式a+b*-4的语法树（dag） + id a* i

11、d b - num4 2021-6-13编译原理与技术讲义20 l-属性定义 如果产生式ax1x2xn 的语义规则只计算 1）a的综合属性，或者 2）xi的继承属性，且该属性仅依赖于产生式右部xi 的左边符号xj（ji）的（综合）属性或a的继承属性； s-属性定义均为l-属性定义 可按深度优先次序计算 一种自然的属性计算次序 在分析期间完成翻译。属性计算与结点建立有联 系；适合于自顶向下和自底向上分析方法。 2021-6-13编译原理与技术讲义21 深度优先次序 procedure dfvisit( n : node ) begin for each child m of n, from le

12、ft to right do begin evaluate inherited attributes of m; dfvisit( m ) ; end; evaluate synthesized attributes of n; end 2021-6-13编译原理与技术讲义22 e.g.5 非l-属性定义的语法制导定义 产生式语义规则 alml.i := l(a.i) m.i := m(l.s) a.s := f(m.s) aqrr.i := r(a.i) q.i := q(r.s) a.s := f(q.s) 2021-6-13编译原理与技术讲义23 翻译方案中的动作 语义动作可放在产生式右

13、端任何位置；这也就显式 地给出了动作的执行时刻。（可认为是在深度优先 遍历中的执行时刻） e.g. 6将含有+和-运算的中缀表达式翻译为后缀形式： et r r addop t print( addop.lex_val) r | t number print( number.lex_val) 2021-6-13编译原理与技术讲义24 e.g. 6 中缀翻译为后缀 ：9-4+5 e tr 9print(9) -tprint(-)r 4print(4)+tprint(+) 5print(5) r 1 2 3 4 5 2021-6-13编译原理与技术讲义25 翻译方案中的动作 设计翻译方案时，必须保

14、证动作所引用的属性值是 可用的。 只有综合综合属性时（s-属性定义），动作放在 产生式末尾； 若有继承属性时，动作的放置须保证： （产生式右部）符号的继承属性必须在 此符号前计算； 动作不要引用其右边符号的综合属性； 左部非终结符的综合属性一般放在产生式末 尾（确保它引用的属性均已计算完且可用） 2021-6-13编译原理与技术讲义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 a a print( a.in ) 2021-6-13编译原理

15、与技术讲义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) 2021-6-13编译原理与技术讲义28 e.g.8 类型说明的语法制导定义（0） 属性传递 d tl l，k l，j i int 2021-6-13编译原理与技术讲义29 e.g.8类型说明的语法制导定义（1） 改写上述类型声明文法，使得其中的t

16、成为l 的子结点（即产生式右部），可以避免继承 属性的使用。修改后文法如下： dl tint treal ll1 , id lt id 2021-6-13编译原理与技术讲义30 e.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.type 2021-6-13编译原理与技术讲义31 e.g.8类型说明的 语法制导定义

17、（2） 属性传递 d t l l，k l，j i int 2021-6-13编译原理与技术讲义32 e.g.8 类型说明的语法制导定义（3） pascal语言类型声明文法如下： dl : t tint treal ll1 , id lid 该声明文法的“问题”在于，l中 声明的变量的类型t处于产生式中 l的右边！若用继承属性l.in来传 递类型信息t.type形成非l属性 定义。从而无法在完成l分析同时 将有关类型信息填入符号表！可以可以 考虑将考虑将t作为作为l的子结点（通过修的子结点（通过修 改文法）来改变这种情况改文法）来改变这种情况 2021-6-13编译原理与技术讲义33 e.g.8

18、 类型说明的语法制导定义（4） 产生式语义规则 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.type 2021-6-13编译原理与技术讲义34 e.g.9 翻译方案的计算次序 ee+t print( “1” ) et print( “2” ) tt*f print( “3” ) tf print( “4” ) f(e) print( “5” ) fid print(

19、 “6” ) 输入串是id*(id+id)时，该翻译方案输出什么？ 2021-6-13编译原理与技术讲义35 s-属性定义的自底向上计算 拓广分析栈，即添加属性栈，包含文法符号 的综合属性。在归约实施前，右部各符号的 综合属性（若有的话）已放在与符号位置对 应的属性栈上，因此，可以先计算获得左部 非终结符的综合属性。然后再归约，这时从 分析栈中弹出句柄，（注意，此时改变栈顶注意，此时改变栈顶 top即可即可）最后，将左部符号连同其属性放入 由top指示的分析栈及属性栈的位置中。 这种属性栈只能存放综合属性。 回想yacc中如何做的？ 2021-6-13编译原理与技术讲义36 如果axyz，相关

20、 语义规则如下： a.a := f(x.x,y.y,z.z) 显然， x.x在valtop-2 y.y在valtop-1 z.z在valtop a.a在valntop ，ntop = top |句柄长度|+1 val ntop := f( valtop-2, valtop-1, valtop ) 属性栈与分析栈 zz.z yy.y xx.x 分析栈属性栈 val top bottom 2021-6-13编译原理与技术讲义37 如果ab ，相关 语义规则如下： a.a := b.b 显然， b.b在valtop a.a在valntop ， ntop = top 1+1 = top ,即归约前后栈

21、顶top不变， 也即val ntop 和 valtop对应属性栈同一个单元， 所以，可以省略原语义规则对应的属性栈操作：所以，可以省略原语义规则对应的属性栈操作： valntop := valtop 属性栈与分析栈 bb.b 分析栈属性栈val top bottom 2021-6-13编译原理与技术讲义38 e.g.10 计算表达式的（栈）代码 产生式语义规则代码段 le nprint( e.val ) print( valtop-1 ) ee1+te.val := e1.val + t.val valntop:=valtop-2+valtop ete.val := t.val tt1*ft.

22、val := t1.val * f.val valntop:=valtop-2*valtop tft.val := f.val f(e)f.val := e.val valntop:=valtop-1 fdigitf.val := digit.lex_val 2021-6-13编译原理与技术讲义39 如何在自底向上分析中计算继承属性？ 属性栈上仅能存放综合属性 能否将继承属性的引用转换成综合属性？ 分析栈中符号的继承属性 属性copy规则 如果，axy，有语义规则y.i := x.s， 翻译方案可写为： a x y.i := x.s y 自底向上计算继承属性 2021-6-13编译原理与技术讲

23、义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?） bottom xx.s（y.i） 分析栈属性栈 val top 句柄 （归约为y） top句柄长句柄长 2021-6-13编译原

24、理与技术讲义41 e.g.11 c声明的翻译方案 dt l.in := t.type l tint t.type := integer treal t.type := real l l1.in := l.in l1 , id addtype(id.entry, l.in) lid addtype(id.entry, l.in) 对于输入串：int p,q,r 分析过程如下： 2021-6-13编译原理与技术讲义42 输入串 分析栈 产生式 int p,q,r p,q,r int p,q,r t tint ,q,r tp ,q,r tl lid q,r tl, ,r tl,q ,r tl ll

25、, id r tl, tl,r tl ll , id d dtl 注意：每 次归约成 l时，t 与l的位 置关系 t就在 句柄的下 面！ 2021-6-13编译原理与技术讲义43 e.g.11 c声明的“代码段” 产生式 代码段（只含综合属性） dt l tintvalntop:=integer trealvalntop:=real l l1 , id addtype(valtop,valtop-3) lid addtype(valtop,valtop-1) l的继承属性 l.in 2021-6-13编译原理与技术讲义44 问题1：继承属性的位置在构造编译器时不可预知 （或不固定），如e.g.

26、12 产生式语义规则 s a a c c.i := a.s s b a b cc.i := a.s c cc.s := g(c.i) 用c c归约时，c.i的值可能在valtop-1或者在 valtop-2的位置上。解决办法是考虑将其统一。 引入标记非终结符 m和产生式m 。 模拟继承属性的计算 bottom cc ab aa b 分析栈1分析栈2 top 2021-6-13编译原理与技术讲义45 产生式语义规则 s a a cc.i := a.s s b a b m cc.i := m.s m.i := a.s c cc.s := g(c.i) m m.s := m.i 引入m后，c.i 可

27、从句柄c的下面(valtop-1)取得！属性传递： a.s m.i m.s c.i c.s e.g.12 引入标记非终结符 bottom am ab a b 分析栈1分析栈2 top cc 2021-6-13编译原理与技术讲义46 产生式代码段 s a a c s b a b m c c c valntop:= g(valtop-1) m valntop := valtop-1 可否将m放在s a a c产生式中？m.i 2021-6-13编译原理与技术讲义47 模拟继承属性的计算 问题2：语义规则不是简单的属性复写拷贝。 e.g.13 : 将例12中的s a a c语义规则换为： 产生式语义

28、规则 s a a cc.i := f( a.s ) 虽然在例12中引入了m使得“a.s”可在valtop-1 处找到，但在s的两个产生式中c.i的取值方式 不同，导致c.s的计算嘛 这次可以考虑引入标记非终结符n和n 2021-6-13编译原理与技术讲义48 e.g.13 引入标记非终结符n 产生式 语义规则 s a a n c c.i := n.s n.i := a.s nn.s := f(n.i) (其他产生式和语义规则不变） (代码段略） 2021-6-13编译原理与技术讲义49 产生式语义规则 sb b.ps := 10 s.ht := b.ht bb1b2b1.ps := b.ps

29、b2.ps := b.ps b.ht := max(b1.ht,b2.ht) bb1 sub b2 b1.ps := b.ps b2.ps := shrink(b.ps) b.ht := disp(b1.ht,b2.ht) b text b.ht := text.h b.ps e.g.14 文字排版的语法制导定义 2021-6-13编译原理与技术讲义50 s ： s.ht，综合属性；待排公式的整体高度 b ： b.ps，继承属性； 公式（文本）中字体“点”的大小 b.ht，综合属性；公式排版高度 text ：text.h，文本高度 max ：求两个排版公式的最大高度 shrink(b) ：将点

30、大小缩小为b的30 disp(b1.ht，b2.ht)：向下调整b2的位置 文字排版中的符号属性 e 1 val 2021-6-13编译原理与技术讲义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 2021-6-13编译原理与技术讲义5

31、2 文字排版中引入标记符号 为了自底向上计算： b text b.ht := text.h b.ps 必须确定继承属性b.ps的（“属性栈”）位置。为此 引 入标记非终结符l、m和n及其属性，包括相应的空产 生式和有关属性规则。这样b.ps即可在紧靠“句 柄”text 下方的位置上找到。(l的综合属性置为b.ps的初值) sl b bb1m b2 bb1 sub n b2 texttext.h ll.s=10 分析栈属性栈 top bottom 2021-6-13编译原理与技术讲义53 s l b.ps := l.s l l.s := 10 b s.ht := b.ht b b1.ps :=

32、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） 2021-6-13编译原理与技术讲义54 产生式代码段 s l b valntop := valtop bb1 m b2 valntop := max(valtop-2,

33、valtop) bb1 sub n b2 valntop := disp(valtop-3,valtop) b text valntop := valtopvaltop-1 l valntop := 10 m valntop := valtop-1 n valntop := shrink( valtop-2 ) 2021-6-13编译原理与技术讲义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

34、r y r1.i := g(r.i, y.y) r1 r.s := r1.s r r.s := r.i /返回结果 2021-6-13编译原理与技术讲义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), y2.y) y2 a.a xr.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 2021-6-13编译原理与技术讲义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 :=