lex

计算机领域的词法分析器

Lex是Lexical Analyzer Generator的缩写，是Unix环境下非常著名的工具，主要功能是生成一个词法分析器(scanner)的C语言源码，描述规则采用正则表达式(regular expression)。

生成工具

描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c 的文件，然后由C编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符很容易被后续阶段处理。如图1所示。

它被设计用来对输入字符流进行词法处理。它接受一种高级的、面向问题的说明书，并用它匹配字符串中的字符、生成能够识别正则表达式的程序。正则表达式通过用户输入的代码说明书给入。Lex识别这些表达式，并且将输入流分成一些匹配这些表达式的字符串。在这些字符串的分界处，用户提供的程序片段被执行。Lex代码文件将正则表达式和程序片断关联。对每一条输入到由Lex生成程序的表达式，相应的代码片段被执行。

为了完成任务，除了需要提供匹配的表达式以外，用户还需要提供其它代码，甚至是由其他生成器产生的代码。用户提供一般程序设计语言的代码片断完成程序识别表达式。因此，用户自由编写动作时，并不影响其编写高层的表达式语言来匹配字符串表达式。这就避免迫使用户使用字符串语言来进行输入分析时，也必须使用同样的方法来编写字符处理程序，而这样做有时是不合适的。Lex不是完整的语言，但是是一个新语言的生成器，它可以插入到各种不同的被叫做“宿主语言”的程序设计语言中。就像大多数目的语言可以生成在不同计算机硬件上运行的代码，Lex可以生成不同的宿主语言。宿主语言用于Lex生成输出代码，也用于用户插入程序片断。这使得Lex适用于不同的环境和不同的使用者。每一个应用程序可以是硬件、适用于该任务的宿主语言、用户背景和局部接口属性的直接结合。现在，Lex支持的宿主语言是C，尽管Fortran（形式为Ratfor[2]）在过去也被支持。Lex自身存在于UNIX、GCOS和OS/370上；但是Lex生成的代码可以在任何适当的编译器上使用。

Lex将用户输入的表达式和动作actions（在这篇文章中被称作源代码）转换为宿主语言；生成的程序叫做yylex。yylex识别字符流中的表达式（本文称作输入流），并且当每一个表达式被检测出来后，输出相应的动作。

过程如图。

让我们来仔细研究一下这个奇妙的工具吧。先看看Lex文件的结构。 Lex文件结构简单，分为三个部分：

分别是声明，转换规则和其它函数。

声明段包括变量的声明、符号常量的声明和正则表达式声明。希望出现在目标C源码中的代码，用%{…%}扩在一起。比如：

正则表达式声明如下

这段正则表达式描述识别数(number)、标识符(id)的“规则”。过一会我们再细说正则表达式。

规则段是由正则表达式和相应的动作组成的。

值得注意的是，lex 依次尝试每一个规则，尽可能地匹配最长的输入流。如果有一些内容根本不匹配任何规则，那么 lex 将只是把它拷贝到标准输出。比如

编译后运行一下，

可以看出lex的确按照最长的规则匹配。

程序段部分放一些扫描器的其它模块，比如一些动作执行时需要的模块。也可以在另一个程序文件中编写，最后再链接到一起。生成C代码后，需用C的编译器编译。连接时需要指定链接库。gcc的连接参数为 -ll。

正则表达式可以描述有穷状态自动机(finite automata)接受的语言，也就是定义一个可以接受的串的集.lex中用到的正则表达式的一些规则如下：

转义字符（也称操作符）：

这些符号有特殊含义，不能用来匹配自身。如果需要匹配的话，可以通过引号

都可以匹配C++。

非转义字符：所有除了转义字符之外的字符都是非转义字符。一个非转义字符可以匹配自身。比如

integer

匹配文本中出现的integer。

通配符：通配符就是.（dot），可以匹配任何一个字符。

字符集：用一对[]指定的字符构成一个字符集。比如[abc]表示一个字符集，可以匹配a、b、c中的任意一个字符。使用 – 可以指定范围。比如[a-z]表示可以匹配所有小写字母的字符集。

重复：

* 任意次重复+ 至少一次的重复，相当于xx*? 零次或者一次

选择和分组：|符号表示选择，二者则一；括号表示分组，括号内的组合被看作是一个原子。比如(ab|cd)匹配ab或者cd。

Lex源代码

一般的Lex源代码格式为

而definitions和user subroutines经常被忽略。第二个%%是可选择的，但是第一个必须存在以标记rules的开始。因此最简单的Lex程序是

（没有definitions和rules），这个程序输入将不加修改地复制到输出。

由上面的Lex程序轮廓可知，规则（rules）反映了用户的控制；它是一个表格，左侧是正则表达式（regular expressions）（参见第3节），而右侧是动作（actions），当表达式被识别出以后，动作的程序片断被执行。所以，一个单独的规则可能是

它用于在输入流中寻找字符串中的integer，找到后输出“found keyword INT”。在这个例子中，主程序为C语言并且用C库函数printf打印字符串。用第一个出现的空白符或者制表符作为表达式的结束标记。如果action仅仅是一条简单的C表达式，那么它可以直接写在这一行的右侧；如果是复合表达式或者包含了很多行，则必须用大括号括起来。作为一个更有用的例子——用来将一些英式拼写转换为美式拼写——其词法分析器应该以如下规则开始：

这些规则是不够强大的，比如pertroleum应该变为gaseum；一种处理它的方法将在下文中予以介绍。

警告和缺陷

有一些病态的表达式会使由表格转化的确定的自动机成指数增长；幸运的是，这样的情况很少见。

REJECT没有重复扫描输入；而是记住先前扫描的结果。这意味着如果一条规则需要回退发现的上下文，并且REJECT被执行了，用户将不能使用unput来改变输入流中的后续字符。这是对用户操作后续输入的限制。

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省

丽江市

云南省