内容提要 1 语法制导翻译语法制导定义 S 属性定义的自下而上计算 L 属性定义的自上而下计算 L 属性定义的自下而上计算 2 中间代码生成中间语言声明语句赋值语句布尔表达式和控制流语句

Transcription

1 编译原理 第七章语法制导翻译及中间代码生成 方徽星 扬州大学信息工程学院 (505) 2018 年 6 月

2 内容提要 1 语法制导翻译语法制导定义 S 属性定义的自下而上计算 L 属性定义的自上而下计算 L 属性定义的自下而上计算 2 中间代码生成中间语言声明语句赋值语句布尔表达式和控制流语句

3 11 语法制导定义 (Syntx-Directed Definition) SDD 是一个附带有属性及语义规则的上下文无关文法 每个文法符号有一组属性,b 每个产生式 (A α) 有一组语义规则,b = f(c 1, c 2,, c k ) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

4 11 语法制导定义 (Syntx-Directed Definition) SDD 是一个附带有属性及语义规则的上下文无关文法 每个文法符号有一组属性,b 每个产生式 (A α) 有一组语义规则,b = f(c 1, c 2,, c k ) b 称为 A 的综合属性 (synthesized trribute): 如果 b 是 A 的属性, 且 c 1,c 2,, c k 是产生式右部文法符号的属性或 A 的其他属性方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

5 11 语法制导定义 (Syntx-Directed Definition) SDD 是一个附带有属性及语义规则的上下文无关文法 每个文法符号有一组属性,b 每个产生式 (A α) 有一组语义规则,b = f(c 1, c 2,, c k ) b 称为 A 的综合属性 (synthesized trribute): 如果 b 是 A 的属性, 且 c 1,c 2,, c k 是产生式右部文法符号的属性或 A 的其他属性 b 称为 X 的继承属性 (inherited ttribute): 如果 b 是产生式右部某个文法符号 X 的属性, 且 c 1,c 2,, c k 是 A 的属性或右部文法符号的属性方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

6 11 语法制导定义 (Syntx-Directed Definition) SDD 是一个附带有属性及语义规则的上下文无关文法 每个文法符号有一组属性,b 每个产生式 (A α) 有一组语义规则,b = f(c 1, c 2,, c k ) b 称为 A 的综合属性 (synthesized trribute): 如果 b 是 A 的属性, 且 c 1,c 2,, c k 是产生式右部文法符号的属性或 A 的其他属性 b 称为 X 的继承属性 (inherited ttribute): 如果 b 是产生式右部某个文法符号 X 的属性, 且 c 1,c 2,, c k 是 A 的属性或右部文法符号的属性 b 依赖于 c 1,c 2,, c k 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

7 11 语法制导定义 (Syntx-Directed Definition) 终结符只有综合属性, 属性值由词法分析器提供,SDD 中没有计算终结符号属性值的语义规则 属性文法 : 语义规则函数没有副作用的 SDD, 其规则仅仅通过其他属性值和常量值来定义一个属性值 产生式 语义规则 1 L E n Lvl = Evl 2 E E 1 + T Evl = E 1 vl + Tvl 3 E T Evl = Tvl 4 T T 1 F Tvl = T 1 vl Fvl 5 T F Tvl = Fvl 6 F (E) Fvl = Evl 7 F digit Fvl = digitlexvl 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

8 11 语法制导定义 (Syntx-Directed Definition) 仅仅使用综合属性的语法制导定义称为 S 属性定义 对于 S 属性定义, 分析树各结点属性的计算可以自下而上地完成, 通过计算语义规则而得到结点的属性 每个结点的属性值都标注出来的分析树称为注释分析树, 计算各结点属性值的过程叫做分析树的注释或修饰方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

9 11 语法制导定义 (Syntx-Directed Definition) Lvl = 19 Evl = 19 n Evl = 15 + Tvl = 4 Tvl = 15 Fvl = 4 Tvl = 3 Fvl = 5 digitlexvl = 4 Fvl = 3 digitlexvl = 5 digitlexvl = 3 图 : n 的注释分析树 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

10 11 语法制导定义 (Syntx-Directed Definition) 在分析树中, 结点的继承属性是由它的兄弟结点 父结点和自己的属性来定义的 非终结符 T 有综合属性 type,l 有继承属性 in, ddtype 把类型信息加到符号表中各个标识符的条目中 : 产生式 语义规则 1 D TL Lin = Ttype 2 T int Ttype = integer 3 T rel Ttype = rel 4 L L 1, id L 1 in = Lin ddtype(identry, Lin) 5 L id ddtype(identry, Lin) identry: 在词法分析过程中得到的一个指向某个符号表对象的值 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

11 11 语法制导定义 (Syntx-Directed Definition) D Ttype = integer Lin = integer int Lin = integer, id 3 Lin = integer, id 2 id 1 图 : int id 1, id 2, id 3 的注释分析树 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

12 11 语法制导定义 (Syntx-Directed Definition) 分析树结点属性之间的依赖关系可以使用依赖图进行描述 分析树中每个结点属性在依赖图中有的结点与之对应 属性之间的依赖, 通过依赖图中相应结点的有向边来体现 D T 4 type in 5 L 6 int in 7 L 8, id 3 3 entry in 9 L 10, id 2 2 entry id 1 1 entry 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

13 11 语法制导定义 (Syntx-Directed Definition) 拓扑排序是有向无环图中的结点的一种排序 (m i m j ) = m i 先于 m j 由拓扑排序可以确定依赖图中属性的计算顺序 可保证由规则 b = f(c 1,, c k ) 计算 b 时, 属性 c i 已计算出来方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

14 11 语法制导定义 (Syntx-Directed Definition) 拓扑排序是有向无环图中的结点的一种排序 (m i m j ) = m i 先于 m j 由拓扑排序可以确定依赖图中属性的计算顺序 可保证由规则 b = f(c 1,, c k ) 计算 b 时, 属性 c i 已计算出来 翻译过程可以按如下步骤完成方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

15 11 语法制导定义 (Syntx-Directed Definition) 拓扑排序是有向无环图中的结点的一种排序 (m i m j ) = m i 先于 m j 由拓扑排序可以确定依赖图中属性的计算顺序 可保证由规则 b = f(c 1,, c k ) 计算 b 时, 属性 c i 已计算出来 翻译过程可以按如下步骤完成 首先根据文法构造输入的分析树分析树方法方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

16 11 语法制导定义 (Syntx-Directed Definition) 拓扑排序是有向无环图中的结点的一种排序 (m i m j ) = m i 先于 m j 由拓扑排序可以确定依赖图中属性的计算顺序 可保证由规则 b = f(c 1,, c k ) 计算 b 时, 属性 c i 已计算出来 翻译过程可以按如下步骤完成 首先根据文法构造输入的分析树 再由分析树构造属性依赖图 ( 因此依赖图是动态构建的 ) 分析树方法方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

17 11 语法制导定义 (Syntx-Directed Definition) 拓扑排序是有向无环图中的结点的一种排序 (m i m j ) = m i 先于 m j 由拓扑排序可以确定依赖图中属性的计算顺序 可保证由规则 b = f(c 1,, c k ) 计算 b 时, 属性 c i 已计算出来 翻译过程可以按如下步骤完成 首先根据文法构造输入的分析树 再由分析树构造属性依赖图 ( 因此依赖图是动态构建的 ) 对依赖图中的结点进行拓扑排序, 得到语义规则的计算顺序 按照计算顺序得到输入串的翻译分析树方法方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

18 11 语法制导定义 (Syntx-Directed Definition) D T 4 type in 5 L 6 int in 7 L 8, id 3 3 entry in 9 L 10, id 2 2 entry id 1 1 entry 结点 1,2,3 的属性 entry 由词法分析器提供 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

19 11 语法制导定义 (Syntx-Directed Definition) T D 4 type in 5 L 6 属性计算序号为 n 的结点属性记为 n 4 = integer 5 = 4 int in 7 L 8, id 3 3 entry ddtype(id 3 entry, 5 ) 7 = 5 ddtype(id 2 entry, 7 ) in 9 L 10, id 2 id 1 1 entry 2 entry 9 = 7 ddtype(id 1 entry, 9 ) 结点 1,2,3 的属性 entry 由词法分析器提供 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

20 11 语法制导定义 (Syntx-Directed Definition) 分析树方法缺点 若依赖图有环, 则失败 速度慢, 计算顺序是动态和即时确定的方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

21 11 语法制导定义 (Syntx-Directed Definition) 分析树方法缺点 若依赖图有环, 则失败 速度慢, 计算顺序是动态和即时确定的 如何改进? 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

22 11 语法制导定义 (Syntx-Directed Definition) 分析树方法缺点 若依赖图有环, 则失败 速度慢, 计算顺序是动态和即时确定的 如何改进? 基于规则的方法 : 在编译前, 手工或工具对产生式的语义规则进行分析, 得到计算顺序缺点 : 对依赖关系复杂的 SDD 很难事先确定计算顺序方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

23 11 语法制导定义 (Syntx-Directed Definition) 分析树方法缺点 若依赖图有环, 则失败 速度慢, 计算顺序是动态和即时确定的 如何改进? 基于规则的方法 : 在编译前, 手工或工具对产生式的语义规则进行分析, 得到计算顺序缺点 : 对依赖关系复杂的 SDD 很难事先确定计算顺序 忽略规则的方法 : 根据编译器生成工具的计算策略限定编译器设计者所提供的语义规则的形式缺点 : 限制了 SDD 的形式 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

24 12 S 属性定义的自下而上计算 以构造抽象语法树为例, 熟悉 S 属性定义及在自下而上分析过程中完成属性计算语法分析树 E E E N 3 * E N 5 + E N 8 抽象语法树 + * 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

25 12 S 属性定义的自下而上计算 mklef(id, entry): 建立标记为 id 的标识符结点, 该结点另一个域的值为 entry, 为符号表中该标识符条目的指针 产生式 语义规则 1 E E 1 + T Enptr = mknode( +, E 1 nptr, Tnptr) 2 E T Enptr = Tnptr 3 T T 1 F Tnptr = mknode(, T 1 nptr, Fnptr) 4 T F Tnptr = Fnptr 5 F (E) Fnptr = Enptr 6 F id Fnptr = mklef(id, identry) 7 F num Fnptr = mklef(num, numvl) 综合属性 nptr 是用来记住函数调用返回的指针 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

26 12 S 属性定义的自下而上计算 mklef(id, vl): 建立标记为 num 的整数结点, 该结点另一个域的值为 vl, 为该整数的值 产生式 语义规则 1 E E 1 + T Enptr = mknode( +, E 1 nptr, Tnptr) 2 E T Enptr = Tnptr 3 T T 1 F Tnptr = mknode(, T 1 nptr, Fnptr) 4 T F Tnptr = Fnptr 5 F (E) Fnptr = Enptr 6 F id Fnptr = mklef(id, identry) 7 F num Fnptr = mklef(num, numvl) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

27 12 S 属性定义的自下而上计算 mknode(op, left, right): 建立标记为 op 的算法结点,left 和 right 分别是左右子树的指针 产生式 语义规则 1 E E 1 + T Enptr = mknode( +, E 1 nptr, Tnptr) 2 E T Enptr = Tnptr 3 T T 1 F Tnptr = mknode(, T 1 nptr, Fnptr) 4 T F Tnptr = Fnptr 5 F (E) Fnptr = Enptr 6 F id Fnptr = mklef(id, identry) 7 F num Fnptr = mklef(num, numvl) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

28 12 S 属性定义的自下而上计算 考虑表达式 + 5 b, 构造注释分析树和抽象语法树 Enptr Enptr + Tnptr Tnptr Tnptr Fnptr Fnptr Fnptr id id num 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

29 12 S 属性定义的自下而上计算 考虑表达式 + 5 b, 构造注释分析树和抽象语法树 Enptr Enptr + Tnptr Tnptr + Tnptr Fnptr Fnptr Fnptr id id 指向符号表中 的入口 num num 5 id id 指向符号表中 b 的入口 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

30 12 S 属性定义的自下而上计算对于输入表达式 : + 5 b, 实际执行的函数调用如下 : p 1 = mklef(id, extry ) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

31 12 S 属性定义的自下而上计算对于输入表达式 : + 5 b, 实际执行的函数调用如下 : p 1 = mklef(id, extry ) p 2 = mklef(num, 5) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

32 12 S 属性定义的自下而上计算对于输入表达式 : + 5 b, 实际执行的函数调用如下 : p 1 = mklef(id, extry ) p 2 = mklef(num, 5) p 3 = mklef(id, entry b ) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

33 12 S 属性定义的自下而上计算对于输入表达式 : + 5 b, 实际执行的函数调用如下 : p 1 = mklef(id, extry ) p 2 = mklef(num, 5) p 3 = mklef(id, entry b ) p 4 = mknode(, p 2, p 3 ) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

34 12 S 属性定义的自下而上计算对于输入表达式 : + 5 b, 实际执行的函数调用如下 : p 1 = mklef(id, extry ) p 2 = mklef(num, 5) p 3 = mklef(id, entry b ) p 4 = mknode(, p 2, p 3 ) p 5 = mknode( +, p 1, p 4 ) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

35 12 S 属性定义的自下而上计算 综合属性可由自下而上的语法分析器在分析输入的同时计算 栈中增加一个域来保存文法符号的综合属性 归约时计算产生式头符号的综合属性 top top 1 top 2 Z Zz Y Yy X Xx stte vl 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

36 12 S 属性定义的自下而上计算 若产生式 A XYZ 的语义规则是 A = f(xx, Yy, Zz) 归约前, 属性 Zz 的值存在 stck[top]vl, 归约时,A 存在 stck[top 2]stte, 综合属性的值 A 放入 stck[top 2]vl, 然后 top := top 2 top top 1 top 2 Z Zz Y Yy X Xx stte vl 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

37 12 S 属性定义的自下而上计算 使用 LR 分析器实现计算器 产生式 语义规则 1 L E n Lvl = Evl 2 E E 1 + T Evl = E 1 vl + Tvl 3 E T Evl = Tvl 4 T T 1 F Tvl = T 1 vl Fvl 5 T F Tvl = Fvl 6 F (E) Fvl = Evl 7 F digit Fvl = digitlexvl 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

38 12 S 属性定义的自下而上计算 使用 LR 分析器实现计算器 产生式 语义动作 1 L E n {print(stck[top 1]vl); top = top 1;} 2 E E 1 + T {stck[top 2]vl = stck[top 2]vl + stck[top]vl; top = top 2;} 3 E T 4 T T 1 F {stck[top 2]vl = stck[top 2]vl stck[top]vl; top = top 2;} 5 T F 6 F (E) {stck[top 2]vl = stck[top 1]vl; top = top 2;} 7 F digit 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

39 12 S 属性定义的自下而上计算 翻译表达式 n 输入 stte vl 所用产生式 n n n F 8 F digit +5 2n T 8 T F n E + T F F digit n E + T T T F L 18 L E n 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

40 13 L 属性定义的自上而下计算 若考虑继承属性呢? 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

41 13 L 属性定义的自上而下计算 L 属性定义如果语法制导定义 D 的每个产生式 A X 1 X 2 X n 的每条语义规则 R 满足 : 1 R 计算的属性是 A 的综合属性, 或 2 R 计算的是 X j 的继承属性, 且仅依赖 X i<j 的属性和 A 的继承属性则称 D 是 L 属性的 S 属性定义属于 L 属性定义方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

42 13 L 属性定义的自上而下计算 L 属性定义产生式语义规则 1 D TL Lin = Ttype 2 T int Ttype = integer 3 T rel Ttype = rel 4 L L 1, id L 1 in = Lin ddtype(identry, Lin) 5 L id ddtype(identry, Lin) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

43 13 L 属性定义的自上而下计算 L 属性定义 产生式 语义规则 1 D TL Lin = Ttype 2 T int Ttype = integer 3 T rel Ttype = rel 4 L L 1, id L 1 in = Lin ddtype(identry, Lin) 5 L id ddtype(identry, Lin) 第 1 行的语义规则 Lin = Ttype 归约时对 Lin 进行赋值, 但在此之前, 第 4 行和第 5 行中需要用到 Lin 的值 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

44 13 L 属性定义的自上而下计算 可以使用翻译方案来描述语义规则的执行时机方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

45 13 L 属性定义的自上而下计算 可以使用翻译方案来描述语义规则的执行时机 翻译方案的语义动作放在括号 {} 内方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

46 13 L 属性定义的自上而下计算 可以使用翻译方案来描述语义规则的执行时机 翻译方案的语义动作放在括号 {} 内 可以插入到产生式右部的任何位置方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

47 13 L 属性定义的自上而下计算 可以使用翻译方案来描述语义规则的执行时机 翻译方案的语义动作放在括号 {} 内 可以插入到产生式右部的任何位置如果 A α{c}β, 则语义动作 C 的执行 1 在 α 的推导 ( 或向 α 的归约 ) 结束之后, 2 在 β 的推导 ( 或向 β 的归约 ) 开始之前方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

48 13 L 属性定义的自上而下计算翻译方案 : E TR R ddop T {print(ddoplexeme); } R 1 ε T num {print(numvl); } 把加和减算符的中缀表达式翻译成后缀表达式的如果输入是 , 该翻译方案的输出是 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

49 13 L 属性定义的自上而下计算 只有综合属性时, 为每条语义规则建议一个赋值动作, 把动作放在产生式最右端即可得到翻译方案方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

50 13 L 属性定义的自上而下计算 只有综合属性时, 为每条语义规则建议一个赋值动作, 把动作放在产生式最右端即可得到翻译方案 如果含有继承属性, 则方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

51 13 L 属性定义的自上而下计算 只有综合属性时, 为每条语义规则建议一个赋值动作, 把动作放在产生式最右端即可得到翻译方案 如果含有继承属性, 则 产生式右部符号的继承属性必须在先于这个符号的动作中计算 ( 插在该符号的左端位置 ) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

52 13 L 属性定义的自上而下计算 只有综合属性时, 为每条语义规则建议一个赋值动作, 把动作放在产生式最右端即可得到翻译方案 如果含有继承属性, 则 产生式右部符号的继承属性必须在先于这个符号的动作中计算 ( 插在该符号的左端位置 ) 一个动作不能引用该动作右边符号的综合属性方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

53 13 L 属性定义的自上而下计算 只有综合属性时, 为每条语义规则建议一个赋值动作, 把动作放在产生式最右端即可得到翻译方案 如果含有继承属性, 则 产生式右部符号的继承属性必须在先于这个符号的动作中计算 ( 插在该符号的左端位置 ) 一个动作不能引用该动作右边符号的综合属性 左部非终结符号的综合属性只能在它所引用的所有属性都计算完成后才能计算, 放在产生式最右端方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

54 13 L 属性定义的自上而下计算 L 属性定义 产生式 语义规则 1 S B Bps = 10 Sht = Bht 2 B B 1 B 2 B 2 ps = Bps B 1 ps = Bps Bht = mx(b 1 ht, B 2 ht) 3 B B 1 sub B 2 B 2 ps = shrink(bps) B 1 ps = Bps Bht = disp(b 1 ht, B 2 ht) 4 B text Bht = texth Bps ps 是 B 的继承属性, 且仅依赖产生式头的继承属性 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

55 13 L 属性定义的自上而下计算产生式 1 S B 语义规则 Bps = 10 Sht = Bht 翻译方案 S {Bps = 10; } B {Sht = Bht} 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

56 13 L 属性定义的自上而下计算 产生式 语义规则 2 B B 1 B 2 B 1 ps = Bps B 2 ps = Bps Bht = mx(b 1 ht, B 2 ht) 翻译方案 B {B 1 ps = Bps; } B 1 {B 2 ps = Bps; } B 2 {Bht = mx(b 1 ht, B 2 ht); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

57 13 L 属性定义的自上而下计算 产生式 3 B B 1 sub B 2 语义规则 B 1 ps = Bps B 2 ps = shrink(bps) Bht = disp(b 1 ht, B 2 ht) 翻译方案 B {B 1 ps = Bps; } B 1 sub {B 2 ps = shrink(bps); } B 2 {Bht = disp(b 1 ht, B 2 ht); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

58 13 L 属性定义的自上而下计算产生式 4 B text 语义规则 Bht = texth Bps 翻译方案 B text {Bht = texth Bps; } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

59 13 L 属性定义的自上而下计算 文法中存在左递归的 SDD 产生式 语义规则 1 E E 1 + T Enptr = mknode( +, E 1 nptr, Tnptr) 2 E T Enptr = Tnptr 3 T T 1 F Tnptr = mknode(, T 1 nptr, Fnptr) 4 T F Tnptr = Fnptr 5 F (E) Fnptr = Enptr 6 F id Fnptr = mklef(id, identry) 7 F num Fnptr = mklef(num, numvl) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

60 13 L 属性定义的自上而下计算 存在左递归的翻译方案 产生式 语义动作 1 E E 1 + T {Enptr = mknode( +, E 1 nptr, Tnptr); } 2 E T {Enptr = Tnptr; } 3 T T 1 F {Tnptr = mknode(, T 1 nptr, Fnptr)} 4 T F {Tnptr = Fnptr; } 5 F (E) {Fnptr = Enptr; } 6 F id {Fnptr = mklef(id, identry); } 7 F num {Fnptr = mklef(num, numvl); } 需要消除左递归 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

61 13 L 属性定义的自上而下计算 考虑一般性的左递归问题 : A A 1 Y {A = g(a 1, Yy); } A X {A = f(xx); } 1 Vl A() 2 { 3 A 1 = A(); 4 Yy = Y(); 5 A = g(a 1, Yy); 6 7 return A; 8 } 1 Vl A() 2 { 3 Xx = X(); 4 A = f(xx); 5 6 return A; 7 } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

62 13 L 属性定义的自上而下计算 消除左递归之后 : A XR R YR ε 1 Vl R(R in) 2 { 3 R out = R in; 4 return R out; 5 } 1 Vl A() 2 { 3 Xx = X(); 4 /* A = f(xx) */ 5 R in = f(xx); 6 R out = R(R in); 7 A = R out; 8 return A; 9 } 1 Vl R(R in) 2 { 3 Yy = Y(); 4 /*A = g(a 1,Yy);*/ 5 R 1 in = g(rin, Yy); 6 R 1 out = R(R 1 in); 7 Rout = R 1 out; 8 return R out; 9 } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

63 13 L 属性定义的自上而下计算消除左递归之后 A X {Rin = f(xx); } R {A = Rout; } R Y {R 1 in = g(rin, Yy); } R 1 {Rout = R 1 out; } R ε {Rout = Rin; } 消除左递归之前 A A 1 Y {A = g(a 1, Yy); } A X {A = f(xx); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

64 13 L 属性定义的自上而下计算使用 i 代替 in, s 代替 out, 换名之后 A X {Ri = f(xx); } R {A = Rs; } R Y {R 1 i = g(ri, Yy); } R 1 {Rs = R 1 s; } R ε {Rs = Ri; } 消除左递归之前 A A 1 Y {A = g(a 1, Yy); } A X {A = f(xx); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

65 13 L 属性定义的自上而下计算 语法制导的预测翻译器构造算法 输入 : 语法制导的翻译方案 输出 : 语法制导翻译器的代码 方法 : 修改预测分析器的构造技术 为每个非终结符 A 构造一个函数 1 A 的每个继承属性声明为该函数的一个形式参数 2 A 的综合属性作为函数返回值 3 在函数中为 A 产生式中的其他每个文法符号的每个属性声明一个局部变量 4 A 函数的代码框架和预测分析过程一致 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

66 13 L 属性定义的自上而下计算 语法制导的预测翻译器构造算法 输入 : 语法制导的翻译方案 输出 : 语法制导翻译器的代码 方法 : 修改预测分析器的构造技术 与产生式相关联的代码按如下方法生成 : 1 对于有属性 x 的终结符号 X, 把 x 的值保存在为 Xx 声明的变量中, 然后调用匹配过程 2 对于非终结符号 B, 产生赋值 c = B(b 1,, b k ), b i 是对应 B 继承属性的变量,c 是代表 B 综合属性的变量 3 对于每个语义动作, 把代码复制到函数体中, 把对属性的引用改成相应的局部变量的引用 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

67 13 L 属性定义的自上而下计算 基于如下翻译方案构造预测翻译器 E T {Ri = Tnptr; } R {Enptr = Rs; } R +T {R 1 i = mknode( +, Ri, Tnptr); } R 1 {Rs = R 1 s; } R ε {Rs = Ri; } T F {Wi = Fnptr; } W {Tnptr = Ws; } W F {W 1 i = mknode(, Wi, Fmptr); } W 1 {Ws = W 1 s; } W ε {Ws = Wi; } F (E) {Fnptr = Enptr; } F id {Fnptr = mklef(id, identry); } F num {Fnptr = mklef(num, numvl); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

68 13 L 属性定义的自上而下计算为每个非终结符构造函数 syntxtreenode E() syntxtreenode R(syntxTreeNode i) syntxtreenode T() syntxtreenode W(syntxTreeNode i) syntxtreenode F() 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

69 13 L 属性定义的自上而下计算 1 syntxtreenode* R ( syntxtreenode* i) { 2 syntxtreenode * nptr, *i1, *s1, *s; 3 chr ddoplexeme; 4 if (lookhed == '+') { 5 ddoplexeme = lexvl; 6 mtch('+'); 7 nptr = T(); 8 i1 = mknode( ddoplexeme, i, nptr); 9 s1 = R(i1); 10 s = s1; 11 } 12 else s = i; 13 return s; 14 } i 对应继承属性,s 对应综合属性 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

70 13 L 属性定义的自上而下计算考虑如下文法 : D L : T T integer chr L L, id id 在第一个产生式中, 非终结符 L 从它右边的 T 获得类型信息, 因此基于此文法的 SDD 不是 L 属性定义的, 需修改文法方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

71 13 L 属性定义的自上而下计算 修改后新的文法 : D id L L, id L : T T integer chr 此时, 类型作为 L 的综合属性 Ltype, 可以有翻译方案 : D id L {ddtype(identry, Ltype); } L, id L 1 {Ltype = L 1 type; ddtype(identry, L 1 type); } L : T {Ltype = Ttype; } T integer {Ttype = integer; } T chr {Ttype = chr; } 此翻译方案仅含有综合属性 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

72 14 L 属性定义的自下而上计算 在自下而上分析框架中实现 L 属性定义的方法, 使用自下而上的方法来完成任何可以用自上而下方式完成的翻译过程方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

73 14 L 属性定义的自下而上计算 通过修改文法将语义动作变换到产生式的右端 引入新的 ( 标记 ) 非终结符号 M 和产生式 M ε 每个嵌入动作由不同的非终结符号 M 代表 如果 M 在某个产生式 T α {c} β 中替换了语义动作 c, 对 c 进行修改得到 c, 并且将 c 关联到 M ε 上, 动作 c : 将动作 c 需要的属性作为 M 的继承属性进行复制 按照 c 中的方法计算各属性, 但是将计算得到的这些属性作为 M 的综合属性 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

74 14 L 属性定义的自下而上计算 将如下含有嵌入动作的翻译方案变换成无嵌入动作的方案 : E TR R +T {print( + ); } R 1 T {print( ); } R 1 ε T num {print(numvl); } 变换成 : E TR R +TMR 1 TNR 1 ε T num {print(numvl); } M ε {print( + ); } N ε{print( ); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

75 14 L 属性定义的自下而上计算考虑如下翻译方案 ( 部分 ): S while ( 1 {L 1 = new(); L 2 = new(); Cflse = Snext; Ctrue = L 2 ; } C ) 2 {S 1 next = L 1 ; } S 1 {Scode = lbel L 1 Ccode lbel L 2 S 1 code; } 用 M 替换第 1 个语义动作, 用 N 替换第 2 个语义动作方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

76 14 L 属性定义的自下而上计算在分析以 while 开始的串之前某个符号 Snext stte vl top 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

77 14 L 属性定义的自下而上计算 top 将空串归约为 M 之后栈的情况 M Ctrue, Cflse, L 1, L 2 ( while 某个符号 Snext stte vl 执行的代码 : L 1 = new(); L 2 = new(); Ctrue = L 2 ; Cflse = stck[top 3]next 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

78 14 L 属性定义的自下而上计算 top 将空串归约为 N 之后栈的情况 N S 1 next ) C Ccode M Ctrue, Cflse, L 1, L 2 ( while 某个符号 Snext stte vl 执行的代码 :S 1 next = stck[top 3]L 1 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

79 内容提要 1 语法制导翻译语法制导定义 S 属性定义的自下而上计算 L 属性定义的自上而下计算 L 属性定义的自下而上计算 2 中间代码生成中间语言声明语句赋值语句布尔表达式和控制流语句

80 21 中间语言 抽象语法树和 C 语言都可以作为源程序的一种中间表示 中间表示 -1: 后缀表示后缀表示表达式 E 的后缀表示可以定义如下 : 如果 E 是变量或者常数, 那么 E 的后缀表示就是其自身,x vs x, 12 vs 12 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

81 21 中间语言 抽象语法树和 C 语言都可以作为源程序的一种中间表示 中间表示 -1: 后缀表示后缀表示表达式 E 的后缀表示可以定义如下 : 如果 E 是变量或者常数, 那么 E 的后缀表示就是其自身,x vs x, 12 vs 12 如果 E 是形式为 E 1 op E 2 的表达式, 其中 op 是任意二元算符, 则 E 的后缀表示是 E 1 E 2 op, 其中 E 1 和 E 2 分别是 E 1 和 E 2 的后缀表示, vs 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

82 21 中间语言 抽象语法树和 C 语言都可以作为源程序的一种中间表示 中间表示 -1: 后缀表示后缀表示 表达式 E 的后缀表示可以定义如下 : 如果 E 是变量或者常数, 那么 E 的后缀表示就是其自身,x vs x, 12 vs 12 如果 E 是形式为 E 1 op E 2 的表达式, 其中 op 是任意二元算符, 则 E 的后缀表示是 E 1 E 2 op, 其中 E 1 和 E 2 分别是 E 1 和 E 2 的后缀表示, vs 如果 E 是 (E 1 ), 则 E 的后缀表示是 E 1 的后缀表示 (1 2) 3 vs 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

83 21 中间语言 中间表示 -2: 有向无环图 (Directed Acyclic Grph, DAG) ssign + * d c + * d c uminus b () 抽象语法树 ssign + + * d c uminus b (b) 有向无环图图 : = ( b + c d) + (c d) 的图形表示方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

84 21 中间语言 中间表示 -2: 有向无环图 (Directed Acyclic Grph, DAG) 产生式 语义规则 1 S id = E Snptr = mknode( ssign, mklef(id, identry), Enptr) 2 E E 1 + E 2 Enptr = mknode( +, E 1 nptr, E 2 nptr) 3 E E 1 E 2 Enptr = mknode(, E 1 nptr, E 2 nptr) 4 E E 1 Enptr = mkunode( uminus, E 1 nptr) 5 E (E 1 ) Enptr = E 1 nptr 6 E id Enptr = mklef(id, identry) 有向无环图也可以使用上述 SDD 进行构造 构造结点的函数检查是否有相同结点存在 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

85 21 中间语言 中间表示 -3: 三地址代码, 每条指令 / 语句的一般形式为 x = y op z 其中,x, y, z 是名字 常数或临时变量,op 代表算符 每条指令通常含有 3 个地址 : 两个运算对象地址和一个结果地址 x + y z 将被翻译成 t 1 = y z t 2 = x + t 1 其中 t 1 和 t 2 是临时名字 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

86 21 中间语言 ssign + * d c + * d c uminus b () 抽象语法树 t 1 = b t 2 = c d t 3 = t 1 + t 2 t 4 = c d t 5 = t 3 + t 4 = t 5 (b) 对应抽象语法树的代码方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

87 21 中间语言 ssign + + * d c uminus b (c) 有向无环图 t 1 = b t 2 = c d t 3 = t 1 + t 2 t 4 = t 3 + t 2 = t 4 (d) 对应有向无环图的代码方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

88 21 中间语言常见三地址指令形式 : 形如 x = y op z 的赋值指令, 其中 op 是双目算术 / 逻辑运算符,x, y, z 是地址方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

89 21 中间语言常见三地址指令形式 : 形如 x = y op z 的赋值指令, 其中 op 是双目算术 / 逻辑运算符,x, y, z 是地址 形如 x = op y 的赋值指令, 其中 op 是单目运算符 : 单目减 逻辑非 转换运算方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

90 21 中间语言常见三地址指令形式 : 形如 x = y op z 的赋值指令, 其中 op 是双目算术 / 逻辑运算符,x, y, z 是地址 形如 x = op y 的赋值指令, 其中 op 是单目运算符 : 单目减 逻辑非 转换运算 形如 x = y 的复制指令, 它把 y 的值赋给 x 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

91 21 中间语言常见三地址指令形式 : 形如 x = y op z 的赋值指令, 其中 op 是双目算术 / 逻辑运算符,x, y, z 是地址 形如 x = op y 的赋值指令, 其中 op 是单目运算符 : 单目减 逻辑非 转换运算 形如 x = y 的复制指令, 它把 y 的值赋给 x 无条件转移指令 goto L, 下一步要执行的指令是带标号 L 的三地址指令方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

92 21 中间语言 常见三地址指令形式 : 形如 x = y op z 的赋值指令, 其中 op 是双目算术 / 逻辑运算符,x, y, z 是地址 形如 x = op y 的赋值指令, 其中 op 是单目运算符 : 单目减 逻辑非 转换运算 形如 x = y 的复制指令, 它把 y 的值赋给 x 无条件转移指令 goto L, 下一步要执行的指令是带标号 L 的三地址指令 形如 if x goto L 的条件转移指令, 如果 x 为真时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

93 21 中间语言常见三地址指令形式 : 形如 if Flse x goto L 的条件转移指令, 如果 x 为假时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

94 21 中间语言常见三地址指令形式 : 形如 if Flse x goto L 的条件转移指令, 如果 x 为假时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令 形如 if x relop y goto L 的条件转移指令, 对 x 和 y 应用一个关系运算符 ( 如 :<, ==, >=) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

95 21 中间语言常见三地址指令形式 : 形如 if Flse x goto L 的条件转移指令, 如果 x 为假时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令 形如 if x relop y goto L 的条件转移指令, 对 x 和 y 应用一个关系运算符 ( 如 :<, ==, >=) 形如 prm x 的指令进行参数传递方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

96 21 中间语言常见三地址指令形式 : 形如 if Flse x goto L 的条件转移指令, 如果 x 为假时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令 形如 if x relop y goto L 的条件转移指令, 对 x 和 y 应用一个关系运算符 ( 如 :<, ==, >=) 形如 prm x 的指令进行参数传递 形如 cll p, n 的指令进行过程调用,n 表示实参个数方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

97 21 中间语言常见三地址指令形式 : 形如 if Flse x goto L 的条件转移指令, 如果 x 为假时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令 形如 if x relop y goto L 的条件转移指令, 对 x 和 y 应用一个关系运算符 ( 如 :<, ==, >=) 形如 prm x 的指令进行参数传递 形如 cll p, n 的指令进行过程调用,n 表示实参个数 形如 y = cll p, n 的指令进行进行函数调用方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

98 21 中间语言 常见三地址指令形式 : 形如 if Flse x goto L 的条件转移指令, 如果 x 为假时, 下一步将执行带有标号 L 的指令 ; 否则下一步执行序列中的后一条指令 形如 if x relop y goto L 的条件转移指令, 对 x 和 y 应用一个关系运算符 ( 如 :<, ==, >=) 形如 prm x 的指令进行参数传递形如 cll p, n 的指令进行过程调用,n 表示实参个数形如 y = cll p, n 的指令进行进行函数调用返回指令 return y, 其中 y 表示返回值 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

99 21 中间语言常见三地址指令形式 : x = y[i], 将位置 y 之后的第 i 个存储单元中存放的值赋给 x 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

100 21 中间语言常见三地址指令形式 : x = y[i], 将位置 y 之后的第 i 个存储单元中存放的值赋给 x x[i] = y, 将位置 y 中存放的值赋给 x 之后的第 i 个存储单元中方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

101 21 中间语言 常见三地址指令形式 : x = y[i], 将位置 y 之后的第 i 个存储单元中存放的值赋给 x x[i] = y, 将位置 y 中存放的值赋给 x 之后的第 i 个存储单元中 x = &y, 将 x 的右值设置为 y 的左值 变量 : [L, R] L ε R ε 常量 : [L, R] L = ε Pre :{ x : [L x, R y ], y : [L y, R y ] } x = &y Post :{ x : [L x, L y ], y : [L y, R y ] } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

102 21 中间语言 常见三地址指令形式 : x = y[i], 将位置 y 之后的第 i 个存储单元中存放的值赋给 x x[i] = y, 将位置 y 中存放的值赋给 x 之后的第 i 个存储单元中 x = &y, 将 x 的右值设置为 y 的左值 x = y, 将 x 的右值设置为存储在位置 y 中的值 变量 : [L, R] L ε R ε 常量 : [L, R] L = ε Pre :{ x : [L x, R y ], y : [L y, R y ], z : [L z, R z ], L z = R y } x = y Post :{ x : [L x, R z ], y : [L y, R y ], z : [L z, R z ] } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

103 21 中间语言 常见三地址指令形式 : x = y[i], 将位置 y 之后的第 i 个存储单元中存放的值赋给 x x[i] = y, 将位置 y 中存放的值赋给 x 之后的第 i 个存储单元中 x = &y, 将 x 的右值设置为 y 的左值 x = y, 将 x 的右值设置为存储在位置 y 中的值 x = y, 将 y 的右值放入 x 指向的存储单元中 变量 : [L, R] L ε R ε 常量 : [L, R] L = ε Pre :{ x : [L x, R x ], y : [L y, R y ], z : [L z, R z ], L z = R x } x = y Post :{ x : [L x, R x ], y : [L y, R y ], z : [L z, R y ] } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

104 21 中间语言 中间表示 -4: 静态单赋值形式 (Sttic Single-Assignment Form, SSA) 所有赋值指令都是对不同变量的赋值 使用不同的下标区分变量 p = + b q = p c p = q d p = e p q = p + q p 1 = + b q 1 = p 1 c p 2 = q 1 d p 3 = e p 2 q 2 = p 3 + q 1 () 三地址代码 (b) 静态单赋值形式 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

105 21 中间语言同一个变量可能在不同的控制流路径上被赋值 : 1 if( flg) 2 x = -1; 3 else 4 x = 1; 5 6 y = x * ; 如果在条件语句的两个分支上使用不同的名字, 那么在赋值 y = x 中应该为 x 使用哪个名字呢? 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

106 21 中间语言 1 if( flg) 2 x 1 = -1; 3 else 4 x 2 = 1; 5 6 x 3 = ϕ(x 1, x 2 ); 7 y = x 3 * ; 使用 ϕ 函数 如果控制流通过条件为真的部分, ϕ(x 1, x 2 ) 返回 x 1 ; 否则返回 x 2 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

107 22 声明语句 过程中声明的翻译方案,P 是一个表示过程的文法符号 : P {offset = 0} D; S D D; D D id : T {enter(idlexeme, Ttype, offset); offset = offset + Twidth; } T integer {Ttype = integer; Twidth = 4; } T rel {Ttype = rel; Twidth = 8; } T rry[num] of T 1 {Ttype = rry(numvl, T 1 type); Twidth = numvl T 1 width; } T T 1 {Ttype = pointer(t 1 type); Twidth = 4; } 其中全局变量 offset 表示相对地址 ;enter 表示建立符号表条目 ;width 表示字节数目 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

108 22 声明语句 过程嵌套的声明翻译方案,tS 为符号表栈 ;os 为相对地址栈 : P M D; S {ddwidth(top(ts), top(os)); pop(ts); pop(os); } M ε D D 1 ; D 2 D proc id; N D 1 ; S D id : T N ε ddwidth: 把当前的相对位置存入符号表 ; 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

109 22 声明语句 过程嵌套的声明翻译方案,tS 为符号表栈 ;os 为相对地址栈 : P M D; S {ddwidth(top(ts), top(os)); pop(ts); pop(os); } M ε {t = mktble(nil); push(t, ts); push(0, os); } D D 1 ; D 2 D proc id; N D 1 ; S D id : T N ε mktble: 建立新的符号表, 新符号表中含有上一层的符号表的指针 ; 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

110 22 声明语句 过程嵌套的声明翻译方案,tS 为符号表栈 ;os 为相对地址栈 : P M D; S {ddwidth(top(ts), top(os)); pop(ts); pop(os); } M ε {t = mktble(nil); push(t, ts); push(0, os); } D D 1 ; D 2 D proc id; N D 1 ; S D id : T {t = top(ts); ddwidth(t, top(os)); pop(ts); pop(os); enterproc(top(ts), idlexeme, t); } N ε enterproc: 为子过程建立符号表条目 ; 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

111 22 声明语句 过程嵌套的声明翻译方案,tS 为符号表栈 ;os 为相对地址栈 : P M D; S {ddwidth(top(ts), top(os)); pop(ts); pop(os); } M ε {t = mktble(nil); push(t, ts); push(0, os); } D D 1 ; D 2 D proc id; N D 1 ; S D id : T N ε {t = top(ts); ddwidth(t, top(os)); pop(ts); pop(os); enterproc(top(ts), idlexeme, t); } {enter(top(ts), idlexeme, Ttype, top(os)); top(os) = top(os) + Twidth; } enter: 建立新的符号表条目 ; 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

112 22 声明语句 过程嵌套的声明翻译方案,tS 为符号表栈 ;os 为相对地址栈 : P M D; S {ddwidth(top(ts), top(os)); pop(ts); pop(os); } M ε {t = mktble(nil); push(t, ts); push(0, os); } D D 1 ; D 2 D proc id; N D 1 ; S D id : T {t = top(ts); ddwidth(t, top(os)); pop(ts); pop(os); enterproc(top(ts), idlexeme, t); } {enter(top(ts), idlexeme, Ttype, top(os)); top(os) = top(os) + Twidth; } N ε {t = mktble(top(ts)); push(t, ts); push(0, os); } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

113 22 声明语句 记录类型表达式 T record L D end {Ttype = record(top(ts)); Twidth = top(os); pop(ts); pop(os); } L ε {t = mktble(nil); push(t, ts); push(0, os); } record: 记录类型构造器方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

114 23 赋值语句 在处理赋值语句中的名字时, 需要在符号表中查找它的定义, 获取它的属性, 然后在三地址代码中使用它在符号表中位置的指针 S id := E E E 1 + E 2 {p = lookup(idlexeme); if(p! = nil) emit(p, =, Eplce); else error; } {Eplce = newtemp(); emit(eplce, =, E 1 plce, +, E 2 plce); } E 的属性 plce 用来记住符号表条目的地址, 函数 newtemp 新建一个临时变量的名字, 把名字存入符号表, 并返回该条目的地址 ; 过程 emit 将其参数写到输出文件中, 其参数构成一条三地址指令 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

115 23 赋值语句 在处理赋值语句中的名字时, 需要在符号表中查找它的定义, 获取它的属性, 然后在三地址代码中使用它在符号表中位置的指针 S id := E {p = lookup(idlexeme); if(p! = nil) emit(p, =, Eplce); else error; } E E 1 + E 2 {Eplce = newtemp(); emit(eplce, =, E 1 plce, +, E 2 plce); } E E 1 {Eplce = newtemp(); emit(eplce, =, uminus, E 1 plce); } E (E 1 ) {Eplce = E 1 plce; } E id {p = lookup(idlexeme); if(p! = nil) Eplce = p; else error; } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

116 23 赋值语句 一维数组的元素一般是顺序存放, 如果每个数组元素的宽度是 w, 那么一维数组 A 的第 i 个元素从地址 bse + (i low) w (1) 开始, 其中 low 是下标的下界,bse 是分配给该数组的地址, 即 bse 是 A[low] 的地址, 表达式 (1) 可以重写为 : i w + (bse low w) 则可以在编译时完成表达式后一部分的计算, 从而减少运行时的计算方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

117 23 赋值语句 二维数组 : 行为主, 一行接一行 列为主, 一列接一列 对于一个 2 3 的数组 A 以行为主 A[1, 1] A[1, 2] A[1, 3] 以列为主 A[1, 1] A[1, 2] A[1, 3] A[2, 1] A[2, 2] A[2, 3] A[2, 1] A[2, 2] A[2, 3] 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

118 23 赋值语句 以行为主的二维数组,A[i, j] 的地址可以由公式 : bse + ((i low 1 ) n 2 + (j low 2 )) w 计算, 其中 low 1 和 low 2 分别是这两维的下界,n 2 是第二维的大小 ; 如果 high 2 是 j 的上界, 则 n 2 = high 2 low 若 i, j 都是编译时不能确定的值, 则公式可以重写为 ((i n 2 ) + j) w + (bse ((low 1 n 2 ) + low 2 ) w) 该表达式的后一项可以在编译时计算 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

119 23 赋值语句 k 维数组引用 A[i 1, i 2,, i k ] 的三地址代码需要对表达式 ( ((i 1 n 2 + i 2 ) n 3 + i 3 ) ) n k + i k 进行计算, 使用递推过程 : e 1 = i 1 来完成, 直到 m = k 为止 e m = e m 1 n m + i m 除了第一个下标表达式 i 1 外, 对其他下标表达式, 需要产生乘和加两条三地址指令 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

120 23 赋值语句含有数组表达式的赋值文法, 如果 L 是简单名字, 则产生正常的赋值 ; 否则产生由 L 的两个属性确定的存储单元的索引赋值 : S L := E {if(loffset == null) emit(lplce, =, Eplce); else emit(lplce, [, Loffset, ], =, Eplce); } Loffset 为空时, 表示简单名字方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

121 23 赋值语句数学表达式的代码和之前的一样 : E E 1 + E 2 {Eplce = newtemp(); emit(eplce, =, E 1 plce, +, E 2 plce); } E (E 1 ) {Eplce = E 1 plce; } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

122 23 赋值语句如果 E 产生数组元素 L, 可用索引得到存储单元 Lplce[Loffset] 的内容 : E L {if(l, offset = null) Eplce = Lplce; else begin Eplce = newtemp(); emit(eplce, =, Lplce, [, Loffset, ] ); end} 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

123 23 赋值语句 L 产生数组表达式时,Lplce 为新的临时变量赋值为不变部分已经计算好的值 ;Loffset 对应需要动态计算的部分 : L Elist] {Lplce = newtemp(); emit(lplce, =, invrint(elistrry)); Loffset = newtemp(); emit(loffset, =, Elistplce,, width(elistrry)); } Elist 的综合属性 rry 用于传递符号表中数组名条目的指针 函数 invrint(rry) 从 rry 所指向的符号表中的条目读取静态可计算的值 函数 width(rry) 从 rry 所指向的符号表中的条目读取单个数组元素的字节数量 Elistplce 用来保存根据 Elist 的下标表达式计算的值 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

124 23 赋值语句 L 产生简单名字时 : L id {Lplce = idplce; Loffset = null; } offset 为空表示简单名字方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

125 23 赋值语句 多于一个下标表达式的情况 : Elist Elist 1, E {t = newtemp(); m = Elist 1 ndim + 1; emit(t, =, Elist 1 plce,, limit(elist 1 rry, m)); emit(t, =, t, +, Eplce); Elistrry = Elist 1 rry Elistplce = t; Elistndim = m; } Elistndim 记录已经分析过的下标表达式的个数 limit(rry, j) 返回 rry 所指向的数组中的第 j 维的大小 Elist 1 plce 对应递推公式中的 e m 1 Elistplce 对应递推公式中的 e m 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

126 23 赋值语句最后, 对应递推公式中 m = 1 的情况 Elist id[e {Elistplce = Eplce; Elistndim = 1; Elistrry = idplce; } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

127 23 赋值语句 Lplce = x Loffset = null := S Eplce = t 4 x Elistplce = y Elistndim = 1 Elistrry = A Lplce = t 2 Loffset = t 3 Elistplce = t 1 Elistndim = 2 Elistrry = A ], Eplce = z A [ Eplce = y Lplce = y Loffset = null y Lplce = z Loffset = null 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94 z 赋值语句 x := A[y, z] 的注释分析树其中 A 是 的数组

128 23 赋值语句 赋值语句 x := A[y, z] 的三地址指令序列如下 : t 1 = y 20 t 1 = t 1 + z t 2 = c /* 预先计算好的数组静态地址 */ t 3 = t 1 4 /* 每个元素有 4 个字节 */ t 4 = t 2 [t 3 ] x = t 4 w = 4, n 1 = 10, n 2 = 20 ((i n 2 ) + j) w + (bse ((low 1 n 2 ) + low 2 ) w) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

129 23 赋值语句 考虑存在类型转换的情况 x = y + i j x,y:rel,i,j:integer t 1 = i int j t 2 = inttorel t 1 t 3 = y rel + t 2 x = t 3 1 E E 1 + E 2 2 { 3 E plce = newtemp() ; 4 i f (E 1 type==i n t e g e r && E 2 type==i n t e g e r ) begin 5 emit (E plce, =,E 1 plce, i n t+,e 2 plce ) ; 6 E type = i n t e g e r ; 7 end e l s e i f (E 1 type==i n t e g e r && E 2 type==r e l ) begin 8 u = newtemp() ; 9 emit (u, =, i n t t o r e l,e 1 plce ) ; 10 emit (E plce, =,u, r e l+,e 2 plce ) ; 11 E type = r e l ; 12 end e l s e 13 } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

130 24 布尔表达式和控制流语句 布尔表达式文法 : B B or B B nd B not B (B) E relop E True Flse 其中,or 和 nd 是左结合的,or 的优先级最低, 然后是 nd, 最后是 not 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

131 24 布尔表达式和控制流语句 短路计算, 完成部分计算就可以知道真假, 把 B 1 or B 2 定义成 if B 1 then True else B 2 把 B 1 nd B 2 定义成 if B 1 then B 2 else Flse 如果 B i 有副作用 ( 如修改某个全局变量 ), 则完全计算和短路计算的结果可能有差异方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

132 24 布尔表达式和控制流语句 短路计算, 完成部分计算就可以知道真假, 把 B 1 or B 2 定义成 把 B 1 nd B 2 定义成 if B 1 then True else B 2 if B 1 then B 2 else Flse 如果 B i 有副作用 ( 如修改某个全局变量 ), 则完全计算和短路计算的结果可能有差异 翻译语句 if(x < 100 or x > 200 nd x! = y) x = 0; 1 if x<100 goto L 2 2 if Flse x>200 goto L 1 3 if Flse x!=y goto L 1 4 L 2 : x=0 5 L 1 : 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

133 24 布尔表达式和控制流语句考虑控制流语句的文法 : S if B then S 1 if B then S 1 else S 2 while B do S 1 S 1 ; S 2 其中 B 是布尔表达式 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

134 24 布尔表达式和控制流语句 继承属性 Btrue/Bflse 是 B 为真 / 假时, 控制流应该转向的标号 SDD 中的符号 是串连接运算符 函数 newlbel 用于产生新标号 产生式 S if B then S 1 控制流语句的语法制导定义 语义规则 Btrue Bflse S 1 next Scode = newlbel() = Snext = Snext = Bcode gen(btrue, : ) S1code 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

135 24 布尔表达式和控制流语句 标号 Snext 是继承属性 控制流语句的语法制导定义 产生式 S if B then S 1 else S 2 语义规则 Btrue Bflse S1next S2next Scode = newlbel() = newlbel() = Snext; = Snext; = Bcode gen(btrue, : ) S 1 code gen( goto, Snext) gen(bflse, : ) S 2 code 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

136 24 布尔表达式和控制流语句 begin 是局部变量, 存放 while 语句的第一条指令的标号 控制流语句的语法制导定义 产生式 S while B do S 1 语义规则 begin Btrue Bflse S 1 next Scode = newlbel() = newlbel() = Snext = begin = gen(begin, : ) Bcode gen(btrue, : ) S 1 code gen( goto, begin) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

137 24 布尔表达式和控制流语句 最后, 串行组合语句 控制流语句的语法制导定义 产生式 语义规则 S S 1 ; S 2 S 2 next = Snext() S 1 next = newlbel() Scode = S 1 code gen(s 1 next, : ) S 2 code 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

138 24 布尔表达式和控制流语句 布尔表达式的语法制导定义 B True Bcode = gen( goto, Btrue) B Flse Bcode = gen( goto, Bflse) B E 1 relop E 2 Bcode = E 1 code E 2 code gen( if, E 1 plce, relopop, E 2 plce, goto, Btrue) gen( goto, Bflse) 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

139 24 布尔表达式和控制流语句 布尔表达式的语法制导定义 B (B 1 ) B 1 true = Btrue B 1 flse = Bflse Bcode = B 1 code B not B 1 B 1 true = Bflse B 1 flse = Btrue Bcode = B 1 code 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

140 24 布尔表达式和控制流语句 布尔表达式的语法制导定义 B B 1 nd B 2 B 1 true = newlbel() B 1 flse = Bflse B 2 true = Btrue B 2 flse = Bflse Bcode = B 1 code gen(b 1 true, : ) B 2 code B B 1 or B 2 B 1 true = Btrue B 1 flse = newlbel() B 2 true = Btrue B 2 flse = Bflse Bcode = B 1 code gen(b 1 flse, : ) B 2 code 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

141 24 布尔表达式和控制流语句 考虑布尔表达式 < b or c < d nd e < f, 则可以翻译得到如下代码 1 if <b goto L true 2 goto L 1 3 L 1 : if c<d goto L 2 4 goto L flse 5 L 2 : if e<f goto L true 6 goto L flse 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

142 24 布尔表达式和控制流语句 考虑语句 : 1 while <b do 2 if c<d then 3 x:=y+z 4 else 5 x:=y-z 代码 : 1 L begin : 2 B code 3 L true B : 4 S 1 code 5 goto L begin 其中 : B = < b S 1 = if c < d then x := y + z else x := y z 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

143 24 布尔表达式和控制流语句 1 while <b do 2 if c<d then 3 x:=y+z 4 else 5 x:=y-z 1 L begin : 2 if <b goto L true B 3 goto L flse B 4 L true B : 5 S 1 code 6 goto L begin 7 L flse B : 其中 : L flse B 是 while 语句的下一条语句的标号 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

144 24 布尔表达式和控制流语句 1 while <b do 2 if c<d then 3 x:=y+z 4 else 5 x:=y-z 1 L begin : 2 if <b goto L true B 3 goto L flse B 4 L true B : 5 IfB code 6 L true IfB : 7 Sub S1 code 8 goto L begin 9 L flse IfB : 10 Sub S2 code 11 goto L begin 12 L flse B : IfB 是 c < d;sub S1 是 x := y + z;sub S2 是 x := y z 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

145 24 布尔表达式和控制流语句 1 while <b do 2 if c<d then 3 x:=y+z 4 else 5 x:=y-z 1 L begin : 2 if <b goto L true B 3 goto L flse B 4 L true B : 5 if c<d goto L true IfB 6 goto L flse IfB 7 L true IfB : 8 Sub S1 code 9 goto L begin 10 L flse IfB : 11 Sub S2 code 12 goto L begin 13 L flse B : 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

146 24 布尔表达式和控制流语句 1 while <b do 2 if c<d then 3 x:=y+z 4 else 5 x:=y-z 1 L begin : 2 if <b goto L true B 3 goto L flse B 4 L true B : 5 if c<d goto L true IfB 6 goto L flse IfB 7 L true IfB : 8 t 1 =y + z 9 x=t 1 10 goto L begin 11 L flse IfB : 12 Sub S2 code 13 goto L begin 14 L flse B : 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

147 24 布尔表达式和控制流语句 1 while <b do 2 if c<d then 3 x:=y+z 4 else 5 x:=y-z 1 L begin : 2 if <b goto L true B 3 goto L flse B 4 L true B : 5 if c<d goto L true IfB 6 goto L flse IfB 7 L true IfB : 8 t 1 =y + z 9 x=t 1 10 goto L begin 11 L flse IfB : 12 t 2 =y - z 13 x=t 2 14 goto L begin 15 L flse B : 其实 L flse B = while 语句的下一条语句的标号 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

148 24 布尔表达式和控制流语句 考虑如下 switch-cse 语句 : 1 switch (E) { 2 cse V 1 : S 1 3 cse V 2 : S cse V n 1 : S n 1 6 defult: S n 7 } 计算表达式 E 的值在 n 1 个常量 V 1,V 2,,V n 1 中寻找和 E 的值相同的常量若有匹配的常量 V i, 则执行 S i ; 否则执行 S n 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

149 24 布尔表达式和控制流语句 1 E 的代码, 其中 t 用来存储 E 的值 2 if t!=v 1 goto L 1 3 code for S 1 4 goto next 5 L 1 : if t!=v 2 goto L 2 6 code for S 2 7 goto next 8 L 2 : 9 10 L n 2 : if t!=v n 1 goto L n 1 11 code for S n 1 12 goto next 13 L n 1 : code for S n 14 next: 问题 : 在处理分支的时是不知道下一个分支的 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

150 24 布尔表达式和控制流语句 1 E 的代码, 其中 t 用来存储 E 的值 2 goto test 3 L 1 : code for S 1 4 goto next 5 L 2 : code for S 2 6 goto next 7 8 L n 1 :code for S n 1 9 goto next 10 L n : code for S n 11 goto next 12 test:if t=v 1 goto L 1 13 if t=v 2 goto L if t=v n 1 goto L n 1 16 goto L n 17 next: 1 cse t V 1 L 1 2 cse t V 2 L cse t V n 1 L n 1 5 cse t t L n 6 next: cse 三地址指令 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

151 24 布尔表达式和控制流语句 考虑如下包含过程调用语句的文法 S id(elist) EList Elist, E Elist E 1 prm E 1 plce 2 prm E 2 plce 3 4 prm E n plce 5 cll id plce, n 翻译方案 ( 使用队列 q 存储参数 ) S id(elist) { 对 q 中每个 Eplce, 执行 emit( prm, Eplce); 然后 emit( cll, idplce, len(q));} EList Elist, E { 把 Eplce 放入队列 q 末尾 ; } Elist E { 初始化队列 q, 把 Eplce 放入 q 末尾 ; } 方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94

152 小结 语法制导定义的概念和形式,S 属性及 L 属性定义 语法制导翻译方案, 语义动作可以放在产生式体的任何位置 抽象语法树的例子 基于语法制导定义和翻译生成中间代码 三地址码比较重要方徽星 ( 扬州大学信息工程学院 ) 语法制导翻译及中间代码生成 / 94