编译技术综述-第1篇

编译技术综述

张世奇Summary：本文通过介绍编译技术的发展历史，进而引入编译系统，通过对编译系统的五大步骤的系统介绍，使读者初步认识什么是编译系统，以及编译系统各个步骤的主要功能。最后联系当前人工智能技术，分布式技术，多核技术对编译技术的影响，对未来的编译技术的发展进行展望。Key：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）汇编语言代码。三、对未来编译技术的展望随着人工智能技术的崛起，将人工智能技术应用与编译技术，为大幅提升编译效率带来了希望。如今，双向长短期神经网络已经初步运用到了词法分析当中，使词法分析效率进一步提高。此外，就目前的分布式技术发展情况来看，并行编译技术已经使编译速度大大提高，近年来分布式技术的迅速发展发展，并行运算量将会再上一个台阶，这将极大推动并行编译技术的发展。从硬件发展的角度来看，随着多核技术的不断成熟，编译技术正逐步从单核编译技术向多核编译技术转变，从而提高编译执行的效率，我们相信随着未来技术的不断进步，编译技术必将迎来革命性的发展。Reference：[1]陈火旺，钱家骅，孙永强。著，程序设计语言编译原理[M]国防工业出版社，2017.3[2]AlfredV.Aho，MonicaS.Lam，RaviSethi，JeffreyD.Ullman著，机械工业出版社，2008.12[3]赵雄芳，白克明，易忠兴，张克强，编译原理例解析疑。长沙：湖南科技出版社，1991科学与财富2018年20期科学与