编译原理实践 1.课程说明及引论

序言 《编译原理》的课程实践一般有两种安排： 配合编译课程教学，安排多次小型实践，分别支 持编译程序的各个阶段 针对某一规模适中的语言来设计和实现一个相对 完整、独立的编译器。 《编译原理实践》作为《编译原理》课程的延 伸，目的是让大家动手设计和实现某一规模适 中的语言的编译器 涉及编译程序的各个阶段 强调了编译的总体设计、各个阶段的接口安排等 等 学会运用所学技术解决实际问题

课程目标 回顾编译相关的文法和形式语言基本理论 以PL/0语言为例，介绍一个编译程序从语法定义、 词法分析、语法分析、出错处理、代码生成到解释 执行的全过程。使学生了解什么是编译，并懂得怎 样从语言的定义出发，系统地去开发一个语言的编 译程序 介绍Lex（词法分析程序的生成系统） & Yacc（语 法分析程序的生成系统）

PL/0编译器 PL/0 语言程序 类 p-code 代码 PL/0编译程序 源语言(PL/0) 目标语言(类p-code) 给出一个简单的类Pascal语言，其编译程序用高级 语言（C/Pascal）实现。通过剖析该高级语言程 序以理解各编译成分的功能及手工实现方法。 PL/0 语言程序 类 p-code 代码 PL/0编译程序 源语言(PL/0) 目标语言(类p-code) 实现语言(pascal/C) 类 p-code PL/0 pascal/C

PL/0编译系统的结构框架 PL/0源程序 PL/0编译程序 类 p－code代码 类 p－code解释程序 输入数据 输出数据

课程作业 给出某个语言的词法和语法规则，要求实现该 语言编译程序，包括词法分析、语法分析、出 错处理、代码生成和解释程序 用该语言编若干个程序，用自己开发的编译程 序对它编译，在编译过程中要求能连续指出语 法错误不中断，能生成代码程序，能解释执行 代码程序，最后输出正确结果 可以用自己熟悉的程序设计语言实现 优秀学生作品演示

详细要求和评分规则见《编译原理实践作业要求 》 为了避免检查冲突，将把大家分成若干组，每组完 成语言的不同扩展 指定扩展不加分，非指定扩展视完成情况加分 先检查的同学将获得更高的时间分，每组扩展点的 难度也是由简单到复杂

考核方式 平时成绩(15%) 出勤率 课堂练习 期末考试(30%)—第10周 课程作业成绩(55%)

引论 什么是编译程序 编译程序的组成 编译程序的结构 程序设计语言的发展历程 构建一个编译器的相关科学

1.什么是编译程序/编译器 编译器是将高级语言编写的程序转换成能在一台计 算机上执行的等价目标代码或机器语言程序的软件 系统 可以扩展到包含： 将一种高级语言程序转换成另一种高级语言程序的系 统 从一种机器语言程序转换成另一种机器语言程序的系 统 从一种高级语言程序转换成一种中间语言程序的系统 等等

编译器是一种相当复杂的程序，其代码长度可 从10000到1000000行不等。编写甚至读懂这 样的一个程序都非易事，大多数的计算机科学 家和专业人员从来也没有编写过一个完整的编 译器 但是，几乎所有形式的计算均要用到编译器， 而且任何一个与计算机打交道的专业人员都应 掌握编译器的基本结构和操作

编译器是应用程序与操作系统及处理器之间沟通的 桥梁 处理器与编译器发展相辅相成，没有编译技术做支 撑，再好的处理器也没挥不了应有的作用 截止2010年，“图灵奖”43年历史中，约1/3的 获奖都在“编译技术和程序设计语言”这个领域

编译器历史回顾 本世纪40年代，开始时程序都是用机器语言 （machine language）编写的。机器语言就是 表示机器实际操作的数字代码，例如： C7 06 0000 0002 表示在IBM PC上使用的Intel 8x86处理器将数字 2移至地址0 0 0 0（1 6进制）的指令。

这种代码形式很快就被汇编语言(assembly language)代替了。在汇编语言中，都是以符号形 式给出指令和存储地址的。例如，汇编语言指令 MOV X, 2 就与前面的机器指令等价(假设符号存储地址X是0 0 0 0) 汇编程序(assembler)将汇编语言的符号代码和存 储地址翻译成与机器语言相对应的数字代码

发展编程技术的下一个重要步骤就是以一个更类似 于数学定义或自然语言的简洁形式来编写程序的操 作，它应与任何机器都无关，而且也可由一个程序 翻译为可执行的代码 例如，前面的汇编语言代码可以写成一个简洁的与 机器无关的形式 x = 2;

在1954年至1957年期间，IBM的John Backus 带领的一个研究小组对FORTRAN语言及其编译器 的开发 Noam Chomsky开始了他的自然语言结构的研究。 他的发现最终使得编译器结构异常简单，甚至还带 有了一些自动化 Chomsky的研究导致了根据语言文法(grammar) 的难易程度以及识别它们所需的算法来为语言分类

乔姆斯基分类结构( Chomsky hierarchy)---文 法的4个层次：0型、1型、2型和3型文法，且其 中的每一个都是其前者的专门化 2型(或上下文无关文法(context-free grammar)) 被证明是程序设计语言中最有用的，而且今天它已 代表着程序设计语言结构的标准方式

2. 编译程序的组成 词法分析 符 出 号 错 表 处 管 语法分析 理 语义分析与中间代码生成 代码优化 目标代码生成 源程序 单词符号 语法单位 中间代码 目标代码 符 号 表 管 理 编译程序结构框图 出 错 处

编译过程 <1>关键字或保留字(如BEGIN、END、IF) <2>标识符 <3>常数 1.词法分析 输入源程序，对构成源程序的字符串进行扫描和分解， 识别出一个个具有独立意义的最小语法单位“单词 (token) ” 单词：是语言的基本语法单位，一般语言有四大类单词： <1>关键字或保留字(如BEGIN、END、IF) <2>标识符 <3>常数 <4>分界符(运算符)，如+、-、*、/、；、(、)…

举例： 1)a:=10+c*20 2)while x>0 do x:=x-1 词法分析是一种线性分析

2.语法分析 在词法分析的基础上，根据语言的语法定义规则， 识别出构成单词符号串的各类语法单位。 通过语法分析，确定整个输入符号串是否构成语法 上正确的“程序” 举例： a:=10+c*20 语法分析是一种层次分析

3.语义分析与中间代码产生 对识别出的各种语法成份进行语义分析，并产生相 应的中间代码 中间代码：一种介于源语言和目标语言之间的中间 语言形式 生成中间代码的目的： <1>便于做优化处理 <2>便于编译程序的移植

中间代码的形式：编译程序设计者可以自己设计， 常见的中间代码有：三元式、间接三元式、四元式、 逆波兰表示、树形表示、 P-Code、C-Code、U- Code、bytecode等 中间代码具有易于产生，易于翻译成目标程序的特 点，可以看成是一种抽象机的指令代码 中间代码的设计在相当大的程度上是一种技巧，而 不是科学 中间代码设计方案数可能两倍于编译器套件种类数！

举例： a:=10+c*20 由语法分析识别出为赋值语句，语义分析首先要分 析语义上的正确性，例如要检查表达式中和赋值号 两边的类型是否一致 根据赋值语句的语义，生成中间代码。即用一种语 言形式来代替另一种语言形式，这是翻译的关键步 骤。

4.代码优化 经过语义分析后，编译程序将源程序生成中间代码， 这时的中间代码往往有些重复和冗余。对代码进行 优化的目的是提高目标程序的执行效率 代码优化首先在中间代码上进行。在局部范围可能 做的优化有常数表达式的计算或根据操作符的某些 性质如可结合性、可交换性和分配性以及检测公共 子表达式进行优化 不同的编译器所作的代码优化工作量相差很大

5.目标代码生成 编译的最后一步是将中间代码生成特定机器上的低 级语言代码 这部分与机器类型有关，对程序中的每个变量指定 存贮单元，把中间代码的指令翻译成等价的某种类 型机器的机器指令代码或汇编指令代码

目标代码的形式可以是绝对指令代码、可重定位的机器 指令代码或汇编指令代码 如果目标是绝对指令代码，则可立即执行 如果是汇编指令代码，还需经汇编程序翻译后才能运行 现在多数编译程序产生的是可重定位的机器指令代码，这 种目标代码在运行前必须借助于一个连接装配程序把各个 目标模块（包括系统提供的库模块）连接在一起，确定程 序中的变量在内存中的位置，装入内存中指定起始地址， 使之成为一个可以运行的绝对指令代码程序

什么是链接器（Linker） 链接器的功能是，将一个或多个由编译器生成的目 标文件及库链接为一个可执行文件。

注意！ 上述编译过程的5个阶段是一种典型的分法，并非 所有的编译程序都分成5个阶段 本书中PL/0语言的编译程序省略了优化阶段；同 时省去了最后的目标代码生成阶段，取而代之的是 增加一个解释程序，由解释程序来解释执行中间代 码程序，同样可以得到最终结果

编译和解释 解释程序：在解释程序的执行过程中不产生目标代码。 每读一条源程序代码，就将它解释成等价的若干条机器 代码，并执行之。一些规模较小的语言，如BASIC， 常采用此方式。 通常把编译和解释作某种程度的结合。如Java，先将 源程序由java编译器(javac)编译生成字节码 (bytecode)文件，然后由一个虚拟机对得到的字节码 加以解释执行(java)。 注：字节码文件是与平台无关的二进制码。 PL/0编译程序也采用了编译和解释相结合的方式

6.符号表管理 编译过程中要记录源程序中出现的标识符，并收集 每个标识符的各种属性信息。为此需要建立一个符 号表记录有关标识符的各种信息。 符号表是由若干记录组成的数据结构，每个标识符 在表中有一条记录，每条记录有多个域，每个域记 载标识符的一个属性。 符号表的设计在很大程度上说它是一种艺术比说它 是科学原理更合适：符号表的属性随语言的不同而 变化，全局符号表最重要的是接口和性能，等等

7.出错处理 编译的各个阶段都可能发现源程序中的错误。发现错误后如 果立即停止编译，往往会降低调试程序的效率，所以应对出 现的错误做适当的处理，从而使编译能继续进行。 词法分析可以检测出源程序中的非法符号，就好比自然语言 语句中的出现的错字、错词。语法分析能够发现程序语句中 的各种语法错误，如括号不匹配等等。语义分析能判断运算 对象的类型是否匹配、变量是否重复声明或没声明就使用等 错误。 任意时刻发现错误，都应该报告错误信息，包括错误出现的 位置、错误性质等，为程序员调试程序提供方便。由此可见， 错误检测和恢复也是编译程序中的一项重要工作。

3. 编译程序的结构 在设计和实现编译程序时，要考虑编译程序分“遍” 的问题。 所谓一“遍”是指在编译时把源程序或者中间形式 从头到尾扫描一遍，并作相关处理，生成新的中间 形式或目标代码 采用不同的分遍方式，编译程序的结构也有所不同

单遍编译程序 单遍编译程序只对源程序进行一遍扫描，就完成编译的 各项任务，产生目标代码。在单遍编译程序中，往往以 语法分析程序为中心，词法分析和语义分析作为语法分 析的子程序。其工作过程如下： 当语法分析需要读进一个新单词时，就调用词法分析子程 序。词法分析子程序则从源程序中依次读入字符，组合成 单词符号，并将单词符号返回给语法分析程序。 当语法分析程序识别出一个语法成分时，就调用语义分析 子程序进行语义分析，并生成目标程序。 当源程序处理完后，进行善后处理，优化目标程序。

单遍编译程序 语法成分 语法分析 语义分析生成 目标程序 S.P. 返回分析结果 取单词 整理目标程序 停机 返回单词 词法分析 O.P.

多遍编译程序 有的编译程序把编译程序的五项任务分几遍来进行，每 遍只完成部分任务， 多遍编译程序的工作过程如下： 调用词法分析程序将高级语言源程序转换成用单词符号 表示的程序，即将字符串程序转换成单词符号串源程序。 调用语法分析程序对符号串源程序进行语法归类检查。 调用语义分析程序进行语义检查，并生成中间的代码程 序。 调用代码优化程序对中间代码程序进行优化。 调用目标生成程序将优化后的中间代码程序转换成目标 代码程序。

源程序 词法分析 语法分析 语义分析 代码优化 目标代码生成 错误处理 符号表 目标程序 多遍编译程序结构

实际上，根据语言的不同，编译器可以是一遍 (one pass)——所有的阶段由一遍完成，其结果 是编译得很好，但(通常)代码却不太有效。 大多数带有优化的编译器都需要超过一遍：典型的 安排是将一遍用于扫描和分析，将另一遍用于语义 分析和源代码层优化，第3遍用于代码生成和目标 层的优化。 更深层的优化则可能需要更多的遍： 5遍、6遍、 甚至8遍都是可能的。

试问世界上第一个编译程序是用什么语言书写的？ 用高级语言书写？ *没有编译器，如何编译？ 因此世界上第一个编译器只能是用机器语言开发的

编译程序的自展技术 直接用目标机器上的机器语言书写源语言的编译程 序工作量太大 用目标机器上的机器语言书写源语言的一个子集的 编译程序，然后再用这个子集作为书写语言，实现 源语言的编译程序。

如果把这个过程根据情况分为若干步，像滚雪球一 样直到生成预计源语言的编译程序为止，我们把这 样的实现方式称为自展技术 简要来说就是：用被编译的语言来书写该语言自身 的编译程序

4.程序设计语言的发展历程 按语言的代分类 第一代：机器语言 第二代：汇编语言 第三代：高级程序设计语言，如 Fortran,Cobol,Lisp,C,C++,C#,Java 第四代：为特定应用设计的语言，如用于数据库查 询的SQL，用于文字排版的Postscript 第五代：基于逻辑和约束的语言，如Prolog和 OPS5

按程序中指名如何完成一个计算任务来分类 命令式语言：用命令式程序设计语言编写程序，就是 描述解题过程中每一步的过程，程序的运行过程就是 问题的求解过程，因此也称为过程式语言。如 C,C++,C#和Java等 声明式语言：描述目标性质，让计算机明白目标，而 非流程。声明式编程通常被看做是形式逻辑的理论， 把计算看做推导。如 ML,Haskell,Prolog,HTML,CSS,正则表达式等 还有些语言是混合式的，既有声明式，也有动作处理

对编译器的影响 程序设计语言的发展对编译器设计提出了新的要求， 编译器也推动了这些高级语言的使用 编译器必须能够正确翻译源语言书写的所有程序， 这样的程序的集合通常是无穷的。为一个源程序生 成最佳目标代码的问题一般来说是不可判定的 有关编译器的研究也是关于如何使用理论来解决实 践问题的研究

构建一个编译器的相关科学 编译器的设计中，有很多通过数学方法抽象出问题 本质从而解决现实世界中复杂问题的完美例子 对编译器的研究主要是如何设计正确的数学模型和 选择正确算法的研究 需要考虑到对通用性及功能的要求与简单性及有效 性之间的平衡

最基本的数学模型是有穷状态自动机和正则表达式： 用于描述词法单位以及描述被编译器用来识别这些 单位的算法 上下文无关文法：用于描述程序设计语言的语法结 构 树形结构：表示程序结构以及程序到目标代码的翻 译方法的重要模型

编译技术的应用 懂得编译有助于深刻理解和正确使用程序设计语言， 有助于加深对整个计算机系统的理解 虽然只有少数人从事构造或维护编译器的工作，但 是大部分系统软件和应用程序的开发，通常要用到 编译原理和技术 例如，设计词法分析器的串匹配技术已用于正文编 辑器、信息检索和模式识别程序。上下文无关文法 和语法制导定义已用于创建诸如排版、绘图系统和 语言结构化编辑器，等等。