第四章 语法制导的翻译 本章内容 1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式 语法制导的定义 翻译方案 第四章 语法制导的翻译 本章内容 1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式 语法制导的定义 翻译方案 2、介绍语法制导翻译的实现方法

4.1 语法制导的定义 例 简单计算器的语法制导定义 产 生 式 语 义 规 则 L  E n print (E.val) 4.1 语法制导的定义 例 简单计算器的语法制导定义 产 生 式 语 义 规 则 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.lexval

4.1 语法制导的定义 4.1.1 语法制导定义的形式 基础文法 每个文法符号有一组属性 每个文法产生式A  有 4.1 语法制导的定义 4.1.1 语法制导定义的形式 基础文法 每个文法符号有一组属性 每个文法产生式A  有 一组形式为b=f(c1, c2, …, ck )的语义规则，其中 b和c1, c2, …, ck 是该产生式文法符号的属性， f 是函数 综合属性：如果b是A的属性，c1 , c2 , …, ck 是产生式右部文法符号的属性或A的其它属性 继承属性：如果b是右部某文法符号X的属性

4.1 语法制导的定义 4.1.2 综合属性 S属性定义：仅使用综合属性的语法制导定义 产 生 式 语 义 规 则 L  E n 4.1 语法制导的定义 4.1.2 综合属性 S属性定义：仅使用综合属性的语法制导定义 产 生 式 语 义 规 则 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.lexval

4.1 语法制导的定义 注释分析树:结点的属性值都标注出来的分析树 8+5*2 n的注释分析树 digit.lexval = 2 L 4.1 语法制导的定义 注释分析树:结点的属性值都标注出来的分析树 8+5*2 n的注释分析树 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n 4.1 语法制导的定义 分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n T.val = 10 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 T.val = 5 +  F.val = 5 F.val = 2 digit.lexval = 5

4.1 语法制导的定义 4.1.3 继承属性 int id, id, id 产 生 式 语 义 规 则 D  TL 4.1 语法制导的定义 4.1.3 继承属性 int id, id, id 产 生 式 语 义 规 则 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

4.1 语法制导的定义 例 int id1, id2, id3的标注了部分属性的分析树 不可能像像综合属性那样自下而上标注属性 D 4.1 语法制导的定义 例 int id1, id2, id3的标注了部分属性的分析树 不可能像像综合属性那样自下而上标注属性 D int T.type = integer , id3 L.in = integer id2 id1

4.1 语法制导的定义 4.1.4 属性依赖图 例 int id1, id2, id3的分析树（虚线）的依赖图（实线） D  TL L.in = T.type D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.4 属性依赖图 例 int id1, id2, id3的分析树（虚线）的依赖图（实线） L L1, id L1.in = L.in; addType (id.entry, L.in) D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.4 属性依赖图 例 int id1, id2, id3的分析树（虚线）的依赖图（实线） L id 4.1 语法制导的定义 4.1.4 属性依赖图 例 int id1, id2, id3的分析树（虚线）的依赖图（实线） L id addType (id.entry, L.in) D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.5 属性计算次序 1、拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点 4.1 语法制导的定义 4.1.5 属性计算次序 1、拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点 例 1，2，3，4，5，6，7，8，9，10 D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树 D int T , id3 L id2 id1 4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树 D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树，构造属性依赖图 D int T , id3 L id2 4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树，构造属性依赖图 D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序 D int T , 4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序 D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 4.1.5 属性计算次序 2、属性计算次序：构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性 D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

4.1 语法制导的定义 语义规则的计算方法 分析树方法：刚才介绍的方法，动态确定计算次序，效率低 概念上的一般方法 4.1 语法制导的定义 语义规则的计算方法 分析树方法：刚才介绍的方法，动态确定计算次序，效率低 概念上的一般方法 基于规则的方法：（编译器实现者）静态确定（编译器设计者提供的）语义规则的计算次序 适用于手工构造的方法 忽略规则的方法：（编译器实现者）事先确定属性的计算策略（如边分析边计算）,（编译器设计者提供的）语义规则必须符合所选分析方法的限制 适用于自动生成的方法

4.2 S属性定义的自下而上计算 4.2.1 语法树 语法树是分析树的浓缩表示：算符和关键字是作为内部结点 语法制导翻译可以基于分析树，也可以基于语法树 语法树的例子： if B then S1 else S2 8 + 5  2 if-then-else B S1 S2 + * 2 5 8

4.2 S属性定义的自下而上计算 4.2.2 构造语法树的语法制导定义 产 生 式 语 义 规 则 E  E1 + T 产 生 式 语 义 规 则 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)

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr id +  num num 5 指向符号表中a的入口 指向符号表中b的入口

4.2 S属性定义的自下而上计算 4.2.3 S属性的自下而上计算 LR分析器的栈增加一个域来保存综合属性值 若产生式A →XYZ的语义规则是 A.a = f (X.x, Y.y, Z.z)， 那么归约后： . . . Z Z. z Y Y. y X X.x top . . . A A.a top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 语 义 规 则 L  E n 产 生 式 语 义 规 则 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.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (E.val) 产 生 式 代 码 段 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.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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] T  F T.val = F.val F (E) F.val = E.val F  digit F.val = digit.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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] T  F F (E) F.val = E.val F  digit F.val = digit.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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] T  F F (E) val [top 1] F  digit F.val = digit.lexval . . . Z Z. z Y Y. y X X.x top 栈 state val

4.2 S属性定义的自下而上计算 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n 产 生 式 代 码 段 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] T  F F (E) val [top 1] F  digit . . . Z Z. z Y Y. y X X.x top 栈 state val

4.3 L属性定义的自上而下计算 边分析边翻译的方式能否用于继承属性？ 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制 分析树的结点是自左向右生成 如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算

4.3 L属性定义的自上而下计算 4.3.1 L属性定义 如果每个产生式AX1…Xj-1Xj…Xn的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，但它仅依赖： 该产生式中Xj左边符号X1, X2, …, Xj-1的属性； A的继承属性 S属性定义属于L属性定义

4.3 L属性定义的自上而下计算 变量类型声明的语法制导定义是一个L属性定义 产 生 式 语 义 规 则 D  TL 产 生 式 语 义 规 则 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

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  num{print (8)}addop T{print (+)}R  num{print(8)}addop num{print(5)}{print (+)}R … {print(8)}{print(5)}{print(+)}addop T{print()}R … {print(8)}{print(5)}{print(+)}{print(2)}{print()}

4.3 L属性定义的自上而下计算 例 数学排版语言EQN E sub 1 .val E .val S  B B  B1 B2 B  B1 sub B2 B  text E 1 .val

4.3 L属性定义的自上而下计算 例 数学排版语言EQN（语法制导定义） E sub 1 .val E .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 ) 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

4.3 L属性定义的自上而下计算 例 数学排版语言EQN（翻译方案） S  {B.ps = 10 } B继承属性的计算 B {S.ht = B.ht } 位于B的左边

4.3 L属性定义的自上而下计算 例 数学排版语言EQN（翻译方案） S  {B.ps = 10 } B综合属性的计算 B {S.ht = B.ht } 放在右部末端

4.3 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 {B.ht = disp (B1.ht, B2.ht ) }  B  text {B.ht = text.h  B.ps } 58

4.3 L属性定义的自上而下计算 例 左递归的消除引起继承属性 产 生 式 语 义 规 则 E  E1 + T 例 左递归的消除引起继承属性 产 生 式 语 义 规 则 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)

4.3 L属性定义的自上而下计算 E  T {R.i = T.nptr} T + T + T + … R {E.nptr = R.s} 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 {W.s = W1.s} W   {W.s = W.i } F 产生式部分不再给出

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s  指向符号表中a的入口 指向符号表中b的入口 i W s i W  略去了E  TR  T 部分

4.3 L属性定义的自上而下计算 4.3.3 预测翻译器的设计 把预测分析器的构造方法推广到翻译方案的实现 产生式R  +TR |  的分析过程 void R( ) { if (lookahead == '+' ) { match ( '+' ); T( ); R( ); } else / 什么也不做 /

4.3 L属性定义的自上而下计算 i1 = mkNode(addoplexeme, i , nptr); syntaxTreeNode R (syntaxTreeNode i) { syntaxTreeNode nptr, i1, s1, s; char addoplexeme; 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 （非L属性定义） T  integer | char L  L, id | id 信息从右向左流，归约从左向右，两者不一致

4.3 L属性定义的自上而下计算 4.3.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D  L : T （非L属性定义） T  integer | char L  L, id | id 等所需信息获得后再归约 改成从右向左归约 D  id L L  , id L | : T D : L , id integer T

4.3 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} D : L , id integer T

4.4 L属性的自下而上计算 在自下而上分析的框架中实现L属性定义的方法 它能实现任何基于LL(1)文法的L属性定义 也能实现许多（但不是所有的）基于LR(1) 的L属性定义

4.4 L属性的自下而上计算 4.4.1 删除翻译方案中嵌入的动作 E  T R R  + T {print (‘+’)}R1 |  T {print (‘’)}R1 |  T  num {print (num.val)} 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M  的右端 R  + T M R1 |  T N R1 |  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 id {addtype (id.entry, L.in )}

4.4 L属性的自下而上计算 4.4.2 分析栈上的继承属性 D T L , r q p int  type in 1、属性位置能预测 例 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.2 分析栈上的继承属性 D T L , r q p int  type in 1、属性位置能预测 例 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属性的自下而上计算 D T L , r q p int  type in 产 生 式 代 码 段 D  TL T int 代 码 段 D  TL T int val[top] = integer T real val[top] = real L L1, id addType(val[top], val[top3]) L id addType(val[top], val[top1])

4.4 L属性的自下而上计算 2、属性的位置不能预测 S  aAC C.i = A.s S  bABC C.i = A.s C  c C.s = g(C.i) 增加标记非终结符，使得位置可以预测 S  bABMC M.i = A.s; C.i = M.s M   M.s = M.i

4.4 L属性的自下而上计算 2、属性的位置不能预测 S  aAC C.i = A.s S  bABC C.i = A.s C  c C.s = g(C.i) 增加标记非终结符，使得位置可以预测 S  bABMC M.i = A.s; C.i = M.s C  c C.s = g(C.i) 还得考虑M.s 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) 增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行 S  aANC N.i = A.s; C.i = N.s N   N.s = f (N.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 {B.ht = disp (B1.ht, B2.ht ) }  B  text {B.ht = text.h  B.ps }

4.4 L属性的自下而上计算 产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   L.s = 10 将B.ps存入栈中，便于引用 B  B1 MB2 B1.ps = B.ps; M.i = B.ps; B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M   M.s = M.i B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   L.s = 10 将B.ps存入栈中，便于引用 B  B1 MB2 B1.ps = B.ps; M.i = B.ps; B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M   M.s = M.i 单纯为了属性位置可预测 B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   L.s = 10 将B.ps存入栈中，便于引用 B  B1 MB2 B1.ps = B.ps; M.i = B.ps; B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M   M.s = M.i 单纯为了属性位置可预测 B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) 兼有计算功能 B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 举例说明 在text归约成B时，B的ps属性 都在次栈顶位置 S M s B  L s text sub N s

4.4 L属性的自下而上计算 产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   L.s = 10 B  B1 MB2 B1.ps = B.ps; M.i = B.ps; B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M   M.s = M.i B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   L.s = 10 产 生 式 代 码 段 S  LB val[top1] = val[top] L   L.s = 10 B  B1 MB2 B1.ps = B.ps; M.i = B.ps; B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M   M.s = M.i B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   产 生 式 代 码 段 S  LB val[top1] = val[top] L   val[top+1] = 10 B  B1 MB2 B1.ps = B.ps; M.i = B.ps; B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M   M.s = M.i B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   产 生 式 代 码 段 S  LB val[top1] = val[top] L   val[top+1] = 10 B  B1 MB2 val[top2] = max(val[top2], val[top]) M   M.s = M.i B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   产 生 式 代 码 段 S  LB val[top1] = val[top] L   val[top+1] = 10 B  B1 MB2 val[top2] = max(val[top2], val[top]) M   val[top+1] = val[top1] B  B1 sub NB2 B1.ps =B.ps; N.i = B.ps; B2.ps = N.s; B.ht = disp (B1.ht, B2.ht ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   产 生 式 代 码 段 S  LB val[top1] = val[top] L   val[top+1] = 10 B  B1 MB2 val[top2] = max(val[top2], val[top]) M   val[top+1] = val[top1] B  B1 sub NB2 val[top3] = disp (val[top3], val[top] ) N   N.s = shrink(N.i) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   产 生 式 代 码 段 S  LB val[top1] = val[top] L   val[top+1] = 10 B  B1 MB2 val[top2] = max(val[top2], val[top]) M   val[top+1] = val[top1] B  B1 sub NB2 val[top3] = disp (val[top3], val[top] ) N   val[top+1] = shrink(val[top2]) B  text B.ht = text.h  B.ps

4.4 L属性的自下而上计算 产 生 式 代 码 段 S  LB val[top1] = val[top] L   产 生 式 代 码 段 S  LB val[top1] = val[top] L   val[top+1] = 10 B  B1 MB2 val[top2] = max(val[top2], val[top]) M   val[top+1] = val[top1] B  B1 sub NB2 val[top3] = disp (val[top3], val[top] ) N   val[top+1] = shrink(val[top2]) B  text val[top] = val[top]  val[top1]

本 章 要 点 语义规则的两种描述方法：语法制导的定义和翻译方案 设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点 本 章 要 点 语义规则的两种描述方法：语法制导的定义和翻译方案 设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点 语法制导定义和翻译方案的实现 S属性的自下而上计算（边分析边计算） L属性的自上而下计算（边分析边计算） L属性的自下而上计算（边分析边计算） 不再介绍先分析后计算的方法 不能边分析边计算的情况是存在的，见5.6节

例 题 1 下面是产生字母表 = {0, 1, 2}上数字串的一个 文法： S  D S D | 2 D  0 | 1 例 题 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产生的二进制数的值。例如，输入 例 题 2 为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产生的二进制数的值。例如，输入 101.101时，S.val = 5.625（可以修改文法） 若按22+ 0 + 20 + 2-1 + 0 + 2-3来计算，该文法对小数点 左边部分的计算不利，因为需要继承属性来确定每个B 离开小数点的距离 S  L . L | L L  L B | B B  0 | 1 S . L B

例 题 2 为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产生的二进制数的值。例如，输入 例 题 2 为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产生的二进制数的值。例如，输入 101.101时，S.val = 5.625（可以修改文法） 若小数点左边按(1  2 + 0)  2 + 1计算。该办法不能 直接用于小数点右边，需改成((1  2 + 0)  2 + 1)/23， 这时需要综合属性来统计B的个数 S  L . L | L L  L B | B B  0 | 1 S . L B

例 题 2 为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产生的二进制数的值。例如，输入 例 题 2 为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产生的二进制数的值。例如，输入 101.101时，S.val = 5.625（可以修改文法） 更清楚的办法是将文法改成下面的形式 S  L . R | L L  L B | B R  B R | B B  0 | 1 S . L B R

例 题 2 S  L . R S. val = L. val + R. val S  L S. val = L. val 例 题 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. val = 1

例 题 3 给出把中缀表达式翻译成没有冗余括号的中 缀表达式的语法制导定义。例如,因为和是 左结合, 例 题 3 给出把中缀表达式翻译成没有冗余括号的中 缀表达式的语法制导定义。例如,因为和是 左结合, ((a  (b + c ))  (d ))可以重写成a  (b + c )  d 两种方法： 先把表达式的括号都去掉，然后在必要的地方再加括号 去掉表达式中的冗余括号，保留必要的括号

例 题 3 第一种方法 S  E print ( E. code ) E  E1 + T if T. op == plus then 例 题 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 = T. code; E. op = T. op

例 题 3 T  T1  F if (F. op == plus) or (F. op == times) then 例 题 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 T. code = T1. code || “” || F. code; T. op = times

例 题 3 T  F T. code = F. code; T. op = F. op F  id 例 题 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 分别表示左右两侧算符的优先级 例 题 3 第二种方法 给E，T和F两个继承属性left_op和right_op 分别表示左右两侧算符的优先级 给它们一个综合属性self_op表示自身主算符的优先级 再给一个综合属性code表示没有冗余括号的代码 分别用1和2表示加和乘的优先级，用3表示id和(E)的优先级，用0表示左侧或右侧没有运算对象的情况

例 题 3 S  E E. left_op = 0; E. right_op = 0; print ( E. code ) 例 题 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. 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 = 例 题 3 F  ( E ) E. left_op = 0; E. right_op = 0; F. self_op = if (F. left_op < E. self_op) and (E. self_op >= F. right_op) then E. self_op else 3 F. code = then E. code else “(” || E. code || “)”

习 题 第一次 4.1，4.3，4.5 第二次 4.7，4.9, 4.10 第三次 4.13，4.14