语法制导的翻译 （Syntax-Directed Translation）

Presentation on theme: "语法制导的翻译 （Syntax-Directed Translation）"— Presentation transcript:

1 语法制导的翻译 （Syntax-Directed Translation）

2 语法制导的翻译：一种由语法分析器驱动的翻译方法
How？ 词 法 分析器 token getNextToken 源程序 分析树 语义分析、 中间代码生成 语 法分析器 中间表示 符号表 用语法分析的过程和分析树引导语义分析和中间代码生成 两种方法：语法制导的定义、语法制导的翻译方案

3 语法制导的定义 例 简单计算器的语法制导定义 产 生 式 语 义 规 则 L  E n L.val = E.val E  E1 + T
例 简单计算器的语法制导定义 产 生 式 语 义 规 则 L  E n L.val = 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 语法制导的定义 基础文法 每个文法符号有一组属性 每个文法产生式A  有
一组形式为b=f(c1, c2, …, ck )的语义规则，其中 b和c1, c2, …, ck 是该产生式文法符号的属性， f 是函数 综合属性：b是A的属性，c1 , c2 , …, ck 是产生式右 部文法符号的属性或A的其它属性 继承属性：b是右部某文法符号X的属性，c1, c2, …, ck 是产生式右部文法符号的属性或A的属性

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

6 S属性的语法制导定义 注释分析树：结点的属性值都标注出来的分析树 digit.lexval = 2 L.val = 18
8+5*2 n 的注释分析树 digit.lexval = 2 L.val = 18 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

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

8 继承属性 产 生 式 语 义 规 则 D  TL L.in = T.type T int T. type = integer
int id1, id2, id3 产 生 式 语 义 规 则 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

9 继承属性 例 int id1, id2, id3的标注了部分属性的分析树 D T.type = integer L.in = integer
不可能像综合属性那样自下而上标注属性 D int T.type = integer , id3 L.in = integer id2 id1

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

11 属性依赖图 例 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

12 属性依赖图 例 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

13 属性计算次序 拓扑排序：结点的一种排序，使得边只会从该次 序中先出现的结点到后出现的结点 例 1，2，3，4，5，6，7，8，9，10 D
例 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

14 语义规则的计算方法 （1）构造输入的分析树；（2）构造属性依赖图； （3）对结点进行拓扑排序；（4）按拓扑排序的 次序计算属性 D int
, id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

15 语义规则的计算方法 （1）构造输入的分析树；（2）构造属性依赖图； （3）对结点进行拓扑排序；（4）按拓扑排序的 次序计算属性
digit.lexval = 2 L.val = 18 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

16 具有受控副作用的语义规则 按照依赖图的任何拓扑顺序进行属性计算都可以 产生同样的副作用 D int T , id3 L id2 id1
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 L id addType(id.entry, L.in)

17 具有受控副作用的语义规则 按照依赖图的任何拓扑顺序进行属性计算都可以 产生同样的副作用 产 生 式 语 义 规 则 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

18 语义规则的计算方法 分析树方法：刚才介绍的方法，在编译过程中确 定计算次序，效率低 概念上的一般方法
分析树方法：刚才介绍的方法，在编译过程中确 定计算次序，效率低 概念上的一般方法 考虑在编译前（在构造编译器时）决定计算次序， 不在编译时显式构造依赖图 （编译器实现者）对（编译器设计者提供的）语义规 则进行分析，静态确定计算次序 适用于手工构造编译器。属性依赖关系复杂的语法制导定义很难 事先确定属性计算次序 （编译器实现者）事先确定属性的计算策略（如边分 析边计算）,（编译器设计者提供的）语义规则必须 符合所选分析方法的限制 适用于编译器的自动生成。限制语法制导定义的种类

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

20 构造语法树的语法制导定义 产 生 式 语 义 规 则 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)

21 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

22 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

23 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

24 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

25 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

26 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

27 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

28 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

29 a+5b的语法树的构造 指向符号表中a的入口 指向符号表中b的入口 E.nptr + T.nptr  F.nptr num id

30 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

31 简单计算器的语法制导定义改成栈操作代码 产 生 式 语 义 规 则 L  E n print (E.val) E  E1 + T
产 生 式 语 义 规 则 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

32 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (E.val) E  E1 + T
产 生 式 代 码 段 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

33 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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 省略top指针的移动

34 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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 省略top指针的移动

35 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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 省略top指针的移动

36 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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 省略top指针的移动

37 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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 省略top指针的移动

38 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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

39 简单计算器的语法制导定义改成栈操作代码 产 生 式 代 码 段 L  E n print (val [ top1] )
产 生 式 代 码 段 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

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

41 L属性定义 每个产生式AX1…Xj-1Xj…Xn的每条语义规则计算 的属性要么是A的综合属性；要么是Xj 的继承属 性，但它仅依赖：
该产生式中Xj左边符号X1, X2, …, Xj-1的属性； A的继承属性 S属性定义属于L属性定义 依赖A的综合属性？ 综合属性可能需要把产生式的右部全看完才计算

42 变量类型声明的语法制导定义是一个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

43 变量类型声明的语法制导定义是一个L属性定义
属性信息自左向右流动 D int T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type

44 变量类型声明的语法制导定义是一个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

45 怎么办？ 需要考虑语义规则的执行时机 语法制导的翻译方案：反映语义规则执行时机的 描述方法 在产生式右部中嵌入了语义动作
A   {…} ，{…}中语义动作的执行在的推导（或向 的归约）结束以后，在的推导（或向的归约）开 始以前

46 L属性定义的翻译方案 例 把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5 2，则输出是8 5 + 2  E  T R
例 把有加和减的中缀表达式翻译成后缀表达式 如果输入是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()} 如果移到别处会导致结果不正确

47 设计翻译方案时，语义动作放哪？ 必须保证动作在引用属性时其值已经计算出来了
只有综合属性：为每条语义规则建立一个赋值动作，放 在产生式右部末端 有继承属性时： 产生式右部符号的继承属性必须在先于这个符号的动作中计算 一个动作不能引用该动作右边符号的综合属性 左部非终结符的综合属性只能在它所引用的所有属性都计算完 后才能计算。通常放在产生式右部末端 对L属性定义，总是可能构造满足这三个条件的翻译方案

48 L属性定义 E .val 例 数学排版语言EQN E sub 1 .val S  B B  B1 B2 B  B1 sub B2
B  text E 1 .val

49 L属性定义 例 数学排版语言EQN（语法制导定义） 产 生 式 语 义 规 则 S  B B.ps = 10; S.ht = B.ht
产 生 式 语 义 规 则 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 B1和B2继承B的字体大小 B2字体缩小 计算B的高度时把B2向下偏置 实际高度：文本的正常高度 * 字体大小

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

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

52 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 } 52

53 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)

54 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 {W.s = W1.s} W   {W.s = W.i } F 产生式部分不再给出 必须要把第一个T的信息传给R 每个产生式结束时把属性向上传

55 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

56 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

57 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

58 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

59 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

60 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

61 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

62 a * 5 * b的语法树构造 略去了E  TR  T 部分 T i W F.nptr id  i W num i W s 

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

64 L属性的自底向上计算 前面介绍了S属性定义的自底向上计算 修改文法，使得L属性定义中所有的嵌入动作都 变换成只出现在产生式右端 产 生 式
产 生 式 代 码 段 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

65 L属性的自底向上计算 删除翻译方案中嵌入的动作 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 (‘’)} 这些动作的一个重要特点： 没有引用原来产生式文法符号的属性 所以可以如此变换

66 L属性的自底向上计算 A   {a} ，若动作a引用A或中符号的属性呢？ 考虑A  X Y的移进-归约分析栈
若X有综合属性X.s，则会放在分析栈中X对应的地方 那么在Y以下的任何子树归约前，X.s的值已经在分析 栈中 如果Y的继承属性Y.i由 Y.i = X.s 定义，那么在需要使用 Y.i的地方可以用X.s来代替 如果能静态预测X.s在栈中的位置，那么对Y.i的使用很 容易换成栈操作代码

67 L属性的自底向上计算 分析栈上的继承属性 例 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 )}

68 L属性的自底向上计算 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 )}

69 L属性的自底向上计算 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 )} L.in = T.type ，而T.type此时位于栈顶 – 1 L.in = T.type ，而T.type此时位于栈顶 – 3

70 L属性的自底向上计算 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 )} L.in = T.type ，而T.type此时位于栈顶 – 1 L.in = T.type ，而T.type此时位于栈顶 – 3 T.type ，栈顶 – 3 T.type ，栈顶 – 1

71 L属性的自底向上计算 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 )} 继承属性的计算可 以删去，引用继承属 性的地方改成引用其 他符号的综合属性

72 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])

73 L属性的自底向上计算 2、属性的位置不能预测 S  aAC C.i = A.s S  bABC C.i = A.s
C  c C.s = g(C.i) 在用C  c归约时，C.i的值（也就是A.s的值）可能在val[top – 2]，也可能在val[top – 1]

74 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 在用C  c归约时，C.i的值总是在val[top – 1]

75 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 还得考虑M.i 计算的可预测 在用M  归约时，M.i的值总是在val[top – 1]

76 L属性的自底向上计算 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) 在用N  归约时，N.i的值总是在val[top] 在用C  c归约时，C.i的值总是在val[top – 1]

77 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 } 77

78 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

79 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

80 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

81 L属性的自底向上计算 举例说明 S M s B  L s text sub N s 在text归约成B时，B的 ps属性都在次栈顶位置
在归约成M时，M.i也 在次栈顶位置 在归约成N时，N.i在 栈顶 – 2的位置

82 L属性的自底向上计算 产 生 式 语 义 规 则 S  LB B.ps = L.s; S.ht = B.ht L   L.s = 10
产 生 式 语 义 规 则 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

83 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

84 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

85 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

86 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

87 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

88 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

89 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]

90 本章小结 语法制导的定义和翻译方案 语法制导定义和翻译方案的实现 S属性的自底向上计算（边分析边计算） L属性的自顶向下计算（边分析边计算）