语法制导翻译5.1-5.4

1、语法制导翻译语法制导翻译5.1-5.45.1-5.4第五章：语法制导翻译v语法制导翻译主题：使用上下文无关文法来引导对语言的翻译用途v类型检查和中间代码生成（第六章）v完成特殊任务的语言,如排版（第五章）2第五章：语法制导翻译v语法制导翻译属性文法v通过把属性附加到代表语法结构的文法符号上，将语义信息和程序设计语言的语法结构联系起来，属性的值是用与文法产生式相联系的语义规则来计算的v语法制导定义SDD：文法产生式和语义规则分开说明关于语言翻译的高层次规格，隐藏了许多具体实现细节，使用户不必显式地说明发生的顺序易读、适合作为对翻译的规约（描述）v语法制导翻译方案SDT：文法产生式和语义规则交错把

2、语义规则用括起来，插入到规则右部的合适位置上，指明了语义规则的计算顺序，以便说明某些实现细节高效、适合用于翻译的实现3第五章：语法制导翻译v语法制导翻译翻译过程：输入字符串=语法分析树=依赖图=语义规则计算顺序v对输入符号(记号/终结符)串进行语法分析，构建语法分析树v根据需要遍历语法分析树，得到描述节点属性间依赖关系的依赖图当实现一遍编译程序时，可在分析期间计算语义规则而不明显地构造语法分析树和依赖图v由依赖图得到语义规则的计算顺序计算语义规则：生成代码、在符号表中保存信息、发出错误信息或完成其他活动v按上述计算顺序在语义分析树节点处进行语义规则计算，得到翻译结果4第五章：语法制导翻译v语法

3、制导翻译本章重点本章重点vL属性翻译方案（L代表从左到右）：包含了所有不必显式构造语法分析树即可完成的翻译方案，即可以在语法分析过程中完成的翻译方案vS属性翻译方案（S代表综合）：可以很容易和自底向上语法分析（如LR语法分析）过程联系起来的L属性翻译方案55.1 语法制导定义SDD（5.1）v语法制导定义SDD：CFG+属性+规则属性：和文法符号相关联v每个文法符号都有一个相关的属性集，属性可以代表任何对象：字符串、数字、类型、内存单元或其他对象。v与这些属性相关的信息，即属性值可以在语法分析过程中计算和传递。属性加工的过程即语义的处理过程。规则：和产生式相关联65.1 语法制导定义SDDv属

4、性：综合属性vs继承属性综合属性v语法分析树结点N上的非终结符A的综合属性是由N上的产生式所关联的语义规则定义的这个产生式的头一定是非终结符A；结点结点N N上的综合属性只能通过上的综合属性只能通过其子节点或其本身的属性值来定义其子节点或其本身的属性值来定义继承属性v语法分析树结点N上的非终结符B的继承属性是由N的父结点上的产生式所关联的语义规则定义的这个产生式的体中一定包含非终结符B；结点结点N N上的继承属性只能上的继承属性只能通过其父节点、其本身及其兄弟结点上的属性值来定义通过其父节点、其本身及其兄弟结点上的属性值来定义75.1 语法制导定义SDDv属性：综合属性vs继承属性几点说明v终

5、结符号只有综合属性，它们由词法分析器提供，在语法制导定义中没有计算终结符的属性值的语义规则v非终结符既可有综合属性也可有继承属性；不允许结点N上的继承属性通过N的子结点上的属性值定义允许N的综合属性通过结点N的继承属性来定义v总可以用综合属性来改写语法制导定义，但使用带有继承属性的语法制导定义更为自然。举例：使用继承属性跟踪一个标识符，看它是出现在赋值号的左边还是右边来确定它的地址还是它的值上下文有关v文法开始符号的所有继承属性作为属性计算前的初始值85.1 语法制导定义SDDvS属性SDD：一个只包含综合属性的SDD每个规则都根据相应产生式的产生式体中的属性值来计算产生式头部非终结符的一个属

6、性可以和LR语法分析器一起自然地实现例5.1：图5-一个简单台式计算器的语法制导定义（参考图.）95.1 语法制导定义SDDvL属性SDD一个产生式体所关联的各个属性之间依赖图的边总是从左到右，而不能从右到左 。即每个属性v或者是综合属性v或者是继承属性，但是它的规则存在如下限制。假设存在一个产生式A-X1X2Xn,并且有一个通过这个产生式所关联的规则计算得到的继承属性Xi.a，那么这个规则只能使用：1）和产生式头A关联的继承属性；2）位于Xi左边的文法符号X1、X2、Xi-1相关的继承属性或者综合属性；3）和这个Xi的实例本身相关的继承属性或者综合属性，但是在由这个Xi全部属性组成的依赖图中

7、不存在环。105.2 S属性定义的自下而上计算属性定义的自下而上计算5.2.3 S属性的自下而上计算属性的自下而上计算LR分析器的栈分析器的栈增加增加一个域来保存综合属性值一个域来保存综合属性值若产生式若产生式A XYZ的语义规则是的语义规则是A.a = f (X.x, Y.y, Z.z)，那么归约后：那么归约后：. . . . . .AA.a. . . . . .top. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操

8、作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 语语 义义 规规 则则 L E n 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.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操

9、作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n 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.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码

10、. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) 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.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作

11、代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top 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.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法

12、制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T 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.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改

13、成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制

14、导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) F.val = E.val F digit F.val = digit.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码

15、. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit F.val = digit.lexval5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码. .

16、 . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit 5.3 L属性定义的自上而下计算属性定义的自上而下计算边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结属性的计算次序

17、一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制分析树的结点是自左向右生成分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算析的同时完成属性计算5.3 L属性定义的自上而下计算属性定义的自上而下计算5.3.1 L属性定义属性定义v如果每个产生式如果每个产生式AX1Xj-1XjXn的每条语的每条语义规则计算的属性是义规则计算的属性是A的综合属性；或者是的综合属性；或者是Xj 的继承属性，但它仅依赖：的继承属性，但它仅依赖：该产生式中该产生式中Xj左边符号左边符号X1, X2, , Xj-1的属性；的

18、属性；A的继承属性的继承属性vS属性定义属于属性定义属于L属性定义属性定义5.3 L属性定义的自上而下计算属性定义的自上而下计算变量类型声明的语法制导定义是一个变量类型声明的语法制导定义是一个L属性定义属性定义 产产 生生 式式 语语 义义 规规 则则 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in; addType(id.entry, L.in) L id addType(id.entry, L.in) 5.3 L属性定义的自上而下计算属性定义的自上而下计算5.3.2

19、 翻译方案翻译方案例例 把有加和减的中缀表达式翻译成后缀表达式把有加和减的中缀表达式翻译成后缀表达式如果输入是如果输入是8+5 2，则输出是，则输出是8 5 + 2 E T RR addop T print (addop.lexeme) R1 | T num print (num.val)E T R num print (8) R numprint (8)addop Tprint (+)R numprint(8)addop numprint(5)print (+)R print(8)print(5)print(+)addop Tprint( )R print(8)print(5)print(+

20、)print(2)print( )5.3 L属性定义的自上而下计算属性定义的自上而下计算v例例 数学排版语言数学排版语言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text E1.val5.3 L属性定义的自上而下计算属性定义的自上而下计算v例例 数学排版语言数学排版语言EQN（语法制导定义）（语法制导定义） E sub 1 .val 产产 生生 式式 语语 义义 规规 则则 S B B.ps = 10; S.ht = B.ht B B1 B2 B1.ps = B.ps; B2.ps = B.ps; B.ht = max(B1.ht, B2.ht )

21、B B1 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 E1.val5.3 L属性定义的自上而下计算属性定义的自上而下计算v例例 数学排版语言数学排版语言EQN（翻译方案）（翻译方案） S B.ps = 10 B继承属性的计算继承属性的计算BS.ht = B.ht 位于位于B的左边的左边5.3 L属性定义的自上而下计算属性定义的自上而下计算v例例 数学排版语言数学排版语言EQN（翻译方案）（翻译方案） S B.ps = 10 B综合属性的计算综合属性

22、的计算BS.ht = B.ht 放在右部末端放在右部末端5.3 L属性定义的自上而下计算属性定义的自上而下计算v例例 数学排版语言数学排版语言EQN（翻译方案）（翻译方案） S B.ps = 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B textB.ht = text.h B.ps 5.3 L属性定义的自上而下计算属性定义的自上而下计算v例例 左递归

23、的消除引起继承属性左递归的消除引起继承属性产产 生生 式式语语 义义 规规 则则 E E1 + T E.nptr = mkNode( +, E1.nptr, T.nptr) E T E.nptr = T.nptr T T1 F T.nptr = mkNode( , T1.nptr, F.nptr) T F T.nptr = F.nptr F (E) F.nptr = E.nptr F id F.nptr = mkLeaf (id, id.entry) F num F.nptr = mkLeaf (num, num.val) 5.3 L属性定义的自上而下计算属性定义的自上而下计算E T R.i

24、= T.nptr T + T + T + RE.nptr = R.sR +TR1.i = mkNode ( +, R.i, T.nptr)R1R.s = R1.sR R.s = R.i T F W.i = F.nptrWT.nptr = W.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i F 产生式部分不再给出产生式部分不再给出5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入

25、口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定

26、义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W

27、F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分练习-S属性/语法制导定义4.1v简单台式计算器的语法制导定义如下：L-En print(E.val)E-E1+T E.val=E1.val+T.valE-T E.val=T.valT-T1*F T.val=T1.val*F.valT-F F.val=E.valF-(E) F.val=E.valF-digit F.val=digit.lexvalv为输入表达式(4*7+1)*2构造注释