编译器词法分析程序实现探讨

朱朝霞

（长江大学计算机科学学院，荆州434023）

0 引言

编译原理是计算机学科的一门专业核心课程，在计算机科学领域中具有重要地位，学习编译原理课程的目的在于让学生系统地了解并掌握程序设计语言编译器的构造原理及实现技术。词法分析是编译程序的第一步，其主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。构造程序设计语言的词法分析程序有手工生成和自动生成2种方法，在本课程的教学中笔者发现很多同学不能理解词法分析的2种生成方法的实质，以至于很难真正掌握词法分析技术。本文以词法分析程序的实现为主线，剖析手工实现与自动生成的本质与区别，以对编译原理教学有所启发。

1 单词的描述

为构造识别语言单词符号的词法分析程序，必须先对单词进行结构描述。目前，多数程序设计语言的单词符号都能使用正规文法或正规式进行描述。

例如以“标识符”为例，用正规文法描述可写为：

＜标识符＞→l｜l＜字母数字＞

＜字母数字＞→l｜d｜l＜字母数字＞｜d＜字母数字＞

用正规式描述可写为：字母（字母｜数字）＊

其中l代表a～z中任一英文字母；d代表0～9中任一数字。2种定义方式各有不同的特点，用正规式定义简洁清晰，用正规文法定义单词易于识别。

2 词法分析程序的实现

构造词法分析程序有2种方法：一是通过手工方式实现，即根据识别语言单词的状态转换图，使用某种高级语言直接编写词法分析程序；二是利用词法分析程序的自动生成工具自动生成。

2.1 词法分析程序的手工实现

一个词法分析程序手工生成可通过以下步骤得到：

（1）根据语言的词法规则写出描述单词的正规文法或正规式；

（2）将正规文法或正规式转换成相应的状态转换图NFA（Nondeterministic Finite Automata）；

（3）将NFA确定化并最小化转换为DFA（Deterministic Finite Automata）；

（4）将最小化的DFA转换成算法的流程图，进而实现词法分析程序。

用图1可描述为：

图1 词法分析程序的手工生成

可见，词法分析程序的手工生成其实质是通过有穷自动机来实现词法分析程序，只要构造出识别语言单词符号的有穷自动机，就很容易构造出识别语言单词符号的词法分析程序。状态转换图实际上是词法分析程序的流程图。

编译程序的词法分析采用手工实现具有工作量大，维护困难等缺点，现在多数编译器的词法分析程序都是利用自动生成工具来完成，从而省掉了手工编写词法分析程序的烦琐工作。

2.2 词法分析程序的自动生成

词法分析程序的自动生成是指由一个自动生成程序来生成词法分析程序。目前，词法分析程序自动生成工具有1972年美国Bell实验室用C语言研制的词法分析程序自动生成工具LEX（Lexical Analyzer Generator），可在 UNIX、Linux、DOS、Windows等环境下运行。其工作原理是将LEX源程序中的正规式转换成相应的DFA，并将相应的动作插入到输出的词法分析器中适当的地方，控制流由该DFA的解释掌握。其中LEX源程序用来描述各类语言的语法，由说明部分、识别规则和辅助过程3部分组成。

LEX的使用流程为：

（1）使用正规式描述语言的词法并编写LEX源文件；

（2）编译运行LEX源文件，产生LEX语言目标程序文件lex.yy.c；

（3）lex.yy.c程序经由C编译，并和其他 C模块连接产生执行文件a.out（即词法分析程序）；

（4）调试执行文件，直至将输入字符流变换成正确的单词流。

LEX必须和C一起使用，LEX源文件含有大量的C语言程序，并且LEX不能检测源文件中C代码的任何错误。词法分析自动生成的流程可用图2表示。

图2 使用LEX生成词法分析程序

例：下面以C语言的标识符、部分关键字、运算符和分界符为例构造其LEX源程序。

程序中1～4行为插入到LEX产生的C程序中，位于任何过程的外部；5～8行为正规式的定义；9～15行为识别规则部分；11～13行表示在识别标识符、关键字、运算符和界符时输出不同的内容。22～26行为主函数，打开输入输出文件。此LEX源程序经过LEX编译器运行，产生一个C语言程序lex.yy.c，经过C语言编译器编译后生成词法分析程序a.out，此时输入下段C语言源程序

由上例可见，对于任何一种高级语言，若要构造其词法分析程序，只须用LEX源程序描述该语言的语法，LEX编译系统对LEX源程序处理后，便可产生这种高级语言的词法分析程序。

3 结语

词法分析程序使用高级语言手工生成，程序结构复杂，不易修改。词法分析程序利用自动工具实现，程序结构简单，并将词法分析的重点放在正规表达式的描述和识别正规表达式之后的处理上，更易于维护词法分析器。正确理解词法分析程序手工生成与自动生成2种方法的实质及区别，对于正确理解程序设计语言编译程序的构造原理及编译原理课程的教学具有重要意义。

[1]朱朝霞，周云才.编译技术语法分析实践教学探讨[J].北京教育学院学报，2008，3（3）：11－14.

[2]李冬梅，施海虎.编译原理[M].北京：人民邮电出版社，2006：50－100.

[3]张素琴，吕映芝.编译原理[M].北京：清华大学出版社，2005：50－67.

[4]张幸儿.编译原理编译程序构造与实践[M].北京：机械工业出版社，2008：46－81.

[5]胡伦骏，徐兰芳.编译原理[M].北京：电子工业出版社，2004：173－177.

[6]张昱，陈意云.编译原理与技术[M].北京：高等教育出版社，2010：13－37.

[7]蒋宗礼，姜守旭.编译原理[M].北京：高等教育出版社，2010：64－112.