编译技术综述

张世奇

摘要：本文通过介绍编译技术的发展历史，进而引入编译系统，通过对编译系统的五大步骤的系统介绍，使读者初步认识什么是编译系统，以及编译系统各个步骤的主要功能。最后联系当前人工智能技术，分布式技术，多核技术对编译技术的影响，对未来的编译技术的发展进行展望。

关键词：DFA，NFA，句柄，最左素短语

一、编译技术发展历史

在二十世纪五十年代，编译器的开发还是一件非常困难的事情。因为早期大多数的编译工作是人们手动将算术公式翻译为机器代码，当面对复杂的运算公式时，这项工作就变得十分繁琐。在这个时期，出现了许多高级编程语言，然而第一个Fortran编译器却经历了多年的开发才完成。到二十世纪年代末期，研究人员开始研究能够自动编译的工具。从二十世纪六十年代开始，人们开始使用自展技术来构造编译程序。

近二十年来，随着计算机技术的迅猛发展，编译技术也有了长足进步，涌现出了多种优异的编译技术，如并行编译技术，交叉编译技术等等。与此同时，认人们也开发了多种自动生成工具，LEX用于生成词法分析程序，YACC用于生成语法分析程序等。

二、编译系统

我们使用高级编程语言边写程序，通常是将我们对业务逻辑的理解转化为程序代码。编译则是将我们编写的源程序通过转化，成为计算机能够运行的机器代码。编译过程主要分为以下五个阶段（如下图一）。

（一）词法分析

词法分析器工作的首要步骤是对输入的源程序进行预处理，即去除空白符，回车符等编辑性字符，此外还要去除程序中出现的注解。其次，通过超前搜索来对输入的单词符号进行识别。最后，构建非确定有限自动机（NFA），并对NFA进行确定化，使其转换为有限自动机（DFA）来识别字符串。

（二）语法分析[1]

语法分析是建立在词法分析的基础之上进行的，它根据文法的产生式来识别输入的字符串是否可以构成一个句子。下面会介绍两种语法分析的方法。

自上而下分析法是基于文法进行的，以文法产生式的开始符号作为树根，自顶向下的构建一棵语法树。语法分析过程从本质上来讲，是一种试探性的分析过程，是一个不断使用不同的产生式来进行字符串匹配的过程。

自底向上分析法分为算符优先分析法和规范分析法。它们均利用了计算机中的栈，用一个栈区来存储产生式中的符号，利用栈先进后出的特性，先把符号一个一个移进到栈中。当栈顶出现某一个产生式的候选式时，把栈顶的这一部分进行规约。其中规范规约首先利用产生式规则，对输入串构建一棵语法树，根据构建的语法树寻找句柄，并在符号栈内进行规约。算符优先分析同样需要根据产生式规则建立一棵语法树，并寻找最左素短语来进行规约，由于算符优先分析跳过了所有单非产生式对对应的规约步骤，由此可能会出现无法构成句子的输入串，误认为是一个句子的错误。

（三）语义分析与中间代码生成[2]

当词法分析和语法分析完成后，编译程序就要进行静态语义检查和翻译。所谓静态语义检查，即操作符的类型检查，对控制流语句使用的合法性进行检查，检查是否有对象被重复定义，以及相关名字检查。

在编译过程中，我们还需要将源程序转化为中间语言，通常有后缀式、三地址代码以及DAG图三种方式。

后缀式表示法，又被人们称之为逆波兰表达式。这一种表示方法，其主要作用是将表达式中的操作数写在表达式前面，将算符写在表达式的后面。

图表示法包括两种表达方式，分别为DAG和抽象语法树。

（四）优化

优化的目的是为了提高代码效率，在优化时，对代码的变换需要遵守以下原则：

1）等价原则。代码经优化过后不会影响代码最终的执行结果。

2）有效原则。使代码优化后，尽可能的降低时间复杂度和空间复杂度，使减少代码运行时间，占用较小的内存

3）合算原则。尽可能以较小代价取得较好的优化效果。

代码优化通常使用这几种方法：

1）删除公共子表达式

假设一个表达式S被计算过一次，且在计算之后表达式S之中的变量值为发生改变，那么我们将S称之为公共子表达式。我们为了避免对这些公共表达式的重复计算，要将它们删除，也可以称为删除多余运算。

2）复写传播[3]

例如H1：=H2； Z：=X[H1]；

H2将值付给H1，Z=X[H1]；引用了H1的值，我们可以将Z=X[H1]；改为Z=X[H2]；我们称这种变换方式为复写传播。

3）删除无用代码

对于进行复写传播的表达式中的变量以及一些临时变量，因为在整个程序中不会被再次使用，且这些变量的赋值对程序运行的最终结果没有影响。我们可以将其删除。

4）代码外提

对于程序之中的循环结构，若一些代码在循环中产生的结果是不改变的，我们可以将这一部分代码从循环内部提取出来，将它们放在该循环结构外面。

5）强度削减

将循环中的乘除法变为加减法，因为在计算机中，加减法的运算速度要比乘除法的运算速度快。

6）删除归纳变量

（五）目標代码生成

该阶段利用经语义分析或者优化后的中间代码转化为目标代码。

目标代码通常有以下三种形式：

1）计算机可以立即执行的机器代码

2）待装配的机器语言模块

3）汇编语言代码。

三、对未来编译技术的展望

随着人工智能技术的崛起，将人工智能技术应用与编译技术，为大幅提升编译效率带来了希望。如今，双向长短期神经网络已经初步运用到了词法分析当中，使词法分析效率进一步提高。此外，就目前的分布式技术发展情况来看，并行编译技术已经使编译速度大大提高，近年来分布式技术的迅速发展发展，并行运算量将会再上一个台阶，这将极大推动并行编译技术的发展。从硬件发展的角度来看，随着多核技术的不断成熟，编译技术正逐步从单核编译技术向多核编译技术转变，从而提高编译执行的效率，我们相信随着未来技术的不断进步，编译技术必将迎来革命性的发展。

参考文献：

[1]陈火旺，钱家骅，孙永强。著，程序设计语言编译原理 [M]国防工业出版社，2017.3

[2]Alfred V.Aho ，Monica S.Lam，Ravi Sethi，Jeffrey D.Ullman 著，机械工业出版社，2008.12

[3]赵雄芳，白克明，易忠兴，张克强，编译原理例解析疑。长沙：湖南科技出版社，1991