语义分析简介 编译程序的目标：将源程序翻译成为语义等价的目标程序。 语义分析的主流技术：

Presentation on theme: "语义分析简介 编译程序的目标：将源程序翻译成为语义等价的目标程序。 语义分析的主流技术："— Presentation transcript:

1 语义分析简介 编译程序的目标：将源程序翻译成为语义等价的目标程序。 语义分析的主流技术：
源程序与目标程序具有不同的语法结构，表达的结果却是相同的。 语义分析的主流技术： 语法制导翻译技术

2 语义分析简介 语义分析的功能 审查每个语法结构的静态语义 例：类型、运算、维数、越界 在验证完静态语义后，才执行真正的翻译
例：变量的存储分配 例：表达式的求值 例：语句的翻译（中间代码的生成）

3 语义分析简介 语义规则和产生式相联系的两种方式 语法制导定义
对应每一个产生式编制一个语义子程序，当一 个产生式获得匹配时，调用相应的语义子程序 实现语义检查与翻译。 语法制导的翻译方案 在产生式的右部的适当位置，插入相应的语义 动作，按照分析的进程，执行遇到的语义动作。

4 语义分析简介 怎么办呢？ 语义信息是上下文有关的 例如：变量使用前要先定义 文法定义可以写成： L={wcw|w是任意的a和b的串}
问题：这个文法不是上下文无关的 怎么办呢？

5 语义分析简介 属性文法 目前情况 上下文无关文法 能够有效描述语言语法结构 具有有效的分析方法，如LR(1)、LALR等 程序语义
编译器进行翻译的时候所必须的信息 无法用上下文无关文法表示 这两者之间怎么衔接？ 属性文法

6 本讲纲要 01 属性文法

7 属性文法 也称属性翻译文法 Donald Ervin Knuth在1968年提出
在上下文无关文法的基础上，为每个文法符号（终结 符或非终结符）配备若干相关的“值”（称为属性）。 属性代表与文法符号相关信息，如类型、值、代 码序列、符号表内容等。 属性可以进行计算和传递。 语义规则：对于文法的每个产生式都配备了一组 属性的计算规则。

8 属性文法 语法制导的定义 带属性和规则的上下文无关文法。 在语法制导定义中的文法被称为基础文法。

9 属性文法 表达式文法 E  E + T | E  T T  T * F | T  E F  (E ) | F  digit
为了计算表达式的值，首先为这个文法的非终结符添加val属性

10 4.1 语法制导的定义 例：简单台式计算器的语法制导定义 产 生 式 语 义 规 则 L  E n E  E1 + T E  T
4.1 语法制导的定义 例：简单台式计算器的语法制导定义 产 生 式 语 义 规 则 L  E n E  E1 + T E  T T  T1 * F T  F F (E) F  digit print (E.val) E.val := E1 .val + T.val E.val := T.val T.val := T1.val * F.val T.val := F.val F.val := E.val F.val := digit.lexval

11 属性值由分析树中它的子结点的属性值来计算
4.1.1 语法制导定义的形式 基础文法 每个文法符号有一组属性。 每个文法产生式A  有一组形式为b := f(c1, c2, …, ck )的语义规则，其中f 是函数，b和c1, c2, …, ck 是该产生式文法符号的属性。 综合属性：如果b是A的属性，c1 , c2 , …, ck 是产生式右部文法符号的属性或A的其它属性。 继承属性：如果b是产生式右部某个文法符号X的属性， c1 , c2 , …, ck 是产生式右部文法符号的属性或A的其它属性。 属性值由分析树中它的子结点的属性值来计算 属性值由结点的兄弟结点及父结点的属性值来计算。 综合属性：从分析树底层结点逐步传递上去的属性 继承属性：从分析树高层传递下来的属性

12 继承属性和综合属性的性质 关于属性的一些常识 终结符只有综合属性，并且这些综合属性通常由词 法分析器提供。
非终结符号既有综合属性也可有继承属性，文法的 开始符号没有继承属性，除非另外加以说明。 文法符号的综合属性集和继承属性集的交集应为空。 因为开始符号没有任何的兄弟结点或者父结点。

13 继承属性和综合属性的性质 关于属性的一些常识
对出现在产生式右边的继承属性和出现在产生式左边 的综合属性都必须提供一个计算规则。属性计算规则 中只能使用相应产生式中的文法符号的属性。 出现在产生式左边的继承属性和出现在产生式右边的 综合属性不由所给的产生式的属性计算规则进行计算， 它们由其它产生式的属性规则计算或者由属性计算器 的参数提供。

14 语义规则 语义规则所描述的工作可以包括 属性计算、静态语义检查、符号表操作、代码生成 等等。 例：考虑非终结符A，B和C，其中A有一个继承 属性a和一个综合属性b，B有综合属性c，C有继 承属性d。产生式A→BC可能有规则： C.d:=B.c+1 A.b:=A.a+B.c 而属性A.a和B.c在其它地方计算。

15 语义规则 语义规则b := f(c1, c2, …, ck )中，函数 f 通常是表达式（T.val=F.val）。也有一些规则写成过程调用或程序段（打印值，输出中间代码等），称为产生副作用的操作（如：print(E.val)）可看成是产生式左部非终结符的虚拟综合属性。 属性文法是指语义规则函数无副作用的语法制导定义。 基础文法 属性文法

16 本讲纲要 01 综合属性 02 继承属性

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

18 每个结点的属性值都标注出来的分析树，称为～。
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

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

20 3*5+4n的带注释的分析树 L E.val=19 n E.val=15 + T.val=4 T.val=15 F.val=4
产 生 式 语 义 规 则 L→En 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 L E.val=19 n E.val=15 + T.val=4 T.val=15 F.val=4 T.val=3 * F.val=5 digit.lexval=4 F.val=3 digit.lexval=5 digit.lexval=3

21 继承属性 继承属性 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。
用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。

22 4.1 语法制导的定义 4.1.3 继承属性 int id, id, id 产 生 式 语 义 规 则 D  TL T int
4.1 语法制导的定义 4.1.3 继承属性 int id, id, id 产 生 式 语 义 规 则 D  TL T int T real L L1, id L id L.in := T.type T. type := integer 综合属性计算 T. type := real L1.in := L.in; addtype (id.entry, L.in ) addtype (id.entry, L.in )

23 4.1 语法制导的定义 D T.type = integer L.in = integer , int id3 id2 id1
4.1 语法制导的定义 int id1, id2, id3的注释分析树 D int T.type = integer , id3 L.in = integer id2 id1

24 句子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 addtype(id.entry, L.in) D T T.type=integer L L.in=integer int L L.in=integer , id3 L L.in=integer id2 , id1

25 本讲纲要 01 属性依赖图 02 属性计算次序 03 语义规则的计算方法 输入串 分析树 依赖图 语义规则计算次序

26 4.1.4 属性依赖图 在一棵分析树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述。
属性依赖图 在一棵分析树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述。 为每一个包含过程调用的语义规则引入一个虚拟综合属性b，这样把每一个语义规则都写成 b:=f(c1,c2,…,ck) 的形式。 依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。

27 属性依赖图 E→E1＋E2 E.val:=E1.val+E2.val val E E1 + E2 val val

28 句子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 addtype(id.entry, L.in) D 4 type 5 in L 6 - addtype(id.entry, L.in) T int L 8 addtype , id3 3 entry 7 in L 10 addtype , id2 9 in 2 entry id1 1 entry

29 4.1.4 属性依赖图 int id1, id2, id3的分析树的依赖图 D  TL L.in := T.type D int T ,
属性依赖图 int id1, id2, id3的分析树的依赖图 D  TL L.in := T.type 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

30 4.1.5 属性计算次序 拓扑排序：结点的一种排序，使得边只会从该次序中先 出现的结点到后出现的结点。
例：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

31 4.1.5 属性计算次序 依赖图的任一拓扑排序都是一个合理的属性计算顺 序。

32 循环依赖Circular dependency
如果一属性文法不存在属性之间的循环依赖关系， 那么称该文法为良定义的。 产生式 语义规则 A  B A.s := B.i B.i := A.s + 1 A B A.s B.i

33 4.1.5 属性计算次序 一个依赖图的任何拓扑排序都给出一个语法树中结 点的语义规则计算的有效顺序。 属性文法说明的翻译是很精确的。
基础文法用于建立输入符号串的语法分析树； 根据语义规则建立依赖图； 从依赖图的拓扑排序中，可以得到计算语义规则的顺 序。 输入串 分析树 依赖图 语义规则计算次序

34 int id1, id2, id3的分析树的依赖图 D T , id3 L id2 id1 1 entry 2 entry 3 entry
a4:=int; a5:=a4 addtype (id3.entry,a5); a7:=a5; addtype (id2.entry,a7); a9:=a7 addtype (id1.entry,a9); D T , id3 L id2 id1 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type int

35 4.1.5 属性计算次序 例：考虑属性文法G。其中，S有继承属性a，综合属 性b；X有继承属性c、综合属性d；Y有继承属性e、综 合属性f；Z有继承属性h、综合属性g。 产生式 语义规则 S→XYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b X→x X.d :=2*X.c Y→y Y.f := Y.e*3 Z→z Z.g :=Z.h+1

36 假设S.a的初始值为0，输入串为xyz S:a=0, b=0 S:a=0 X X:c=1 d=2 Y Y:e=0 f=0 Z Z:h=0
产 生 式 语 义 规 则 S→XYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.b X→x X.d :=2*X.c Y→y Y.f := Y.e*3 Z→z Z.g :=Z.h+1 S:a=0, b=0 S:a=0 X X:c=1 d=2 Y Y:e=0 f=0 Z Z:h=0 g=1 x y z

37 4.1.5 属性计算次序 属性计算次序 1、构造输入的分析树 2、构造属性依赖图 3、对结点进行拓扑排序 4、按拓扑排序的次序计算属性

38 4.1 语法制导的定义 语义规则的计算方法 分析树方法：前面介绍的方法（有环则失败） 基于规则的方法：静态确定语义规则的计算次序。
4.1 语法制导的定义 语义规则的计算方法 分析树方法：前面介绍的方法（有环则失败） 基于规则的方法：静态确定语义规则的计算次序。 忽略规则的方法：事先确定属性的计算策略（如边 分析边计算），那么语义规则的设计必须符合所选 分析方法的限制。

39 语义规则的计算方法 基于（语义）规则的方法 语法分析和属性计算分开，先构造分析树，然后按预 先定义的策略遍历分析树来计算属性。
基于（语义）规则的方法　　 语法分析和属性计算分开，先构造分析树，然后按预 先定义的策略遍历分析树来计算属性。 语义规则的定义和计算顺序（翻译模式）在编译器构 造之前确定。 分析树遍历策略的确定（构造编译器时）要考虑语义 规则的定义及计算顺序，因此是基于规则的方法。

40 语义规则的计算方法 忽略（语义）规则的方法 在进行语法分析的同时进行翻译，即边分析边计算属 性，计算次序由分析方法确定而与语义规则无关。
缺点：这样确定计算次序将限制能实现的语法制导定 义的种类。 优点：不构造依赖图，不对依赖图进行拓扑排序，提 高了时空效率。

41 本讲纲要 01 语法树

42 语法树 S if-then-else S2 B S1 S2 B S1 语法树是分析树的浓缩表示：算符和关键字是作为内部结点。
语法制导翻译可以基于分析树，也可以基于语法树 语法树的例子： S if B then S1 else S2 if-then-else B S1 S2 语法树 S B S1 S2 if then else 分析树

43 语法树 例：表达式 (A - 12) * B + 6 的语法结构树。

44 建立算符表达式的语法树 mknode (op, left, right) mkleaf (id, entry)
mkleaf (num, val) 建立一个数结点，标号为num，一个域val用于存放 数的值。

45 用于构造语法树的语法制导定义（例） 产 生 式 语 义 规 则 E  E1 + T E  T
产 生 式 语 义 规 则 E  E1 + T E  T T  T1*F T  F F  (E) F  id F  num E.nptr := mknode( ‘+’, E1.nptr, T.nptr) E.nptr := T.nptr T.nptr := mknode( ‘*’, T1.nptr, F.nptr) T.nptr := F.nptr F.nptr := E.nptr F.nptr := mkleaf (id, id.entry) F.nptr := mkleaf (num, num.val)

46 用于构造语法树的语法制导定义 注意： 同样是产生式附带语义规则，不同的语义规则产生 不同的作用。
对算符结点，一个域存放算符并作为该结点的标记， 其余两个域存放指向运算对象的指针。 基本运算对象结点，一个域存放运算对象类别，另 一个域存放其值。（也可用其他域保存其他属性或 者指向该属性值的指针）

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

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

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

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

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

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

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

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

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

56 建立抽象语法树的语义规则 产 生 式 语 义 规 则 E→E1+T E.nptr := mknode(‘+’, E1.nptr, T.nptr ) E→E1-T E.nptr := mknode( ‘-’, E1.nptr, T.nptr ) E→T E.nptr := T.nptr T→ (E) T.nptr := E.nptr T→id T.nptr := mkleaf( id, id.entry ) T→num T.nptr := mkleaf( num, num.val )

57 a－4＋c的语法树 E nptr E nptr T nptr id E - T nptr id T nptr + - id id num 4
To entry for c E→E1+T E→E1-T E→T T→ (E) T→id T→num id num 4 To entry for a

58 构造 a-4+c的语法树 (1) p1:=mkleaf(id,entry a); (2) p2:=mkleaf(num, 4);
(3) p3:=mknode(‘-’，p1,p2) (4) p4:=mkleaf(id, entry c) (5) p5:=mknode(‘+’,p3,p4) p1, p2, ..., p5是指向结点的指针， entry a和entry c分别指向符号表中标识符a和c的指针。 ＋ － id 指向c的入口 指向a 的入口 num 4 + p5 id entryc to entry for c p4 - p3 id entrya to entry for a p1 num 4 p2

59 本讲纲要 01 S属性定义的自下而上计算

60 S属性定义的自下而上计算 S-属性文法：只含有综合属性 综合属性可以在分析输入符号串的同时由自下而 上的分析器来计算。
分析器可以保存与栈中文法符号有关的综合属性 值，每当进行归约时，新的属性值就由栈中正在 归约的产生式右边符号的属性值来计算。

61 S属性的自下而上计算 . . . Z Z. z Y Y. y X X.x top . . . A A.a top 栈 state val
将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

62 4.2 S属性定义的自下而上计算 . . . Z Z. z Y Y. y X X.x top 栈 state 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

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

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

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

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

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

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

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

70 翻译输入3*5+4n所做的移动 输入 state val 使用的产生式 3*5+4n - - *5+4n 3 3
*5+4n F Fdigit *5+4n T TF 5+4n T* * +4n T* *5 +4n T* F * F digit

71 翻译输入3*5+4n所做的移动 +4n E 15 E T 4n E+ 15+ n E+F 15+4 F  digit
+4n T T T*F +4n E E T 4n E n E n E+F F  digit n E+T T F n E E E+T En L L En

72 总结 采用自底向上分析，例如LR分析，首先给出S-属 性定义，然后，把S-属性定义变成可执行的代码 段，这就构成了翻译程序。
象一座建筑，语法分析是构架，归约处有一个 “挂钩”，语义分析和翻译的代码段（语义子程 序）就挂在这个钩子上。这样，随着语法分析的 进行，归约前调用相应的语义子程序，完成翻译 的任务。

73 属性值由分析树中它的子结点的属性值来计算
小结 属性值由分析树中它的子结点的属性值来计算 属性值由结点的兄弟结点及父结点的属性值来计算。 属性 综合属性 继承属性 消除左递归 改写文法 基础文法+综合属性 语法制导定义 S属性定义 表示 自上而下分析 自下而上分析 归约：综合属性放入栈中

74 本讲纲要 01 属性的理解

75 加深理解 属性的理解 非终结符 分析过程（函数） 1 综合属性过程的返回值 2 3 继承属性 过程的参数

76 属性理解—例子 int id, id, id 产 生 式 语 义 规 则 D  TL L.in := T.type T int
产 生 式 语 义 规 则 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

77 属性理解—例子 产 生 式 语 义 规 则 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 void D() { T_temp = T(); L_in = T_temp; L(L_in); return ; } int T() { switch lookahead { case INT: return INTEGER; case REAL: return REAL; default: error; void L(int L_in){ L(L_in); match(‘,’); match(id); addtype(id.entry, L_in); } Void L(int L_in){ match (id); addtype(id.entry, L.in);

78 本讲纲要 01 L属性定义

79 边分析边计算，使得语法和语义的计算都在一遍处理完毕，而不需要为语义分析而单独进行一遍编译分析
L属性定义的自上而下计算 S属性定义的计算 边分析边计算 分析完毕，属性也计算完毕 问题： 继承属性是否可以采用边分析边计算的方式进行？ 边分析边计算，使得语法和语义的计算都在一遍处理完毕，而不需要为语义分析而单独进行一遍编译分析

80 L属性定义的自上而下计算 属性计算与分析方法之间的关系 分析树的结点是自左向右生成。
属性的计算次序受分析方法所限定的分析树结点 建立次序的限制。 分析树的结点是自左向右生成。 所以，仅当属性信息是自左向右流动时，才有 可能在分析的同时完成属性计算。

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

82 例 非L属性 文法符号Q的继承属性依赖于它右边文法符号R的属性。

83 另一例 非L属性的语法制导定义 文法符号B的继承属性依赖于它右边文法符号C的属性。

84 L属性定义例子 变量类型声明的语法制导定义 语义规则的执行时刻很重要 产 生 式 语 义 规 则 D  TL L.in := T.type
产 生 式 语 义 规 则 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

85 L属性定义的自上而下计算 对于L属性定义，与S属性的一个最本质区别在于 为了对L属性定义进行翻译，必须提一个概念
翻译方案

86 本讲纲要 01 翻译方案

87 翻译方案 翻译方案 在翻译方案中，和文法符号相关语义动作，用花 括号{ }括起来，插入到产生式右部的合适位置上。
给出了使用语义规则进行计算的次序，这样就可把某些 实现细节表示出来。 在翻译方案中，和文法符号相关语义动作，用花 括号{ }括起来，插入到产生式右部的合适位置上。 这是一种动作和分析交错的方法，以表示动作的 执行时机。

88 翻译方案 语义动作（语义规则）插入到产生式右部的任 何地方，以表达动作的执行时刻。 AB{..}C

89 翻译方案 例 把有加和减的中缀表达式翻译成后缀表达式 如果输入是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()}

90 翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式
E→TR R→addop T {print(addop.lexeme)} R1 |  T→num {print(num.val)} 例：8+5-2 E T R + 8 {print(‘8’)} T {print(‘+’)} R {print(‘5’)} 5 - T {print(‘-’)} R 2 {print(‘2’)} 

91 建立翻译模式 当只需要综合属性时：为每一个语义规则建立 一个包含赋值的动作，并把这个动作放在相应 的产生式右边的末尾。 产生式 语义规则
产生式 语义规则 T→T1*F T.val:=T1.val×F.val 建立产生式和语义动作： T→T1*F {T.val:=T1.val×F.val}

92 建立翻译模式 如果既有综合属性又有继承属性，在建立翻译模式 时就必须保证：
1. 产生式右边的符号的继承属性必须在先于这个符号的 动作中计算出来。 2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所 有属性都计算出来以后才能计算。计算这种属性的动 作通常可放在产生式右端的末尾。

93 例：翻译模式 S  A1A2 {A1.in := 1; A2.in := 2} A  a {print(A.in)} 不符合条件(1)。
若改写成 S  {A1.in := 1; A2.in := 2} A1A A  a {print(A.in)} 则就符合条件(1)。 S A2 A1 a Pr(A.in) A1.in=1,A2.in=2

94 本讲纲要 01 翻译方案----数学排版语言

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

96 L 属性定义的自上而下计算 E .val 例 数学排版语言EQN E sub 1 .val 综合属性： ht = height 继承属性：
ps = point size 例 数学排版语言EQN E sub 1 .val E 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 ) 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

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

98 L 属性定义的自上而下计算 1. 产生式右边的符号的继承属性必须在先于这个符号的 动作中计算出来。
2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所 有属性都计算出来以后才能计算。计算这种属性的动 作通常放在产生式右端的末尾。 例 数学排版语言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 }

99 本讲纲要 01 左递归的消除引起继承属性 翻译方案 消除左递归

100 左递归的消除引起继承属性 例 左递归的消除引起继承属性 产 生 式 语 义 规 则 E  E1 + T E  T T  T1*F
产 生 式 语 义 规 则 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)

101 左递归的消除引起继承属性 T + T + T + … E  E1 + T E  T T  T1*F T  F F  (E) F  id F  num E  TR R  +TR1 R   T  FW W  FW1 W   F 产生式部分不再给出

102 左递归的消除引起继承属性 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 产生式部分不再给出

103 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分

104 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 T  F {W.i = F.nptr} W {T.nptr = W.s}

105 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 T  F {W.i = F.nptr} W {T.nptr = W.s}

106 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 W  F {W1.i = mkNode (‘’,W.i, F.nptr)} W1{W.s = W1.s}

107 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 W  F {W1.i = mkNode (‘’,W.i, F.nptr)} W1{W.s = W1.s}

108 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 W  F {W1.i = mkNode (‘’,W.i, F.nptr)} W1{W.s = W1.s}

109 左递归的消除引起继承属性 E  TR R  +TR1 T R   a*5*b T  F W 略去了E  TR  T 部分
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 W  F {W1.i = mkNode (‘’,W.i, F.nptr)} W1{W.s = W1.s}

110 左递归的消除引起继承属性 W   {W.s = W.i } E  TR R  +TR1 T R   a*5*b T  F W
W  FW1 W   T F.nptr id i W  num num 5 指向符号表中a 的入口 指向符号表中b 的入口 i W s i W  a*5*b 略去了E  TR  T 部分 W   {W.s = W.i }

111 本讲纲要 01 预测翻译器的设计

112 设计递归下降翻译器的方法 对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数。

113 设计递归下降翻译器的方法 非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。

114 设计递归下降翻译器的方法 每个产生式对应的程序代码中，按照从左到右的次 序，对于单词符号（终结符）、非终结符和语义动 作分别作以下工作：
i) 对于带有综合属性x的终结符X，把x的值存入为X.x设置 的变量中。然后产生一个匹配X的调用，并继续读入一 个输入符号。 ii) 对于每个非终结符B，产生赋值语句c=B(b1,b2,…,bk)， 其中，b1,b2,…,bk是为B的继承属性设置的变量，c是为 B的综合属性设置的变量。 iii) 对于语义动作，把动作的代码抄进分析器中，用代表 属性的变量来代替对属性的每一次引用。

115 预测翻译器的设计 目标：为文法计算其中的L属性值 方法： 把预测分析器的构造方法推广到翻译方案的实现 产生式R  +TR |  的分析过程 void R( ) { if (lookahead == '+' ) { match ( '+' ); T( ); R( ); } else / 什么也不做 /

116 i1 = mkNode(addoplexeme, i , nptr); s1 = R(i1); s= s1; return s;
产生式R  +TR |  的翻译方案过程 syntaxTreeNode R(syntaxTreeNode i) { syntaxTreeNode nptr, i1, s1, s; char addoplexeme; if (lookahead=='+' ){/产生式R +TR / addoplexeme=lexval; match('+'); nptr= T(); i1 = mkNode(addoplexeme, i , nptr); s1 = R(i1); s= s1; } else s = i; /产生式R   / return s;

117 本讲纲要 01 用综合属性代替继承属性

118 用综合属性代替继承属性 D L : T L , id integer id Pascal的声明，如m, n : integer
（通过改写文法） Pascal的声明，如m, n : integer D  L : T T  integer | char L  L, id | id D L : T L , id integer id

119 用综合属性代替继承属性 D : L , id integer T
Pascal的声明，如m, n : integer D  L : T T  integer | char L  L, id | id 改成从右向左归约 D  id L L  , id L | : T D : L , id integer T

120 用综合属性代替继承属性 D : L , id integer T
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

121 本讲纲要 01 L属性定义的自上而下计算

122 L 属性的自下而上计算 L属性的自上而下计算与自上而下的语法分析的过程是一致的。 但是，自上而下分析能够处理的文法局限于LL(1)。

123 L 属性的自下而上计算 在自下而上语法分析的框架中实现L属性定义的方法，可以做到： 实现任何基于LL(1)文法的L属性定义。
实现许多（但不是所有的）基于LR(1) 的L属性定义。

124 L 属性的自下而上计算 . . . Y Y. y X X.x top 栈 state val L 属性自下而上计算需要解决的问题：
AX Y {Z.i = X.x} Z 一个状态（文法符号）对应一个综合属性，该属性的值一般在处理完该文法符号之后得到。那么在Z还没有开始处理前，继承属性Z.i 就没有对应的val条目供其使用！ . . . Y Y. y X X.x top 解决办法：在栈上消除继承属性 栈 state val

125 本讲纲要 01 删除翻译方案中嵌入的动作

126 删除翻译方案中嵌入的动作 问题 问题的解决方案： 自下而上的分析中，语义动作的执行是在使用产生式对句柄进行归约的时候
但是，L属性定义的继承属性的计算需要嵌在产生式右部不同的地方 问题的解决方案： 通过改写文法，使得所有嵌入在产生式中间的动作变换成只在产生式的最右端出现

127 删除翻译方案中嵌入的动作 特殊情况一：删除翻译方案中嵌入的动作
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 (‘’)}

128 本讲纲要 01 分析栈上的继承属性

129 分析栈上的继承属性 复写规则 特殊情况二：分析栈上的继承属性 所依赖的属性在分析栈上的位置能静态确定 例 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 )} 所依赖的属性在分析栈上的位置能静态确定 复写规则 所依赖的属性在分析栈上的位置能静态确定

130 分析栈上的继承属性 特殊情况二：分析栈上的继承属性 属性位置能预测 L id {addtype (id.entry, L.in )}
q p int  type in 状态 输入 所用产生式 - int p,q,r int p,q,r T Tint Tp ,q,r TL Lid TL, q,r TL,q ,r LL,id r TL,r D DTL 每个L结点上L.in = T.type L id {addtype (id.entry, L.in )} L {L1.in := L.in } L1, id {addtype (id.entry, L.in )} L {L1.in := L.in } L1, id {addtype (id.entry, L.in )}

131 分析栈上的继承属性 属性T.type在栈中的位置相对于栈顶是事先知道的。因此，可以用栈中的属性值T.type代替L.in。 D T L ,
r q p int  type in 产 生 式 代 码 段 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]) 属性T.type在栈中的位置相对于栈顶是事先知道的。因此，可以用栈中的属性值T.type代替L.in。

132 分析栈上的继承属性 一个不能预知属性值在栈中所放位置的例子 考虑下面翻译模式： 产生式 语义规则 S  aAC C.i := A.s
产生式 语义规则 S  aAC C.i := A.s S  bABC C.i := A.s C  c C.s := g(C.i) 属性C.i 通过一个复写规则来继承属性A.s 的值。 S a A  C s i S b A B  C s i

133 分析栈上的继承属性 产生式 语义规则 S  aAC C.i := A.s S  bABMC M.i :=A.s; C.i := M.s
产生式 语义规则 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 S b A B  C s i (a)原产生式 S b A B  M   C s i s i  (b) 依赖关系

134 分析栈上的继承属性 c A a _ A.s ... top M B b M.s B.s
SaAC SbABMC Cc val [top]=g(val [top-1]) M  val [top+1]=val [top-1]

135 分析栈上的继承属性 所依赖的属性在分析栈上的位置不能静态确定 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 SaAC SbABMC Cc val [top]=g(val [top-1]) M  val [top+1]=val [top-1]

136 本讲纲要 01 模拟继承属性的计算

137 模拟继承属性的计算 模拟继承属性的计算（一般情况） 继承属性是某个综合属性的一个函数 S  aAC C.i := f (A.s ) C  c C.s := g(C.i ) S a A  C s i c A a C.s A.s ... top

138 这样，每次需要使用继承属性的时候，刚好都在本文法符号的正下方
模拟继承属性的计算 增加标记非终结符，把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 ) 这样，每次需要使用继承属性的时候，刚好都在本文法符号的正下方 c S iC iNs As a  c N A a C.s N.s A.s ... top

139 模拟继承属性的计算 c A a C.s A.s ... top c S iC iNs As a  c N A a C.s N.s A.s

140 本讲纲要 01 模拟继承属性的计算----数学排版语言

141 模拟继承属性的计算 例 数学排版语言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 }

142 模拟继承属性的计算 在计算文本的字体和高度的时候，无法确定所依赖的继承属性值的位置。 例如：栈顶元素可能是 text => B
B text => B B B sub text => B sub B

143 模拟继承属性的计算 产 生 式 语 义 规 则 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

144 模拟继承属性的计算 S  L { B.ps := L.s } B { S.ht := B.ht } L   { L.s := 10 } B  { B1.ps := B.ps } B1 { M.i := B.ps } M { B2.ps := M.s } B2 { B.ht := max(B1.ht, B2.ht ) } M   { M.s := M.i } B  { B1.ps :=B.ps } B1 sub { N.i = B.ps } N { B2.ps := shrink(N.s) } B2 { B.ht := disp (B1.ht, B2.ht ) } N   { N.s := N.i } B  text { B.ht := text.h  B.ps }

145 模拟继承属性的计算 S M B  L text E sub N 1 举例说明 ht s=10 ps ht ps s ps ht ht
i s ps ht ht h=E.h ps i s ps ht ht h=1.h h=E.h

146 模拟继承属性的计算 B ht L s 改写为栈代码 产 生 式 语 义 规 则 S  LB
产 生 式 语 义 规 则 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 top 栈 state val

147 模拟继承属性的计算 L s 产 生 式 代 码 段 S  LB val[top1] := val[top] L  
产 生 式 代 码 段 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 top

148 模拟继承属性的计算 B ht M s 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

149 模拟继承属性的计算 B ht L s 产 生 式 代 码 段 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 top

150 模拟继承属性的计算 B ht N s L 产 生 式 代 码 段 S  LB val[top1] := val[top] L  
sub L top 产 生 式 代 码 段 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

151 模拟继承属性的计算 B ht L s 产 生 式 代 码 段 S  LB val[top1] := val[top] L  
sub B ht L s 产 生 式 代 码 段 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

152 模拟继承属性的计算 h L s 产 生 式 代 码 段 S  LB val[top1] := val[top] L  
text h L s 产 生 式 代 码 段 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

153 模拟继承属性的计算 产 生 式 代 码 段 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]

154 本讲纲要 01 引进标记非终结符号对基础文法的影响

155 引进标记非终结符号对基础文法的影响 基础文法是LL(1)文法 基础文法是LR(1)文法
因为每个标记非终结符号是唯一的，而且只有唯一一个的产生式 基础文法是LR(1)文法 可能使修改后的文法变成非LR(1)文法 例如文法L  Lb|a 为LR(1)文法，加了M之后为： L  MLb|a M  

156 本讲纲要 01 语法制导定义小结

157 属性值由分析树中它的子结点的属性值来计算
本章小结 推导：预测分析器的设计 基础文法+综合属性+部分继承属性 翻译方案 L属性定义 表示 自上而下分析 自下而上分析 属性值由分析树中它的子结点的属性值来计算 属性值由结点的兄弟结点及父结点的属性值来计算。 属性 综合属性 继承属性 消除左递归 改写文法 归约：在栈上消除继承属性 基础文法+综合属性 语法制导定义 S属性定义 表示 自上而下分析 自下而上分析 归约：综合属性放入栈中

158 Thank You!