大侠素材铺

Size: px

Start display at page:

Download "大侠素材铺"

枯锐周
5 years ago
Views:

1 编译原理与技术语法制导翻译 Ⅱ 计算机科学与技术学院李诚 22/10/2018

2 Announcement Tutorial on Thursday (25/10/2018) 3B201, Class time Assignment review Q & A Compiler Fall 2018, USTC 2

3 主要内容源程序词法分析器 token 语法分析器分析树语义分析注释分析树中间代码生成中间表示符号表语法分析树抽象语法树从语法制导定义到翻译方案 S 属性定义的 SDT L 属性定义的 SDT Compiler Fall 2018, USTC 3

4 抽象语法树语法树是分析树的浓缩表示 : 算符和关键字是作为内部结点语法制导翻译可以基于分析树, 也可以基于语法树 S if B then S1 else S2 if-then-else S B S 1 S 2 语法树 if B then S else 1 S 2 分析树 Compiler Fall 2018, USTC 4

5 抽象语法树例 : 表达式 (A - 12) * B + 6 的语法结构树 + * 6 - B A 12 Compiler Fall 2018, USTC 5

6 建立算符表达式的语法树 mknode (op, left, right) 建立一个运算符号结点, 标号是 op, 两个域 left 和 right 分别指向左子树和右子树 mkleaf (, entry) 建立一个标识符结点, 标号为, 一个域 entry 指向标识符在符号表中的入口 mkleaf (num, val) 建立一个数结点, 标号为 num, 一个域 val 用于存放数的值 Compiler Fall 2018, USTC 6

7 构造语法树的语法制导定义以算数表达式为例产生式语义规则 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) Compiler Fall 2018, USTC 7

8 构造语法树的语法制导定义注意事项 : 同样是产生式附带语义规则, 不同的语义规则产生不同的作用对算符结点, 一个域存放算符并作为该结点的标记, 其余两个域存放指向运算对象的指针基本运算对象结点, 一个域存放运算对象类别, 另一个域存放其值 ( 也可用其他域保存其他属性或者指向该属性值的指针 ) Compiler Fall 2018, USTC 8

9 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 9

10 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 10

11 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 11

12 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 12

13 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 13

14 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 14

15 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 15

16 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 16

17 S 属性定义的语法树构造 a+5b 的语法树的构造 E.nptr E.nptr + T.nptr T.nptr + T.nptr num num 5 指向符号表中 a 的入口指向符号表中 b 的入口 Compiler Fall 2018, USTC 17

18 构造 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 的入口 Compiler Fall 2018, USTC 18

19 左递归的消除引起继承属性考虑以下左递归文法产生式语义规则 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) Compiler Fall 2018, USTC 19

20 左递归的消除引起继承属性首先消除左递归 T + T + T + E TR R +TR 1 R T FW W FW 1 W F 产生式部分不再给出 Compiler Fall 2018, USTC 20

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

22 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 22

23 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 23

24 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 24

25 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 25

26 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 26

27 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 27

28 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 28

29 左递归的消除引起继承属性 T i W num 略去了 E TR T 部分 i W i W s 指向符号表中 b 的入口 num 5 指向符号表中 a 的入口 Compiler Fall 2018, USTC 29

30 主要内容源程序词法分析器 token 语法分析器分析树语义分析注释分析树中间代码生成中间表示符号表语法分析树抽象语法树从语法制导定义到翻译方案 S 属性定义的 SDT L 属性定义的 SDT Compiler Fall 2018, USTC 30

31 语法制导翻译方案语法制导翻译方案 (SDT) 是在产生式右部中嵌入了程序片段 ( 称为语义动作 ) 的 CFG SDT 可以看作是 SDD 的具体实施方案 Compiler Fall 2018, USTC 31

32 将 S-SDD 转换为 SDT 将一个 S-SDD 转换为 SDT 的方法 : 将每个语义动作都放在产生式的最后 Compiler Fall 2018, USTC 32

33 S- 属性定义的 SDT 实现综合属性可通过自底向上的 LR 方法来计算当归约发生时执行相应的语义动作 Compiler Fall 2018, USTC 33

34 S- 属性定义的 SDT 实现可以通过扩展的 LR 语法分析栈来实现在分析栈中使用一个附加的域来存放综合属性值若支持多个属性, 那么可以在栈中存放指针此时, 分析栈可以看成一个栈, 栈元素包含状态文法符号综合属性三个域 ; 分析栈也可以看成三个栈, 分别是状态栈文法符号栈综合属性栈, 分开看的理由是, 入栈出栈并不完全同步 Compiler Fall 2018, USTC 34

35 S- 属性定义的 SDT 实现可以通过扩展的 LR 语法分析栈来实现语义翻译对应栈的操作 Compiler Fall 2018, USTC 35

36 SLR 分析栈中实现计算器桌面计算器的 SDD 和 SDT 定义如下 : Compiler Fall 2018, USTC 36

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 Compiler Fall 2018, USTC 37

38 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 Compiler Fall 2018, USTC 38

39 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 Compiler Fall 2018, USTC 39

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] E.val = T.val T.val = T 1.val F.val T.val = F.val F.val = E.val F.val = digit.lexval Compiler Fall 2018, USTC 40

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 ] = 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 Compiler Fall 2018, USTC 41

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] T.val = F.val F.val = E.val F.val = digit.lexval Compiler Fall 2018, USTC 42

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 ] = T F F (E) F digit val [top 2]val [top] 值不变, 无动作 F.val = E.val F.val = digit.lexval Compiler Fall 2018, USTC 43

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 F.val = digit.lexval Compiler Fall 2018, USTC 44

45 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 值不变, 无动作 Compiler Fall 2018, USTC 45

46 翻译输入 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 Compiler Fall 2018, USTC 46

47 翻译输入 3*5+4n +4n T 15 T T*F +4n E 15 E T 4n E+ 15+ n E 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 Compiler Fall 2018, USTC 47

48 总结采用自底向上分析, 例如 LR 分析, 首先给出 S- 属性定义, 然后, 把 S- 属性定义变成可执行的代码段, 这就构成了翻译程序随着语法分析的进行, 归约前调用相应的语义子程序, 完成翻译的任务 Compiler Fall 2018, USTC 48

49 主要内容源程序词法分析器 token 语法分析器分析树语义分析注释分析树中间代码生成中间表示符号表语法分析树抽象语法树从语法制导定义到翻译方案 S 属性定义的 SDT L 属性定义的 SDT Compiler Fall 2018, USTC 49

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

51 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 属性定义 Compiler Fall 2018, USTC 51

52 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) Compiler Fall 2018, USTC 52

53 L 属性定义的自上而下计算翻译方案例把有加和减的中缀表达式翻译成后缀表达式如果输入是 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()} Compiler Fall 2018, USTC 53

54 编译原理与技术语法制导翻译 Ⅱ 有些时候不是因为看到希望才坚持, 而是因为坚持久了才看到了希望 Loved by Cheng Li

Microsoft PowerPoint - ch4.ppt [兼容模式]

Microsoft PowerPoint - ch4.ppt [兼容模式] 第四章语法制导的翻译本章内容 1 介绍语义描述的一种形式方法: 语法制导的翻译 (syntax-directed translation), 它包括两种具体形式语法制导的定义 (syntax-directed definition) E E 1 + T E.code = E 1.code T.code + 可读性好, 更适于描述规范翻译方案 (translation scheme) E E