《编译原理实践Implementationofprogramminglanguage窦亮》由会员分享，可在线阅读，更多相关《编译原理实践Implementationofprogramminglanguage窦亮（39页珍藏版）》请在金锄头文库上搜索。
1、编译原理实践Implementation of programming language 窦亮序言 编译原理的课程实践一般有两种可能的安 排。其一，为配合编译课程教学，而安排多次 小型实践，分别支持编译程序的各个阶段。其 二，针对某一规模适中的语言来设计和实现一 个相对完整、独立的编译器。 编译原理实践作为编译原理课程的延 伸，目的是让大家动手设计和实现某一规模适 中的语言的编译器，该编译器不仅涉及编译程 序的各个阶段，而且也强调了编译的总体设计 、各个阶段的接口安排等等。1.课程目标 回顾编译相关的文法和形式语言基本理论 以PL/0语言为例，介绍一个编译程序从 语法定义、词法分析、语法分析、
2、出错处 理、代码生成到解释执行的全过程。使学 生了解什么是编译，并懂得怎样从语言的 定义出发，系统地去开发一个语言的编译 程序 介绍Lex（词法分析程序的生成系统） 在1954年至1957年期间，IBM的John Backus带领的一个研究小组对 FORTRAN语言及其编译器的开发 Noam Chomsky开始了他的自然语言结 构的研究。他的发现最终使得编译器结 构异常简单，甚至还带有了一些自动化 。Chomsky的研究导致了根据语言文法 (grammar)的难易程度以及识别它们所 需的算法来为语言分类 乔姆斯基分类结构( Chomsky hierarchy)-文法的4个层次：0型、1 型、2
3、型和3型文法，且其中的每一个都 是其前者的专门化。2型(或上下文无关 文法(context-free grammar)被证明 是程序设计语言中最有用的，而且今天 它已代表着程序设计语言结构的标准方 式。2.2 编译程序的组成词法分析语法分析语义分析与中间代码生成代码优化目标代码生成源程序单词符号语法单位中间代码中间代码目标代码出 错 处 理符 号 表 管 理编译程序结构框图编译过程1.词法分析 输入源程序，对构成源程序的字符串进 行扫描和分解，识别出一个个具有独立 意义的最小语法单位“单词 (token) ” 词法分析工作中依循的是语言的构词规 则 举例： 1)a:=10+c*20 2)whi
4、le x0 do x:=x-12.语法分析 在词法分析的基础上，根据语言的语法 定义规则，识别出构成单词符号串的各 类语法单位。通过语法分析，确定整个 输入符号串是否构成语法上正确的“程序” 语法分析所依循的是语言的语法规则 词法分析是一种线性分析，而语法分析 是一种层次结构分析3.语义分析与中间代码产生 语义分析的功能是确定源程序的语义是 否正确。在程序设计中，语义错误有很 多，编译程序不能都识别出来，只能尽 力而为。语义分析主要能识别的语义错 误有变量没声明就使用、变量重复声明 、运算对象类型是否匹配等等。如果语 义正确，则进行中间代码的翻译 语义分析程序通常将源程序生成一种中 间表示形式
5、，即中间代码。中间代码是 一种含义明确、便于处理的记号系统， 通常独立于具体的硬件 常见的中间代码有：三元式、间接三元 式、四元式、逆波兰表示和树形表示， P-Code、C-Code、U-Code、bytecode 中间代码具有易于产生，易于翻译成目 标程序的特点，可以看成是一种抽象机 的指令代码4.代码优化 经过语义分析后，编译程序将源程序生 成中间代码，这时的中间代码往往有些 重复和冗余。对代码进行优化的目的是 提高目标程序的执行效率。代码优化首 先在中间代码上进行。在局部范围可能 做的优化有常数表达式的计算或根据操 作符的某些性质如可结合性、可交换性 和分配性以及检测公共子表达式进行优
6、化 5.目标代码生成 编译的最后一步是将中间代码生成特定 机器上的低级语言代码。这部分与机器 类型有关，对程序中的每个变量指定存 贮单元，把中间代码的指令翻译成等价 的某种类型机器的机器指令代码或汇编 指令代码。 目标代码的形式可以是绝对指令代码、可重定 位的机器指令代码或汇编指令代码。如果目标 是绝对指令代码，则可立即执行。如果是汇编 指令代码，还需经汇编程序翻译后才能运行。 现在多数编译程序产生的是可重定位的机器指 令代码，这种目标代码在运行前必须借助于一 个连接装配程序把各个目标模块（包括系统提 供的库模块）连接在一起，确定程序中的变量 在内存中的位置，装入内存中指定起始地址， 使之成为
7、一个可以运行的绝对指令代码程序。 例：C程序处理过程# include # include # define MAX_LINES 75 Enum booleans (FALSE,TRUE); Main (int argc,char *argv*) 预处理器编译器汇编器装配连接编辑骨架程序源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库语言处理过程注意！ 上述编译过程的5个阶段是一种典型的分 发，并非所有的编译程序都分成5个阶段 本书中PL/0语言的编译程序省略了优化 阶段；同时省去了最后的目标代码生成 阶段，取而代之的是增加一个解释程序 ，由解释程序来解释执行中间代码程序
8、，同样可以得到最终结果编译和解释 解释程序：在解释程序的执行过程中不产生目标代 码。每读一条源程序代码，就将它解释成等价的若 干条机器代码，并执行之。一些规模较小的语言， 如BASIC，常采用此方式。 通常把编译和解释作某种程度的结合。如Java，先 将源程序由java编译器(javac)编译生成字节码文件 ，然后由java解释器(java)执行。 注：字节码文件是与平台无关的二进制码，执行时 由解释器解释生成本地机器码，边解释边执行。 PL/0编译程序也采用了编译和解释相结合的方式 6.符号表管理 编译过程中要记录源程序中出现的标识 符，并收集每个标识符的各种属性信息 。为此需要建立一个符号
9、表记录有关标 识符的各种信息。符号表是由若干记录 组成的数据结构，每个标识符在表中有 一条记录，每条记录有多个域，每个域 记载标识符的一个属性。7.出错处理 编译的各个阶段都可能发现源程序中的错误。发现错 误后如果立即停止编译，往往会降低调试程序的效率 ，所以应对出现的错误做适当的处理，从而使编译能 继续进行。词法分析可以检测出源程序中的非法符号 ，就好比自然语言语句中的出现的错字、错词。语法 分析能够发现程序语句中的各种语法错误，如括号不 匹配等等。语义分析能判断运算对象的类型是否匹配 、变量是否重复声明或没声明就使用等错误。任意时 刻发现错误，都应该报告错误信息，包括错误出现的 位置、错误
10、性质等，为程序员调试程序提供方便。由 此可见，错误检测和恢复也是编译程序中的一项重要 工作。2.3 编译程序的结构 在设计和实现编译程序时，要考虑编译 程序分“遍”的问题。所谓一“遍”是指在编 译时把源程序或者中间形式从头到尾扫 描一遍，并作相关处理，生成新的中间 形式或目标代码 采用不同的分遍方式，编译程序的结构 也有所不同单遍编译程序 单遍编译程序只对源程序进行一遍扫描，就完成编译 的各项任务，产生目标代码。在单遍编译程序中，往 往以语法分析程序为中心，词法分析和语义分析作为 语法分析的子程序。其工作过程如下： 当语法分析需要读进一个新单词时，就调用词法分析 子程序。词法分析子程序则从源程
11、序中依次读入字符 ，组合成单词符号，并将单词符号返回给语法分析程 序。 当语法分析程序识别出一个语法成分时，就调用语义 分析子程序进行语义分析，并生成目标程序。 当源程序处理完后，进行善后处理，优化目标程序。词法分析 源程序 取单词 目标程序 开始 语法分析 语义分析及代码生成 送单词 单遍编译程序结构 多遍编译程序 有的编译程序把编译程序的五项任务分几遍来进行， 每遍只完成部分任务， 多遍编译程序的工作过程如下： 调用词法分析程序将高级语言源程序转换成用单词符 号表示的程序，即将字符串程序转换成单词符号串源 程序。 调用语法分析程序对符号串源程序进行语法归类检查 。 调用语义分析程序进行语义
12、检查，并生成中间的代码 程序。 调用代码优化程序对中间代码程序进行优化。 调用目标生成程序将优化后的中间代码程序转换成目 标代码程序。源程序 词法 分析 语法 分析 语义 分析 代码 优化目标代码 生成错误处理符号表目标程序 多遍编译程序结构 实际上，根据语言的不同，编译器可以 是一遍(one pass)所有的阶段由一 遍完成，其结果是编译得很好，但(通常) 代码却不太有效。大多数带有优化的编 译器都需要超过一遍：典型的安排是将 一遍用于扫描和分析，将另一遍用于语 义分析和源代码层优化，第3遍用于代码 生成和目标层的优化。更深层的优化则 可能需要更多的遍： 5遍、6遍、甚至8 遍都是可能的。编
13、译程序的自展技术 由于一个编译程序的功能是把某种高级 语言的源程序翻译成目标机的机器语言 （或汇编语言），目标机只能执行它自 己的机器语言，因此最早的第一个高级 语言的编译程序必须用目标机的汇编语 言或者机器语言书写。而一个结构较复 杂庞大的高级语言的编译程序，若完全 用汇编语言或者机器语言书写会有种种 不便之处，而用自展技术则可以很好地 解决这个问题 自展的思想是先用目标机的汇编语言或机 器语言书写源语言的一个子集的编译程序 ，然后再用这个自己作为书写语言，实现 源语言的编译程序。如果把这个过程根据 情况分为若干步，像滚雪球一样直到生成 预计源语言的编译程序为止，我们把这样 的实现方式称为自展技术 简要来说就是：用被编译的语言来书写该 语言自身的编译程序最后 懂得编译有助于深刻理解和正确使用程 序设计语言，有助于加深对整个计算机 系统的理解 虽然只有少数人从事构造或维护编译器 的工作，但是大部分系统软件和应用程 序的开发，通常要用到编译原理和技术 例如，设计词法分析器的串匹配技术已 用于正文编辑器、信息检索和模式识别 程序。上下文无关文法和语法制导定义 已用于创建诸如排版、绘图系统和语言 结构化编辑器，等等。
