第六章语法制导的翻译本章内容介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。

6.1 属性文法例简单台式计算器的属性文法产生式语义规则 L  E n print (E.val) E  E1 + T
6.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

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

6.1 属性文法 6.1.2 综合属性（synthesized attribute） S属性定义：仅仅使用综合属性的语法制导定义产生式
6.1 属性文法 6.1.2 综合属性（synthesized attribute） 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

6.1 属性文法 8+5*2 n的注释分析树 digit.lexval = 2 L E.val = 18 n T.val = 10
6.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

6.1 属性文法分析树各结点属性的计算可以自下而上地完成 digit.lexval = 2 L E.val = 18 n
6.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

6.1 属性文法注释分析树:结点的属性值都标注出来的分析树 digit.lexval = 2 L E.val = 18 n
6.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

6.1 属性文法 6.1.3 继承属性(inherited attribute) int id, id, id 产生式语义规则
6.1 属性文法 6.1.3 继承属性(inherited attribute) 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

6.1 属性文法 int id1, id2, id3的注释分析树 D T.type = integer L.in = integer ,
6.1 属性文法 int id1, id2, id3的注释分析树 D int T.type = integer , id3 L.in = integer id2 id1

6.2 基于属性文法的处理方法 6.2.1 依赖图 int id1, id2, id3的分析树的依赖图
6.2 基于属性文法的处理方法 6.2.1 依赖图 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

6.2 基于属性文法的处理方法 6.2.1 依赖图 int id1, id2, id3的分析树的依赖图
6.2 基于属性文法的处理方法 6.2.1 依赖图 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

6.2 基于属性文法的处理方法属性计算次序拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。
6.2 基于属性文法的处理方法属性计算次序拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。例：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

6.2 基于属性文法的处理方法属性计算次序构造输入的分析树 D int T , id3 L id2 id1 1 entry 10
6.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

6.2 基于属性文法的处理方法属性计算次序构造输入的分析树，构造属性依赖图 D int T , id3 L id2 id1
6.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

6.2 基于属性文法的处理方法属性计算次序构造输入的分析树，构造属性依赖图，对结点进行拓扑排序 D int T , id3 L id2
6.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

6.2 基于属性文法的处理方法属性计算次序构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。 D int
6.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

6.2 基于属性文法的处理方法属性计算构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。
6.2 基于属性文法的处理方法属性计算构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。也可以多次扫描分析树，如果属性文法不存在循环依赖，每次至少会计算出一个属性值。编译更感兴趣的是一遍扫描的处理方法。

6.2 基于属性文法的处理方法 6.2.4 抽象语法树语法分析与语义处理阶段分离
6.2 基于属性文法的处理方法 6.2.4 抽象语法树语法分析与语义处理阶段分离语法分析树不适合语义处理的因素：提取公共左因子，消除左递归等引入新的产生式和符号，标点等语法要素不含任何语义信息抽象语法树是语法分析和后续阶段的接口。 if-then-else B S1 S2 + * 2 5 8

6.2 基于属性文法的处理方法 6.2.4 抽象语法树产生式语义规则 E  E1 + T
6.2 基于属性文法的处理方法 6.2.4 抽象语法树产生式语义规则 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)

6.2 基于属性文法的处理方法 a+5*b的抽象语法树的构造指向符号表中a的入口指向符号表中b的入口 E.nptr T.nptr + *
6.2 基于属性文法的处理方法 a+5*b的抽象语法树的构造 E.nptr T.nptr F.nptr id + * num num 5 指向符号表中a的入口指向符号表中b的入口

6.3 S属性文法的自下而上计算 6.2.3 S属性的自下而上计算将LR分析器增加一个域来保存综合属性值。 . . . Z Z. z Y
Y. y X X.x top 栈 state val

Y. y X X.x 若产生式A →XYZ的语义规则是 A.a := f (X.x, Y.y, Z.z) top 栈 state val

Y. y X X.x 若产生式A →XYZ的语义规则是 A.a := f (X.x, Y.y, Z.z)，那么归约后： top . . . A A.a top 栈 state val

6.3 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

台式计算器的语法制导定义改成栈操作代码产生式代码段 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

台式计算器的语法制导定义改成栈操作代码产生式代码段 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

6.4 L属性文法的自上而下计算边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。

6.4 L属性文法的自上而下计算边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。
分析树的结点是自左向右生成。

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

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

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

6.4 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

6.4 L属性文法的自上而下计算 6.4.2 翻译方案例把有加和减的中缀表达式翻译成后缀表达式
例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是 。

例把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是 。 E  T R R  addop T {print (addop.lexeme)} R1 |  T  num {print (num.val)}

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

6.4 L属性文法的自上而下计算例左递归的消除引起继承属性产生式语义规则 E  E1 + T
产生式语义规则 E  E1 + T E.nptr := mknode( ‘+’, E1.nptr, T.nptr) E  T E.nptr := T.nptr T  (E) F.nptr := E.nptr F  num F.nptr := mkleaf (num, num.val)

6.4 L属性文法的自上而下计算 E  T {R.i := T.nptr} 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  (E) {T.nptr := E.nptr} T  num {T.nptr := mkleaf ( num, num.val)}

6.4 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  num {T.nptr := mkleaf(num,num.val)}

6.4 L属性文法的自上而下计算 6.4.3 预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现
产生式R  +TR |  的分析过程 procedure R; begin if lookahead = ‘+’ then begin match ( ‘+’ ); T; R end else begin /* 什么也不做 */

6.4 L属性文法的自上而下计算 R : i, s T : nptr + : addoplexeme
function R (in :AST_node ) :AST_node; var nptr , i1, s1, s :  AST_node; addoplexeme : char; begin if lookahead = ‘+’ then begin /* 产生式 R  +T R */ addoplexeme := lexval; match( ‘+’ ); nptr := T(); i1 := mknode(addoplexme, in , nptr) ; s1 := R (i1 ); s : = s1 end else s := in; /* 产生式 R   */ return s end; //演示DiguixiajiangfanyiAST R : i, s T : nptr + : addoplexeme

6.5 自下而上计算继承属性 6.5.1 删除翻译方案中嵌入的动作 E  T R
R  + T {print (‘+’)}R1 |  T {print (‘’)}R1 |  T  num {print (num.val)}

R  + T {print (‘+’)}R1 |  T {print (‘’)}R1 |  T  num {print (num.val)} 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M  的右端。

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 (‘’)}

6.5 自下而上计算继承属性 6.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 )}

6.5 自下而上计算继承属性 6.4.2 分析栈上的继承属性属性位置能预测演示Table610 例 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 )} D T L , r q p int  type in

6.5 自下而上计算继承属性 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])

6.5 自下而上计算继承属性属性的位置不能预测 S  aAC C.i := A.s S  bABC C.i := A.s
C  c C.s := g(C.i)

6.5 自下而上计算继承属性属性的位置不能预测 S  aAC C.i := A.s S  bABC C.i := A.s
C  c C.s := g(C.i) //此时需要C.i，实际上就是A.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

6.5 自下而上计算继承属性 6.4.3 模拟继承属性的计算继承属性是某个综合属性的一个函数 S  aAC C.i := f (A.s)
C  c C.s := g(C.i)

6.5 自下而上计算继承属性 6.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)

6.5 自下而上计算继承属性 6.4.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D  L : T
T  integer | char L  L, id | id

6.5 自下而上计算继承属性 6.4.4 用综合属性代替继承属性 Pascal的声明，如m, n : integer D  L : T
T  integer | char L  L, id | id 改成从右向左归约 D  id L L  , id L | : T

6.5 自下而上计算继承属性 6. 4.4 用综合属性代替继承属性 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

6.5 自下而上计算继承属性 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

本章要点语义规则的两种描述方法：属性文法和翻译方案。设计简单问题的属性文法和翻译方案，这是本章的重点和难点。
本章要点语义规则的两种描述方法：属性文法和翻译方案。设计简单问题的属性文法和翻译方案，这是本章的重点和难点。 S属性的自下而上计算（边分析边计算）。 L属性的自上而下计算（边分析边计算）。 L属性的自下而上计算（边分析边计算）。

第六章语法制导的翻译本章内容介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。

Similar presentations

Presentation on theme: "第六章语法制导的翻译本章内容介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

第六章 语法制导的翻译 本章内容 介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。

Similar presentations

Presentation on theme: "第六章 语法制导的翻译 本章内容 介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。"— Presentation transcript:

Similar presentations

About project

反馈

第六章语法制导的翻译本章内容介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。

Presentation on theme: "第六章语法制导的翻译本章内容介绍一种语义描述方法：语法制导的翻译，介绍语法制导的翻译的实现方法。"— Presentation transcript: