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

第四章语法制导的翻译本章内容 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 语法制导的定义 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 S  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属性定义的自下而上计算 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

产生式代码段 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

产生式代码段 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

产生式代码段 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

产生式代码段 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

产生式代码段 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

产生式代码段 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，则输出是  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属性定义的自上而下计算 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

产生式语义规则 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

产生式语义规则 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

产生式语义规则 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

产生式代码段 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

产生式代码段 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

产生式代码段 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

产生式代码段 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

产生式代码段 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产生的二进制数的值。例如，输入时，S.val = 5.625（可以修改文法）若按来计算，该文法对小数点左边部分的计算不利，因为需要继承属性来确定每个B 离开小数点的距离 S  L . L | L L  L B | B B  0 | 1 S . L B

例题 2 为下面文法写一个语法制导的定义，用S的综合属性val 给出下面文法中S产生的二进制数的值。例如，输入时，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产生的二进制数的值。例如，输入时，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

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

Similar presentations

Presentation on theme: "第四章语法制导的翻译本章内容 1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

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

Similar presentations

Presentation on theme: "第四章 语法制导的翻译 本章内容 1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式 语法制导的定义 翻译方案"— Presentation transcript:

Similar presentations

About project

反馈

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

Presentation on theme: "第四章语法制导的翻译本章内容 1、介绍语义描述的一种形式方法：语法制导的翻译，它包括两种具体形式语法制导的定义翻译方案"— Presentation transcript: