《语义分析II》PPT课件.ppt

2020/10/14 中国科大 1/97 编译原理和技术 大连理工软件学院 胡 彦 2020/10/14 中国科大 2/97 本讲纲要 综合属性 继承属性 2020/10/14 中国科大 3/97 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 2020/10/14 中国科大 4/97 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 每个结点的属性值都标 注出来的分析树，称 为。 2020/10/14 中国科大 5/97 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 8+5*2 n 2020/10/14 中国科大 6/97 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 8+5*2 n 2020/10/14 中国科大 7/97 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 8+5*2 n 2020/10/14 中国科大 8/97 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 8+5*2 n 2020/10/14 中国科大 9/97 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 8+5*2 n 2020/10/14 中国科大 10/97 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 8+5*2 n 2020/10/14 中国科大 11/97 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 8+5*2 n 2020/10/14 中国科大 12/97 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 8+5*2 n 2020/10/14 中国科大 13/97 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 8+5*2 n 2020/10/14 中国科大 14/97 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 8+5*2 n 2020/10/14 中国科大 15/97 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 8+5*2 n 2020/10/14 中国科大 16/97 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 8+5*2 n 2020/10/14 中国科大 17/97 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 ) 综合属性计算 2020/10/14 中国科大 18/97 4.1 语法制导的定义 int id1, id2, id3的注释分析树 D int T.type = integer , id3 L.in = integer L.in = integer L.in = integer id2 id1 , 2020/10/14 中国科大 19/97 本讲纲要 综合属性 继承属性 属性计算 依赖图 属性计算次序 2020/10/14 中国科大 20/97 4.1 语法制导的定义 4.1.4 属性依赖图 int id1, id2, id3的分析树的依赖图 D TL L.in := T.type D int T , id3 L L L id2 id1 , 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type 2020/10/14 中国科大 21/97 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 L L id2 id1 , 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type 2020/10/14 中国科大 22/97 4.1 语法制导的定义 4.1.5 属性计算次序 拓扑排序 ：结点的一种排序，使得边只会从该次序中 先出现的结点到后出现的结点。 例： 1， 2， 3， 4， 5， 6， 7， 8， 9， 10 D int T , id3 L L L id2 id1 , 1 entry 10 2 entry 3 entry in 9 8 in 7 6 in 5 4 type 2020/10/14 中国科大 23/97 4.1 语法制导的定义 属性计算次序 1、构造输入的分析树， 2、构造属性依赖图， 3、对结点进行拓扑排序 4、按拓扑排序的次序计算属性。 2020/10/14 中国科大 24/97 温故知新 属性的理解 非终结符 分析过程（函数） 综合属性 过程的返回值 继承属性 过程的参数 2020/10/14 中国科大 25/97 属性理解 例子 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 addtype (id.entry, L.in ) 温故知新 2020/10/14 中国科大 26/97 属性理解 例子 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; 产 生 式 语 义 规 则 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 ) 温故知新 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); 2020/10/14 中国科大 27/97 4.2 S属性定义的自下而上计算 4.2.1 语法树 语法树是分析树的浓缩表示 ： 算符和关键字是作为 内部结点。 语法制导翻译可以基于分析树，也可以基于语法树 语法树的例子： if-then-else B S1 S2 S if B then S1 else S2 S B S1 S2 if then else 语法树 分析树 2020/10/14 中国科大 28/97 4.2 S属性定义的自下而上计算 4.2.2 (例 )用于 构造语法树的语法制导定义 产 生 式 语 义 规 则 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) 2020/10/14 中国科大 29/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 30/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 31/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 32/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 33/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 34/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 35/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 36/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 37/97 4.2 S属性定义的自下而上计算 a+5*b的语法树的构造 E.nptr T.nptr E.nptr T.nptr F.nptr id T.nptr + * F.nptr F.nptr id num id id num 5 * + 指向符号表中 a的入口 指向符号表中 b的入口 E E1 + T | T T T1 * F |F F (E) F id | num 2020/10/14 中国科大 38/97 4.2 S属性定义的自下而上计算 4.2.3 S属性的自下而上计算（一般方法） 将 LR分析器 增加 一个域来保存综合属性值 。 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 2020/10/14 中国科大 39/97 4.2 S属性定义的自下而上计算 4.2.3 S属性的自下而上计算 将 LR分析器 增加 一个域来保存综合属性值 。 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 若产生式 A XYZ的语义规则是 A.a := f (X.x, Y.y, Z.z)， 那么归约后： . . . . . . A A.a . . . . . . top 2020/10/14 中国科大 40/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 语 义 规 则 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 2020/10/14 中国科大 41/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) 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 2020/10/14 中国科大 42/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) 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 2020/10/14 中国科大 43/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) 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 2020/10/14 中国科大 44/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 := val top 2+val top E T T T1 * F val top 2 := val top 2val top T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval 2020/10/14 中国科大 45/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 := val top 2+val top E T T T1 * F val top 2 := val top 2val top T F F (E) F.val := E.val F digit F.val := digit.lexval 2020/10/14 中国科大 46/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 := val top 2+val top E T T T1 * F val top 2 := val top 2val top T F F (E) val top 2 := val top 1 F digit F.val := digit.lexval 2020/10/14 中国科大 47/97 4.2 S属性定义的自下而上计算 台式计算器的语法制导定义改成栈操作代码 . . . . . . Z Z. z Y Y. y X X.x . . . . . . 栈 state val top 产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 := val top 2+val top E T T T1 * F val top 2 := val top 2val top T F F (E) val top 2 := val top 1 F digit