Microsoft PowerPoint - ch4.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ch4.ppt [兼容模式]"

检周
5 years ago
Views:

1 第四章语法制导的翻译本章内容 1 介绍语义描述的一种形式方法 : 语法制导的翻译 (sytax-directed traslatio), 它包括两种具体形式语法制导的定义 (sytax-directed defiitio) E.code = E 1.code.code 可读性好, 更适于描述规范翻译方案 (traslatio scheme) { prit } 陈述了实现细节 ( 如语义规则的计算时机 ) 2 介绍语法制导翻译的实现方法例简单计算器的语法制导定义产生式语义规则 E prit (E.val) E.val = E 1.val.val E E.val =.val 1 F.val= 1.val F.val F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 语法制导定义的形式基础的上下文无关文法每个文法符号有一组属性每个文法产生式 A α 有一组形式为 b=f(c 1, c 2,, c k ) 的语义规则, 其中 : f 是函数 b 和 c 1, c 2,, c k 是该产生式文法符号的属性, 综合属性 (sythesized attribute): 如果 b 是 A 的属性,c 1, c 2,, c k 是产生式右部文法符号的属性或 A 的其它属性继承属性 (iherited attribute): 如果 b 是右部某文法符号 X 的属性综合属性 S 属性定义 : 仅使用综合属性的语法制导定义产生式 E E 1 F F F (E) F digit 语义规则 prit (E.val) E.val = E 1.val.val E.val =.val.val= 1.val F.val.val= F.val F.val = E.val F.val = digit.lexval 参见 :biso-examples.zip 中的 cofig/expr1.y, expr.lex 注释分析树 (aotated parse tree): 结点的属性值都标注出来的分析树 85*2 ( 为换行符 ) 的注释分析树.val =10.val =8.val =5 F.val =2.val =10.val =8.val =5 F.val =2 1

2 .val =8.val =5.val =10 F.val =2 F digit F.val = digit.lexval.val =8.val =5.val =10 F.val =2 F.val = F.val.val =8.val =5.val =10 F.val =2 E E.val =.val.val =8.val =5.val =10 F.val =2 移进 digit.val =8.val =5.val =10 F.val =2 F digit F.val = digit.lexval.val =8.val =5.val =10 F.val =2 2

3 F.val = F.val.val =8.val =5.val =10 F.val =2.val =8.val =5.val =10 F.val =2.val =10.val =10.val =8.val =5 F.val =2.val =8.val =5 F.val =2.val =10.val =8.val =5 F.val = 继承属性 it,, 产生式语义规则.i =.type it. type = iteger real. type = real 1, 1.i =.i; addype(.etry,.i) addype(.etry,.i) type 的综合属性, i 的继承属性, 把声明的类型传递给标识符列表 addype 把类型信息加到符号表中的标识符条目里 3

4 例 it 1, 2, 3 的标注了部分属性的分析树不可能像综合属性那样自下而上标注属性属性依赖图 (depedece graph) 例 it 1, 2, 3 的分析树 ( 虚线 ) 的依赖图 ( 实线 ).i =.type.type = iteger.i = iteger it.i = iteger, 3.i = iteger, 2 4 type it i 7 i 5 6 8, 3 i 9 10, 2 2 etry 3 etry etry 属性依赖图例 it 1, 2, 3 的分析树 ( 虚线 ) 的依赖图 ( 实线 ) 1, 1.i =.i; addype (.etry,.i) 属性依赖图例 it 1, 2, 3 的分析树 ( 虚线 ) 的依赖图 ( 实线 ) addype (.etry,.i) 4 type i type i 5 6 it i 7 8, 3 3 etry it i 7 8, 3 3 etry i 9 10, 2 2 etry i 9 10, 2 2 etry 1 1 etry 1 1 etry 属性计算次序 1 拓扑排序 (ological sort): 是 AG 的结点的一种排序 m 1,,m k, 若有 m i 到 m j 的边, 则在排序中 m i 先于 m j 例 1,2,3,4,5,6,7,8,9, 属性计算次序 2 属性计算次序 : 构造输入的分析树 4 type i type i 5 6 it i 7 8, 3 3 etry it i 7 8, 3 3 etry i 9 10, 2 2 etry i 9 10, 2 2 etry 1 1 etry 1 1 etry 4

5 4.1.5 属性计算次序 2 属性计算次序: 构造输入的分析树, 构造属性依赖图属性计算次序 2 属性计算次序: 构造输入的分析树, 构造属性依赖图, 对结点进行拓扑排序 4 type i type i 5 6 it i 7 8, 3 3 etry it i 7 8, 3 3 etry i 9 10, 2 2 etry i 9 10, 2 2 etry 1 1 etry 1 1 etry 属性计算次序 2 属性计算次序 : 构造输入的分析树, 构造属性依赖图, 对结点进行拓扑排序, 按拓扑排序的次序计算属性 it 4 type i 9 i 7 8, 3 3 etry 10, 2 2 etry 1 1 etry i 5 6 语义规则的计算方法分析树方法 : 刚才介绍的方法, 动态确定计算次序, 效率低概念上的一般方法基于规则的方法 :( 编译器实现者 ) 静态确定 ( 编译器设计者提供的 ) 语义规则的计算次序适用于手工构造的方法忽略规则的方法 :( 编译器实现者 ) 事先确定属性的计算策略 ( 如边分析边计算 ),( 编译器设计者提供的 ) 语义规则必须符合所选分析方法的限制适用于自动生成的方法语法树 (sytax tree) 语法树是分析树的浓缩表示 : 每个结点表示一个语法构造, 算符和关键字是语法树中的内部结点语法制导翻译可以基于分析树, 也可以基于语法树语法树的例子 : if the S 1 else S if-the-else S 1 S * 构造语法树的语法制导定义产生式语义规则 = mknode(, E 1.ptr, ) E 1 F F F (E) F F = = mknode(, 1.ptr, ) = = = mkeaf (,.etry) = mkeaf (,.val) 参见 :biso-examples.zip 中的 cofig/asg2ast.y, asg.lex 5

6 a5b 的语法树的构造 a5b 的语法树的构造 5 5 a5b 的语法树的构造 a5b 的语法树的构造 5 5 a5b 的语法树的构造 a5b 的语法树的构造 5 5 6

7 a5b 的语法树的构造 a5b 的语法树的构造 5 5 a5b 的语法树的构造 S 属性的自下而上计算 R 分析器的栈增加一个域来保存综合属性值栈 Z Z.z Y Y.y X X.x state val 若产生式 A XYZ 的语义规则是 A.a = f (X.x, Y.y, Z.z), ) 那么归约后 : A A.a 简单计算器的语法制导定义改成栈操作代码 ( 翻译方案 ) 产生式语义规则 E prit (E.val) E.val =E 1.val.val E E.val =.val Z Z.z 1 F.val= 1.val F.val Y Y.y F.val = F.val X X.x F (E) F.val = E.val F digit F.val = digit.lexval 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (E.val) E.val =E 1.val.val E E.val =.val Z Z.z 1 F.val= 1.val F.val Y Y.y F.val = F.val X X.x F (E) F.val = E.val F digit F.val = digit.lexval 栈 state val 参见 :biso-examples.zip 中的 cofig/expr1.y, expr.lex 栈 state val 7

8 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; E.val =E 1.val.val E E.val = val.val Z Z.z Y Y.y 1 F.val= 1.val F.val F.val = F.val X X.x F (E) F.val = E.val F digit F.val = digit.lexval 栈 state val 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; val [ 2] = val [ ] val [ 2] ]; =-2; p ; Z Z.z E E.val =.val Y Y.y 1 F.val= 1.val F.val X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 栈 state val 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; val [ 2] = val [ ] val [ 2] ]; =-2; p ; Z Z.z E Y Y.y 1 F.val= 1.val F.val X X.x F.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval 栈 state val 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; val [ 2] = val [ ] val [ 2] ]; =-2; p ; Z Z.z E Y Y.y 1 F val [ 2] = val [ ] val [ 2] ; =-2; X X.x F.val = F.val F (E) F.val = E.val 栈 state val F digit F.val = digit.lexval 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; val [ 2] = val [ ] val [ 2] ]; =-2; p ; Z Z.z E Y Y.y 1 F val [ 2] = val [ ] val [ 2] ; =-2; X X.x F F (E) F.val = E.val 栈 state val F digit F.val = digit.lexval 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; val [ 2] = val [ ] val [ 2] ]; =-2; p ; Z Z.z E Y Y.y 1 F val [ 2] = val [ ] val [ 2] ; =-2; X X.x F F (E) val [ 2] = val [ -1]; =-2; 栈 state val F digit F.val = digit.lexval 8

9 简单计算器的语法制导定义改成栈操作代码产生式代码段 E prit (val [ 1] ); =-1; val [ 2] = val [ ] val [ 2] ]; =-2; p ; Z Z.z E Y Y.y 1 F val [ 2] = val [ ] val [ 2] ; =-2; X X.x F F (E) val [ 2] = val [ -1]; =-2; 栈 state val F digit 4.3 属性定义的自上而下计算边分析边翻译的方式能否用于继承属性? 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制分析树的结点是自左向右生成如果属性信息是自左向右流动, 那么就有可能在分析的同时完成属性计算属性 : 表示属性信息自左向右流动 4.3 属性定义的自上而下计算属性定义如果每个产生式 A X 1 X j-1 X j X 的每条语义规则计算的属性是 A 的综合属性 ; 或者是 X j 的继承属性, 但它仅依赖 : 该产生式中 X j 左边符号 X 1, X 2,,X j-1 的属性 ; A 的继承属性 S 属性定义属于属性定义 4.3 属性定义的自上而下计算变量类型声明的语法制导定义是一个属性定义产生式语义规则.i =.type it. type = iteger real 1,. type = real 1.i =.i; addype(.etry,.i) addype(.etry,.i) 4.3 属性定义的自上而下计算 4.3 属性定义的自上而下计算翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是 85 2, 则输出是 E R R addop {prit(addop.lexeme)} i l R 1 ε {prit(.val)} E R {prit (8)} R {prit(8)}addop {prit ()}R {prit(8)}addop {prit(5)}{prit ()}R {prit(8)}{prit(5)}{prit()}addop {prit( )}R {prit(8)}{prit(5)}{prit()}{prit(2)}{prit( )} 例数学排版语言 EQN E sub 1.val S 2 sub 2 text E 1.val 9

10 4.3 属性定义的自上而下计算例数学排版语言 EQN( 语法制导定义 ) E sub 1.val E ps-poit size ();ht-height(s) 1.val 产生式 S 2 sub 2 text 语义规则.ps = 10; S.ht =.ht 1.ps =.ps; 2.ps =.ps;.ht = max( 1.ht, 2 1.ps =.ps; 2.ps = shrik(.ps);.ht = disp ( 1.ht, 2.ht = text.h.ps 4.3 属性定义的自上而下计算例数学排版语言 EQN( 翻译方案 ) S {.ps = 10 } 继承属性的计算 {S.ht =.ht } 位于的左边 4.3 属性定义的自上而下计算例数学排版语言 EQN( 翻译方案 ) S {.ps = 10 } S 综合属性的计算 {S.ht =.ht } 放在右部末端 4.3 属性定义的自上而下计算例数学排版语言 EQN( 翻译方案 ) S {.ps = 10 } {S.ht =.ht } { 1.ps =.ps } 1 { 2.ps =.ps } 2 {.ht = max( 1.ht, 2 } { 1.ps =.ps } 1 sub { 2.ps = shrik(.ps) } 2 {.ht = disp ( 1.ht, 2 } text {.ht = text.h.ps } 4.3 属性定义的自上而下计算例左递归的消除引起继承属性 ( 文法 ) 产生式语义规则 = mknode(, E 1.ptr, ) E = 1 F = mknode(, 1.ptr, ) F = F (E) = F = mkeaf (,.etry) F = mkeaf (,.val) 4.3 属性定义的自上而下计算 E {R.i = } R { = R.s} R {R 1.i = mknode (, R.i, )} R 1 {R.s = R 1.s} R ε {R.s = R.i } F {W.i = } W { = W.s} W F {W 1.i = mknode (, W.i, )} W 1 {W.s = W 1.s} W ε {W.s = W.i } F 产生式部分不再给出 10

11 4.3 属性定义的自上而下计算 iw 略去了 E R 部分 i W iws ε 4.3 属性定义的自上而下计算 iw 略去了 E R 部分 FW F i W iws ε 属性定义的自上而下计算 iw 略去了 E R 部分 F W i W iws ε 4.3 属性定义的自上而下计算 iw 略去了 E R 部分 W * F W i W F iws ε 属性定义的自上而下计算 iw 略去了 E R 部分 W * F W i W iws ε 4.3 属性定义的自上而下计算 iw 略去了 E R 部分 W * F W i W F iws ε

12 4.3 属性定义的自上而下计算 iw 略去了 E R 部分 W * F W i W iws ε 4.3 属性定义的自上而下计算 iw 略去了 E R 部分 W ε i W iws ε 属性定义的自上而下计算预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现 ( 文法 ) 产生式 R R ε 的分析过程 vo R( ) { if (lookahead == '' ) { match ( '' ); ( ); R( ); } else / 什么也不做 / } 4.3 属性定义的自上而下计算 sytaxreenode R (sytaxreenode i) { // 继承属性作为参数, 综合属性为返回值 sytaxreenode ptr, i1, s1, s; char addoplexeme; if (lookahead == '' ){ / 产生式 R R / addoplexeme = lexval; match('' ); ptr = (); i1 = mknode(addoplexeme, i, ptr); s1 = R (i1); s = s1; } else s = i; / 产生式 R ε / retur s; } R : i, s : ptr : addoplexeme 4.3 属性定义的自上而下计算 4.3 属性定义的自上而下计算用综合属性代替继承属性 Pascal 的声明, 如 m, : iteger : ( 非属性定义 ) iteger char, 信息从右向左流, 归约从左向右, 两者不一致用综合属性代替继承属性 Pascal 的声明, 如 m, : iteger : ( 非属性定义 ) iteger char, 等所需信息获得后再归约改成从右向左归约, (S 属性定义 ), : : iteger char iteger 12

13 4.3 属性定义的自上而下计算 { addtype (. etry,. type)}, 1 {. type = 1. ype; addtype (. etry, 1. type)} : {. type =. type} iteger {. type = iteger} real {. type = real}, 4.4 属性的自下而上计算在自下而上分析的框架中实现属性定义的方法它能实现任何基于 (1) 文法的属性定义也能实现许多 ( 但不是所有的 ) 基于 R(1) 的属性定义 : iteger 4.4 属性的自下而上计算删除翻译方案中嵌入的动作 E R R {prit ( )}R 1 {prit ( )}R 1 ε {prit (.val)} 在文法中加入产生 ε 的标记非终结符, 让每个嵌入动作由不同标记非终结符 M 代表, 并把该动作放在产生式 M ε 的右端 E R R M R 1 N R 1 ε {prit (.val)} M ε{prit ( )} N ε{prit ( )} YACC 会按照这样的方法来处理输入的文法, 即为嵌入的语义动作引入 ε 产生式 4.4 属性的自下而上计算分析栈上的继承属性例 it p, q, r {.i =.type} it {. type = iteger} real {. type = real} { 1.i =.i } 1,{addtype (.etry,.i )} {addtype (.etry,.i )} 4.4 属性的自下而上计算分析栈上的继承属性 1 属性位置能预测 type i 例 it p, q, r it i, r {.i =.type} i, q it {. type = iteger} real {. type = real} p { 1.i =.i } 1,{addtype (.etry,.i )} {addtype (.etry,.i )} 4.4 属性的自下而上计算分析栈上的继承属性 1 当属性位置能预测时 type i i, 例 it p, q, r it r {.i =.type} i, q it {. type = iteger} p real {. type = real} { 1.i =.i } 继承属性的计算可 1,{addtype (.etry,.i )} 以略去, 引用继承属 {addtype (.etry,.i )} 性的地方改成引用其他符号的综合属性 13

14 4.4 属性的自下而上计算产生式代码段 it real 1, val[] = iteger val[] = real addype(val[], val[ 3]) ; = -2; addype(val[], val[ 1]) ; it type i i, r i, q p 4.4 属性的自下而上计算 2 属性的位置不能预测 S aac C.i = A.s S bac C.i = A.s C c C.s = g(c.i) 可能在, 也可能不在 A 和 C 之间,C.i 的值有 2 种可能增加标记非终结符, 使得位置可以预测 S aac C.i = A.s S bamc M.i = A.s; C.i = M.s C c C.s = g(c.i) M ε M.s = M.i 4.4 属性的自下而上计算 2 属性的位置不能预测 S aac C.i = A.s S bac C.i = A.s C c C.s = g(c.i) 可能在, 也可能不在 A 和 C 之间,C.i 的值有 2 种可能增加标记非终结符, 使得位置可以预测 S aac C.i = A.s S bamc M.i = A.s; C.i = M.s C c C.s = g(c.i) 还得考虑 M.s M ε M.s = M.i 计算的可预测 4.4 属性的自下而上计算模拟继承属性的计算继承属性不直接等于某个综合属性, 而是它的一个函数 S aac C.i = f (A.s) C c C.s = g(c.i) 增加标记非终结符, 把 f(a.s) 的计算移到对标记非终结符归约时进行 S aanc N.i = A.s; C.i = N.s N.s = f (N.i) C c C.s = g(c.i) 4.4 属性的自下而上计算例数学排版语言 EQN S {.ps = 10 } {S.ht =.ht } { 1.ps =.ps } 1 { 2.ps =.ps } 2 {.ht = max( 1.ht, 2 } { 1.ps =.ps } 1 sub { 2.ps = shrik(.ps)} 2 {.ht = disp ( 1.ht, 2 } text {.ht = text.h.ps } 4.4 属性的自下而上计算产生式语义规则 S.ps =.s; S.ht =.ht ε.s = 10 将.ps 存入栈中, 便于引用 M 2 1.ps p =.ps; M.i =.ps; 2.ps = M.s;.ht = max( 1.ht, 2 M ε M.s = M.i sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 14

15 4.4 属性的自下而上计算产生式语义规则 S.ps =.s; S.ht =.ht ε.s = 10 将.ps 存入栈中, 便于引用 M 2 1.ps p =.ps; M.i =.ps; 2.ps = M.s;.ht = max( 1.ht, 2 M ε M.s = M.i 单纯为了属性位置可预测 sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 4.4 属性的自下而上计算产生式语义规则 S.ps =.s; S.ht =.ht ε.s = 10 将.ps 存入栈中, 便于引用 M 2 1.ps p =.ps; M.i =.ps; 2.ps = M.s;.ht = max( 1.ht, 2 M ε M.s = M.i 单纯为了属性位置可预测 sub N 2 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i) 兼有计算功能 text.ht = text.h.ps 举例说明 4.4 属性的自下而上计算 s ε S M s 在 text 归约成时, 的 ps 属性都在次栈顶位置 text ε sub N s text ε text 4.4 属性的自下而上计算产生式语义规则 S.ps =.s; S.ht =.ht ε.s = 10 M 2 1.ps p =.ps; M.i =.ps; 2.ps = M.s;.ht = max( 1.ht, 2 M ε M.s = M.i sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε.s = 10 M 2 1.ps p =.ps; M.i =.ps; 2.ps = M.s;.ht = max( 1.ht, 2 M ε M.s = M.i sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε val[1] = 10 M 2 1.ps p =.ps; M.i =.ps; 2.ps = M.s;.ht = max( 1.ht, 2 M ε M.s = M.i sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 15

16 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε val[1] = 10 M 2 val[ 2] [ ] = max(val[ 2], ( [ val[]) [ M ε M.s = M.i sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε val[1] = 10 M 2 val[ 2] [ ] = max(val[ 2], ( [ val[]) [ M ε val[1] = val[ 1] sub N 2 text 1.ps =.ps; N.i =.ps; 2.ps = N.s;.ht = disp ( 1.ht, 2 N.s = shrik(n.i).ht = text.h.ps 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε val[1] = 10 M 2 val[ 2] [ ] = max(val[ 2], ( [ val[]) [ M ε val[1] = val[ 1] sub val[ 3] = disp (val[ 3], val[]) N 2 N.s = shrik(n.i) text.ht = text.h.ps 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε val[1] = 10 M 2 val[ 2] [ ] = max(val[ 2], ( [ val[]) [ M ε val[1] = val[ 1] sub val[ 3] = disp (val[ 3], val[]) N 2 val[1] = shrik(val[ 2]) text.ht = text.h.ps 4.4 属性的自下而上计算产生式代码段 S val[ 1] = val[] ε val[1] = 10 M 2 val[ 2] [ ] = max(val[ 2], ( [ val[]) [ M ε val[1] = val[ 1] sub val[ 3] = disp (val[ 3], val[]) N 2 val[1] = shrik(val[ 2]) text val[] = val[] val[ 1] 本章要点语义规则的两种描述方法 : 语法制导的定义和翻译方案设计简单问题的语法制导定义和翻译方案, 这是本章的重点和难点语法制导定义和翻译方案的实现 S 属性的自下而上计算 ( 边分析边计算 ) 属性的自上而下计算 ( 边分析边计算 ) 属性的自下而上计算 ( 边分析边计算 ) 不再介绍先分析后计算的方法不能边分析边计算的情况是存在的, 见 5.6 节 16

17 例题 1 下面是产生字母表 Σ = {0, 1, 2} 上数字串的一个文法 : S S 写一个语法制导定义, 判断它接受的句子是否为回文数 S S prit(s.val) S 1 S 1 2 S.val =( 1.val == 2.val)adS 1.val S 2 S.val = true 0.val =0 1.val =1 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入时,S.val = 5.625( 可以修改文法 ) 若按来计算, 该文法对小数点左边部分的计算不利, 因为需要继承属性来确定每个离开小数点的距离 S S 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入时,S.val = 5.625( 可以修改文法 ) 若小数点左边按 (1 20) 21 计算该办法不能直接用于小数点右边, 需改成 ((1 2 0) 2 1)/2 3, 这时需要综合属性来统计的个数 S S 例题 2 为下面文法写一个语法制导的定义, 用 S 的综合属性 val 给出下面文法中 S 产生的二进制数的值例如, 输入时,S.val = 5.625( 可以修改文法 ) 更清楚的办法是将文法改成下面的形式 S.R R R 0 1 S. R R R 例题 2 S.R S.val =.val R.val S S.val =.val 1.val = 1. val 2.val.val =.val R R 1 R. val =R 1. val /2.val /2 R R.val =.val /2 0.val =0 1.val =1 例题 3 给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义例如, 因为和是左结合, ((a (b c )) (d )) 可以重写成 a (b c ) d 两种方法 : 先把表达式的括号都去掉, 然后在必要的地方再加括号去掉表达式中的冗余括号, 保留必要的括号 17

18 例题 3 第一种方法 S E prit( E. code ) if. op == plus the E.code =E 1.code (.code ) else E. code = E 1. code. code; E. op = plus E E. code =. code; E. op =. op 例题 3 1 F if (F. op == plus)or(f. op == times) the if 1. op == plus the. code = ( 1. code ) ( F. code ) else. code = 1. code ( F. code ) else if 1. op = plus the. code = ( 1. code ) F. code else. code = 1. code F. code;. op = times 例题 3 F. code = F. code;. op = F. op F F. code =. lexeme; F. op = F ( E ) F. code = E. code; F. op = E. op 第二种方法例题 3 给 E, 和 F 两个继承属性 left_op 和 right_op 分别表示左右两侧算符的优先级给它们一个综合属性 self_op 表示自身主算符的优先级再给一个综合属性 code 表示没有冗余括号的代码分别用 1 和 2 表示加和乘的优先级, 用 3 表示和 (E) 的优先级, 用 0 表示左侧或右侧没有运算对象的情况例题 3 S E E. left_op =0;E. right_op =0;prit ( E. code ) E 1. left_op = E. left_op; E 1. right_op =1;. left_op =1;. right_op = E. right_op; E.code =E 1.code. code ; E. self_op =1; E. left_op = E. left_op;. right_op = E. right_op; E. code =. code; E. self_op =. self_op 1 F... F... 例题 3 F F. code =. lexeme; F. self_op =3 18

19 例题 3 F ( E ) E. left_op =0;E. right_op =0; F. self_op = if (F. left_op < E. self_op)ad (E. self_op >= F. right_op) the E. self_op else 3 F. code = if (F. left_op < E. self_op)ad (E. self_op >= F. right_op) the E. code else ( E. code ) 19

Microsoft PowerPoint - ch4.ppt [兼容模式]

Microsoft PowerPoint - ch4.ppt [兼容模式] 第四章语法制导的翻译本章内容 1 介绍语义描述的一种形式方法: 语法制导的翻译 (syntax-directed translation), 它包括两种具体形式语法制导的定义 (syntax-directed definition) E E 1 + T E.code = E 1.code T.code + 可读性好, 更适于描述规范翻译方案 (translation scheme) E E