编译原理与技术 语法制导翻译 Ⅱ 计算机科学与技术学院 李诚 22/10/2018
Announcement Tutorial on Thursday (25/10/2018) 3B201, Class time Assignment review Q & A Cheng @ Compiler Fall 2018, USTC 2
主要内容 源程序 词法分析器 token 语法分析器 分析树 语义分析 注释分析树 中间代码生成 中间表示 符号表 语法分析树 抽象语法树 从语法制导定义到翻译方案 S 属性定义的 SDT L 属性定义的 SDT Cheng @ Compiler Fall 2018, USTC 3
抽象语法树 语法树是分析树的浓缩表示 : 算符和关键字是作为内部结点 语法制导翻译可以基于分析树, 也可以基于语法树 S if B then S1 else S2 if-then-else S B S 1 S 2 语法树 if B then S else 1 S 2 分析树 Cheng @ Compiler Fall 2018, USTC 4
抽象语法树 例 : 表达式 (A - 12) * B + 6 的语法结构树 + * 6 - B A 12 Cheng @ Compiler Fall 2018, USTC 5
建立算符表达式的语法树 mknode (op, left, right) 建立一个运算符号结点, 标号是 op, 两个域 left 和 right 分别指向左子树和右子树 mkleaf (, entry) 建立一个标识符结点, 标号为, 一个域 entry 指向标识符在符号表中的入口 mkleaf (num, val) 建立一个数结点, 标号为 num, 一个域 val 用于存放数的值 Cheng @ Compiler Fall 2018, USTC 6
构造语法树的语法制导定义 以算数表达式为例 产生式语义规则 E E 1 + T E.nptr = mknode( +, E 1.nptr, T.nptr) E T T T 1 F T F F (E) F F num E.nptr = T.nptr T.nptr = mknode(, T 1.nptr, ) T.nptr = = E.nptr = mkleaf (,.entry) = mkleaf (num, num.val) Cheng @ Compiler Fall 2018, USTC 7
构造语法树的语法制导定义 注意事项 : 同样是产生式附带语义规则, 不同的语义规则产生不同的作用 对算符结点, 一个域存放算符并作为该结点的标记, 其余两个域存放指向运算对象的指针 基本运算对象结点, 一个域存放运算对象类别, 另一个域存放其值 ( 也可用其他域保存其他属性或者指向该属性值的指针 ) Cheng @ Compiler Fall 2018, USTC 8
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 9
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 10
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 11
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 12
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 13
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 14
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 15
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 16
S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口 指向符号表中 b 的入口 Cheng @ Compiler Fall 2018, USTC 17
构造 a-4+c 语法树的步骤 (1) p1:=mkleaf(,entry a); (2) p2:=mkleaf(num, 4); (3) p3:=mknode( -,p1,p2) (4) p4:=mkleaf(, entry c) (5) p5:=mknode( +,p3,p4) p 1, p 2,..., p 5 是指向结点的指针, entry a 和 entry c 分别指向符号表中标识符 a 和 c 的指针 + p 5 + p 3 - p 4 entryc - p 1 entrya p 2 num 4 to entry for a to entry for c num 4 指向 c 的入口 指向 a 的入口 Cheng @ Compiler Fall 2018, USTC 18
左递归的消除引起继承属性 考虑以下左递归文法 产生式语义规则 E E 1 + T E.nptr = mknode( +, E 1.nptr, T.nptr) E T T T 1 F T F F (E) F F num E.nptr = T.nptr T.nptr = mknode(, T 1.nptr, ) T.nptr = = E.nptr = mkleaf (,.entry) = mkleaf (num, num.val) Cheng @ Compiler Fall 2018, USTC 19
左递归的消除引起继承属性 首先消除左递归 T + T + T + E TR R +TR 1 R T FW W FW 1 W F 产生式部分不再给出 Cheng @ Compiler Fall 2018, USTC 20
左递归的消除引起继承属性 E T {R.i = T.nptr} T + T + T + R {E.nptr = R.s} R + T {R1.i = mknode ( +, R.i, T.nptr)} R 1 {R.s = R 1.s} R {R.s = R.i } T F {W.i = } W {T.nptr = W.s} W F {W1.i = mknode (, W.i, )} W 1 {W.s = W 1.s} W {W.s = W.i } F 产生式部分不再给出 Cheng @ Compiler Fall 2018, USTC 21
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 22
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 23
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 24
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 25
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 26
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 27
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 28
左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Cheng @ Compiler Fall 2018, USTC 29
主要内容 源程序 词法分析器 token 语法分析器 分析树 语义分析 注释分析树 中间代码生成 中间表示 符号表 语法分析树 抽象语法树 从语法制导定义到翻译方案 S 属性定义的 SDT L 属性定义的 SDT Cheng @ Compiler Fall 2018, USTC 30
语法制导翻译方案 语法制导翻译方案 (SDT) 是在产生式右部中嵌入了程序片段 ( 称为语义动作 ) 的 CFG SDT 可以看作是 SDD 的具体实施方案 Cheng @ Compiler Fall 2018, USTC 31
将 S-SDD 转换为 SDT 将一个 S-SDD 转换为 SDT 的方法 : 将每个语义 动作都放在产生式的最后 Cheng @ Compiler Fall 2018, USTC 32
S- 属性定义的 SDT 实现 综合属性可通过自底向上的 LR 方法来计算 当归约发生时执行相应的语义动作 Cheng @ Compiler Fall 2018, USTC 33
S- 属性定义的 SDT 实现 可以通过扩展的 LR 语法分析栈来实现 在分析栈中使用一个附加的域来存放综合属性值 若支持多个属性, 那么可以在栈中存放指针 此时, 分析栈可以看成一个栈, 栈元素包含状态 文法符号 综合属性三个域 ; 分析栈也可以看成三个栈, 分别是状态栈 文法符号栈 综合属性栈, 分开看的理由是, 入栈出栈并不完全同步 Cheng @ Compiler Fall 2018, USTC 34
S- 属性定义的 SDT 实现 可以通过扩展的 LR 语法分析栈来实现 语义翻译对应栈的操作 Cheng @ Compiler Fall 2018, USTC 35
SLR 分析栈中实现计算器 桌面计算器的 SDD 和 SDT 定义如下 : Cheng @ Compiler Fall 2018, USTC 36
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top...... Z Z. z Y Y. y X X.x...... 产生式 L E n E E 1 + T E T T T 1 F T F F (E) F digit 语义规则 print (E.val) E.val =E 1.val +T.val E.val = T.val T.val = T 1.val F.val T.val = F.val F.val = E.val F.val = digit.lexval 栈 state val Cheng @ Compiler Fall 2018, USTC 37
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top...... Z Z. z Y Y. y X X.x...... 产生式 L E n E E 1 + T E T T T 1 F T F F (E) F digit 代码段 print (E.val) E.val =E 1.val +T.val E.val = T.val T.val = T 1.val F.val T.val = F.val F.val = E.val F.val = digit.lexval 栈 state val Cheng @ Compiler Fall 2018, USTC 38
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T E.val =E 1.val +T.val E T E.val = T.val T T 1 F T.val = T 1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval Cheng @ Compiler Fall 2018, USTC 39
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T val [top 2 ] = E T T T 1 F T F F (E) F digit val [top 2]+val [top] E.val = T.val T.val = T 1.val F.val T.val = F.val F.val = E.val F.val = digit.lexval Cheng @ Compiler Fall 2018, USTC 40
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T val [top 2 ] = E T T T 1 F T F F (E) F digit val [top 2]+val [top] 值不变, 无动作 T.val = T 1.val F.val T.val = F.val F.val = E.val F.val = digit.lexval Cheng @ Compiler Fall 2018, USTC 41
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T val [top 2 ] = val [top 2]+val [top] E T T T 1 F val [top 2 ] = T F F (E) F digit val [top 2]val [top] T.val = F.val F.val = E.val F.val = digit.lexval Cheng @ Compiler Fall 2018, USTC 42
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T val [top 2 ] = val [top 2]+val [top] E T 值不变, 无动作 T T 1 F val [top 2 ] = T F F (E) F digit val [top 2]val [top] 值不变, 无动作 F.val = E.val F.val = digit.lexval Cheng @ Compiler Fall 2018, USTC 43
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T val [top 2 ] = val [top 2]+val [top] E T 值不变, 无动作 T T 1 F val [top 2 ] = val [top 2]val [top] T F 值不变, 无动作 F (E) val [top 2 ] =val [top 1] F digit F.val = digit.lexval Cheng @ Compiler Fall 2018, USTC 44
SLR 分析栈中实现计算器 简单计算器的语法制导定义改成栈操作代码 top 栈...... Z Z. z Y Y. y X X.x...... state val 产生式 代码段 L E n print (val [ top1] ) E E 1 + T val [top 2 ] = val [top 2]+val [top] E T 值不变, 无动作 T T 1 F val [top 2 ] = val [top 2]val [top] T F 值不变, 无动作 F (E) val [top 2 ] =val [top 1] F digit 值不变, 无动作 Cheng @ Compiler Fall 2018, USTC 45
翻译输入 3*5+4n 输入 state val 使用的产生式 3*5+4n - - *5+4n 3 3 *5+4n F 3 Fdigit *5+4n T 3 TF 5+4n T* 3* +4n T* 5 3*5 +4n T* F 3*5 F digit Cheng @ Compiler Fall 2018, USTC 46
翻译输入 3*5+4n +4n T 15 T T*F +4n E 15 E T 4n E+ 15+ n E+4 15+4 n E+F 15+4 F digit n E+T 15+4 T F n E 19 E E+T En 19 - L 19 L En Cheng @ Compiler Fall 2018, USTC 47
总结 采用自底向上分析, 例如 LR 分析, 首先给出 S- 属性定义, 然后, 把 S- 属性定义变成可执行的代码段, 这就构成了翻译程序 随着语法分析的进行, 归约前调用相应的语义子程序, 完成翻译的任务 Cheng @ Compiler Fall 2018, USTC 48
主要内容 源程序 词法分析器 token 语法分析器 分析树 语义分析 注释分析树 中间代码生成 中间表示 符号表 语法分析树 抽象语法树 从语法制导定义到翻译方案 S 属性定义的 SDT L 属性定义的 SDT Cheng @ Compiler Fall 2018, USTC 49
L 属性定义的自上而下计算 边分析边翻译的方式能否用于继承属性? 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制 分析树的结点是自左向右生成 如果属性信息是自左向右流动, 那么就有可能在分析的同时完成属性计算 Cheng @ Compiler Fall 2018, USTC 50
L 属性定义的自上而下计算 如果每个产生式 AX 1 X j-1 X j X n 的每条语 义规则计算的属性是 A 的综合属性 ; 或者是 X j 的继承属性, 但它仅依赖 : 该产生式中 X j 左边符号 X 1, X 2,, X j-1 的属性 ; A 的继承属性 S 属性定义属于 L 属性定义 Cheng @ Compiler Fall 2018, USTC 51
L 属性定义的自上而下计算 变量类型声明的语法制导定义是一个 L 属性定义 产生式语义规则 D TL L.in = T.type T int T real L L 1, L T. type = integer T. type = real L 1.in = L.in; addtype(.entry, L.in) addtype(.entry, L.in) Cheng @ Compiler Fall 2018, USTC 52
L 属性定义的自上而下计算 翻译方案 例把有加和减的中缀表达式翻译成后缀表达式如果输入是 8+5 2, 则输出是 8 5 + 2 E T R R addop T {print (addop.lexeme)} R 1 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()} Cheng @ Compiler Fall 2018, USTC 53
编译原理与技术 语法制导翻译 Ⅱ 有些时候不是因为看到希望才坚持, 而是因为坚持久了才看到了希望 Loved by Cheng Li