编译技术综述

2018-08-22 19:35张世奇
科学与财富 2018年20期
关键词:句柄

张世奇

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

关键词: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

猜你喜欢
句柄
TCP/UDP Socket调试工具
基于MATLAB的上海500型拖拉机360°环影系统GUI设计
VBA 7.0的代码兼容性研究
高校图书馆持久标识符应用研究
编译程序语法分析句柄问题分析与探讨
基于句柄和脚本定制的试飞数据自动卸载工具
UEFI驱动程序的研究与开发
油气处理系统集成化的安全管理
基于分布式环境的子进程监控软件设计与实现*