快速掌握编译器设计方法

刘 涛，贾丽娟，于 峰

（1. 哈尔滨理工大学 计算机学院，黑龙江 哈尔滨 150000；2. 哈尔滨理工大学 理学院，黑龙江 哈尔滨 150000）

0 引言

现实世界依赖着程序设计语言设计[3]开发各种软件，解决各领域诸多问题。作为一名理工科院校学生，学会用高级语言编程是其应该具备的最基本的能力，这就需要所用软件平台[8]要提供较好的编译器[1]。软件开发商为我们提供了各种平台的不同语言[9]的编译器，但有些设备（如手机或 PAD）的编译器能力较弱，需要后期的开发者对其进行改进或重新编写。

简单讲，编译器就是将"一种语言(通常为高级语言)"翻译为"另一种语言(通常为低级语言)"的程序。其中主要涵盖了最重要的词法分析和语法分析过程，再之后进行语义分析生成中间代码及优化，生成目标代码。

因此，写好一个编译器程序的前提是要了解编译器的运行原理[4]，并掌握它的词法分析技术与语法分析技术[5]。编译的宗旨是在翻译一个源程序的过程中，编译器所做的所有翻译工作都不能改变被翻译的源程序的含义，这是我们需要遵循的根本原则。

通过对下面对编译器的词法分析器和语法分析器的分析，再写编译器编程就方便了许多。

1 词法分析器[1]

词法分析器的功能输入源程序，按照构词规则分解成一系列单词符号。单词是语言中具有独立意义的最小单位，包括关键字、标识符、运算符、界符和常量等。

首先介绍一下词法分析器，词法分析器读入组成源程序的字符流，并且将它们组织成有意义的词素序列。每组成一个词法单元（Token）就将其传给语法分词器，例如：

int i=10;

那么词法分析器所要做的就是将int ,i ,= ,10分别识别然后结合各词素对应的属性（例如10，作为一个NUM，10就是它的属性value）打包成词法单元传送给语法分析器。

图1 编译流程Fig.1 Compile process

词法分析器需要和符号表进行交互，当词法分析器发现一个标识符的词素‘adan’时，它会询问符号表是否已经存在这一词素，如果没有就创建新的词法单元，并将其加入到符号表中，如果已经存在就读取标识符的信息，以确定向语法分析器传送哪个词法单元。同时词法分析器除了负责读取源程序，它还会执行另外两大任务：

（1）过滤空白和注释

（2）将编译器生成的错误信息与源程序的位置联系起来。

在词法分析器中通常会用正则表达式俩描述一个标识符，对于正则表达式的规则就不做过多的叙述，只在这列举一下用正则表达式在表示的词法单元的模式[1]：

表1 词法单元的模式Tab.1 The pattern of the lexical unit

知道怎么去表达一个标识符之后我们就借助状态转移[1]图来模拟一下词法分析器运行的过程[1,5]：

getToken()：查看对应于刚找到的词素的符号表条目，并且根据符号表中的信息返回该词素所代表的词法单元名字—要么是 id，要么是一个初始化时就加入到符号表的关键字。

图2 r elop状态转移图Fig.2 Relop state transition diagram

图3 ID 和关键字的状态转移图Fig.3 State transfer graph of ID and keywords

图4 无符号数字的状态转移图Fig.4 S tate transition diagram of unsigned digits

2 语法分析器[1]

接下来就介绍一下语法分析器，在设计语言时，每种程序设计语言都有一组精确地规则来描述良构程序的语法结构，程序设计语言的语法可以用上上下文无关文法来描述，文法为语言设计者和编译器的编写者都提供了很大的便利，有很多很多的文法可以用来很好的描述程序设计语法，我们使用预测分析算法[1]来实现一个预测分析表[1]：

expression代表表达式，term代表项factor代表因子：

Expression ->expression + term | term;

term -> term* factor | factor

factor ->NUMBER | (expression)

以上这个文法指明了运算符的结合性和优先级，该文法属于LR（第一个L代表从左向右扫描输入，第二个R代表出声最左推导）文法，适用于自底向上[1]语法分析，但是其为左递归[1,2]，不能用于自顶向下[1]的语法分析，所以推出以上文法的非左递归版本（可用于自顶向下的语法分析）：

expression代表表达式，term代表项factor代表因子；而expression'和term'是为了解决左递归的情况，所以以下给出非左递归的表达式文法：

（1）statements -> “空” | expression; statements

（2）expression-> term expression'

（3）expression'-> +term expression' | “空”

（4）term -> factor term'

（5）term' -> * factor term' | “空”

（6）factor -> number | (expression)

这组修改后的语法规则比修改前更加难以理解，但能保证，这组规则不会出现修改前那样导致解析死循环[1,7]。语法规则中的“空”表示结束，什么都不做。例如如果我们输入一个空字符串“”给语法解析器，那么规则 1中就以“空”来解析输入的空字符串，其结果就是程序什么都不做，直接返回，在程序中“空”相当于return语句。

我们用表达式：1 + 2 ; 看看语法规则形成的解析树[1]是怎样的：

我们以语句id+id*id为例子换一种方式运用栈来通过每步移入归约[2]实现，如表2所示。

给出表驱动的预测语法分析：

输入：一个串W，文法G的预测分析表M。

输出：W在L(G)中，输出的W的第一个最左推导，否则错误提示。

方法：

最初，语法分析器格局：输入缓冲区的是W$，而 G的开始符号S位于栈顶，他的下面是$。一下程序使用预测分析表M生成了处理这个输入的预测分析过程：

设置ip是它指向W的第一个字符，其中ip是输入的指针

while(x!= $){//栈非空

if(x等于ip所指向的符号a)指向栈弹出操作，将ip向前移动一个位置

else if(x是终结符号) error();

else if(M[x,a]是一个报错条目) error();

else if(M[x,a]=x→Y1Y2……Yn){

输出产生式x→Y1Y2……Yk);

输出栈顶符号;

将YkYk-1……Y1压入栈，其中Y1位于栈顶;

}

令x=栈顶元素;

图5 语法规则解析树Fig.5 Parsing tree of syntax rules

表2 id+id＊id行为流程Tab.2 The behavior process of Id+id＊id

}[2]并且编译器的好坏可以在很大程度上影响着这一门编程语言的使用频率，一个好的编译器可以极大的提高程序效率，反之，亦可加大程序的开销，所以编译器的设计和优化[6]都显得尤为重要，希望更多有能力的人投入进来，开发出更为便捷，强大的编译器！

3 结论

了解一个编译器到底在干些什么事情对我们理解语言本身有很大的帮助，当然编译技术本身也有很大的应用潜力。

[1] (美)Alfred V. Aho, Monica S.Lam,Ravi Sethi, Jeffrey D.Ullman, 编译原理[M]. 机械工业出版社, 2008.

[2] 埃克尔, Java编程思想(第四版)[M]. 机械工业出版社, 2007.

[3] Steve McConnell, 代码大全(第2版)[M]. 电子工业出版社出版, 2006.

[4] 高伸仪. 编译原理及编译程序构造[M]. 北京: 北京航空航天大学出版社, 1990.

[5] DavidR. Hanson, ChristopherW.F.可变目标C编译器——设计与实现[M]. 北京: 电子工业出版社, 2005.

[6] 王凤英. C++编译器应用研究与评析[J]. 计算机工程与应用, 2002(15): 121-123.

[7] 吴元斌. C/C++运算求值顺序的缺陷分析[J]. 现代计算机(专业版), 2003(07): 60-62.

[8] C++语言开发跨平台程序的研究与实现[J]. 熊凯, 高茂庭,于仁师. 电脑知识与技术. 2006(05).

[9] Platform-independent code conversion within the C++locale framework. Lars Engebretsen. Software. 2006.

[10] Developing platform independent designs:Model-based design is used to develop source code for multiple compilers,languages and platforms,. Colin Holland. Embedded Systems Europe. 2006.