China-pub.Com 第8章代码生成 315 下载 typedef struct streenode NodeKind kind; Optype op:/used with OpKind + struct streenode +lchild,*rchild; int val;/used with ConstKind + chart strval; used for identifiers and numbers 】STreeNode typedef STreeNode *SyntaxTree; 用这些定义，表达式(x=x+3)+4的语法树如下所示 注意，赋值节点包含了要被赋于的表达式（在stxv1域中），以致一个赋值节点只有一个 子树（要被赋于的表达式）⊙。 基于这棵语法树的结构，我们能写出一个gencode过程来产生程序清单8-7的P.代码。对 图中的代码作如下注释：首先，代码用标准C函数sprintf把字符串连接到本地的临时变量 codestr。其次，调用过程emitCode/用以生成一个P代码行，在数据结构或输出文件中不显 示它的细节。最后，两个操作符（加号和赋值号）需要两个不同的遍历顺序，加号仅需要一些后 序处理，而赋值需要一些前序处理和一些后序处理。因此不可能在所有情况下，能将递归调用 都写成一个样子。 程序清单8-7表81属性文法定义的P码的代码生成过程的实现 .co0E8工zE。max1 ength of11in0oEP-cod0*/ Bw1Ech(化->op】 case Plus: ge tcode(adi") break; destr,"%8s "lda",t->strval) gencode(t->1child) 日在这个例子中，我们将数字也当作字符申保存在strva1域中
typedef struct streenode { NodeKind kind; Optype op; /* used with OpKind */ struct streenode *lchild, *rchild; int val; /* used with ConstKind */ char * strval; /* used for identifiers and numbers */ } STreeNode; typedef STreeNode *SyntaxTree; 用这些定义，表达式( x = x + 3 ) + 4的语法树如下所示： 注意，赋值节点包含了要被赋于的表达式 (在s t r v a l域中)，以致一个赋值节点只有一个 子树(要被赋于的表达式) 。 基于这棵语法树的结构，我们能写出一个 g e n C o d e过程来产生程序清单 8 - 7的P -代码。对 图中的代码作如下注释：首先，代码用标准 C函数s p r i n t f把字符串连接到本地的临时变量 c o d e s t r。其次，调用过程e m i t C o d e用以生成一个P -代码行，在数据结构或输出文件中不显 示它的细节。最后，两个操作符 (加号和赋值号)需要两个不同的遍历顺序，加号仅需要一些后 序处理，而赋值需要一些前序处理和一些后序处理。因此不可能在所有情况下，能将递归调用 都写成一个样子。 程序清单8-7 表8 - 1属性文法定义的P -码的代码生成过程的实现 第 8章 代 码 生 成 3 1 5 下载 在这个例子中，我们将数字也当作字符串保存在s t r v a l域中
316 翁译原理及实践 China-pub.com 下载 amitcode("atn"); break; break; sprintf(codestr,"ka %s","ldc",t->atrval) emitcode(codestr); sprintE(codestr,"%s %s",lod",t->strval) amitCode(codestr): emitcode("Error") break; 即使用到了必需的不同顺序的遍历，显示代码生成仍然可以在分析时进行（没有语法树的 生成)，我们在程序清单8-8中出示了一个Yacc说明文件，它直接对应于程序清单8-7的代码（注 意赋值的前序和后序的组合处理是怎样翻译成独立的部分)。 程序清单8-8根据表8-1的属性文法生成P-代码的Yacc说明 #define ry8 TYPE char· /make Yacc use strings as values*/ token NUM ID % ID aexp +factor (emitcode("adi");) factor ￡actor:'(:●2p)' I NUM sprintf(codestr,"ks %s","ldc",$1) (p(ce ","1od",1)
即使用到了必需的不同顺序的遍历，显示代码生成仍然可以在分析时进行 (没有语法树的 生成)，我们在程序清单8 - 8中出示了一个Ya c c说明文件，它直接对应于程序清单 8 - 7的代码(注 意赋值的前序和后序的组合处理是怎样翻译成独立的部分 )。 程序清单8-8 根据表8 - 1的属性文法生成P -代码的Ya c c说明 3 1 6 编译原理及实践 下载
China-pub.com 第8章代码生成 317 下载 emitcode(codestr):) yruction. 请读者按表&-2的属性文法写出一个genCode过程和生成三地址码的Yacc说明。 8.2.3从中间代码生成目标代码 如果编译器或者直接从分析中或者从一棵语法树中产生了中间代码，那么下一步就是产生 最后的目标代码（通常在对中间代码的进一步处理之后），这一步本来就相当复杂，特别是当中间 代码为高度象征性的，且只包含了很少或根本没包含目标机器和运行时环境的信息。在这种情 况下，最后的代码生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的 代码。寄存器的合适定位和寄存器使用信息的维护（如哪个寄存器可用和哪个包含了已知值）是 个特别重要的问题，我们将在本章最后再时论分配问题细节。现在仅时论这个处理的通用技术 通常，来自中间代码的代码生成涉及了两个标准技术：宏扩展(macro expansion)和静态模拟 (static simulation)。宏扩展涉及到用一系列等效的目标代码指令代替每一种中间代码指令。这要 求编译器保留关于定位和独立的数据结构的代码惯用语的决定，它要求宏过程按照中间代码中 涉及的特殊数据的需要改变代码序列。因此，这一步要比在C预处理器或宏汇编器中可利用的宏 扩展的简单形式复杂得多。静态模拟包括中间代码效果的直线模拟和生成匹配这些效果的目标 代码。这也需要额外的数据结构，它可以是非常简单的跟踪形式，并在与宏扩展的连接中使用， 也可以是非常复杂的抽象解释(abstract)(当计算值时，对它们保持代数学的追踪)。 在考虑从P代码翻译成三元地址码（反之亦然）时，我们能了解这些技术的细节。想象一个 在这节中已作为运行例子用过的小表达式语法，并考虑表达式(x=x+3)+4,它的P代码和三 地址码的翻译在前面己经给出。我们首先考虑将这个表达式的P代码： lod x adi stn 1de 4 adi 翻译成相应的三地址码： t1=x+3 这需要执行一个机翠栈的静态模拟用以发现代码的二地址码等效式。在翻译期间，用实际的 栈数据结构实现它们。在前三条P代码指令后仍无三地址码指令产生，但是已经将P-机器栈修 改以反映这些装入。栈内容如下所示： 3 ◆一栈项 ×的地址
请读者按表8 - 2的属性文法写出一个g e n C o d e过程和生成三地址码的Ya c c说明。 8.2.3 从中间代码生成目标代码 如果编译器或者直接从分析中或者从一棵语法树中产生了中间代码，那么下一步就是产生 最后的目标代码(通常在对中间代码的进一步处理之后)，这一步本来就相当复杂，特别是当中间 代码为高度象征性的，且只包含了很少或根本没包含目标机器和运行时环境的信息。在这种情 况下，最后的代码生成必须支持变量和临时变量的实际定位，并增加支持运行时环境所必需的 代码。寄存器的合适定位和寄存器使用信息的维护(如哪个寄存器可用和哪个包含了已知值)是一 个特别重要的问题，我们将在本章最后再讨论分配问题细节。现在仅讨论这个处理的通用技术。 通常，来自中间代码的代码生成涉及了两个标准技术：宏扩展(macro expansion)和静态模拟 (static simulation)。宏扩展涉及到用一系列等效的目标代码指令代替每一种中间代码指令。这要 求编译器保留关于定位和独立的数据结构的代码惯用语的决定，它要求宏过程按照中间代码中 涉及的特殊数据的需要改变代码序列。因此，这一步要比在C预处理器或宏汇编器中可利用的宏 扩展的简单形式复杂得多。静态模拟包括中间代码效果的直线模拟和生成匹配这些效果的目标 代码。这也需要额外的数据结构，它可以是非常简单的跟踪形式，并在与宏扩展的连接中使用， 也可以是非常复杂的抽象解释(abstract interpretation) (当计算值时，对它们保持代数学的追踪)。 在考虑从P -代码翻译成三元地址码 (反之亦然)时，我们能了解这些技术的细节。想象一个 在这节中已作为运行例子用过的小表达式语法，并考虑表达式 ( x = x + 3 ) + 4，它的P -代码和三 地址码的翻译在前面已经给出。我们首先考虑将这个表达式的 P -代码： lda x lod x ldc 3 adi s t n ldc 4 adi 翻译成相应的三地址码： t1 = x + 3 x = t1 t2 = t1 + 4 这需要执行一个P -机器栈的静态模拟用以发现代码的三地址码等效式。在翻译期间，用实际的 栈数据结构实现它们。在前三条 P -代码指令后仍无三地址码指令产生，但是已经将 P -机器栈修 改以反映这些装入。栈内容如下所示： 第 8章 代 码 生 成 3 1 7 下载 x 的地址 栈顶
318 翁译原理及实践 China-pub.co 下载 现在当处理adi操作时，产生三地址指令 t1=x+3 栈改成： x的地址 stn指令造成三地址指令 x=t1 生成，栈变成为： 下一个指令压常量4入栈： 4 t1 最后adi指令生成三地址指令 t2=t1+4 栈变成为 2☐一找项 这就完成了静态模拟和翻译。 我们现在考虑将三地址码翻译成P代码的情况。假如忽略临时变量名增加的复杂性，就能 用简单的宏扩展来完成。因此，一个三地址指令 总能被翻译成如下的P代码指令序列 lod b or ldc b if b is a const lod c or lde c if c is a const ad上 sto 这导致了如下的三地址码到P代码的翻译（有点不令人满意） adi 8t0 lda x lod t1 袋七0 lda t2
现在当处理a d i操作时，产生三地址指令 t 1 = x + 3 栈改成： s t n指令造成三地址指令 x = t 1 生成，栈变成为： 下一个指令压常量4入栈: 最后a d i指令生成三地址指令 t2 = t1 + 4 栈变成为 这就完成了静态模拟和翻译。 我们现在考虑将三地址码翻译成 P -代码的情况。假如忽略临时变量名增加的复杂性，就能 用简单的宏扩展来完成。因此，一个三地址指令 a = b + c 总能被翻译成如下的P -代码指令序列 lda a lod b ; or ldc b if b is a const lod c ; or ldc c if c is a const a d i s t o 这导致了如下的三地址码到P -代码的翻译(有点不令人满意) lda t1 lod x ldc 3 a d i s t o lda x lod t1 s t o lda t2 3 1 8 编译原理及实践 下载 x 的地址 栈顶 栈顶 栈顶 栈顶
China-pub.Com 第8章代码生成 319 下载： lod t1 Ide 4 adi sto 假如要消除额外的临时变量，就需要用一个比宏扩展复杂得多的方案。一种可能是从三地 址码生成一棵新树，这棵树用每个指令的操作符和所分配的名字来标记树节点，从而显示代码 的效果。它可看作是静态模似的一种形式。前面的三地址码的结果树如下： t2+ x,t1 注意三地址指令 ×=t1 在树中不生成节点，而是造成t1节点获得另一个名字x。这棵树同源代码的语法树类似， 但又有不同⊙。P代码能从这个树产生，这非常类似于从语法树中产生P代码。通过对内部 节点只分配永久名，而消除了临时变量。因此，在这棵样例树中，只分配了x,在P代码中 根本没有使用t1、t2。对应于根节点（七2）的值被放在P机器栈中。这导致了同前面完全 样的P代码生成，只要在存储时用st代替sto即可。我们鼓励读者编写伪码或C代码执行 这个处理。 8.3数据结构引用的代码生成 8.3.1地址计算 在前一节中，我们已经看到如何生成一个简单的算术表达式和赋值语句的中间代码。这些 例子中，所有的基本值或者是常量或者是简单变量（程序变量如x,临时变量如t1)。简单变量 仅通过名字识别一一到目标代码的翻译需要这些名字由实际地址代替，这些地址可以是寄存器、 绝对地址（针对全局变量），或是活动记录的偏移量（针对局部变量，可能包括嵌套层）。这些地 址可以在中间代码生成时插入，也可以推迟到实际代码生成时（用符号保持地址）， 为了定位实际地址，有许多情况需要执行地址计算，即使是在中间代码中，这些计算也必 须被直接表达出来。这样的计算发生在数组下标记录域和指针引用中。我们将依次讨论这些情 况。但首先将描述一下可以表达这样的地址计算的三地址码和P代码扩展。 1)用于地址计算的三地此码在三地止码中，对新操作符的需要不是很多。通常的算术樱 作符能被用来计算地址，但对于显示地址模式的方法需要几个新符号。在我们的三地址码版本 中，使用了与C语言中意义一样的“&”和“*”来指示地址模式。例如，假设想把常量2存放 在变量×加上10个字节的地址处，用三地址码表示如下： 飞1=x+10 ★七1=2 日这棵树是称为基本块的DAG(DAGofa basic block)的一般结构的特例，这在89.3节中描述
lod t1 ldc 4 a d i s t o 假如要消除额外的临时变量，就需要用一个比宏扩展复杂得多的方案。一种可能是从三地 址码生成一棵新树，这棵树用每个指令的操作符和所分配的名字来标记树节点，从而显示代码 的效果。它可看作是静态模似的一种形式。前面的三地址码的结果树如下： 注意三地址指令 x = t1 在树中不生成节点，而是造成 t 1节点获得另一个名字 x。这棵树同源代码的语法树类似， 但又有不同 。P -代码能从这个树产生，这非常类似于从语法树中产生 P -代码。通过对内部 节点只分配永久名，而消除了临时变量。因此，在这棵样例树中，只分配了 x，在P -代码中 根本没有使用 t 1、t 2。对应于根节点 (t 2)的值被放在 P机器栈中。这导致了同前面完全一 样的P -代码生成，只要在存储时用 s t n代替s t o即可。我们鼓励读者编写伪码或 C代码执行 这个处理。 8.3 数据结构引用的代码生成 8.3.1 地址计算 在前一节中，我们已经看到如何生成一个简单的算术表达式和赋值语句的中间代码。这些 例子中，所有的基本值或者是常量或者是简单变量 (程序变量如x，临时变量如t 1)。简单变量 仅通过名字识别一一到目标代码的翻译需要这些名字由实际地址代替，这些地址可以是寄存器、 绝对地址(针对全局变量)，或是活动记录的偏移量 (针对局部变量，可能包括嵌套层 )。这些地 址可以在中间代码生成时插入，也可以推迟到实际代码生成时 (用符号保持地址)。 为了定位实际地址，有许多情况需要执行地址计算，即使是在中间代码中，这些计算也必 须被直接表达出来。这样的计算发生在数组下标记录域和指针引用中。我们将依次讨论这些情 况。但首先将描述一下可以表达这样的地址计算的三地址码和 P -代码扩展。 1) 用于地址计算的三地址码 在三地址码中，对新操作符的需要不是很多。通常的算术操 作符能被用来计算地址，但对于显示地址模式的方法需要几个新符号。在我们的三地址码版本 中，使用了与C语言中意义一样的“&”和“*”来指示地址模式。例如，假设想把常量 2存放 在变量x加上1 0个字节的地址处，用三地址码表示如下： t1 = &x + 10 *t1 = 2 第 8章 代 码 生 成 3 1 9 下载 这棵树是称为基本块的DAG(DAG of a basic block)的一般结构的特例，这在8 . 9 . 3节中描述