《编译与反编译技术实战 》一3.3 词法分析器的LEX实现

本节书摘来自华章出版社《编译与反编译技术实战 》一书中的第3章，第3.3节，庞建民　主编 ，刘晓楠　陶红伟　岳　峰　戴超　编著，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

由于程序设计语言中的单词基本上都可用一组正规式来描述，因此，人们希望构造一个自动生成系统：对于一个给定的高级语言，只要给出用来描述其各类单词词法结构的一组正则表达式，以及识别各类单词时词法分析程序应采取的语义动作，该系统便可自动产生此语言的词法分析程序。1975年美国贝尔实验室的m. lesk和schmidt基于正规式与有限自动机的理论研究，用c语言研制了一个词法分析程序的自动生成工具lex。对任何高级程序语言，用户只需用正规式描述该语言的各个词法类（这一描述称为lex的源程序），lex就可以自动生成该语言的词法分析程序。

lex 的输入是用lex源语言编写的程序，它是扩展名为.l的文件。lex源程序经lex 系统处理后输出一个c 程序文件，此文件含有两部分内容: 一个是依据正规式所构建的状态转移表； 另一个是用来驱动该状态转移表的总控程序yylex ()。该文件再经过Ｃ编译器的编译就产生一个实际可以运行的词法分析程序，其使用方法如图3-4所示。

一般而言，一个lex 源程序由“% %”分隔的三个部分组成，其书写格式为：

定义部分

辅助函数部分

其中，定义部分和辅助函数部分是任选的，识别规则部分则是必备的。如果辅助函数部分缺省， 则第二个分隔号“% %”可以省略；但由于第一个分隔号% %用来指示识别规则部分的开始，故即使没有定义部分， 也不能将其省略。下面将对这三部分的内容及其书写格式作一概括性介绍。

1.定义部分

定义部分对规则部分要引用的文件和变量进行说明，通常可包含头文件表、常数定义、全局变量定义、外部变量定义以及正规式定义等。正规式定义用来定义在规则部分引用的正规式，类似于Ｃ语言中的宏定义，所以也称为宏定义。每一个宏定义由分隔符（适当个数的空格或制表字符） 连接的宏名字和宏内容组成：

其中，di 是要定义的一组互不相同的宏名字，它是以字母或者下划线“_”开始，由字母、数字和下划线“_”组成的字符串，并且大小写敏感；每个ri是以后用来替换宏名字di的宏内容，其都是Σ∪{d1,d2,...,di-1}上的正规式；Σ 是相应程序设计语言的基本字符集。设置宏定义的目的在于给一些较为复杂的正规式命名，以便以后在需要出现这些正规式的地方只需写上相应的宏名字。例如：

其中，digit是匹配单个数字的正规式；letter 是匹配单个字母的正规式。需要注意的是，在以后的定义部分和规则部分，凡对已定义宏名字的引用都需用花括号将它们括起来。例如：

lex扫描源文件时，将{letter}替换为letter 所定义的正规式并加上括号，将{digit}替换为digit所定义的正规式并加上括号，所以，上式等价于

([a-za-z])( ([a-za-z])|([0-9]))*

它将匹配以字母开始并由字母和数字组成的字符串。

除宏定义外，定义部分的其余代码需用符号“%{”和“%}”括起来。lex将“%{”和“% }”之间的内容直接复制到生成的c 文件lexyy.c中。在lex 源程序中，起标识作用的符号“% %”“%{”以及“%}”都必须处于所在行的最左字符位置。另外， 在其中也可随意添加c 语言形式的注释。如

其中，每个pi都是定义在Σ∪{d1 ，d2 ，… ,dn }上的正规式（ di 是定义部分所定义的宏名字），用来描述一种单词模式；ai是一段c语言源代码，用来指出当从输入字符串中识别出词型为pi的单词时词法分析器应执行的操作。每个pi都必须顶行书写，并用分隔符（若干个空格或tab字符）与其后的代码段ai分开。每个代码段ai可引用已定义的符号常量、全局变量和外部变量，并能调用辅助函数部分所定义的函数，必要时也可在ai中定义自己的局部变量。ai一般不必用花括号括起来，但若ai多于一行或者需要在其中定义局部变量，则应使用花括号并且左括号“{”一定要与相应的pi在同一行，以便确定这些局部变量的作用域。

3.辅助函数部分

在识别规则部分中所调用的函数若不是库函数，则需要给出这些函数的定义。这些函数在辅助函数部分给出，由用户用Ｃ语言编写，它们由lex系统直接复制到输出的c程序文件之中。

表3-2中列出了lex中常用的一些变量和函数，在与正规式匹配的动作或辅助过程中都可以使用。

例3.1　下面给出了一个lex源文件，其功能是统计文本文件中的字符数和行数。该程序首先定义了num_chars 和num_lines 两个计数器，分别记录文本文件的字符数和行数。在lex 源文件中定义两个正规式“n”和“.”，分别用来匹配换行符和任意字符，并且在识别这两个正规式后其相应的计数器累加1，从而完成对文件的字符数和行数的统计。

lex 源程序中在宏定义及识别规则部分都涉及许多正规式。这些正规式除应遵循正规式基本定义的规定外，为了便于用户灵活、紧凑地构造复杂的正规式，lex还增添了若干个运算符和新的构造规则，下面将结合这些新增的内容对lex系统中的正规式进行扼要说明。

lex系统中的正规式由通常的文字字符（下面称为正文字符）和元字符组成。元字符一般用作运算符或控制符，常用的元字符有*、 +、 ?、 | 、{ }、 [ ]、() 、. ^ 、＄ 、” 、、 -、 / 、

<、 >。利用正文字符和元字符组成正规式的规则及其匹配输入串的规则分述如下。

（1）单个正文字符

单个正文字符c是正规式，用于匹配与其相同的单个正文字符c。

如果上述元字符需要以正文字符的形式出现于正规式中，则需使用双引号（"）或反斜线（）作为转义字符将其变为正文字符，如" +"（或 +）和"-"（或-）在正规式中分别表示加号和减号。此外，c语言中的一些转义字符序列也可出现在正规式中，如 b、 f 、 n 、

r、 s和 t 分别表示退格、换页、换行、回车、空格和制表。

（2）字符类

字符类是正规式，用于匹配该字符类所确定的字符集合中的任一字符。

需要注意的是， 除^、 和-外，其余元字符在方括号内失去其特殊含义。如果使一个字符类含有这3个字符中的某个字符，只需要将其放在方括号内首字符或末字符的位置上，如[ - + .0 - 9 ] 和[ + .0 - 9 - ]均匹配正号、负号、小数点和十进制数字中的任何字符。

（3）“连接”与“或”

设r1和r2是正规式，则r1r2（表示r1 和r2 的连接）和r1 | r2（表示r1或r2）也都是正规式。

（4）重复

设r为正规式，则“r *”表示r 可重复零次或任意多次，“r +”表示r可重复一次或任意多次，“r ?”表示r可有可无。

（5）通配符

“·”为通配符， 用来匹配除换行之外的任何字符。例如，b·c 不但可以匹配bnc、 bdc 及bvc 等， 而且还可匹配rbyca 中的byc。

（6）行首字符串或行末字符串

以元字符上箭头“^”开头的字符串用于匹配行首字符串，以元符号“＄”为末尾的字符串用于匹配行末字符串。例如，^begin表示仅当字符串begin 出现在某一行的开头才能获得匹配；end$表示仅当字符串end出现在一行的结尾才能获得匹配。这里所说的一行的开头， 是指整个输入字符流的开始，或者紧跟在一个换行字符之后的位置，一行的结尾则指紧靠换行字符之左的位置。

（7）超前搜索

“/”为超前搜索符。设r1 和r2 是正规式，则r1/r2也都是正规式，其r1是否与一个字符串相匹配取决于紧跟其后的超前搜索部分是否与r2相匹配。也就是说，r2仅作为r1获得匹配的条件，而非所要识别单词词型的一部分。例如， 为了识别fortran源程序中的关键字do，需采用超前搜索技术， 相应的词型可写成

do/ ({letter}|{digit})= ({letter}|{digit})

表示词法分析程序在输入缓冲区中超前扫描一串字母或数字，接着扫描等号以及后面的一串字母或者数字，最后扫描到逗号，才能确认关键字do得到识别。

3.3.3　lex 的使用方式

lex 通常有两种使用方式：一种是将lex作为一个单独的工具，用以生成所需的识别程序，这些识别程序多被用在诸如编辑器设计、命令行解释、模式识别、信息检索以及开关系统等一些非开发编译器的应用领域中；另一种是将lex和语法分析器自动生成工具（如yacc）结合起来使用，以生成一个编译程序的扫描器和语法分析器。

lex 和yacc 的最初版本都是作为unix 系统下的工具软件来运行的。假定已有命名为scanner.l 的lex 源文件，则可在unix 系统下通过命令lex scanner.1调出lex 对其进行处理，处理结果是输出名字为lex.yy.c 的c语言文件。再用命令cc lex.yy.c-11调用c 编译器对其进行编译，编译所得到的文件a.out 便是可执行的词法分析程序，其中选择项“-11”表示需调用lex的库。如果用户需对所得目标代码文件命名，如将其命名为cifafenxi，则可用下面的命令进行编译：

cc lex.yy.c-11-o cifafenxi

lex和yacc已经成功移植到windows系统下，parser generator便是其中常用的工具之一，该工具是windows 平台下的lex 和yacc集成环境，其利用lex 和yacc能够生成visual c++、borland c++等c++代码以及相关java代码。parser generator 非常适合于与visual c++（简称vc++）集成，下面对该工具如何生成代码并使用visual c++进行编译做一简要介绍。

在安装了parser generator 后，在vc++中进行以下两项设置，即可使vc++编译和链接由parser generator 产生的文件。

1.目录设置

为了在vc++中可以找到lex 和yacc 的头文件lex.h 和yacc.h，以及lex 和yacc 的库文件，需要对vc++进行相关的目录设置。

2.项目设置

在本小节，我们给出一个针对c 语言单词识别的lex 源程序文件c.lex， 以供参考。该源程序所涉及的各种单词符号和种别编码参见表3-1，在该源程序中针对常数类单词只考虑了十进制整型常数。该文件已在parser generator 环境下编译调试通过。为便于阅读， 特作以下说明：

1）程序前面的行号是为了便于下面的说明而给出的，真正的lex 程序不能书写行号。

2）第1行到第84行介于“%{”和“%}”之间的内容将直接插入由lex产生的Ｃ程序中，第5行至第83行列出了c 语言各类单词的名字及其相应的种别编码定义。

3）第85行到第89行为正规式的宏定义，white代表制表、换行及空格三个字符中的任一字符，把它们均视为“空白字符”。digit代表0到9中的任一数字，letter代表任一大写或者小写字母，number代表十进制整数，id代表c语言中的标识符。

4）第91行到第174行之间为识别规则部分。第91行表示在遇到空白符时，不需要进行任何语义处理，用一个空语句表示，这样就可以将输入字符串的全部空白符过滤掉。第92行和第93行对注释进行处理。第94 行到第173行表示在识别出标识符、十进制整型常数、关键字和运算符时输出其相应的种别编码。第174 行中的“.”表示不能与第91行到第173行正规式匹配的其他字符。

5）第176行到第180行为主函数，打开输入输出文件。其中，yylex()是词法分析程序的入口点，每次调用yylex()，就可以从被编译的源程序中得到一个单词。如果正规式的相关动作中无return语句，则yylex()并不返回值，如此例中第94行到第174行，相关的动作只是向文件result.txt中输出某些提示信息。

下面为c 语言扫描器的lex 源文件c.lex。