编译原理

基本概念

编译原理即是对高级程序语言进行翻译的一门科学技术, 我们都知道计算机程序由程序语言编写而成, 在早期计算机程序语言发展较为缓慢, 因为计算机存储的数据和执行的程序都是由0、1代码组合而成的, 那么在早期程序员编写计算机程序时必须十分了解计算机的底层指令代码通过将这些微程序指令组合排列从而完成一个特定功能的程序, 这就对程序员的要求非常高了。人们一直在研究如何如何高效的开发计算机程序, 使编程的门槛降低。

编译器

C语言编译器是一种现代化的设备, 其需要借助计算机编译程序, C语言编译器的设计是一项专业性比较强的工作, 设计人员需要考虑计算机程序繁琐的设计流程, 还要考虑计算机用户的需求。计算机的种类在不断增加, 所以, 在对C语言编译器进行设计时, 一定要增加其适用性。C语言具有较强的处理能力, 其属于结构化语言, 而且在计算机系统维护中应用比较多, C语言具有高效率的优点, 在其不同类型的计算机中应用比较多。

编译过程一般是在计算机系统中实现的, 是将源代码转化为计算机通用语言的过程。编译器中包含入口点的地址、名称以及机器代码。编译器是计算机程序中应用比较多的工具, 在对编译器进行前端设计时, 一定要充分考虑影响因素, 还要对词法、语法、语义进行分析。

1 词法分析

词法分析是编译器前端设计的基础阶段, 在这一阶段, 编译器会根据设定的语法规则, 对源程序进行标记, 在标记的过程中, 每一处记号都代表着一类单词, 在做记号的过程中, 主要有标识符、关键字、特殊符号等类型, 编译器中包含词法分析器、输入源程序、输出识别记号符, 利用这些功能可以将字号转化为熟悉的单词。

2 语法分析

语法分析是指利用设定的语法规则, 对记号中的结构进行标识, 这包括句子、短语等方式, 在标识的过程中, 可以形成特殊的结构语法树。语法分析对编译器功能的发挥有着重要影响, 在设计的过程中, 一定要保证标识的准确性。

3 语义分析

语义分析也需要借助语法规则, 在对语法单元的静态语义进行检查时, 要保证语法规则设定的准确性。在对词法或者语法进行转化时, 一定要保证语法结构设置的合法性。在对语法、词法进行检查时, 语法结构设定不合理, 则会出现编译错误的问题。前端设计对精确性要求比较好, 设计人员能够要做好校对工作, 这会影响到编译的准确性, 如果前端设计存在失误, 则会影响C语言编译的效果。

C语言编译器是一种先进的设备, 其可以将繁琐复杂的程序转换为机器语言, 具有化繁为简的功能, 在对C语言编译器进行划分的过程中, 需要了解语法构成原理, 设计人员需要灵活掌握语言语法知识, 还要应用C语言代码转化方式, 在对C语言编译器进行总体设计时, 需要从以下几个方面入手。

1 词法分析

C语言程序具有一定的复杂性, 语法分析是编译的初级阶段, 这一过程主要是对词法进行扫描, 所以词法分析阶段, 编译器也被用作是扫描器, 其主要的任务是将源程序中的字符进行连接, 并且对其中的词语进行识别, 并且对词汇进行转化, 将其转换为内部编码, 并且对其语法进行分析与标记。单词符号在编译的过程中, 一般会被转化为二元式, 单词类别主要有二进制、分隔符、单词等, 计算机在正常工作时, 会通过扫描器自动完成词法扫描工作, 这一过程也会自动将注释进行删除, 会将源程序中的单词进行自动识别, 还会将其转换为内部编码。从工作方式角度来分析, 编译流程与语法属于两种接口方式, 若是从功能上讲, 编译器词法分分析的过程主要就是将相应的字符源程序进行转换处理, 从而变成单词串的形式。

2 语义分析

将编译程序转换为一种内部表现形式后, 我们将该种内部表现形式称之为中间语言或者是中间代码, 它含义明确、结构简单, 属于一种记号系统。比如一些编译程序, 基本上没有中间代码, 但是为了在实际应用中, 确保机器的独立运行, 易于实现目标代码的优化, 在许多的编译程序中均设置了中间语言。这种中间语言介于机器语言和源程序语言中, 程序相对复杂, 而C语言编译器却在很大程度上改变以上现状, 其语义分析和语法分析相对成熟, 理论和算法比较完善, 可仍旧存在的问题是没有公认的形式系统, 中间代码仍旧接近于形式化的方法。

3 语法分析

语法分析主要是以单词串形式的源程序作为分析与输入对象, 其最为根本的目标和任务就是为了以设计语言的语法规则为标准, 对源程序的语法结构进行具体的分析, 根据设计语言的语法规则, 对组成这些源程序的语法成分进行分析, 如函数、下标变量、各种程序语句、各种表达式等等, 并且要通过正确性的语法检查, 将中间代码进行阶段处理。但是要注意的一点是根据需要进行了归约处理, 必然存在着相应语法错误, 那么可以将其中全部输入的符号删除, 改变上述格局, 进行移进和归约分析, 并且在此基础上, 不断地寻找一个相应的策略, 从而形成有效的语法分析方法。

课程

《编译原理》作为计算机专业的一门重要专业课程, 是日后深入研究专业领域知识的基础。这门课作为计算机科学与技术的专业课, 融合了离散数学、数据结构、操作系统、计算机组成原理等多个学科的知识, 属于综合性与理论性较强的一门课, 由于编译原理课程内容的以上特点, 目前在实验教学中仍存在一些问题。编译原理实验部分若要设计制作完整的编译器, 实验周期长, 涉及的模块较多, 各模块间衔接较复杂, 不易立即看到整体效果。

计算机类专业本科生学习本专业的第一门语言课程是C语言。C语言由于其类型不安全性, 容易出现一些难以捉摸的错误, 使得学生难以定位和解决问题。如果能让学生根据编译器提供的提示信息, 精确定位程序中的错误类型和位置, 把编译原理中所学用于实际C语言编程需求, 这既完成了课程的教学内容, 也提升了学生的软件编程和系统分析的能力。

从普通高等院校的编译原理教学实际出发, 其课程覆盖范围一般仅限于编译器的前端, 即词法分析、语法分析和语法制导翻译等内容。这其中包括大量抽象且逻辑复杂的理论知识点, 如形式语言理论、正规式、有限自动机、上下文无关文法、属性文法和语法制导翻译等。传统的教学方式强调知识点的灌输, 让学生解决孤立的单一问题, 缺乏各知识点之间的关联。这种“只见树木, 不见森林”的教学方式会极大地削弱学生的学习积极性, 导致整体效果不佳。

(一) 理论与实践相衔接

理论知识的来源一般都有其确定的问题背景。脱离实际问题来进行理论教学, 对学生实际能力的提升没有益处。编译原理课程中的大量理论知识, 存在一种衔接递进的关系, 每个知识点的引入和拓展, 都是对于现实遇到问题的解决路径再现。因此, 整个授课过程就在重现这种解决方案演变的变化历程。而实现这一目标的关键之处, 是教师从之前的“站到讲台前”变到现在的“坐在学生中”。这一变化绝不仅仅是简单地将所有问题留给学生, 从“讲授”变成“答疑”, 而是从问题设计、思考启迪、讨论引导到过程管理等各方面都对教师提高了要求。特别是现代高级语言发展日新月异, 各种新问题层出不穷, 如何在面对开放性的未知问题时, 从系统和整体的角度给出学生解决问题的方式方法, 而不是给出具体每个问题的回答, 这是对教师能力的一种新考验。

(二) 编译器设计实现方案

编译原理课程教学理想情况, 学生应该能够独立自主完成小型编译系统的构造。实际教学中, 学生只需吃透关键的几条原理知识, 如NFA的确定化, LL (1) 文法中FIRST和FOLLOW集合的构造,LR (1) 文法中识别活前缀DFA构造等, 基本上已经满足了课程考试要求。然而, 仅靠理论学习对实现一个基础编译器来说是远远不足的。相比较于学生对理论知识的接受程度, 学生自主动手完成编译系统的能力缺乏就更为明显。如何面对全体学生, 制定出一套适用的实践方案, 是课程实际效用的关键。

发展

在早期冯诺依曼计算机时期 (20世纪40年代) 程序都是以机器语言编写, 机器语言就是实际存储的01代码, 编写程序是十分枯燥乏味的。后来汇编语言代替机器语言一符号形式该处操作指令和地址编码。但汇编语言仍有许多缺点, 阅读理解起来很难, 而且必须依赖于特定的机器, 如果想使编写好的程序在另一台计算机上运行必须重写。在20世纪50年代IBM的John Backus带领一个研究小组对FORTRAN高级语言及其编译器进行开发。编译程序的自动生成工具初现端倪, 现在很多自动生成工具已经广泛使用例如语法分析工具LEX, 语言分析程序YACC等。在20世纪60年代人们不断的用自编译技术构造编译程序, 即用被编译的语言本身来实现该语言的编译程序, 但其基本原理和结构大体相同。经过不断发展现代编译技术已经较为成熟, 多种高级语言发展迅速都离不开编译技术的进步。

基本流程

编译可以分为五个基本步骤:词法分析、语法分析、语义分析及中间代码的生成、优化、目标代码的生成。这是每个编译器都必须的基本步骤和流程, 从源头输入高级语言源程序输出目标语言代码。

1 词法分析

词法分析器是通过词法分析程序对构成源程序的字符串从左到右的扫描, 逐个字符地读, 识别出每个单词符号, 识别出的符号一般以二元式形式输出, 即包含符号种类的编码和该符号的值。词法分析器一般以函数的形式存在, 供语法分析器调用。当然也可以一个独立的词法分析器程序存在。完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。

2 语法分析

语法分析是编译过程的第二个阶段。这阶段的任务是在词法分析的基础上将识别出的单词符号序列组合成各类语法短语, 如“语句”, “表达式”等.语法分析程序的主要步骤是判断源程序语句是否符合定义的语法规则, 在语法结构上是否正确。而一个语法规则又称为文法, 乔姆斯基将文法根据施加不同的限制分为0型、1型、2型、3型文法, 0型文法又称短语文法, 1型称为上下文有关文法, 2型称为上下文无关文法, 3型文法称为正规文法, 限制条件依次递增。

3 语义分析

词法分析注重的是每个单词是否合法, 以及这个单词属于语言中的哪些部分。语法分析的上下文无关文法注重的是输入语句是否可以依据文法匹配产生式。那么, 语义分析就是要了解各个语法单位之间的关系是否合法。实际应用中就是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查等。

4 中间代码生成与优化

在进行了语法分析和语义分析阶段的工作之后, 有的编译程序将源程序变成一种内部表示形式, 这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统, 这种记号系统复杂性介于源程序语言和机器语言之间, 容易将它翻译成目标代码。另外, 还可以在中间代码一级进行与机器无关的优化。

5 目标代码的生成

根据优化后的中间代码, 可生成有效的目标代码。而通常编译器将其翻译为汇编代码, 此时还需要将汇编代码经汇编器汇编为目标机器的机器语言。

6 出错处理

编译的各个阶段都有可能发现源码中的错误, 尤其是语法分析阶段可能会发现大量的错误, 因此编译器需要做出错处理, 报告错误类型及错误位置等信息。

编译过程

C语言的源程序和对应的可执行程序执行时在内存中的运行结构，实现这一转换的最主要的过程就是编译。

源程序是给人看的，本质上就是文本文件，可以用Linux中的vi或Windows中的记事本之类的文本编辑程序打开、编写，但计算机无法直接执行源程序，需要通过一个专门的程序将源程序编译为计算机可执行程序，这个专门的程序就是编译器。编译过程主要分为词法分析、语法分析、中间代码生成、目标代码生成（忽略预处理、语义分析、优化等）。下面我们依次简要讲解编译的主要过程。

人眼中看到的源代码是这样的：

而它在计算机中存储的形式如图1-36所示。



图1-36 案例程序的十六进制形式

这里看不出关键字、运算符、标识符，甚至看不出哪几个字符属于同一个符号。编译的第一阶段是词法分析，目的就是在连续的字符中识别出一个一个的符号，并尽可能地识别出符号的属性。

人们在看C语言源程序时，借助空格、括号等一眼就可以看出标识符、关键字。与人相比，现在计算机的智能还是相当低的，无法像人那样同时看多个字符，只能依据一个非常机械的“电子版”词法，一个字符一个字符地识别。“电子版”词法是将状态转换图的思路融汇在词法分析器的代码中得以体现的。词法分析器从源程序的字符串中识别出一个个符号（token），并按序保存。

词法分析的结果如图1-37所示。



图1-37 词法分析的结果

在词法分析阶段能够识别出一些符号的含义，它们包括关键字、数字、字符串、分隔符，这些符号的含义不需要其他符号的辅助就能确定本身的含义。比如，“int”一定代表整数类型，它不可能是一个变量名称，也不可能是一个运算符。

而另外一些符号需要通过前后的其他符号才能确定出准确含义。比如“m”，在词法阶段仅能判断这是一个标识符，但是如果不对所在的句做分析，就无法得知这个标识符代表一个变量还是一个函数。更多详细的信息需要对符号所在的句型做分析才能获得。这部分工作由语法分析来完成。

如果说词法分析的作用是从连续的字符中识别出标识符、关键字、数字、运算符并存储为符号（token）流，语法分析的作用就是从词法分析识别出的符号流中识别出符合C语言语法的语句。

因为计算机无法像人那样同时看多个标识符、关键字、数字、运算符，无法像人那样一眼看出这是一个函数声明，那是一个if语句，只能非常笨拙地一个符号一个符号去识别。与词法分析器有些类似，语法分析器也是依据用计算机表示的语法，一个符号一个符号地识别出符合C语言语法的语句。语法的计算机表示就是产生式。在语法分析器中把通过产生式产生的C语言语法映射成一套模板，并把这套模板融汇在语法分析器的程序中。语法分析器的作用就是将词法分析器识别出的符号（token）一个一个地与这套模板进行匹配，匹配上这套模板中的某个语法，就可以识别出一句完整的语句，并确定这条语句的语法。

我们以案例中“int fun(int a，int b);”这条函数声明语句为例描述这个过程，它与语句模板的匹配情景如图1-38所示。



图1-38 fun函数声明语句与模板匹配的结果

这段token流最终与函数声明模板相匹配，在匹配成功后，计算机就认为此语句为函数声明语句，并以语法树的形式在内存中记录下来，情景如图1-39所示。



图1-39 fun函数声明语句生成的语法树

以树型结构来记录分析出的语句是一个非常巧妙、深谋远虑、通盘考虑的选择。一方面，树型结构能够“记住”源程序全部的“意思”，另一方面，树型结构更容易对应到运行时结构。

至此，语法树已经承载了源程序的全部信息，后续的转换工作就和源程序没关系了。

如果希望一步到位，从语法树转换为目标代码，理论上和实际上都是可行的。但计算机存在多种CPU硬件平台，考虑到程序在不同CPU之间的可移植性，先转换成一个通用的、抽象的“CPU指令”，这就是中间代码最初的设计思想。然后根据具体选定的CPU，将中间代码落实到具体CPU的目标代码。

语法树是个二维结构，中间代码是准一维结构，语法树到中间代码的转换过程，本质上是将二维结构转换为准一维结构的过程。中间代码特别是RTL已经可以和运行时结构一一对应了。如图1-40所示。 



图1-40 中间代码与目标代码对应的情景示意

运行时结构也是一维的，图1-40左侧部分的转换结果将更贴近运行时结构。

选定具体的CPU、操作系统后，中间代码就可以转换为目标代码——汇编代码（我们配置的是AT&T汇编），这时操作系统的影响还比较小。然后由汇编器依照选定操作系统的目标文件格式，将.s文件转换为具体的目标文件，对于Linux而言是.o文件，对于Windows而言是.obj文件。目标文件中已经是选定的CPU的机器指令了。

最后链接器把一个或多个目标文件（库文件本质上也是目标文件）链接成符合选定操作系统指定格式的可执行文件。

通过操作系统，可执行程序就可以被载入内存执行，形成前两节我们所看到的运行时结构。

本书后续内容将详细讲解编译的主要过程：词法分析、语法分析、中间代码到目标代码，然后是汇编与链接，最后讲解预处理。