[工学]第4章 语法制导的翻译.ppt

1、主讲人：范 敏,陈意云 张 昱 高等教育出版社,编 译 原 理 -4,2021/3/29,第4章 语法制导的翻译,2,引入,复习 词法分析的任务和正规式的作用 语法分析的任务和文法的作用 思考 语言结构的属性如何计算？何时计算？属性值如何存放？,2021/3/29,第4章 语法制导的翻译,3,第1章 编译器概述 第2章 词法分析 第3章 语法分析 第4章 语法制导的翻译 第5章 类型检查 第6章 运行时存储空间的组织和管理 第7章 中间代码生成 第8章 代码生成 第9章* 代码优化 第10章* 编译系统和运行系统 第11章* 面向对象语言的编译 第12章* 函数式语言的编译,目 录,2021/

2、3/29,第4章 语法制导的翻译,4,4.1 语法制导的定义 4.2 S属性定义的自下而上计算 4.3 L属性定义的自上而下计算 4.4 L属性的自下而上计算 4.5 递归计算,第4章 语法制导的翻译,2021/3/29,第4章 语法制导的翻译,5,本章内容,介绍一种形式化的语义描述方法 语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案 介绍语法制导的翻译的实现方法,2021/3/29,第4章 语法制导的翻译,6,本章学习目标,掌握综合属性、继承属性、语法树、翻译方案等概念 掌握语法制导的定义方法 掌握S属性和L属性的计算方法,2021/3/29,第4章 语法制导的翻译,7,4.

3、1 语法制导的定义,例：简单台式计算器的语法制导定义,注意基础文法与拓广文法的区别,2021/3/29,第4章 语法制导的翻译,8,基础文法 基础文法是语法制导定义中的文法。其中，每个文法符号都有一组可以用于计算的属性 每个产生式A 有一组形式为b := f(c1, c2, , ck )的语义规则。其中f 是函数，b, c1 , c2 , , ck 是文法符号的属性 语义规则 一组计算表达式 计算相应产生式中文法符号的属性值,4.1.1 语法制导定义的形式,2021/3/29,第4章 语法制导的翻译,9,文法符号属性分类 继承属性：如果b是产生式右部某个文法符号X的属性，c1 , c2 , ,

4、 ck 是产生式左部文法符号A的属性或产生式右部文法符号属性 综合属性：如果b是A的属性，c1 , c2 , , ck 是产生式右部文法符号属性或A的继承属性,b,b := f(c1, c2, , ck ),A X ,B属于子结点,B属于父结点,2021/3/29,第4章 语法制导的翻译,10,S属性定义：仅使用综合属性的语法制导定义,4.1.2 综合属性,如何计算综合属性值？,2021/3/29,第4章 语法制导的翻译,11,8+5*2 n的计算：1. 根据基础文法画出推导出句子的分析树,2021/3/29,第4章 语法制导的翻译,12,8+5*2 n的计算：2. 标出分析树中每个结点的属性

5、（如果有）,注意注释分析树与分析树之间的区别,2021/3/29,第4章 语法制导的翻译,13,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,14,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,15,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,16,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制

6、导的翻译,17,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,18,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,19,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,20,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,21,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、

7、从左到右地完成,2021/3/29,第4章 语法制导的翻译,22,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,23,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,24,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,2021/3/29,第4章 语法制导的翻译,25,8+5*2 n的计算：3. 分析树各结点属性的计算可以自下而上、从左到右地完成,打印E属性值 Print(E.val),2021/3/29,第4

8、章 语法制导的翻译,26,利用分析树对S属性定义中综合属性的计算方法小结 画出句子（词法记号流符号串）的分析树 标出每个结点的属性（如果有） 根据语义规则自下而上、从左到右完成各个结点属性的计算,2021/3/29,第4章 语法制导的翻译,27,int id, id, id,4.1.3 继承属性,如何计算继承属性值？,2021/3/29,第4章 语法制导的翻译,28,int id1, id2, id3的注释分析树 分析树,2021/3/29,第4章 语法制导的翻译,29,int id1, id2, id3的注释分析树 在注释分析树每个L结点，除传递继承属性in给子结点L1外，addtype过程

9、在符号表中将L右子结点上标识符id的类型记为整型：addtype (id.entry, L.in ),L1.in := L.in,2021/3/29,第4章 语法制导的翻译,30,int id1, id2, id3的分析树的依赖图 描述结点属性间依赖关系的有向图称为依赖图 D TL L.in := T.type ,4.1.4 属性依赖图,所有属性可用结点表示,2021/3/29,第4章 语法制导的翻译,31,int id1, id2, id3的分析树的依赖图 L L1, id L1.in := L.in; addtype (id.entry, L.in ),注意：L有两个属性(继承属性in和虚

10、拟属性),2021/3/29,第4章 语法制导的翻译,32,拓扑排序：属性结点出现顺序的一种排序，使得有向边只从该次序中先出现的结点指向后出现的结点 例：1，2，3，4，5，6，7，8，9，10,4.1.5 属性计算次序,只有结点属性传递的方向性不够,2021/3/29,第4章 语法制导的翻译,33,属性计算过程 （1）构造输入串的分析树,2021/3/29,第4章 语法制导的翻译,34,属性计算过程 （1）构造输入串的分析树；（2）构造属性依赖图,2021/3/29,第4章 语法制导的翻译,35,属性计算过程 （1）构造输入串的分析树；（2）构造属性依赖图；（3）对属性结点进行拓扑排序,20

11、21/3/29,第4章 语法制导的翻译,36,属性计算过程 （1）构造输入串的分析树；（2）构造属性依赖图；（3）对属性结点进行拓扑排序；（4）按拓扑排序的次序计算属性,2021/3/29,第4章 语法制导的翻译,37,属性计算过程 a4:=integer; a5:=a4; addtype(id3.entry,a5); a7:=a5; addtype(id2.entry,a7); a9:=a7; addtype(id1.entry,a9);,2021/3/29,第4章 语法制导的翻译,38,语义规则的计算方法,2021/3/29,第4章 语法制导的翻译,39,语义规则的计算方法 分析树方法：前

12、面介绍方法（编译速度慢）,2021/3/29,第4章 语法制导的翻译,40,语义规则的计算方法 分析树方法：前面介绍方法（编译速度慢） 基于规则的方法：基于事先静态确定语义规则的计算次序（手工构造编译器，时空改善）,2021/3/29,第4章 语法制导的翻译,41,语义规则的计算方法 分析树方法：前面介绍方法（编译速度慢） 基于规则的方法：基于事先静态确定语义规则的计算次序（手工构造编译器，时空改善） 忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制（时空改善）,2021/3/29,第4章 语法制导的翻译,42,本节小结,介绍了语法制导定义

13、、继承属性、综合属性、属性依赖图、拓扑顺序等概念 详细介绍了利用分析树计算属性的方法 简单对比了属性计算的三种方法,2021/3/29,第4章 语法制导的翻译,43,作业,P140：1,2021/3/29,第4章 语法制导的翻译,44,思考,语言结构属性计算的基础是什么？ 依赖图和拓扑顺序有什么作用？它们对计算S属性定义中的综合属性是否有用？ 计算语言结构属性的步骤是什么？ 本节在语法制导定义的基础上通过分析树研究了属性计算次序的问题，那么如何在此基础上编程实现呢？,2021/3/29,第4章 语法制导的翻译,45,4.2 S属性定义的自下而上计算,语法树是分析树的浓缩表示：算符和关键字作为内

14、部结点 语法树的例子：,if-then-else,B,S1,S2,4.2.1 语法树,算符,运算 对象,if B then S1 else S2,复习 S属性定义？,2021/3/29,第4章 语法制导的翻译,46,4.2 S属性定义的自下而上计算,语法树是分析树的浓缩表示：算符和关键字作为内部结点 语法树的例子：,if-then-else,B,S1,S2,4.2.1 语法树,算符,运算 对象,if B then S1 else S2,8 + 5 * 2,算符优先级别？,2021/3/29,第4章 语法制导的翻译,47,4.2 S属性定义的自下而上计算,语法树是分析树的浓缩表示：算符和关键字作

15、为内部结点 语法树的例子：,if-then-else,B,S1,S2,+,*,8,4.2.1 语法树,算符,运算 对象,if B then S1 else S2,8 + 5 * 2,2021/3/29,第4章 语法制导的翻译,48,4.2 S属性定义的自下而上计算,语法树是分析树的浓缩表示：算符和关键字作为内部结点 语法树的例子：,4.2.1 语法树,算符,运算 对象,if B then S1 else S2,8 + 5 * 2,2021/3/29,第4章 语法制导的翻译,49,4.2 S属性定义的自下而上计算,语法树是分析树的浓缩表示：算符和关键字是作为内部结点 语法制导翻译可以基于分析树，

16、也可以基于语法树,4.2.1 语法树,算符,运算 对象,if B then S1 else S2,8 + 5 * 2,2021/3/29,第4章 语法制导的翻译,50,4.2.2 构造语法树的语法制导定义,语法树的存储 语法树的结点可以用有若干域的记录来实现 对于算符结点：一个域存放算符，该域作为该结点的标记，其余两个域含指向运算对象的指针 三地址 对于基本运算对象结点：一个域存放运算对象类别，另一个域存放其值 二地址 用于语法制导翻译时，一个结点可能还有其它域来保存加在该结点的其它属性值（即域中保存属性值存储位置的指针）,结点的类型,2021/3/29,第4章 语法制导的翻译,51,用于构造

17、算术表达式语法树的语法制导定义,mkleaf(id,entry)：建立标识符id的结点，结点的entry域用于存放该标识符条目的指针,2021/3/29,第4章 语法制导的翻译,52,用于构造算术表达式语法树的语法制导定义,mkleaf(num,val)：建立数num的结点，结点的val域用于存放该数值,2021/3/29,第4章 语法制导的翻译,53,用于构造算术表达式语法树的语法制导定义,mknode(op,left,right)：建立算符op的结点，指针域left和right分别存放该算符左、右运算对象的指针,2021/3/29,第4章 语法制导的翻译,54,a+5*b的语法树的构造,2

18、021/3/29,第4章 语法制导的翻译,55,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,56,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,57,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,58,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,59,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,60,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,61,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,62,a+5*b的语法树的

19、构造,2021/3/29,第4章 语法制导的翻译,63,a+5*b的语法树的构造,2021/3/29,第4章 语法制导的翻译,64,S属性可以由自下而上分析器在语法分析输入时完成计算，即“边分析边计算” 自下而上分析器用栈保存已经分析的子树的信息，S属性定义的翻译器可以借助LR分析器的生成器来实现 LR分析器可以把文法符号的综合属性放在它的栈内，每当归约时，根据出现在栈顶的产生式右部符号串中符号的属性来计算左部符号的综合属性,4.2.3 S属性的自下而上计算,复习LR分析器的工作原理：栈内可以不存储文法符号,综合属性来自于子节点或自身的继承属性,2021/3/29,第4章 语法制导的翻译,65

20、,将LR分析器增加一个域来保存综合属性值,栈 state val,top,2021/3/29,第4章 语法制导的翻译,66,将LR分析器增加一个域来保存综合属性值,栈 state val,top,若产生式A XYZ的语义规则是 A.a := f (X.x, Y.y, Z.z),右部符号从左至右压入栈内,2021/3/29,第4章 语法制导的翻译,67,将LR分析器增加一个域来保存综合属性值,若产生式A XYZ的语义规则是 A.a := f (X.x, Y.y, Z.z)， 那么归约后：,2021/3/29,第4章 语法制导的翻译,68,例：台式计算器的语法制导定义改成栈操作代码,栈 state

21、 val,top,2021/3/29,第4章 语法制导的翻译,69,例：台式计算器的语法制导定义改成栈操作代码,栈 state val,top,2021/3/29,第4章 语法制导的翻译,70,例：台式计算器的语法制导定义改成栈操作代码,2021/3/29,第4章 语法制导的翻译,71,例：台式计算器的语法制导定义改成栈操作代码,2021/3/29,第4章 语法制导的翻译,72,例：台式计算器的语法制导定义改成栈操作代码,2021/3/29,第4章 语法制导的翻译,73,例：台式计算器的语法制导定义改成栈操作代码,2021/3/29,第4章 语法制导的翻译,74,例：台式计算器的语法制导定义改

22、成栈操作代码,2021/3/29,第4章 语法制导的翻译,75,例：台式计算器的语法制导定义改成栈操作代码,2021/3/29,第4章 语法制导的翻译,76,例：台式计算器的语法制导定义改成栈操作代码,2021/3/29,第4章 语法制导的翻译,77,4.3 L 属性定义的自上而下计算,边分析边翻译的方式能否用于继承属性？ 属性的计算次序受分析方法所限定的分析树结点建立次序的限制,2021/3/29,第4章 语法制导的翻译,78,4.3 L属性定义的自上而下计算,边语法分析边翻译的方式能否用于继承属性？ 属性的计算次序受分析方法所限定的分析树结点建立次序的限制 语法分析方法的共同特点：分析树的

23、结点是自左向右生成 如果属性信息自左向右流动，那么就有可能在分析的同时完成 L 属性计算 L代表属性从左向右传递的方向,2021/3/29,第4章 语法制导的翻译,79,（1）如果每个产生式A X1 X2 Xj Xn 的每条语义规则计算的属性是A的综合属性；或者（2）如果是Xj 的继承属性，1 j n,但它仅依赖于： 该产生式中Xj左边（兄弟结点）符号X1, X2, , Xj-1的属性 A的继承属性 那么语法制导定义是L属性定义,4.3.1 L属性定义,2021/3/29,第4章 语法制导的翻译,80,（1）如果每个产生式A X1 X2 Xj Xn 的每条语义规则计算的属性是A的综合属性；或者

24、（2）如果是Xj 的继承属性，1 j n,但它仅依赖于： 该产生式中Xj左边（兄弟结点）符号X1, X2, , Xj-1的属性 A的继承属性 那么语法制导定义是L属性定义 S属性定义是L属性定义的一个特例,2021/3/29,第4章 语法制导的翻译,81,例：变量类型声明的语法制导定义是一个L属性定义,2021/3/29,第4章 语法制导的翻译,82,计算属性需要考虑执行语义规则的时机 翻译方案将语义动作放在 内，并将它当作文法符号插入产生式右部任何位置 语义动作插入的位置就是产生式的项目中的点的位置 执行时机：当语法分析到该文法符号（语义动作）而进行推导或归约时，执行该语义动作,4.3.2

25、翻译方案,什么是项目？,2021/3/29,第4章 语法制导的翻译,83,只有综合属性的翻译方案的建立 首先为每条语义规则建立一个放在一对 括号内赋值动作，然后把这些动作分别放在对应产生式右部的末端,2021/3/29,第4章 语法制导的翻译,84,例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输出是8 5 + 2 E T R R addop T print (addop.lexeme) R1 | T num print (num.val),2021/3/29,第4章 语法制导的翻译,85,例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输出是8 5

26、+ 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)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(),2021/3/29,第4章 语法制导的翻译,86,例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输

27、出是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)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(),2021/3/29,第4章 语法制导的翻译,87,例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+

28、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)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(),2021/3/29,第4章 语法制导的翻译,88,例:把有加和减的中缀表达式翻译成后缀表达式 如

29、果输入是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)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(),关注动作,2021/3/29,第4章 语法制导的翻译,89,例:把有加和减的中缀表达

30、式翻译成后缀表达式 如果输入是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)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(),关注动作,2021/3/29,第4章 语法制导的翻译,90,例

31、:把有加和减的中缀表达式翻译成后缀表达式 如果输入是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)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(),关注动作,2021/3/29,第4章 语

32、法制导的翻译,91,有继承属性的翻译方案的建立 建立含有继承属性翻译方案的规则： （1）产生式右部符号的继承属性必须在先于该符号的动作中计算 （2）一个动作不能引用该动作右边符号的综合属性 （3）左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算，且计算该属性的动作通常放在产生式右部末端,2021/3/29,第4章 语法制导的翻译,92,例：数学排版语言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text,2021/3/29,第4章 语法制导的翻译,93,例：数学排版语言EQN （B.ps为继承属性） E sub 1 .val,2021/

33、3/29,第4章 语法制导的翻译,94,例：数学排版语言EQN （B.ps为继承属性） 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 B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B textB.ht := text.h * B.ps ,规 则 一,规则三,2021/3/29,第4章 语法制导的翻译,95,例：左递归的消除可能引起继承属性(可能原 来只有综合属性）

34、-算术表达式语法制导定义,2021/3/29,第4章 语法制导的翻译,96,算术表达式文法 E E + T | T T T * F | F F ( E ) | id 消除左递归后文法： E TR R + TR1 | T FW W * F W1 | F ( E ) | id,AAa |b 消除直接左递归： A b A A a A | ,其中：R和W为引入的辅助文法符号,2021/3/29,第4章 语法制导的翻译,97,E T R.i := T.nptr RE.nptr := R.s R + TR1.i := mknode ( +, R.i, T.nptr) R1R.s := R1.s R R.s

35、 := R.i T F W.i := F.nptr WT.nptr := W.s W * FW1.i := mknode ( *, W.i, F.nptr) W1W.s := W1.s W W.s := W.i F (E) F. nptr := E.nptr F idF. nptr := mkleaf(id, id.entry) F num F. nptr := mkleaf(num, num.entry),R和W的i属性是继承属性,2021/3/29,第4章 语法制导的翻译,98,E T R.i := T.nptr RE.nptr := R.s R + TR1.i := mknode ( +

36、, R.i, T.nptr) R1R.s := R1.s R R.s := R.i T F W.i := F.nptr WT.nptr := W.s W * FW1.i := mknode ( *, W.i, F.nptr) W1W.s := W1.s W W.s := W.i F (E) F. nptr := E.nptr F idF. nptr := mkleaf(id, id.entry) F num F. nptr := mkleaf(num, num.entry),2021/3/29,第4章 语法制导的翻译,99,用算术表达式语法制导定义构造a*5*b语法树,1,2,3,4,5,6,

37、7,8,9,10,11,12,13,14,15,16,略去了E TR T 部分,递归： 自上而下 从左到右,推导而非归约,2021/3/29,第4章 语法制导的翻译,100,把预测分析器的构造方法推广到翻译方案的 实现（每个非终结符都对应一个过程或函数） 参见p126算法4.1）：适用于自上而下分析 例：产生式R +TR | 的分析过程： procedure R; begin if lookahead = + then begin match ( + ); T; R end else begin /* 什么也不做 */ end end,4.3.3 预测分析器的设计,预测分析器的特点？,2021

38、/3/29,第4章 语法制导的翻译,101,产生式R +TR | 的语法树的递归下降构造： function R (i :syntax_tree_node ) :syntax_tree_node; var nptr , i1, s1, s : syntax_tree_node; addoplexeme : char; begin if lookahead = + then begin /* 匹配产生式 R +T R */ addoplexeme := lexval; /* 载入运算符*/ match( + ); nptr := T; i1 := mknode(addoplexme, i , n

39、ptr) ; s1 := R (i1); s : = s1 end else s := i; /* 产生式 R */ return s end;,R : i, s T : nptr + : addoplexeme,2021/3/29,第4章 语法制导的翻译,102,改变文法可能导致继承属性或综合属性 例如：消除左递归可能产生继承属性 Pascal的声明，如m, n : integer D L : T T integer | char L L, id | id,4.3.4 用综合属性代替继承属性,2021/3/29,第4章 语法制导的翻译,103,Pascal的声明，如m, n : intege

40、r D L : T T integer | char L L, id | id 改成从右向左归约 D id L L , id L | : T T integer | char,2021/3/29,第4章 语法制导的翻译,104,Pascal的声明，如m, n : integer D L : T T integer | char L L, id | id 改成从右向左归约 D id L L , id L | : T T integer | char,2021/3/29,第4章 语法制导的翻译,105,D id L addtype (id. entry, L. type) L , id L1 L.

41、 type := L1. Type; addtype (id. entry, L1. type) L : T L. type := T. type T integer T. type := integer T real T. type := real,修改后文法从右向左归约，信息流向和归约方向的一致性使属性可以实现“边分析边计算”,2021/3/29,第4章 语法制导的翻译,106,在自下而上分析的框架中实现L属性定义的方法 它能实现任何基于LL(1)文法的L属性定义 也能实现许多（但不是所有的）基于LR(1) 的L属性定义,4.4 L属性的自下而上计算,2021/3/29,第4章 语法制导的

42、翻译,107,自下而上翻译方案中，S属性定义的语义动作位于产生式最右端；L属性定义嵌在产生式右部不同位置的动作可以通过修改文法而把这些动作也放在产生式最右端 修改方法 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表 把该动作放在产生式M 的最右端,4.4.1 删除翻译方案中嵌入的动作,2021/3/29,第4章 语法制导的翻译,108,例： E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) E T R R + T M R1 | T N R1 | T num print (num.val) M p

43、rint (+) N print (),2021/3/29,第4章 语法制导的翻译,109,属性位置能准确预测 （栈中） 例：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.2 分析栈上的继承属性,2021/3/29,第4章 语法制导的翻译,110,属性位置能准确预测 （栈中） 例：int p, q, r D T L

44、.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 ),移进-归约特点 每次归约L产生式右部时，T刚好在该右部下面，因此T.type在栈中位置可以静态确定(位置能预测),DTL,2021/3/29,第4章 语法制导的翻译,111,移进-归约特点 每次归约L产生式右部时，T刚好在该右部下面，因此T.type在栈中位置可以静态确定(位置能预测),2021/3/29,第4

45、章 语法制导的翻译,112,移进-归约特点 每次归约L产生式右部时，T刚好在该右部下面，因此T.type在栈中位置可以静态确定(位置能预测),2021/3/29,第4章 语法制导的翻译,113,属性的位置不能预测（栈中） S aACC.i := A.s S bABCC.i := A.s C cC.s := g(C.i),分析栈中，B使C.i继承属性值无法肯定从栈中哪个位置获取,2021/3/29,第4章 语法制导的翻译,114,属性的位置不能预测（栈中） S aACC.i := A.s S bABCC.i := A.s C cC.s := g(C.i) 解决办法：增加标记非终结符 S aACC

46、.i := A.s S bABMCM.i := A.s; C.i := M.s M M.s := M.i C cC.s := g(C.i),M使C.i值从栈中valtop-1处获取，并使M 归约时M.i值从valtop-2处获得（此时M处于栈顶）,2021/3/29,第4章 语法制导的翻译,115,继承属性是某个综合属性的一个函数 S aACC.i := f (A.s) C cC.s := g(C.i),4.4.3 模拟继承属性的计算,2021/3/29,第4章 语法制导的翻译,116,继承属性是某个综合属性的一个函数 S aACC.i := f (A.s) C cC.s := g(C.i)

47、问题：继承属性不能通过属性简单复制计算办法：增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行 S aANCN.i := A.s; C.i := N.s N N.s := f (N.i) C cC.s := g(C.i),2021/3/29,第4章 语法制导的翻译,117,例：数学排版语言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 B1 sub B2.ps := shrink(B.ps) B2B.ht := d

48、isp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,2021/3/29,第4章 语法制导的翻译,118,L,M,N保证了在任何情况下向B归约时，B.ps的值总是正好在右部下面,N模拟继承属性,2021/3/29,第4章 语法制导的翻译,119,2021/3/29,第4章 语法制导的翻译,120,S.ht := B.ht,2021/3/29,第4章 语法制导的翻译,121,B.ps := L.s; L.s := 10,2021/3/29,第4章 语法制导的翻译,122,B.ht := max(B1.ht, B2.ht ),2021/3/29,第4章 语法

49、制导的翻译,123,B2.ps := M.s;M.s := M.i; M.i := B.ps;B1.ps := B.ps,2021/3/29,第4章 语法制导的翻译,124,B.ht := disp (B1.ht, B2.ht ),2021/3/29,第4章 语法制导的翻译,125,B2.ps := N.s; N.s := shrink(N.i); N.i := B.ps;,2021/3/29,第4章 语法制导的翻译,126,向B归约时，B.ps的值正好在右部下面,2021/3/29,第4章 语法制导的翻译,127,算法4.2（p134）： 对基础文法是LL(1)的L属性定义的有继承属性的自下

50、而上翻译 方法：把问题简化为每个非终结符A只有一个继承属性A.i，且每个文法符号X都有一个综合属性X.s。如果X是终结符，则综合属性是词法分析器的记号属性 操作说明：（1）对每个产生式AX1Xn引入n个标记非终结符M1Mn，用A M1 X1 Mn Xn代替。综合属性Xj.s进入分析栈val数组相应于Xj的条目；继承属性Xj.出现在val数组相应于Mj的条目。（2）如果继承属性A.i存在，则它的值位于val数组M1下面且紧帖M1的条目处,2021/3/29,第4章 语法制导的翻译,128,4.5 递 归 计 算,回顾：语法制导定义的实现 分析树方法,2021/3/29,第4章 语法制导的翻译,1

51、29,4.5 递 归 计 算,回顾：语法制导定义的实现 分析树方法 边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）,2021/3/29,第4章 语法制导的翻译,130,4.5 递 归 计 算,回顾：语法制导定义的实现 分析树方法 边分析边进行属性计算，只能完成L属性计算（忽略规则的方法） 本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）,2021/3/29,第4章 语法制导的翻译,131,4.5 递 归 计 算,回顾：语法制导定义的实现 分析树方法 边分析边进行属性计算，只能完成L属性计算（忽略规则的方法） 本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的

52、方法） 为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分,2021/3/29,第4章 语法制导的翻译,132,4.5 递 归 计 算,回顾：语法制导定义的实现 分析树方法 边分析边进行属性计算，只能完成L属性计算（忽略规则的方法） 本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法） 为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分 为非终结符的不同综合属性构造不同的函数,2021/3/29,第4章 语法制导的翻译,133,为B构造一个属性计算函数 S B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps :=

53、 B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,4.5.1 自左向右遍历,2021/3/29,第4章 语法制导的翻译,134,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在结点n的产生式 of B B1 B2: ps1 := ps; ht1 := B(child(n,1), ps1); ps2 := ps;

54、ht2 := B(child(n,2), ps2); return max(ht1, ht2);,B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) ,函数以结点n和它的继承属性ps为参数，返回结点n的综合属性值,非终结符继承属性的计算必须先于对该非终结符的函数调用,2021/3/29,第4章 语法制导的翻译,135,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在结点n的产生式 of B B1 sub B2: ps1 := ps; ht1 := B(child(

55、n,1), ps1); ps2 := shrink(ps); ht2 := B(child(n,3), ps2); return disp(ht1, ht2);,B B1.ps := B.ps B1sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) ,函数以结点n和它的继承属性ps为参数，返回结点n的综合属性值,非终结符继承属性的计算必须先于对该非终结符的函数调用,2021/3/29,第4章 语法制导的翻译,136,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在结点n的

56、产生式 of B text: return ps text.h; default: error end,B textB.ht := text.h B.ps ,函数以结点n和它的继承属性ps为参数，返回结点n的综合属性值,非终结符继承属性的计算必须先于对该非终结符的函数调用,2021/3/29,第4章 语法制导的翻译,137,按所需次序访问结点的子结点，可用于非L属性定义 A LM L.i := l(A.i); M.i := m(L.s); A.s := f (M.s) A QR R.i := r(A.i); Q.i := q(R.s); A.s := f (Q.s),4.5.2 其它遍历方法,

57、2021/3/29,第4章 语法制导的翻译,138,A LM:/* 从左到右的次序 */ li := l(ai); ls := L(child(n,1), li); mi := m(ls); ms := M(child(n,2), mi); return f (ms);,2021/3/29,第4章 语法制导的翻译,139,A QR:/* 从右到左的次序 */ ri := r(ai); rs := R(child(n,2), ri); qi := q(rs); qs := Q(child(n,1), qi); return f (qs);,2021/3/29,第4章 语法制导的翻译,140,S

58、E E.i := g(E.s); S.r := E.t E E1E2 E.s := fs(E1.s, E2.s); E1.i := fi1(E.i); E2.i := fi2(E.i); E.t := ft (E1.t, E2.t) E id E.s := id.s; E.t := h(E.i),2021/3/29,第4章 语法制导的翻译,141,综合属性t不可能和s在同一遍扫描中完成计算,2021/3/29,第4章 语法制导的翻译,142,function Sr(n); begin s := Es(child(n,1); i := g(s); t := Et(child(n,1), i);

59、return t end;,2021/3/29,第4章 语法制导的翻译,143,function Es(n); | function Et(n, i); begin | begin case 在结点n的产生式 of | case 在结点n的产生式 of E E1 E2: |E E1 E2: s1 := Es(child(n,1); | i1:= fi1(i); s2 := Es(child(n,2); | t1 := Et(child(n,1), i1); return fs(s1, s2); | i2:= fi2(i); E id: | t2 := Et(child(n,2), i2); r

60、eturn id.s; | return ft(t1, t2); default: |E id: error | return h(i); end |default: end; | error |end | end;,2021/3/29,第4章 语法制导的翻译,144,本 章 要 点,语义规则的两种描述方法：语法制导的定义和翻译方案 设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点 语义规则的三种计算方法：分析树方法、基于规则的方法和忽略规则的方法。 S属性的自下而上计算（边分析边计算） L属性的自上而下计算（边分析边计算） L属性的自下而上计算（边分析边计算） 递归计算（先分析后计