C语言编译器设计与实现毕业论文设计(3)

北京邮电大学毕业设计

第二章 理论基础

2.1 编译系统概述 2.1.1 什么是编译器

编译器，是将便于人类编写、阅读、维护的计算机高级语言程序翻译为机器能够识别、运行的计算机低级语言程序的一种系统软件。编译器将源程序（Source Program）作为输入，翻译产生使用目标语言的等价目标程序（（Target Program）。其中，源程序一般为高级语言（High-level language），如Pascal，C++等，而目标语言则是汇编语言

[3]

或目标机器的机器语言。编译器的这一作用如图2-1所示：

图2-1 编译器的作用

2.1.2 编译器的产生

本世纪四十年代，由于冯·诺依曼在存储程序计算机方面的先锋作用，使得编写一串代码或程序已成为可能和必要，这样计算机就可以执行所需的计算。在初期，这些程序都是用机器语言编写，编写或维护这样的代码是非常枯燥乏味且效率低下的，所以机器语言很快就被汇编语言代替了。汇编语言大大提高了程序编写速度和准确度，但它也有许多缺点。于是发展编程技术的下一个重要革新就是以一个更加类似于数学定义或自然语言的简洁形式来编写程序的功能操作，它应与任何机器都无关，而且也可由一个程序翻译为可执行的代码。

随着对形式语言和自动机理论的研究，人们对高级程序设计语言的认识越来越深，对编译器结构的设计也越来越清晰。人们通过对形式语言文法规则的研究，相当完善地解决了分析问题。当分析问题变得相对成熟时，设计者们又花费了很多的精力来研究这一部分的编译器的自动构造，这就是分析程序生成器（parser generator）最初的雏形。类似地，对有穷自动机的研究也促进了一种称为扫描程序生成器（scanner generator）工具的发展。接着，人们又深化了生成有效目标代码的方法，这些就构成了传统的编译器，在这个过程中运用到的技术被一直使用至今。

2.2 编译器的结构

严格地说，编译器是一个将高级语言源程序转换成能在一台计算机上执行的等价目标代码或机器语言程序的软件系统。这个定义可扩展到包含将一个高级语言程序转换成

4

北京邮电大学毕业设计

汇编语言程序的系统，将一个高级语言程序转换成另一种高级语言程序的系统，从一个机器语言程序转换成另一种机器语言程序的系统，从一种高级语言程序转换成一种中间语言程序的系统，等等。

在通常情况下，一个编译器应由一系列的阶段组成，这些阶段从要编译的源程序的字符序列开始，依次对一个给定形式的程序进行分析，并得到一种新的表示形式，在大多数情况下最终产生一个可以与其他目标代码链接，并装入一台机器的存储器中执行的可重定位目标模块。这一编译过程一般由如下6个阶段构成，它们执行不同的逻辑操作如图2-2所示[4]：

（1） 扫描程序（scanner）

在这个阶段，编译器阅读源程序（通常以字符流的形式表示，比如本实验设计的C语言的源程序.c），由扫描程序执行词法分析（lexical analysis）：它将字符序列收集到称为记号（token）的单元中，也就是说，将其识别为一个个符合编程语言词法规范的单词符号。实际上，一个扫描程序所做的工作与自然语言中对英文单词的拼写是十分类似的。扫描程序还可完成与识别记号一起执行的其他操作，例如，可将相应的记号输入到对应的符号表中。

（2） 语法分析程序（parser）

语法分析程序从扫描程序中获取记号形式的代码，并完成定义程序结构的语法分析（syntax analysis），根据语言的语法规则将上阶段产生的单词串分解成各类语法单位（如表达式、语句、子过程等），这与自然语言中关于某篇文章的句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树或语法树。

（3） 语义分析程序（semantic analyzer） 程序的语义就是它的“意思”，程序如何运行以及运行结果都由它的语义来决定。大多数程序设计语言具有在执行之前被确定语义的特征，这些特征不容易用语法结构表示，更无法用词法分析程序进行分析，这些特征被称为静态语义。语义分析程序的职责就是分析这样的语义，为代码生成阶段搜集相关的语义信息。一般程序设计语言的典型静态语义有声明和类型检查。而在程序执行阶段才能确定的程序特性称为动态语义，语义分析程序无法对这类特性做出分析。语义分析程序还要计算被称为属性（attribute）的程序固有信息，如数据类型、值等。语义分析程序通常将计算后的属性值添加到语法树中（也可将属性添加到符号表中）。

（4） 源代码优化程序（source code optimizer） 完善的编译器通常包括许多代码改进和优化步骤。这些优化和改进一般是在语义分析之后完成的。在语法分析和语义分析的基础之上，将源程序变换为等价的中间代码。所谓中间代码，是指一种结构简单、含义明确、形式多样化的记号系统，它比较容易能转换为目标代码。优化程序将源代码以中间代码（intermediate code）的形式输出，进而完成对源代码的相应优化处理，目的是使将来生成的目标代码更为高效（即省时间、省空间）。

（5） 代码生成器（code generator）

这是编译的最后必备阶段，它将中间代码（或经优化后的中间代码）转换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。由于该阶段的工作与硬件系统结构和机器指令含义有关，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据的存储空间分配以及寄存器调度等，也就是说目标机器的特性成为了主要因

5

北京邮电大学毕业设计

素，所以这个阶段的工作相当复杂。正是出于这点考虑，本实验设计选择了与机器指令无关的三地址码的四元式表示形式。

（6） 目标代码优化程序（target code optimizer） 在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括对编址模式的选择、提高性能、将速度慢的指令更换成速度快的以及删除多余的操作等。

除了这6个阶段，编译器通常还包含一张符号表和访问该表的若干例程，以及针对编译过程中发现的各种错误进行检查和处理的错误处理程序，它们在编译过程的所有阶段都会使用到。

上述编译过程的阶段划分只是一个典型模式，事实上并非所有的编译程序都分成这6个阶段，有些编译程序并不生成中间代码，有些编译程序并不进行优化，有些最简单的编译程序甚至在语法分析的同时产生目标代码。编译器生成的目标代码可以是可重定位目标代码或汇编代码，如果是汇编代码则需要再用汇编器来生成可重定位目标代码，本实验设计的C编译器生成的目标代码是三地址码的四元式表示形式。

2.3 编译器的组织

2.3.1 编译的分遍

在2.2节中我们讨论了一个编译器的典型结构，简要介绍了编译器的6个阶段各自应完成的基本工作，并通过图2-2指出了它们之间的相互关系，但需要注意的是，这些关系仅代表它们之间的逻辑关系，并不一定就是执行时间上的先后顺序。事实上，可按不同的执行流程来组织上述各阶段的工作，这在很大程度上依赖于编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。这里所说的“遍”，是指对源程序或其内部表示从头到尾扫视一次，并进行有关的加工处理工作，每一遍的工作都是从获取上一遍的工作结果开始，经过本遍的加工后，将结果保存起来以便交给下一遍[5]。例如，对于要求经一遍扫描就能完成从源代码到目标代码翻译的编译程序，我们可以语法分析程序为中心来组织它的工作流程，这样就不必产生中间代码，显然，这种做法所得到的目标代码的质量是不能保证的，总体来说弊大于利。

对于绝大部分语言（例如Pascal或C），实现一遍扫描的编译程序是非常困难的，所以宜于采用多遍扫描的编译程序结构。具体的做法是将整个编译程序划分为若干个相继执行的模块，每一模块都对它前一模块的输出扫描一遍，并在扫描过程中完成前述6个阶段中的一个或几个，然后将工作结果保存下来供下一模块加工。显然，第一个模块所扫描的是字符序列形式的源程序，最后一个模块所输出的是目标代码，而每一个中间模块输出的是与源程序等价的内部表示或中间代码。 2.3.2 分遍的设计

在设计一个编译程序时，如何确定扫描遍数，如何组织各遍中的工作，主要取决于源语言的具体情况及编译程序运行的具体环境，如语言的结构、计算机软硬件的配置，以及对编译程序本身运行效率的要求等等。一般而言，多遍扫描源程序具有如下优点：

（1） 由于采用了模块结构，各遍扫描的功能相对独立，整个编译程序的结构比较清晰。

6

北京邮电大学毕业设计

（2） 由于对源程序及其内部表示进行多次扫视和加工，有利于进行比较细致和充分的代码优化处理。

（3） 由于可将编译程序按模块依次调入内存，有利于采用覆盖技术，以减少执行编译程序时所占的内存空间。

由于分遍问题对具体语言及编译程序的运行环境有很强的依赖性，经过权衡，本实验设计的编译器采用了简单的1遍扫描策略。

2.4 编译器中的主要数据结构

当然，编译器的各个阶段使用的算法与支持这些阶段的数据结构之间的交互是非常密切的。编译器的编写者在实施这些算法的同时应尽可能地保证它们不过于复杂，最理想的情况是：该编译器在编译时所耗费的时间与程序大小成线形比例，即时间复杂度为O(n)。能否达到这样的理想情况，很大程度上取决于所采用的数据结构，它们是各个阶段都需要使用到的，并用来在各阶段之间交流信息。通常编译器中的主要数据结构包括：记号、语法树、符号表、常数表、中间代码、临时文件等。

2.5 编译程序的开发

2.5.1 历史与发展

在编译器开发的原始阶段，人们主要用机器语言或汇编语言来构造编译程序，难度极大且效率很低。现在的大部分编译器是用某种高级语言开发的，这样更节约时间，而且易读、易改、易移植，同时也便于进行编译器的优化设计。相信在不久的将来，编译器的开发将主要借助于成熟的自动化生成编译程序技术。 2.5.2 开发注意事项

（1） 源语言：对被编译的源语言，要深刻理解其结构和含义。在定义C语言的过程中，是通过严格制定其词法规则、语法规则和语义规则来达到的。

（2） 目标语言： C编译器的目标语言选择为三地址的四元表达式。

（3） 编译技术：词法分析、语法分析、语义分析、代码优化及代码生成的相关技术有很多，必须根据所开发的编译器的需求和特点来选择最合适的编译技术和方法。关于C编译器中使用到的编译技术可详细参考论文第四章。

（4） 各种具体因素：例如系统功能要求、硬件开发环境、软件开发工具等。 2.5.3 编译技术和软件工具

为了提高软件开发的效率和保证开发质量，人们除了要遵循软件工程中对软件开发过程的规范化或标准化之外，还应尽量使用先进的软件开发技术和相应的软件工具，而大部分软件工具的开发，常常要用到编译技术和方法。实际上编译程序本身也是一种软件开发工具。为了提高编程效率，缩短调试时间，软件工作人员研制了不少对源程序处

7

北京邮电大学毕业设计

理的工具，这些工具的开发不同程度地用到编译程序各个部分的技术和方法，典型的有下面几种[7]：

（1） 语言的结构化编辑器：结构化编辑器是引导用户在语言的语法制导下编制程序，能自动地提供关键字和与其匹配的关键字，这样可以减少语法上的错误，加快对源程序的输入和调试，提高效率和质量。现在的可视化开发工具基本都具备了这个功能。

（2） 语言程序的调试工具：调试是软件开发过程中一个重要环节，凡是对算法的实现错误或程序没能反映算法的功能等错误就需用调试器来协助解决。调试器的功能越强则实现越复杂，它必须与语法分析、语义处理有紧密联系。

（3） 语言程序测试工具：对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系；也可在源程序的适当位置插入某些信息，并用测试用例记录程序运行时的实际路径，将运行结果与期望的结果进行比较分析，帮助编程人员快速查找问题所在。

（4） 高级语言之间的转换工具：为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题，这种异种程序设计语言之间的翻译转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已，这与实现一个完整的编译程序相比工作量要少些。

（5） 并行编译技术：随着并行机及多处理机的发展，对软件的并行处理提出了新的要求，特别是并行编译技术发展很快。运用重构技术把已有的串行语言编写的程序经过分析分解成可并行的成分，然后分配到多处理机上运行。如果编程人员能按程序设计情况写出并行语言程序，那么两者结合将产生更高的效率。

8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库C语言编译器设计与实现毕业论文设计(3)在线全文阅读。