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来改变输入流中的后续字符。这是对用户操作后续输入的限制。