《编译语言语法制导的翻译 4.ppt》由会员分享，可在线阅读，更多相关《编译语言语法制导的翻译 4.ppt（109页珍藏版）》请在三一文库上搜索。
1、第四章 语法制导的翻译,本章内容 介绍一种形式化的语义描述方法：语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案 介绍语法制导翻译的实现方法,4.1 语法制导的定义,例 简单台式计算器的语法制导定义,4.1 语法制导的定义,4.1.1 语法制导定义的形式 基础文法 每个文法符号有一组属性 每个文法产生式A 有一组形式为b = f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式文法符号的属性 综合属性：如果b是A的属性，c1 , c2 , , ck 是产生式右部文法符号的属性或A的其它属性 继承属性：如果b是产生式右部某个文法符号X
2、的属性,4.1 语法制导的定义,4.1.2 综合属性 S属性定义：仅仅使用综合属性的语法制导定义,4.1 语法制导的定义,8+5*2 n的注释分析树,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下
3、而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,分析树各结点属性的计算可以自下而上地完成,4.1 语法制导的定义,注释分析树:结点的属性值都标注出来的分析树,4.1 语法制导的定义,4.1.3 继承属性 int id, id, id,4.1 语法制导的定义,int id1, id2, id3的注释分析树,4.1 语法制导的定义,4.1.4 属性依赖图 int id1, id2, id3的分析树的依赖图 D TL
4、 L.in = T.type,4.1 语法制导的定义,4.1.4 属性依赖图 int id1, id2, id3的分析树的依赖图 L L1, id L1.in = L.in; addType (id.entry, L.in),4.1 语法制导的定义,4.1.5 属性计算次序 拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点 例：1，2，3，4，5，6，7，8，9，10,4.1 语法制导的定义,属性计算次序 构造输入的分析树,4.1 语法制导的定义,属性计算次序 构造输入的分析树，构造属性依赖图,4.1 语法制导的定义,属性计算次序 构造输入的分析树，构造属性依赖图，对结
5、点进行拓扑排序,4.1 语法制导的定义,属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性,4.1 语法制导的定义,语义规则的计算方法 分析树方法：前面介绍的方法,4.1 语法制导的定义,语义规则的计算方法 分析树方法：前面介绍的方法 基于规则的方法：静态确定语义规则的计算次序,4.1 语法制导的定义,语义规则的计算方法 分析树方法：前面介绍的方法 基于规则的方法：静态确定语义规则的计算次序 忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制,4.2 S属性定义的自下而上计算,4.2.1 语法树 语法
6、树是分析树的浓缩表示：算符和关键字是作为内部结点 语法制导翻译可以基于分析树，也可以基于语法树 语法树的例子：,4.2 S属性定义的自下而上计算,4.2.2 构造语法树的语法制导定义,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S
7、属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,a+5b的语法树的构造,4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算 将LR分析器增加一个域来保存综合属性值,栈 state val,top,4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算 将LR分析器增加一个域来保存综合属性值,栈 state val,top,若产生式A XYZ的语义规则是 A.a = f (X.x, Y.y, Z.z),4.2 S属性定义的自下而上计算,4.2.3 S属性的自下而上计算 将LR分析器增加一个域来保存综合属性值,栈 state val,t
8、op,若产生式A XYZ的语义规则是 A.a = f (X.x, Y.y, Z.z)， 那么归约后：,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操
9、作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.3 L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？ 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制,4
10、.3 L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？ 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制 分析树的结点是自左向右生成,4.3 L属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？ 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制 分析树的结点是自左向右生成 如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算,4.3 L属性定义的自上而下计算,4.3.1 L属性定义 如果每个产生式A X1 X2 Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，1 j n, 但它仅依赖： 该产生式中Xj左边符号X1
11、, X2, , Xj-1的属性； A的继承属性,4.3 L属性定义的自上而下计算,4.3.1 L属性定义 如果每个产生式A X1 X2 Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，1 j n, 但它仅依赖： 该产生式中Xj左边符号X1, X2, , Xj-1的属性； A的继承属性 S属性定义属于L属性定义,4.3 L属性定义的自上而下计算,变量类型声明的语法制导定义是一个L属性定义,4.3 L属性定义的自上而下计算,4.3.2 翻译方案 例 把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输出是8 5 + 2 ,4.3 L属性定义的自上而下计算,4.3
12、.2 翻译方案 例 把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输出是8 5 + 2 E T R T + T + T + R addop T print (addop.lexeme) R1 | T num print (num.val),4.3 L属性定义的自上而下计算,4.3.2 翻译方案 例 把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输出是8 5 + 2 E T R R addop T print (addop.lexeme) R1 | T num print (num.val) E T R num print (8) R numprint (8)
13、addop Tprint (+)R numprint(8)addop numprint(5)print (+)R print(8)print(5)print(+)addop Tprint()R print(8)print(5)print(+)print(2)print(),4.3 L属性定义的自上而下计算,例 数学排版语言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text,4.3 L属性定义的自上而下计算,例 数学排版语言EQN E sub 1 .val,4.3 L属性定义的自上而下计算,例 数学排版语言EQN S B.ps = 10 B S.ht
14、= 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 ,4.3 L属性定义的自上而下计算,例 左递归的消除引起继承属性,4.3 L属性定义的自上而下计算,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
15、R R.s = R.i T F W.i = F.nptr W T.nptr = W.s W F W1.i = mkNode ( , W.i, F.nptr) W1 W.s = W1.s W W.s = W.i ,4.3 L属性定义的自上而下计算,E T R.i = T.nptr T + T + T + R E.nptr = R.s R + T R1.i = mkNode ( +, R.i, T.nptr) R1 R.s = R1.s R R.s = R.i T F W.i = F.nptr W T.nptr = W.s W F W1.i = mkNode ( , W.i, F.nptr) W1
16、 W.s = W1.s W W.s = W.i ,4.3 L属性定义的自上而下计算,略去了E TR T 部分,4.3 L属性定义的自上而下计算,4.3.3 预测翻译器的设计 把预测分析器的构造方法推广到翻译方案的实现 产生式R +TR | 的分析过程 void R( ) if (lookahead = + ) match ( + ); T( ); R( ); else / 什么也不做 / ,4.3 L属性定义的自上而下计算,syntaxTreeNode R (syntaxTreeNode i) syntaxTreeNode nptr, i1, s1, s; char addoplexeme;
17、if (lookahead = + ) / 产生式 R +T R / addoplexeme = lexval; match(+ ); nptr = T(); i1 = mkNode(addoplexeme, i , nptr); s1 = R (i1); s = s1; else s = i; / 产生式 R / return s; ,R : i, s T : nptr + : addoplexeme,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D L : T T integer | char L L, id |
18、id,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D L : T T integer | char L L, id | id 改成从右向左归约 D id L L , id L | : T T integer | char,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D L : T T integer | char L L, id | id 改成从右向左归约 D id L L , id L | : T T integer | char,4.3
19、 L属性定义的自上而下计算,D id L addtype (id. entry, L. type) L , id L1 L. type = L1. Type; addtype (id. entry, L1. type) L : T L. type = T. type T integer T. type = integer T real T. type = real,4.4 L属性的自下而上计算,在自下而上分析的框架中实现L属性定义的方法 它能实现任何基于LL(1)文法的L属性定义 也能实现许多（但不是所有的）基于LR(1) 的L属性定义,4.4 L属性的自下而上计算,4.4.1 删除翻译方案中
20、嵌入的动作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val),4.4 L属性的自下而上计算,4.4.1 删除翻译方案中嵌入的动作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端,4.4 L属性的自下而上计算,4.4.1 删除翻译方案中嵌入的动作 E T R R + T print (+)R1 | T print ()R1 | T num p
21、rint (num.val) 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端 E T R R + T M R1 | T N R1 | T num print (num.val) M print (+) N print (),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性 例 int p, q, r D T L.in = T.type L T int T. type = integer T real T. type = real L L1.in = L.in L1, id addtype (id.entry, L.in ) L
22、 id addtype (id.entry, L.in ),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性 属性位置能预测 例 int p, q, r D T L.in = T.type L T int T. type = integer T real T. type = real L L1.in = L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,属性的位置不能预测 S aAC C.i = A.s S bABC C.i = A.s
23、 C c C.s = g(C.i),4.4 L属性的自下而上计算,属性的位置不能预测 S aAC C.i = A.s S bABC C.i = A.s C c C.s = g(C.i) 增加标记非终结符 S aAC C.i = A.s S bABMC M.i = A.s; C.i = M.s C c C.s = g(C.i) M M.s = M.i,4.4 L属性的自下而上计算,4.4.3 模拟继承属性的计算 继承属性是某个综合属性的一个函数 S aAC C.i = f (A.s) C c C.s = g(C.i),4.4 L属性的自下而上计算,4.4.3 模拟继承属性的计算 继承属性是某个综
24、合属性的一个函数 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 N.s = f (N.i) C c C.s = g(C.i),4.4 L属性的自下而上计算,例 数学排版语言EQN 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
25、B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps ,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,举例说明,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,本 章 要 点,语义规则的两种描述方法：语法制导的定义和翻译方案 设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点 S属性的自下而上计算（边分析边计算） L属性的自上而下
26、计算（边分析边计算） L属性的自下而上计算（边分析边计算） 不再介绍先分析后计算的方法 不能边分析边计算的情况是存在的，见5.6节,例 题 1,下面是产生字母表 = 0, 1, 2上数字串的一个 文法： S D S D | 2 D 0 | 1 写一个语法制导定义，判断它接受的句子是否为回文 数 S S print(S.val) S D1 S1 D2 S.val = (D1.val = D2.val) and S1.val S 2 S.val = true D 0 D.val = 0 D 1 D.val = 1,例 题 2,为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产
27、生的二进制数的值。例如，输入 101.101时，S. val = 5.625。不得修改文法，但属性使用 没有限制 S L . R | L L L B | B R B R | B B 0 | 1,例 题 2,S L . R S. val = L. val + R. val S L S. val = L. val L L1 B L. val = L1. val 2 + B. val L B L. val = B. val R B R1 R. val = R1. val / 2 + B. val / 2 R B R. val = B. val / 2 B 0 B. val = 0 B 1 B. va
28、l = 1,例 题 3,给出把中缀表达式翻译成没有冗余括号的中缀表 达式的语法制导定义。例如,因为和是左结合, (a (b + c ) (d )可以重写成a (b + c ) d 先把表达式的括号都去掉，然后在必要的地方再加括号 去掉表达式中的冗余括号，保留必要的括号,例 题 3,第一种方法 S E print ( E. code ) E E1 + T if T. op = plus then E.code =E1.code|“+”|“(”|T.code|“)” else E. code = E1. code | “+” | T. code; E. op = plus E T E. code
29、= T. code; E. op = T. op,例 题 3,T T1 F if (F. op = plus) or (F. op = times) then if T1. op = plus then T. code = “(” | T1. code | “)” | “” | “(” | F. code | “)” else T. code = T1. code | “” | “(” | F. code | “)” else if T1. op = plus then T. code = “(” | T1. code | “)” | “” | F. code else T. code = T
30、1. code | “” | F. code; T. op = times,例 题 3,T F T. code = F. code; T. op = F. op F id F. code = id. lexeme; F. op = id F ( E ) F. code = E. code; F. op = E. op,例 题 3,第二种方法 给E，T和F两个继承属性left_op和right_op 分别表示左右两侧算符的优先级 给它们一个综合属性self_op表示自身主算符的优先级 再给一个综合属性code表示没有冗余括号的代码 分别用1和2表示加和乘的优先级，用3表示id和(E)的优先级，用
31、0表示左侧或右侧没有运算对象的情况,例 题 3,S E E. left_op = 0; E. right_op = 0; print ( E. code ) E E1 + T E1. left_op = E. left_op; E1. right_op = 1; T. left_op = 1; T. right_op = E. right_op; E.code =E1.code| “+” | T. code ; E. self_op = 1; E T T. left_op = E. left_op; T. right_op = E. right_op; E. code = T. code; E
32、. self_op = T. self_op,例 题 3,T T1 F . . . T F . . . F id F. code = id. lexeme; F. self_op = 3,例 题 3,F ( E ) E. left_op = 0; E. right_op = 0; F. self_op = if (F. left_op = F. right_op) then E. self_op else 3 F. code = if (F. left_op = F. right_op) then E. code else “(” | E. code | “)”,习 题,第一次 4.1，4.3，4.5 第二次 4.7，4.9, 4.10 第三次 4.13，4.14,