再版前言

Transcription

1 第七章中间代码生成 在第一章已经介绍, 编译器的前端把源程序翻译成中间表示, 后端从中间代码产生目标代码, 与目标语言有关的细节尽可能限制在后端 使用独立于机器的中间形式的好处是 : 1. 再目标 (retargeting) 比较容易 把针对新机器的后端加到现成的前端上, 可以得到另一种机器的编译器 2. 独立于机器的代码优化器可用于这种中间表示 第九章将介绍这种代码优化 因此, 虽然可以把源程序直接翻译并生成目标代码, 但编译器一般都采用中间语言 本章将用第四章的语法制导定义方法来说明程序设计语言的结构怎样被翻译成中间形式 为简单起见, 假定对源程序的分析和静态检查已经完成, 如图 7.1 表示的那样 本章大多数语法制导定义可以用第四章的技术在自下而上或自上而下的分析期间实现, 所以, 如果愿意的话, 中间代码生成可以在分析阶段完成 记号流 分析器 静 态 检查器 中间代码 生成器 中间代码 代 码 生成器 图 7.1 中间代码生成器的位置 7.1 中间语言 4.2 节介绍的语法树是一种图形化的中间表示, 本节再介绍几种常用的中间表示 : 后缀 表示 其它图形表示和三地址代码 本章主要使用三地址代码 从程序设计语言的各种结 构产生三地址代码的语义规则类似于产生语法树或后缀表示的那些规则 后缀表示表达式 E 的后缀表示可以如下递归定义 : (1) 如果 E 是变量或常数, 那么 E 的后缀表示就是 E 本身 (2) 如果 E 是形式为 E 1 ope 2 的表达式, 其中 op 是任意的二元算符, 那么 E 的后缀表示是 E 1 E 2 op, 其中 E 1 和 E 2 分别是 E 1 和 E 2 的后缀表示 (3) 如果 E 是形式为 (E 1 ) 的表达式, 那么 E 1 的后缀表示也是 E 的后缀表示 后缀表示不需要括号, 因为算符的位置及其运算对象的个数使得后缀表示仅有一种解释 例如,(8 4) + 2 的后缀表示是 , 而 8 (4 + 2) 的缀表示 上面的定义很容易拓广到含一元算符的表达式 后缀表示的最大优点是便于计算机处理表达式 利用一个栈, 自左向右扫描表达式的后缀表示 每碰到运算对象, 就把它压进栈 ; 每碰到运算符, 就从栈顶取出相应个数的运算对象进行计算, 再将结果压进栈 最终的结果留在栈顶 后缀表示也可以拓广到表示赋值语句和控制语句, 但很难用栈来描述它的计算 后缀表示又叫做逆波兰表示, 它是波兰逻辑学家卢卡西维奇发明的 图形表示语法树是一种图形化的中间表示, 它是分析树的浓缩表示, 描绘了源程序在语义上的层次结构 后缀表示是语法树的一种线性表示, 例如, 赋值语句 a := ( b + c d ) + c d 的语法树在图 7.2(a), 对应的后缀表示为 1

2 a b uminus c d + c d + assign assign assign a + a + + uminus c c d b (a) 语法树 d + uminus c b (b) dag d 图 7.2 a := ( b + c d ) + c d 的图形表示 有向无环图 (directed acyclic grahp, 简称 dag) 也是一种中间表示 和语法树相比, 它 以更紧凑的方式给出同样的信息, 因为公共子表达式标识出来了 见图 7.2(b), 公共子表达 式 c d 不只一个父结点 在考虑代码优化时, 有向无环图比语法树更适用 表 7.1 的语法制导定义构造赋值语句的语法树, 它是 4.2 节构造表达式语法树的语法制 导定义的一个拓展, 其中 mkunode(op, child) 是构造一元运算结点的函数 这里用的是二义 文法, 假定算符的结合性和优先关系与通常的一样, 虽然我们没有把它们加入文法 这个 定义从输入 a := ( b + c d ) + c d 构造出图 7.2 (a) 的语法树 ( 按照该定义, 叶结点的形式应 该像图 4.5 的叶结点那样 ) 表 7.1 构造赋值语句语法树的语法制导定义 产生式 语 义 规 则 S id :=E S.nptr := mknode( assign, mkleaf (id, id.entry), E.nptr) E E 1 +E 2 E.nptr := mknode( +, E 1.nptr, E 2.nptr) E E 1 E 2 E.nptr := mknode(, E 1.nptr, E 2.nptr) E E 1 E.nptr := mkunode( uminus, E 1.nptr) E (E 1 ) E.nptr := E 1.nptr F id E.nptr := mkleaf (id, id.entry) 我们修改构造结点的函数, 仍然用这个语法制导定义, 可以构造出有向无环图 如果构造结点的函数首先检查是否已经有相同的结点存在, 如果有就返回先前构造的这种结点的指针而不是构造新结点, 那么就可以得到 dag 这个语法制导定义从输入 a := ( b + c d ) + c d 构造出的 dag 见图 7.2 (b) 三地址代码 三地址代码是一般形式为 x := y op z 的语句序列, 其中 x y 和 z 是名字 常数或编译器产生的临时变量,op 代表算符, 如定点 或浮点算术算符, 或是对布尔类型数据操作的逻辑算符等 之所以叫做三地址代码, 是因 为每个语句通常包含三个地址, 两个运算对象的地址和一个结果的地址 因为每个语句的 右边只有一个算符, 所以源语言的表达式 x + y z 翻译成的三地址语句序列是 t 1 := y z t 2 := x + t 1 其中 t 1 和 t 2 是编译器产生的临时名字 用临时名字保存中间结果使得较容易为三地址代码 2

3 重新安排计算次序, 在后缀表示上要改变计算次序是很困难的 三地址代码是语法树或 dag 的一种线性表示, 其中新增加的临时名字对应图的内部结 点 图 7.2 的语法树和 dag 由图 7.3 的三地址语句序列表示 t 1 := b t 2 := c d t 1 := b t 2 := c d t 3 := t 1 + t 2 t 3 := t 1 + t 2 t 4 := c d t 4 := t 3 + t 2 t 5 := t 3 + t 4 a := t 4 a := t 5 (a) 语法树的代码 图 7.3 对应图 7.2 的树和 dag 的三地址代码 (b)dag 的代码 三地址语句类似于汇编代码 语句可以有符号标号, 而且可以有控制流语句 下面是 本书常用的三地址语句 : (1) 形式为 x := y op z 的赋值语句, 其中 op 是二元算术或逻辑运算 (2) 形式为 x := op y 的赋值语句, 其中 op 是一元运算 一元运算主要包括一元减, 逻辑否定, 移位运算和类型转换运算 (3) 形式为 x := y 的复写语句 (4) 无条件转移 goto L 标号为 L 的语句是下一步将要执行的三地址语句 (5) 形如 if x relop y goto L 的条件转移 这种指令用于 x 和 y 的关系运算 (< = 和 >= 等 ), 如果关系成立, 执行标号为 L 的语句 ; 否则, 与通常的顺序一样, 执行 if x relop y goto L 的下一个三地址语句 (6) param x 和 call p, n 用于过程调用, 其中 n 表示实参个数 return y 用于过程返 回,y 代表返回值, 它也可以不出现 过程调用的典型使用是 param x 1 param x 2... param x n call p, n 这些语句是过程调用 p(x 1, x 2,..., x n ) 的中间代码 (7) 形式为 x := y[i] 和 x[i] := y 的索引赋值 第一个语句把 y 的存储单元以上第 i 个存 储单元的值赋给 x 第二个语句把 y 的值赋给 x 的存储单元以上第 i 个存储单元 在这些指 令中,x,y 和 i 都代表数据对象 (8) 形式为 x := &y,x := y 和 x := y 的地址和指针赋值 第一个语句把 y 的存储单元 地址赋给 x, 可以猜想 y 是名字 ( 或临时变量 ), 它表示像 a 和 A[ i, j ] 这样有左值的表达 式,x 是指针变量或临时变量, 即 x 的右值是某个对象的左值 在第二个语句中,y 是右值 为存储单元地址的指针变量或临时变量,x 的右值等于那个存储单元的内容 最后, x := y 把 y 的右值置入 x 指向的存储单元 选译适当的算符集合是中间代码设计的重要问题 很显然, 它必须大到足以实现源语 言的操作 较小的算符集合易于在新的目标机器上实现, 但是, 较小的算符集合可能迫使 前端对源语言的某些运算产生较长的三地址语句序列, 此时如果想产生好代码的话, 优化 器和代码生成器的工作会比较艰巨 三地址语句是中间代码的抽象形式 在编译器中, 三地址语句可以用记录来实现, 这 3

4 种记录有算符域和运算对象域, 不同的编译器对这种记录的设计可能是不一样的 7.2 声明语句 在分析过程或程序块的声明序列时, 我们为局部名字建立符号表条目, 并为它分配存储单元 这样, 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息, 相对地址是对静态数据区基址的偏移或是对活动记录中某个基址的偏移 前端分配地址时必须想到目标机器, 目标机器的指令系统可能偏爱数据对象和它们地址的某种安排 在这里我们忽略数据对象的对齐问题 过程中的声明 C,Java,Pascal 和 Fortran 这些语言的语法允许一个过程中的所有声明集中在一起处理 在这种情况下, 我们可用全局变量, 例如 offset, 来记住下一个可用的相对地址 在图 7.4 的翻译方案中, 非终结符 P 产生形式为 id:t 的声明序列, 再产生可执行语句 S, 本节先考虑声明序列 在检查第一个声明之前,offset 置为 0 每次为一个名字分配存储单元时, 它的偏移等于 offset 的当前值, 同时 offset 增加由该名字指示的数据对象的宽度 过程 enter(name, type, offset) 为名字 name 建立符号表条目, 该名字的类型是 type, 它在数据区的相对地址是 offset 我们用综合属性 type 和 width 表示非终结符的类型和宽度 ( 该类型的对象所需的存储单元数 ) 属性 type 代表从基本类型 integer 和 real 应用类型构造器 pointer 和 array 构造的类型表达式 如果类型表达式用图形表示, 那么属性 type 可以是一个指针, 指向代表类型表达式的结点 在图 7.4 中, 整数宽度是 4, 实数宽度是 8, 数组的宽度由每个元素的宽度乘以数组元素的个数而得到, 每个指针的宽度假定为 4 在 Pascal 和 C 中, 在看见指针所指对象的类型之前可以先看见指针, 由于所有的指针通常都有同样的宽度, 因此这里的存储分配是简单的 P {offset := 0} D S D D ; D D id : T {enter ( id.name, T.type, offset); offset := offset + T.width } T integer {T.type := integer; T.width := 4 } T real {T.type := real; T.width := 8 } T array [ num ] of T 1 {T.type := array (num.val, T 1.type); T.width := num.val T 1.width} T T 1 {T.type := pointer (T 1.type); T.width := 4 } 图 7.4 计算被声明名字的类型和相对地址 作用域信息的保存 现在我们考虑像 Pascal 这样允许过程嵌套的语言 为简单起见, 我们仅讨论无参过程, 4

5 并且认为过程不会递归 我们所讨论语言的文法如下 : P D S D D ; D id : T proc id ; D ; S (7.1) 在这样的语言里, 局部于每个过程的名字仍然可以用图 7.4 的方式来分配相对地址, 每 个过程建立单独的符号表 这样, 每个过程要有自己的符号表指针和自己的 offset 在一边扫描一边建立符号表和完成存储分配的情况下, 当碰到过程嵌套时, 对外围过 程声明的处理需要暂时停止, 等被嵌套过程处理完后再继续 我们可以用两个栈分别保存 尚未处理完的过程的符号表指针和它们的 offset, 这两个栈顶的元素分别是正在处理的过程 的符号表指针和 offset 按照这种方式, 基于文法 (7.1) 的翻译方案见图 7.5, 其中 T( 类型 ) 产生式的语义动 作和图 7.4 的一致, 我们略去 ; 非终结符 S( 语句 ) 的语义动作在 7.3 节开始介绍 图 7.5 的语义动作根据下面的操作定义 : (1)mktable(previous) 建立新的符号表, 并返回新符号表的指针 变元 previous 指向先 前建立的符号表, 可以猜想, 这是直接外围过程的符号表 指针 previous 放在新建符号表 的首部, 首部除了包括直接外围过程的符号表的指针外, 还包含所有局部变量所需存储单 元的总数等信息 (2)enter(table, name, type, offset) 在 table 指向的符号表中为变量名 name 建立新条目 和前面一样,enter 把类型 type 和相对地址 offset 置于该条目的域中 如果要说的详细一些 的话, 本过程还需要完成检查名字是否重复定义等事情 (3)addwidth(table, width) 把符号表 table 所有条目的累加宽度记录在该符号表的首部 (4)enterproc(table, name, newtable) 在 table 指向的符号表中为过程名 name 建立新条 目 变元 newtable 指向过程 name 本身的符号表 我们再对图 7.5 的语义动作做一些解释 对于过程声明 D proc id ; D 1 ; S, 在扫描 D 1 之前, 需要建立新的符号表, 并让它指向直接外围过程的符号表, 然后将 D 1 中声明的名字 的条目建立在该新符号表中, 同时根据新的 offset 进行存储分配 这些动作是通过标记非终 结符 N 的动作完成的 在结束内嵌过程的扫描, 执行 D proc id ; N D 1 ; S 右部的动作时, 由 D 1 产生的所有声明的宽度在 offset 栈的顶上, 用 addwidth 把它记录在符号表中, 然后 tblptr ( 符号表指针 ) 栈和 offset 栈的顶元弹出, 再把过程名 id 的条目建立在直接外围过程的符 号表中 这些都结束后, 继续分析外围过程的声明 非终结符 M 的动作完成一些初始化的工作, 它用操作 mktable(nil) 建立最外层作用域的 符号表, 并用两个 push 操作来完成 tblptr 栈和 offset 栈的初始化 P M D S {addwidth (top (tblptr), top (offset) ); M pop(tblptr); pop (offset) } {t := mktable (nil); D D 1 ; D 2 D proc id ; N D 1 ; S {t := top(tblptr); push(t, tblprt); push (0, offset) } addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(top(tblptr), id.name, t) } D id : T {enter(top(tblptr), id.name, T.type, top(offset) ); top(offset) := top(offset) + T.width } N {t := mktable(top(tblptr) ); 5

6 push(t, tblptr); push(0, offset) } 图 7.5 处理嵌套过程中的声明 按图 7.5 的翻译方案, 为图 6.17 的 Pascal 程序生成的符号表在图 7.6 给出 过程的符号表之间用双向链连接, 从这个双向链可以知道过程的嵌套关系, 例如, 过程 readarray, exchange 和 quicksort 的符号表逆向指向直接外围过程 sort 的符号表, 而 sort 的符号表中有 3 个指针指向这 3 个过程 当碰到名字的引用性出现时, 若在本过程的符号表中找不到这个名字, 那么就需要到它的外围过程的符号表中去找, 逆向指针可用于这个目的 若语言有预定义的标准标识符 ( 程序员可以重新定义其含义 ), 如 Pascal 语言的 integer,true 等, 那么主过程符号表的逆向指针应该指向标准标识符的符号表, 以便确定程序员没有定义的标识符是不是一个标准标识符 我们实际上已经解释了 7.3 节用到的符号表查找函数 lookup 如果允许过程递归的话, 图 7.5 的翻译方案需要修改 在产生式 D proc id ; N D 1 ; S 的语义动作中, 该过程 id 是在把该过程体处理完后再进入符号表的, 这样, 在 S 中若有直接递归调用, 在符号表查找该 id 时会报告没有定义 若是有参过程, 对构造符号表来说, 形式参数的处理和其它局部名字的处理没有很大的区别, 但是填在条目中的属性, 如存储分配信息等, 会有些区别 如果是一遍扫描的编译器, 每个过程被扫描后, 它的目标代码已经生成, 若无其它需要, 该过程的符号表可以释放, 不必再保留和指向外围过程的符号表 这时编译器可以将符号表组织成一个栈, 碰到一个过程声明时将该过程声明的名字进栈, 该过程被扫描结束时将它的符号全部弹出栈 sort 空表头 a x readarray 指向 readarray exchange 指向 exchange quicksort i readarrary 表头 exchange 表头 k v quicksort 表头 partition i j 表头 partition 记录的域名 图 7.6 嵌套过程的符号表 在图 7.4 文法上增加下面一个产生式使得非终结符 T 除了可以产生基本类型, 指针和数 6

7 组外, 还能产生记录类型 : T record D end 在图 7.7 的翻译方案中, 语义动作强调了记录类型中域的存储安排同过程的局部名字在活动记录中安排的相似性 因为过程定义不影响图 7.5 的宽度计算, 因此我们把上面的产生式放宽到允许过程定义出现在记录类型里面, 这只是为了翻译方案的简洁易懂 T record L D end {T.type := record (top(tblptr) ); T.width := top(offset); pop(tblptr); pop(offset) } L {t := mktable (nil); push(t, tblprt); push(0, offset) } 图 7.7 为记录中的域名建立符号表 看见关键字 record 后, 标记非终结符 L 的动作为域名建立新的符号表 该符号表的指针压进 tblptr 栈, 相对地址 0 压入 offset 栈 产生式 D id: T 的动作把域名 id 的信息加入记录类型的符号表 在记录类型的域分析完后,offset 栈顶保存记录类型中所有对象的总宽度 在图 7.7 中,end 后的动作把总宽度作为综合属性 T.width 返回 把构造器 record 作用于该记录的符号表指针可以得到 T.type 在 7.3 节, 这个指针用来恢复记录类型中域名的名字, 类型和相对地址 记录类型定义和过程声明的处理还是有区别的 处理记录类型时并未真正为哪个变量分配了存储单元, 只是决定了该类型的宽度和每个域在记录存储空间中的相对位置 在处理记录类型的变量声明时, 才真正在活动记录中为该记录类型的变量分配存储单元 7.3 赋值语句 在本节中, 表达式的类型可以是整型 实型 数组和记录 为使得我们的翻译方案简 洁, 我们采用二义的表达式文法, 并选择加运算作为二元运算的代表 作为赋值语句翻译 成三地址指令的一部分, 我们说明怎样从符号表中查找名字 怎样访问数组元素和怎样访 问记录的域 T0:=1+2 T1:=T0+2 T2:=T0+T 符号表的中名字在 7.1 节介绍中间语言时, 为直观起见, 我们让名字本身直接出现在中间语言中, 但是应该把名字理解为它们在符号表中位置的指针 实际在处理源程序时, 当在赋值语句中遇到名字的时候, 我们需要在符号表中查找它的定义, 获得它的属性, 然后在生成的三地址代码中, 使用它在符号表中位置的指针 S id := E {p := lookup(id.name); if p nil then emit ( p, :=, E.place) 7

8 else error } E E 1 + E 2 {E.place := newtemp; emit (E.place, :=, E 1.place, +, E 2.place) } E E 1 {E.place := newtemp; emit (E.place, :=, uminus, E 1.place) } E (E 1 ) {E.place := E 1.place } E id {p := lookup(id.name); if p nil then E.place := p else error } 图 7.8 为赋值语句产生三地址代码的翻译方案 在图 7.8 的翻译方案中, 名字 id 的 name 属性代表组成该名字的字符序列,lookup(id.name) 用于根据名字的拼写检查符号表中是否存在该名字的条目 如果有, 返回该条目的指针, 否则 lookup 返回 nil, 以表示没有找到 是否有过程嵌套, 会影响 lookup 函数的设计, 但不影响图 7.8 的翻译方案使用该函数来查符号表 E 的属性 place 用来记住符号表条目的地址 函数 newtemp 用来产生一个新的临时变量的名字, 把该名字也存入符号表, 并返回该条目的地址 过程 emit 将其参数写到输出文件上, 就像 Pascal 语言的 writeln 一样 emit 的参数构成一个三地址语句 如果碰到像 p.info 这样对记录的域的访问, 如何查表找到所需的属性 首先, 从过程的名字表中可以找到 p, 它应该是记录类型的变量 根据 节我们可以知道,p 的类型是 record(tblprt),tblprt 是该记录类型的符号表, 从该表中可以找到 info 的条目, 从而我们可以得到所需的属性 临时名字的重新使用 我们使用了这样的假定 : 每当需要临时变量时,newtemp 产生新的临时名字 这在优化 编译器中尤其有用, 在第九章我们会看到这样做是合理的 但是, 大量临时变量会增加编 译时符号表管理的负担, 在非优化编译器中也会增加运行时临时数据占的空间 我们可以 根据临时变量的生存期特征, 修改 newtemp 函数, 使临时变量可以重新使用 在语法制导的翻译期间, 大量的临时变量由图 7.8 这样的语义动作产生 例如,E E 1 + E 2 的动作产生的代码的一般形式为 : 计算 E 1 到 t 1 计算 E 2 到 t 2 t 3 := t 1 + t 2 从综合属性 E.place 的动作可以看出,t 1 和 t 2 在程序的其它地方并不引用 这些临时变量的 生存期像配对括号那样嵌套或并列 事实上, 计算 E 2 时用的所有临时变量的生存期都包含 在 t 1 的生存期中 所以有可能修改 newtemp, 使得它在过程的数据区域中用一个小数组来保 存临时数据, 好像它是一个栈一样 为简单起见, 假定仅处理整数 我们使用一个计数器 c, 它的初值为 0 每当临时名字 作为运算对象使用时,c 减少 1; 每当要求产生新的临时名字时, 使用 $c, 并把 c 加 1 注 意这个临时数据的 栈 在运行时并没有压栈和退栈的操作, 虽然编译器可能碰巧会产生 在 栈顶 存或取临时数据的指令 例 7.1 考虑赋值语句 8

9 x := a b + c d e f 表 7.2 给出了 newtemp 被修改后, 由图 7.8 的语义动作产生的三地址语句序列 这张表还包 含了每个语句生成中间代码后 c 的 当前值 例如计算 $0 $1 时,c 的值减小到 0, 所以 用 $0 来保存结果 有些场合, 例如循环语句, 临时变量的赋值和 / 或引用不只一次, 这时临时变量不能按 上述后进先出的方式指派名字 由于它们很少出现, 可以对所有这样的临时值单独指派名 字 表 7.2 基于临时变量生成期特征的三地址代码 语 句 c 的值 0 $0 := a b 1 $1 := c d 2 $0 := $0 + $1 1 $1 := e f 2 $0 := $0 $1 1 x := $ 数组元素的地址计算一个数组的所有元素通常按一定的次序存于连续的存储块中, 这样可以迅速访问这些元素 一维数组的元素一般是顺序存放, 如果每个数组元素的宽度是 w, 那么一维数组 A 的第 i 个元素从地址 base + ( i low ) w (7.2 ) 开始, 其中 low 是下标的下界,base 是分配给该数组的地址 ( 可能是活动记录中的相对地址 ), 即 base 是 A[ low ] 的地址 如果把表达式 (7.2) 重写成 i w + (base low w) 那么我们可以在编译时完成该表达式后一部分的计算, 从而减少了运行时的计算 二维数组通常用两种形式之一存储, 行为主 ( 一行接一行 ) 或列主为 ( 一列接一列 ) Fortran 语言使用列为主形式,Pascal 语言和 C 语言都使用行为主形式 对于一个 2 3 的 A 数组, 若是行为主, 其元素的存放次序是 : A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3] 若是列为主, 其元素的存放次序是 : A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 在行为主的情况下, 因为 A[i, j] 等价于 A[i][j], 因此可以说是各个数组 A[i] 依次连续存放 在行为主的两维数组情况下,A[i 1, i 2 ] 的地址可以由公式 base + ( (i 1 low 1 ) n 2 + (i 2 low 2 ) ) w 计算, 其中 low 1 和 low 2 分别是这两维的下界,n 2 是第二维的大小 即, 如果 high 2 是 i 2 值的上界, 那么 n 2 = high 2 low 假定 i 1 和 i 2 是编译时不能知道的值, 我们可以把上面表达式重写成 ( (i 1 n 2 ) + i 2 ) w + (base ( (low 1 n 2 ) + low 2 ) w) (7.3 ) 同样, 该表达式的后一项可以在编译时计算 可以推广行为主或列为主的形式到多维数组 行为主形式的存储可以这样理解, 当朝高地址扫描存储块时, 最右边的下标变化最快, 就像里程计上的数字 表达式 (7.3) 的推 9

10 广使得 A[i 1, i 2,..., i k ] 的地址表达式如下 : ( ( ( (i 1 n 2 + i 2 ) n 3 + i 3 ) ) n k + i k ) w + base ( ( ( (low 1 n 2 + low 2 ) n 3 + low 3 ) ) n k + low k ) w (7.4 ) 因为对所有的 j,n j = high j low j + 1 是固定的,(7.4) 第二行的项可以在编译时分析数组声明时计算, 存于符号表的 A 条目中 列为主的形式是相反的布局, 最左边的下标变化最快 某些语言允许数组的大小在过程调用时动态指定, 这种数组在运行栈上的分配在 6.2 节已经讨论了, 其元素的访问公式和固定大小的数组相同, 但由于上下界在编译时不知道, 因此地址计算全部在运行时完成 数组元素地址计算的翻译方案 根据 (7.4) 式知道,k 维数组引用 A[i 1, i 2,, i k ] 的三地址代码主要是完成 ( ( (i 1 n 2 + i 2 ) n 3 + i 3 ) ) n k + i k (7.5) 的计算, 然后乘以 w, 再加上 (7.4) 式第 2 行的值 (7.5) 式的值可以由递推计算来完成 e 1 i 1 e m e m 1 n m + i m (7.6) 一直到 m = k 为止 根据 (7.6) 的递推计算, 除了第一个下标表达式 i 1 外, 对其它每一个下标表达式, 需 要产生乘和加两个三地址语句 ( 除了下标表达式本身值计算的三地址语句外 ), 因此在处 理下标表达式时需要访问符号表中 A 的条目, 以得到 A 各维的大小 如果用有下列产生式 L id [ Elist ] id Elist Elist, E E 的非终结符 L 取代图 7.8 中 id, 那么数组引用可以出现在赋值语句中 如果仅用综合属性, 在处理 Elist E 和 Elist Elist, E 时, 我们访问不到符号表中 A 的条目, 因为这是数组 id 的属性 加标记非终结符也解决不了 为了解决这个问题, 我们将产生式重写为 L Elist ] id Elist Elist, E id [E 即数组名和最左边一个下标表达式连在一起 这个文法虽然不直观, 但是从下面的翻译方 案可以知道它能解决我们的问题 我们使用 Elist 的综合属 array 来传递符号表中数组名条目的指针 我们还使用 Elist.ndim 来记录已分析过的下标表达式的个数 函数 limit(array, j) 返回 n j, 它是该数组 (array 指向 它的符号表条目 ) 第 j 维的大小 函数 base(array) 和 invariant(array) 分别从符号表条目中取 (7.4) 式第二行 base 的值和除 base 以外部分的值 最后,Elist.place 指示临时变量, 该变 量保存根据 Elist 的下标表达式计算的值 左值 L 有两个属性,place 和 offset 当 L 是简单名字时,L.place 是该名字的符号表条 目指针,L.offset 是 null, 后者表示该左值是一个简单名字而不是数组元素引用 和图 7.8 一样, 非终结符 E 有 place 属性, 并且含义一样 我们将语义动作加到下面文法上 : (1) S L := E (2) E E + E (3) E (E ) (4) E L (5) L Elist ] (6) L id 10

11 (7) Elist Elist, E (8) Elist id [ E 和没有介绍数组元素引用时的表达式一样, 三地址代码由调用过程 emit 产生 如果 L 是简单名字, 产生正常的赋值 ; 否则产生对由 L 的两个属性确定的存储单元的索引赋值 : (1) S L := E {if L.offset = null then / L 是简单变量 / emit (L.place, :=, E.place) else emit (L.place, [, L.offset, ], :=, E.place) } 算术表达式的代码和图 7.8 的完全一样 : (2) E E 1 + E 2 {E.place := newtemp; emit (E.place, :=, E 1.place, +, E 2.place) } (3) E (E 1 ) {E.place := E 1.place } 如果 E 产生数组元素 L, 则需要 L 的右值, 可用索引得到存储单元 L.place [L.offset] 的内容 : (4) E L {if L.offset = null then / L 是简单变量 / E.place := L.place else begin E.place := newtemp; emit (E.place, :=, L.place, [, L.offset, ] ) end } L.place 和 L.offset 都是新的临时变量, 前者对应 (7.4) 式的第二项 ; 后者保存 w 乘以 Elist.place 的值, 对应 (7.4) 的第一项 : (5) L Elist ] {L.place := newtemp; emit (L.place, :=, base(elist.array),, invariant(elist.array) ); L.offset := newtemp; emit (L.offset, :=, Elist.place,, w) } offset 为空时表示简单名字 : (6) L id {L.place := id.place; L.offset := null } 当看见下一个下标表达式时, 使用递推公式 (7.6) 在下面的动作中,Elist 1.place 对应 (7.6) 的 e m -1,Elist.place 对应 e m 如果 Elist 1 有 m 1 个成分 那么产生式左边的 Elist 有 m 个成分 : (7) Elist Elist 1, E{t := newtemp; m := Elist 1.ndim + 1; emit (t, :=, Elist 1.place,, limit(elist 1.array, m) ); emit (t, :=, t, +, E.place); Elist.array := Elist 1.array; Elist.place := t; Elist.ndim := m} 下面的 E.place 保存表达式 E 的值, 也是 (7.6) 式 m = 1 时的值 : (8) Elist id [ E {Elist.place := E.place; Elist.ndim := 1; Elist.array := id.place } 例 7.2 设 A 是 的数组,n 1 =10 且 n 2 = 20, 取 w = 4 赋值语句 x := A[ y, z ] 的注 11

12 释分析树如图 7.9 所示 该赋值语句翻译成下列三地语句序列 t 1 := y 20 t 1 := t 1 + z t 2 :=A 84 t 3 := 4 t 1 t 4 := t 2 [t 3 ] x := t 4 对每个变量, 我们已用它的名字代替了 id.place S L.place := x L.offset := null x := E.place := t 4 L.place := t 2 L.offset := t 3 Elist.place := t 1 Elist.ndim := 2 Elist.array := A ] Elist.place := y Elist.ndim := 1 Elist.array := A A [, E.place := y L.place := y L.offset := null E.place := z L.place := z L.offset := null z y 图 7.9 x := A[ y, z ] 的注释分析树 类型转换到目前为止的中间代码生成, 我们忽略了可能有的数据对象的类型转换操作 考虑上述赋值语句的文法, 假定有整数和实数两个类型, 必要时整数可转为实数 我们直接使用在 5.3 节已经熟悉的属性 E.type, 它的值是 real 或 integer 我们还忽略类型错误的检查, 因为它在第五章已讨论过了 E E + E 和大多数其它产生式的语义动作都可以修改成必要时产生 x := inttoreal y 的三地址语句, 它的作用是把整数 y 转换成值相等的实数, 再赋给 x, 我们还必须给算符一个标记, 用以标明这是定点还是浮点算术运算 产生式 E E 1 + E 2 的完整语义动作列在图 7.10 例如, 假定 x 和 y 的类型是 real,i 和 j 的类型是 integer, 对于输入 x := y + i j 根据图 7.10, 输出的三地址语句序列是 t 1 := i int j 12

13 t 2 := inttoreal t 1 t 3 := y real+ t 2 x := t 3 图 7.10 的语义动作为非终结符 E 使用了两个属性 E.place 和 E.type E.place := newtemp; if E 1.type = integer and E 2.type = integer then begin emit (E.place, :=, E 1.place, int+, E 2.place); E.type = integer end else if E 1.type = real and E 2.type = real then begin emit (E.place, :=, E 1.place, real+, E 2.place); E.type := real end else if E 1.type = integer and E 2.type = real then begin u := newtemp; emit (u, :=, inttoreal, E 1.place); emit (E.place, :=, u, real+, E 2.place); E.type := real end else if E 1.type = real and E 2.type = integer then begin u := newtemp; emit (u, :=, inttoreal, E 2.place); emit (E.place, :=, E 1.place, real+, u); E.type := real end else E.type := type_error; 图 7.10 E E 1 + E 2 的语义动作 7.4 布尔表达式和控制流语句 在编程语言中, 布尔表达式有两个基本目的 它们用于计算逻辑值, 但更经常的是在控制流语句中用作条件表达式, 如 if-then,if-then-else 或者 while-do 语句 布尔表达式也可以像算术表达式那样递归地定义 下面是本节所用的布尔表达式文法, 其中 relop 是关系算符, 为简单起见, 它的两个运算对象都只允许是变量 E E or E E and E not E ( E ) id relop id true false 按习惯, 我们认为 or 和 and 都是左结合的,or 的优先级最低, 然后是 and, 最后是 not 在有些情况下, 只要完成了布尔表达式的部分计算就可以知道表达式的结果, 那么表达式剩下的部分是否还要计算? 编程语言的语义决定布尔表达式是否需要全部计算 Pascal 语言要求所有部分都必须计算, 而 C 语言允许部分计算 如果语言定义允许 ( 或要求 ) 部分布尔表达式不计算, 那么, 编译器可以优化布尔表达式的计算, 使之只计算足以确定它值的那部分表达式 我们把这样的计算称为 短路 计算 因此, 在 E 1 or E 2 这样的表达式 13

14 中,E 1 或 E 2 可能不必计算 ( 或不必完全计算 ) 但是如果 E 1 或 E 2 是有副作用的表达式 ( 即 含改变非局部变量的函数 ), 那就可能会出现与预期不一致的结果 为避免不同的优化有 不同的结果, 有些语言对短路计算做了严格的语义规定, 把 E 1 or E 2 定义成 if E 1 then true else E 2 把 E 1 and E 2 定义成 if E 1 then E 2 else false 表示布尔表达式的值有两种主要方法 第一种方法是把真和假数值化, 使布尔表达式 的计算类似于算术表达式的计算, 常常用 1 表示真, 用 0 表示假 当然还有许多其它的编 码方式, 例如, 可以用非 0 表示真, 用 0 表示假, 或者用非负数表示真, 用负数表示假 实现布尔表达式的第二种方法是用控制流, 即用程序中的位置来表示布尔表达式的值, 它适用于短路计算的情况, 用这种方式实现控制流语句中的布尔表达式尤其方便 因为对 于控制流语句来说, 只要能根据布尔表达式的情况从正确的位置继续执行就可以了, 对它 的值无须再关心 布尔表达式的翻译 首先考虑用 1 和 0 分别表示真和假, 并且布尔表达式将从左到右地完全地被计算 显 然, 这时布尔表达式的中间代码生成和算术表达式的没有多少区别 例如 : a or b and not c 翻译成的三地址语句序列是 t 1 := not c t 2 := b and t 1 t 3 := a or t 2 a < b 这样的关系表达式等价于条件语句 if a < b then 1 else 0, 它被翻译成的三地址语句 序列是 ( 因为涉及转移指令, 所以需要给语句以编号, 这里从 100 开始编号是随意的 ): 100: if a < b goto : t := 0 102: goto : t := 1 104: 为布尔表达式产生三地址代码的翻译方案见图 7.11 在这个方案中, 变量 nextstat 给出 在输出序列中下一个三地址语句的序号,emit 在产生每个三地址语句后将 nextstat 加 1 我 们给 relop 以属性 op, 用来确定该关系算符究竟代表哪个关系运算 E E 1 or E 2 {E.place := newtemp; emit (E.place, :=, E 1.place, or E 2.place) } E E 1 and E 2 {E.place := newtemp; emit (E.place, :=, E 1.place, and, E 2.place) } E not E 1 {E.place := newtemp; emit (E.place, :=, not,e 1.place) } E (E 1 ) {E.place := E 1.place } E id 1 relop id 2 {E.place := newtemp; emit ( if, id 1.place, relop.op, id 2.place, goto, nextstat+3 ); emit (E.place, :=, 0 ); emit ( goto, nextstat + 2 ); 14

15 E true E false emit (E.place, :=, 1 ) } {E.place := newtemp; emit (E.place, :=, 1 ) } {E.place := newtemp; emit (E.place, :=, 0 ) } 图 7.11 用数值表示布尔值的翻译方案 例 7.3 图 7.11 的翻译方案为表达式 a < b or c < d and e < f 产生的三地址代码如图 7.12 所示 100: if a < b goto : t 2 := 1 101: t 1 := 0 108: if e < f goto : goto : t 3 := 0 103: t 1 := 1 110: goto : if c < d goto : t 3 := 1 105: t 2 := 0 112: t 4 := t 2 and t 3 106: goto : t 5 := t 1 or t 4 图 a < b or c < d and e < f 的翻译 控制流语句的翻译 现在考虑 if-then,if-then-else,while-do 和顺序语句到三地址语句的翻译, 这些语句由 下面的文法产生 : S if E then S 1 if E then S 1 else S 2 while E do S 1 S 1 ; S 2 在这些产生式中,E 是布尔表达式 图 7.13 用图形表示出这四个语句的三地址代码的结构 图中 E.code 和 S.code 分别表示 E 和 S 的三地址代码, 它们在图中的次序就表示了它们在整 个代码中的次序 例如在 if-then 的结构图中,E.code 在 S.code 的上面, 它表示 E 的三地址 代码在 S 的三地址代码前面 E.true: E.code S 1.code 指向 E.true 指向 E.false E.true: E.code S 1.code 指向 E.true 指向 E.false... (a) if-then E.false: goto S.next S 2.code... S.begin: E.true: E.code S 1.code goto S.begin... (c) while-do 指向 E.true 指向 E.false S 1.next: (b) if-then-else S 1.code S 2.code... (d) S 1 ; S 2 15 图 7.13 if-then, if-then-else, while-do 和顺序语句的代码

16 图 7.13 中的 E.true,E.false,S.begin 和 S.next 都是三地址语句的标号, 它们都是继承属 性 我们看 if-then 的结构图, 由于 S 1.code 究竟有多少个语句, 在翻译 E 时是不知道的, 因 此我们不能像上一小节那样, 用 nextstat 加一个适当的常数来确定 S 1.code 的第一个语句的 编号 在这里, 我们给三地址语句以符号标号, 函数 newlabel 每次调用时返加一个新的符 号标号 对布尔表达式 E, 我们用两个标号 E.true 和 E.false 分别表示 E 为真和为假时控制流应 该转向的标号, 这两个属性由 E 的上下文决定 S.begin 是 S 第一个三地址语句的标号,S.next 表示执行完 S 后应该执行的第一个三地址语句的标号, 它们都由 S 的上下文决定 对于 S 1 ;S 2 的情况,S 1 的 next 显然是 S 2 的第一条语句, 如图 7.13(d) 所示 对于其它语句, 情况就不这 么简单, 我们看图 7.13(b) 的 if-then-else 语句 我们在 S 1.code 的后面有 goto S.next, 因为 S 1 执行结束意味着 S 执行结束, 因此我们需要这个三地址语句, 并且当 S 1 是赋值语句时肯定 会执行这个语句 问题是 S 1 的 next 应该是什么, 它可以是 goto S.next 这个语句的标号, 但 这意味着如果 S 1 中有三地址语句跳转到 S 1.next 的话, 那么紧接着再执行 goto S.next 这种 连续跳转显然应该并且可以避免, 因此我们让 S 1.next 等于 S.next 出于同样的原因,S.next 标号不一定就是在紧挨着 S 2 的地方 控制流语句的语法制导定义在表 7.3 和赋值语句的翻译方案不一样的是, 我们用函数 gen 代替了过程 emit,gen 把形成的代码串作为函数值, 而不是输出到文件上 还有, 是 作为串的连接算符 表 7.3 没有给出布尔表达式的语法制导定义,7.4.1 节的翻译方案在此不适用, 我们在 下一小节另行给出 表 7.3 控制流语句的语法制导定义 产生式语义规则 S if E then S 1 S if E then S 1 else S 2 E.true := newlabel; E.false := S.next; S 1.next := S.next; S.code := E.code gen(e.true, : ) S 1.code E.true := newlabel; 16

17 S while E do S 1 S S 1 ; S 2 E.false := newlabel; S 1.next := S.next; S 2.next := S.next; S.code := E.code gen(e.true, : ) S 1.code gen( goto, S.next) gen(e.false, : ) S 2.code S.begin:= newlabel; E.true := newlabel; E.false := S.next; S 1.next := S.begin; S.code := gen(s.begin, : ) E.code gen(e.true, : ) S 1.code gen( goto, S.begin) S.code := S 1.code gen(s 1.next, : ) S 2.code 布尔表达式的控制流翻译 现在讨论上一小节的 E.code, 即为布尔表达式 E 产生中间代码 我们采用本节一开始 提到的实现布尔表达式的第二种方式, 即把 E 翻译成一串条件转移和无条件转移的三地址 语句序列 设计这个翻译的基本想法是这样, 假定 E 是 a < b 的形式, 那么生成的代码形式为 : if a < b goto E.true goto E.false 设 E 是 E 1 or E 2 的形式 如果 E 1 为真, 那么可以知道 E 本身为真, 即 E 1.true 和 E.ture 一样 如果 E 1 为假, 那么 E 2 必须计算, 可以让 E 1.false 是 E 2 代码的第一个语句的标号 E 2 的 true 和 false 分别与 E 的 true 和 false 一样 类似的考虑可用于 E 1 and E 2 的翻译 形式为 not E 1 的表达式无需代码, 只要交换 E 的 true 和 false 就得到 E 1 的 true 和 false 按这种方法为布尔表达式生成三地址代码的语法制导 定义见表 7.4 例 7.4 再次考虑表达式 a < b or c < d and e < f 假定整个表达式的 true 和 false 已分别置为 L true 和 L false 那么用表 7.4 的定义可以得到下列 代码 : if a < b goto L true goto L 1 L 1 : if c < d goto L 2 goto L false L 2 : if e < f goto L true goto L false 生成的代码还不是最优的, 因为删掉第二个语句不会改变代码的值 这种形式的冗余 指令不难在以后的处理中删除 避免产生这些冗余转移的另一个办法是把形式为 id 1 < id 2 的关系表达式翻译成 if id 1 > id 2 goto E.false, 即条件为真时执行正文上紧跟它的代码, 而条 件为假时跳转, 我们简称为假转方式 表 7.4 布尔表达式的语法制导定义 产生式语义规则 E E 1 or E 2 E 1.true := E.true; E 1.false := newlabel; 17

18 E 2.true := E.true; E 2.false := E.false; E.code := E 1.code gen(e 1.false, : ) E 2.code E E 1 and E 2 E 1.true := newlabel; E 1.false := E.false; E 2.true := E.true; E 2.false := E.false; E.code := E 1.code gen(e 1.true, : ) E 2.code E not E 1 E 1.true := E.false; E 1.false := E.true; E.code := E 1.code E (E 1 ) E 1.true := E.true; E 1.false := E.false; E.code := E 1.code E id 1 relop id 2 E.code := gen( if, id 1.place, relop.op, id 2.place, goto, E.true) gen( goto, E.false) E true E.code := gen( goto, E.true) E false E.code := gen( goto, E.false) 例 7.5 考虑语句 while a < b do if c < d then else x := y + z x := y z 表 7.4 的语法制导定义, 和赋值语句的翻译方案及控制流语句的语法制导定义合在一起, 为 该语句产生下列代码 : L 1 : if a < b goto L 2 goto L next L 2 : if c < d goto L 3 goto L 4 L 3 : t 1 := y + z x := t 1 goto L 1 L 4 : t 2 := y z x := t 2 goto L 1 改变条件测试的方向可以删除前两个 goto 语句 开关语句的翻译在许多语言中都有 开关 语句或者 分情况 语句, 但它们的语法和语义可能不同, 我们讨论的开关语句的语法如下 : switch E 18

19 begin end case V 1 : S 1 case V 2 : S 2... case V n - 1 : S n - 1 default: S n 这里有一个需要计算的开关表达式, 后面有 n 1 个常量值, 它们是该表达式可能取的 值 最后一个分支包含一个默认值, 如果这 n 1 个常量值不能和该表达式匹配的话, 那么 该默认值总能匹配 匹配分支的执行结束就是该语句的执行结束 开关语句的执行流程是 : (1) 计算开关表达式的值 (2) 分支测试, 即在分情况表中找和该表达式值相同的常量值 如果没有这样的常量 值, 那么默认值和该表达式值匹配 (3) 执行相匹配分支的语句 (4) 跳转到该语句的后继语句 步骤 (2) 的分支测试, 它有多种实现方法 如果分支数不是很多, 比方说少于 10 时, 那么把开关语句翻译成下面的条件转移序列是合理的 t := E 的代码 if t V 1 goto L 1 S 1 的代码 goto next L 1 : if t V 2 goto L 2 S 2 的代码 L 2 :... goto next... L n-2 : if t V n-1 goto L n-1 S n -1 的代码 goto next L n-1 : S n 的代码 next: 该方式的缺点是, 很难对分支测试的代码进行特别处理 为提高效率, 程序员应该把 经常出现的分支放在前面 另一种翻译方式是将分支测试的代码集中在一起, 放在该语句代码的后部 : t := E 的代码 goto test L 1 : S 1 的代码 goto next L 2 : S 2 的代码 goto next... L n-1 : S n -1 的代码 goto next L n : S n 的代码 19

20 goto next test: if t = V 1 goto L 1 next: if t = V 2 goto L 2... if t = V n-1 goto L n-1 goto L n 把分支测试序列的代码放在代码的前部是不方便的, 因为编译器不可能在看见每个 S i 前就产生这样的代码 为了便于识别从标号 test 开始的测试是开关语句的分支测试序列, 以利于代码生成器 对它进行特别处理, 我们可以给中间代码增加一种 case 语句, 将分支测试序列的中间代码 改成下面的形式 : 其中 case V test: case V 1 L 1 next: case V 2 L 2... case V n-1 L n-1 case t L n L 和 if t = V goto L 的含义一样 代码生成器实现这个测试序列的一种紧凑办法是建立一张二元组表, 每个二元组由常 量值和对应代码的入口地址组成 通过一个循环, 将表达式的值和表中的各个值相比, 如 果没有其它的值可匹配, 最后的默认条目肯定匹配 如果常量值的数目较多, 那么用散列表效率会更高一些 对一种经常出现的特殊情况, 我们可以用更有效的办法实现 n 个分支 如果所有的常 量值落在一个较小的区间, 比方说 i min 和 i max 之间, 并且 n 和 i max i min 的比值较大, 那么可 以构造标号数组, 让与常量值 j 对应的标号放在偏移是 j i min 的条目中, 空白的条目全填上 默认语句的标号 为完成分支测试和执行相匹配的语句, 先计算开关表达式, 获到它的值 m, 检查 m 是否在 i min 和 i max 之间, 若在其中, 则间接转移到偏移为 m i min 的条目所指的地址 为把开关语句翻译成上面形式的代码, 编译器看见保留字 switch 时, 产生两个新的标 号 test 和 next 以及新的临时变量 t, 在分析表达式 E 时, 产生计算 E 到 t 的代码, 并产生跳 转语句 goto test 然后为每个 case V i : S i 产生新建的标号 L i, 后面跟着 S i 的代码, 再后面是 跳转 goto next 与此同时, 将标号 L i 加入符号表, 并将这个符号表条目的指针和常量 V i 放 入专用于存储 V i 和 L i 对应关系的队列 当看见终止开关体的保留字 end 时, 用这个队列中 的信息产生分支测试的语句序列 过程调用的翻译我们在第六章已详细介绍了过程调用的实现, 包括存储空间的组织 过程调用序列和过程返回序列等, 本小节我们用下面的文法 : S call id (Elist) Elist Elist, E Elist E 简单介绍过程调用语句的中间代码生成 我们知道, 过程调用的不同实现方式有不同的过程调用序列和返回序列, 为了让中间代码能方便地用于不同的实现方式, 我们特别为中间代码设计了一种 param 语句, 专用于 20

21 指示实在参数, 就象开关语句的中间代码 case 指示分支测试一样 过程调用 id(e 1, E 2,, E n ) 的中间代码结构如下 : E 1.place := E 1 的代码 E 2.place := E 2 的代码... E n.place := E n 的代码 param E 1.place param E 2.place... param E n.place call id.place, n 根据上面的代码结构, 我们知道, 在生成 E i.place := E i 的代码后, 我们需要保存 E i.place 的值, 队列是保存这些值的一种适当的数据结构 下面是采用这种数据结构的翻译方案 : S call id (Elist) { 为长度为 n 的队列中的每个 E.place,emit( param, E.place); emit( call, id.plase, n) } Elist Elist, E { 把 E.place 放入队列末尾 } Elist E { 将队列初始化, 并让它仅含 E.place} 在用 Yacc 等生成器来描述时, 这个队列一般声明成一个全局的数据结构 对于返回语句, 产生它的中间代码是一件直截了当的事情 习 题 7.1 把算术表达式 ( a + b ) ( c + d ) + (a + b + c ) 翻译成 (a) 语法树 (b) 有向无环图 (c) 后缀表示 (d) 三地址代码 7.2 把下面 C 程序 main () { int i; int a[10]; while (i < = 10 ) a[i] = 0; } 的可执行语句翻译成 (a) 语法树 (b) 后缀表示 (c) 三地址代码 *7.3 证明 : 如果所有算符都是二元的, 那么算符和运算对象的串是后缀表达式, 当且仅当 : (1) 算符个数正好比运算对象个数少一个 ; (2) 在这个表达式的每个非空前缀中, 算符数少于运算对象数 7.4 修改图 7.4 中计算声明名字的类型和相对地址的翻译方案, 允许名字表而不是单个 21

22 名字出现在形式为 D id : T 的声明中 7.5 算符 作用于表达式 e 1, e 2,, e k 的前缀形式是 p 1 p 2 p k, 其中 p i 是 e i 的前缀形式 (a) 写出 a (b + c) 的前缀形式 *(b) 证明 : 所有的语义动作都是打印, 并且所有的动作都出现在产生式右部末端的 翻译方案不可能把中缀表达式翻译成前缀表达式 (c) 给出把中缀表达式翻成前缀形式的语法制导定义 7.6 编一个程序, 实现表 7.4 的翻译布尔表达式到三地址代码的语法制导定义 7.7 修改图 7.11 的语法制导定义, 为栈机器产生代码 7.8 表 7.4 的语法制导定义把 E id 1 < id 2 翻译成一对语句 if id 1 < id 2 goto goto 我们可以用一个语句 if id 1 > id 2 goto 来代替, 当 E 是真时执行后继代码 修改表 7.4 的语法制导定义, 使之产生这种性质的代码 7.9 下面的 C 语言程序 main() { int i,j; while ( (i j) && (j > 5) ) { i =j; } } 在 X86/Linux 机器上编译生成的汇编代码如下 :.file "bool.c".version "01.01" gcc2_compiled.:.text.align 4.globl main.type main,@function main: pushl %ebp movl %esp,%ebp subl $8,%esp nop.p2align 4,,7.L2: cmpl $0,-4(%ebp) jne.l6 cmpl $0,-8(%ebp) jne.l6 jmp.l5.p2align 4,,7.L6: cmpl $5,-8(%ebp) jg.l4 jmp.l5.p2align 4,,7.L5: jmp.l3.p2align 4,,7 22

23 .L4:.L3:.L1: movl -8(%ebp),%eax movl %eax,-4(%ebp) jmp.l2.p2align 4,,7 leave ret.lfe1:.size main,.lfe1-main.ident "GCC: (GNU) egcs /Linux (egcs release)" 在该汇编代码中有关的指令后加注释, 将源程序中的操作和生成的汇编代码对应起来, 以 判断确实是用短路计算来完成布尔表达式计算的 它和 7.10 编一个程序, 实现表 7.3 给出的控制流语句的语法制导定义 7.11 用 7.3 节的翻译方案, 把下列赋值语句翻译成三地址代码 : A[i, j] := B[i, j] + C[ A[k, 1] ] + D[ i + j ] 7.12 C 语言的 for 语句有下列形式 for (e 1 ; e 2 ; e 3 ) stmt e 1 ; while (e 2 ) do begin end stmt; e 3 有同样的含义 构造一个语法制导定义, 把 C 语言风格的 for 语句翻译成三地址代码 7.13 Pascal 标准定义语句 for v := initial to final do stmt 和下面代码序列有同样的含义 begin end t 1 := initial; t 2 := final; if t 1 t 2 then begin end v := t 1 ; stmt; while v t 2 do begin end v := succ (v); stmt (a) 考虑下面的 Pascal 程序 : program forloop (input, output); var i, initial, final: integer; begin read (initial, final); for i := initial to final do 23

24 end. writeln (i) 当 initial = MAXINT 5 并且 final = MAXINT 时, 该程序的行为是什么? 其中 MAXINT 是目 标机器的最大整数 *(b) 构造语法制导的定义, 为 Pascal 的 for 语句产生正确的三地址代码 7.14 考虑下面的 for 语句 for i := 1 step 10 j until 10 j do j := j + 1 对这样的 for 语句可以有三种不同的语义定义 一种可能的含义是, 步长表达式 10 j 和终 值表达式 10 j 都仅在循环前计算一次, 例如 PL/I 语言 这样, 如果在循环前 j = 5, 那么该 循环体执行 10 次 第二种语义完全不同, 要求每次通过循环体时, 都要执行步长表达式和 终值表达式 例如, 若在循环前 j = 5, 那么该循环将不会终止,C 语言的 for 语句是属于这 种情况, 其表达式 e 2 和 e 3 是要重复计算的 ( 见 7.12 题 ) 第三种含义由 Algol 这样的语言 给出 当步长是负数时, 该循环终止的测试是 i<10 j, 而不是 i>10 j 分别写出这三种定义 下的中间代码结构 24