Lex–一个词法分析器的生成器(全文)

Lex – 一个词法分析器的生成器(全文)
Lex – 一个词法分析器的生成器

M. E. Lesk和E. Schmidt

贝尔实验室

Murray Hill, New Jersey 07974

 

翻译：彭一凡

北京工业大学计算机科学与技术

 

 

摘 要

 

 

Lex用于编写一些程序，这些程序能够通过正则表达式识别输入流中的控制流。它能很好的适用于文本脚本类型的翻译，以及用于语法分析例程的输入分段。

Lex源文件是一个由正则表达式和相应程序片断构成的表格。表格被转换成程序，该程序读取输入流、拷贝它到输出流、并且将输入分割成能够匹配给定表达式的字符串。每一次当字符串被识别后，相应的程序片断被执行。表达式的识别由Lex生成的有限状态自动机执行。输入流中相应的正则表达式被识别后，用户写的程序片断按顺序被执行。

Lex写就的词法分析器接受二义性的说明书，在每一个输入点上选择最长的可能匹配。如果必要，输入中会有前向搜索，但是输入流会回退到当前的分割处，这样用户可以在很大程度上拥有操作的自由。

Lex可以生成C或者Ratfor的分析器，Ratfor是一种可以被自动转换为Fortran的语言。在PDP-11 UNIX、Honeywell GCOS和IBM OS系统上都可以使用Lex。然而，这个使用手册只讨论了UNIX系统上用C语言生成解析器的方法，它只适用于UNIX Version 7下的Lex形式。对于那些希望联合使用编译器生成器的程序，Lex的设计使其很容易与Yacc一起使用。

 

Lex – 一个词法分析器的生成器

M. E. Lesk和E. Schmidt

贝尔实验室

Murray Hill, New Jersey 07974

目录

1．介绍    2

2．Lex源代码    4

3．Lex正则表达式    4

4．Lex动作    6

5．二义性的源文件规则    8

6．Lex代码中的定义    10

7．使用    10

8．Lex和Yacc    11

9．实例    11

10．上下文左侧有关    13

11．字符集    15

12．源代码格式总结    15

13．警告和缺陷    16

14．感谢    17

15．参考资料    17

 

 

 

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

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

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

 

图 1

作为一个简单的例子，考虑一个用于删除输入中每行结尾处所有空白符的程序。

%%
  
[ /t]+$
 ;
 

是其全部。程序包含%%界定符表示规则的开始，以及一条规则。这条规则包括一条正则表达式，用来匹配一个或多个、仅出现在行尾字符串中的空格或者制表符（根据C语言传统，显式的写为/t）。中括号表明字符类由空格和制表符组成；+表示“一个或者多个……”；而$就像在QED中一样表示“行尾”。没有提供具体的动作，所以Lex生成的程序（yylex）会忽略这些字符。其他的字符会被拷贝。如果要将字符串中的空格或者制表符转换为单个空格，需要增加一条规则：

%%
 ;
 
[ /t]+$
  
[ /t]+
 printf(" ");
 

由这个源文件生成的有穷自动机同时扫描两条规则，查看字符串中的空格或制表符后是否有一个换行符，并且执行规则中的动作。第一条规则匹配所有以空格或制表符为结尾的行，而第二条规则匹配除此之外的字符串中的空格或者制表符。

Lex可以被独自用于简单的转换，或者在词法层面上用于分析和统计。Lex也可以在语法分析器的生成器中用于词法分析阶段；将Lex和Yacc[3]结合使用是极其方便的。Lex仅识别正则表达式；Yacc编写的语法分析器可以接受一大类上下文无关文法，但是需要一个底层的分析器识别输入记号。因此结合使用Lex和Yacc是合适的。当用于语法分析器生成器的预处理程序时，Lex用于分割输入流，而语法分析器生成器将结果赋予结构。这种情况下的流程图如2所示（比如一个编译器的前半部分）。程序的其他部分，由其他生成器生成或者手写，可以被方便的插入由Lex产生的程序中。

 

图 2

Yacc使用者会发现yylex是Yacc用于接收语法分析器结果的名字，所以使用Lex中的名字可以简化操作。

Lex由源文件中的正则表达式产生确定的有穷状态自动机[4]。为了节省空间，这个自动机是被解释，而不是被编译得到的。结果仍是高速分析器。特别的，Lex程序识别和分割输入流的时间与输入的长度成正比。Lex中规则的数量和复杂度对于执行速度来说是无关的，除非规则中包含的前向上下文需要大量的反复扫描。与规则的数量和复杂度相关的是有穷自动机的体积，因此也就是Lex生成程序的大小。

在由Lex生成的程序中，用户的片断（每一条正则表达式匹配后的动作）像switch中的case那样被收集。自动解释器控制流程。用户也可以有机会加入声明或者在动作例程中加入额外的语句，或者也可以加入动作例程以外的子函数。

Lex不局限于只允许超前扫描一个基本字符。例如，如果有两条规则，一个寻找ab，另一个寻找abcedfg，而输入流是abcdefh，Lex会识别ab，而将输入指针定位到cd…前。这样的回退比起处理简单语言来说更耗时。

 

2．Lex源代码
一般的Lex源代码格式为

{definitions}

%%

{rules}

%%

{user subroutines}

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

%%

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

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

integer
 printf("found keyword INT");
 

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

colour
 printf("color");
 
mechanise
 printf("mechanize");
 
petrol
 printf("gas");
 

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

 

3．Lex正则表达式
正则表达式的定义与QED[5]很相似。一个正则表达式用于识别一组匹配的字符串。它包括文本字符（匹配字符串中的相应字符）和运算符（用于循环、选择和其他特点）。字母表中的字母和数字通常为文本字符；因此正则表达式

integer

匹配出现在表达式中的字符串integer。而表达式

a57D

寻找字符串a57D

运算符。运算符为

" / [ ] ˆ − ? . * + | ( ) $ / { } % <>

如果它们被用于文本字符，则必须使用转义字符（escape）。引号（“）表示两个引号中的任何内容被看作文本字符。因此

xyz”++”

匹配字符串xyz++。注意字符串的一部分可以在两个引号中，这样做虽然无害，但是却没有必要将一般的文本字符括起来。表达式

"xyz++"

与上面的表达式的功能相同。因此通过将所有非字母表中的字符括起来作为一个文本字符，使用者可以避免记忆上面的操作符，并且这样做对于以后扩展Lex长度是安全的。

一个操作符也可以使用/作为转义字符以转换为文本字符。

xyz/+/+

与上面的表达式有相同的作用，但是破坏了可读性。引号的另一个作用是在表达式中加入空白符；如上所述，通常空白符和制表符作为规则的结束。任何不在[]（见下）中的空白符必须被引用。一些标准的带有/的C转义字符也会被识别：/n是换行符，/t是制表符，/b是回退符。想引入/，使用//。因为换行符在表达式中是不合法的，所以/n必须被使用；而制表符和回退符的转义不是必须的。除了空白符、制表符、换行符和上面列表中的字符以外，所有的字符都是文本字符。

字符类。字符类用操作符[]表示。样式[abc]匹配a、b或者c的单个字符。在中括号中，大多数的操作符被忽略。只有三个字符例外：/，-和^。字符-表示范围。例如，

[a-z0-9<>_]

表示包含所有小写字母、数字、尖括号和下划线的字符类。范围可以以任何顺序给出。对于任意字符，它们不同时为大写字母、小写字母或者数字，使用-的结果是不可知的，并且会得到警告。（例如，[0-z]在ASCII中表示的字符要多于在EBCDIC中）。如果想在字符类中使用-作为文本字符，则必须在开始或者末尾处使用；因此

[-+0-9]

匹配所有数字和正负号。

在字符类中，操作符^只能出现在左中括号后的第一个字符位置处；它表示结果字符串是不含该类中字符串的计算机字符集合。因此

[^abc]

匹配除了a、b或者c的所有字符，包括特殊符号或者控制符号；而

[^a−zA−Z]

表示所有非字母符号。/符号在中括号中表示通常意义的转义作用。

任意字符。操作符

.

表示除了换行符以外的所有字符。尽管不方便，但是使用八进制是可行的：

[/40−/176]

在ASCII字符集中匹配从八进制40（空白符）到176（tilde）的所有可以打印的字符。

选择符。操作符?是表达式中的选择元素。所以

ab?c

匹配ac或者abc。

重复的表达式。重复的类可以用操作符*和+表示。

a*

表示任意数目的a字符序列，包括0个a；而

a+

表示1个或者更多的a实例。例如，

[a−z]+

表示所有小写字母的字符串。而

[A-Za-z][A-Za-z0-9]*

表示所有以字母表中的字符作为开始符号的全部文字和数字的字符串。这是识别计算机语言中标识符的典型表达式。

交替与分组。操作符|表示交替：

(ab | cd)

匹配ab或者cd。注意：尽管在外层不需要，但是小括号可以用于分组。

ab | cd

就足够了。小括号可以用于更复杂的表达式：

(ab | cd+)?(ef)*

匹配像abefef、efefef、cdef或者cddd这样的字符串，而不能匹配abc、abcd或者abcdef。

上下文有关。Lex可以识别少量的surrounding context。其中两个最简单的操作符是^和$。如果一个表达式的第一个字符为^，那么这个表达式仅在一行的起始部分被匹配（在一个换行符后，或者在输入流的开始处）。这种用法不会与^的另一个用法——字符类的非操作——相矛盾，因为后一种用法只出现在[]中。如果最后一个字符为$，则这个表达式仅匹配这一行的末尾（当后面紧跟换行符时）。另一个操作符是/，它用来跟随上下文。表达式

ab/cd

匹配字符串ab，但是当且仅当ab后面是cd。因此

ab$

与

ab//n

等价。左线性文法在Lex中由开始状态处理，这部分内容在第10节中阐述。如果一条规则只在Lex自动解释器处于开始状态x时被执行，则该规则应该有使用尖括号的前缀

如果我们想将“一行的起始部分”作为开始状态，那么操作符^与

是等价的。开始状态会在稍后作更具体的说明。

重复和定义。操作符{}用来表示重复（如果它用来括住数字）或者定义解释（如果它用来括住一个名字）。例如

{digit}

用于查找一个先前被定义的叫做digit的字符串，并且将它插入本表达式的相应位置。定义在Lex输入的第一部分，于规则之前被给出。相反，

a{1,5}

查找从连续的1个a到连续的5个a。

最后，初始的%是特别的，它用于分隔Lex源代码的各个部分。

 

4．Lex动作
当一条上述表达式匹配以后，Lex将执行相应的动作。本节介绍Lex中编写动作的一些特点。注意，Lex中存在一个从输入到输出直接拷贝的默认动作。在遇到所有不匹配的字符串时，这个默认动作自动执行。另外，如果Lex用户希望截获所有输入而没有输出，那么必须提供能够匹配所有字符的规则。当在Yacc中使用Lex时，这是一种常见情形。我们可以认为action是代替直接将输入拷贝到输出的动作；另外通常情况下，仅仅执行拷贝任务的动作可以被忽略。同样，一个被规则忽略的出现在输入中的字符组合，会被直接输出。因此要特别注意规则间的断层。

忽略输入是最简单的事情之一，这仅仅需要使用一条C空语句;。一条常用的规则：

[ /t/n]
 ;
 

可以使得三种空白符被忽略（空白符、制表符和换行符）。

另外一种回避写动作的方法是使用符号|，它表示这条规则的动作与下一条规则的动作相同。上述例子也可以被写成

" "

"/t"

"/n"

虽然形式不同，当时二者结果一样。/n和/t的引号可以省略。

在更复杂的动作中，用户经常需要了解表达式的精确文本匹配，比如[a-z]+。Lex将匹配的文本存在名为yytext的字符数组中。因此，打印匹配的名字，可以使用规则

[a−z]+
 printf("%s", yytext);
 

打印字符串yytext。C函数printf接收格式参数和被打印的数据；在上述例子中，格式为“打印字符串”（%表示数据转换，s表示字符串类型），数据是yytext中的字符。所以这条语句是将匹配的字符串输出。这种动作是很常见的，它也可以用ECHO书写：

[a−z]+
 ECHO;
 

由于默认的动作就是打印匹配的字符，所有可能有人会问为什么还需要提供类似上述的动作来执行默认的动作呢？这样的规则可以用来避免匹配一些不需要的规则。例如，如果有一条匹配read的规则，它通常会匹配bread或者readjust中的read；为了避免这种错误，需要一条形如[a-z]+的规则。这种情况将在下面进一步介绍。

有时，获得匹配字符串的结束位置是方便的；因此Lex提供了一个计数器yyleng来计算已经匹配的字符数目。为了同时计算输入中单词和字符的数目，用户可以写

[a−zA−Z]+
 {words++; chars += yyleng;}
 

这里chars用于计算匹配了的单词中字符的数目。字符串中被匹配的最后一个字符可以通过

yytext[yyleng−1]

获得。有时，一个Lex动作可能需要处理当规则没有能够正确识别时的字符宽度。两个例程用于处理这种情况。首先，yymore()被调用会使得下一条被识别的表达式追加到本次输入后。而通常情况下，下一次被识别的输入会完全覆盖yytext。其次，yyless(n)被调用表示现在不需要所有的字符串被成功匹配。参数n表示此时yytext中保留的剩余字符数。先前已经匹配的字符串被退回到输入。这个函数提供了与前向操作符/相同的功能，但是形式不同。

例：考虑一种语言，它用于确定字符集中在引号（“）中的字符串，并且如果字符串中含有”，那么需要转义符/。匹配如上要求的正则表达式有一些难写，所以可以采用下面的写法

/"[ˆ"]*
 {
 
  if (yytext[yyleng−1] == ¢//¢)

yymore();

else

... normal user processing

}
 

当遇到形如”abc/”def”的字符串时，他会首先匹配前5个字符”abc/；然后调用yymore()使得右面的字符串”def被追加到后面。注意，标志字符串结束的引号应该在代码“normal processing”中被截获。

函数yyless()在多数情况下用于文本的再生。考虑C问题中的二义问题“=-a”。假设需要处理“=-a”，但是要打印一条信息。一条规则可能写成

=-[a−zA−Z]
 {
 
  printf("Operator (=-) ambiguous/n");

yyless(yyleng−1);

... action for =- ...

}
 

它会打印一条信息，返回操作符后的字符到输入流中。另外，它也可以将其处理为“= -a”。如果想这样，只需返回字母以及它前面的负号到输入流中即可：

=-[a−zA−Z]
 {
 
  printf("Operator (=-) ambiguous/n");

yyless(yyleng−2);

... action for =- ...

}
 

上面的代码提供了另一种解释。注意，上述两种情况的表达式，如果第一种写成

=-/[A−Za−z]

第二种写成

=/−[A−Za−z]

会更容易一些；动作中不需要反斜杠。识别整个标识符来区别二义性是没有必要的。

=-/[ˆ /t/n]

对于“=-3”也是不错的规则。

另外，Lex允许直接使用I/O例程。它们是：

input()，返回下一个输入字符；
output(c)，将字符c写入输出
unput(c)，将字符c压回输入流，下次input()时被读出。
这些例程都有默认的宏定义，但是用户可以重写它们以适应不同的需求。这些例程定义了外部文件和内部字符之间的关系，并且只能同时存在或更改。它们可以被重写使得输入或者输出被定向到特殊的位置，包括其他的程序或者内存；但是字符集的使用必须在整个例程中保持统一；input必须返回0以表示文件结束；unput和input之间的关系必须保留，否则Lex不能完成向前搜索的操作。Lex在不需要的时候不会向前搜索，但是每一个以+*?$结尾的、或者含有/的规则需要这个功能。同样，当一个表达式是另一个的前缀时，向前搜索也是必不可少的。参阅下文中有关Lex使用的字符集的讨论。默认的Lex库使用100个字符作为备用限制。

另一个用户可以重定义的Lex库函数是yywrap()，它在Lex遇到文件结束符时被调用。如果yywrap返回1，Lex以通常的意义继续运行到输入结束。然而有时需要从一个新的代码处得到更多的输入。在这种情况下，用户需要提供yywrap来安排新的输入并且使它的返回值为0。这样Lex才可以继续运行。yywrap默认的返回值为1。这个例程对于在程序末尾打印表格、总结等内容非常方便。注意，写出一个正规规则来识别文件结束是不可能的；唯一的方法是通过yywrap。实际上，除非提供一个私有的input()，一个只包含空的文件是不能够被处理的，因为input返回的值0表示文件结束。

5．二义性的源文件规则
Lex可以处理二义性的说明书。当超过一个表达式可以同时匹配当前输入时，Lex做出如下选择：

优先选择最长的匹配。
在能够匹配相同数量字符的规则中，选择靠前的规则。
因此，假设如下规则

integer
 keyword action ...;
 
[a−z]+
 identifier action ...;
 

按照顺序给出。如果输入为integers，那么它被当作identifier因为[a-z]+匹配8个字符而integer只匹配7个。如果输入为integer，两条规则都匹配7个字符，那么将使用关键字规则，因为它更靠前。任何更短的字符串（比如int）将不会匹配表达式integer，所以Lex使用identifier进行解释。

优先选择最长的匹配使得含有表达式.*的规则变得危险。例如，

‘.*’

看上去是一条很好的识别被单引号括住的字符串的规则。但是它使得程序需要进行很远的前向搜索，以找到远端的另一个单引号。给定输入

’first’ quoted string here, ‘second’ here

上述的表达式会匹配

’first’ quoted string here, ‘second’ here

而这可能不是我们需要的结果。一种更好的规则形式是

‘[ˆ’/n]*’

它对于上面的输入，将会停止在’first’。错误的结果将会由于操作符.没有匹配换行符而减少。因此，类似于.*的表达式将停在当前行上。不要试图用诸如[./n]+或者等价的表达式去替换它；Lex生成的程序会尝试扫描整个输入文件，从而导致内部缓冲区溢出。

请注意，Lex通常用于将输入流分隔开，而不是查找所有满足表达式的匹配。这意味着每一个字符解释且仅解释一次。例如，假设需要计算输入文本中she和he的个数。处理这个问题的Lex规则可能是

she
 s++;
 
he
 h++;
 
/n
 |
 
.
 ;
 

这里最后两条规则用于忽略除了he和she的其他一切信息。记住，.不包括换行符。因为she包括he，Lex通常不时识别she中的he，因为一旦它处理过she，这些字符就过去了。

有时候，用户希望阻止这种选择。动作REJECT表示“进行下一次选择。”它使得当当前规则被执行后，其他的规则可以第二次被选择。因此输入指针的位置会被调整。假设用户确实想计算she中的he个数：

she
 {s++; REJECT;}
 
he
 {h++; REJECT;}
 
/n
 |
 
.
 ;
 

以上规则是前面例子变体的一种。在计算了每一个表达式以后，它被后退（rejected）；无论是否合适，其他的表达式会再次计算。当然在这个例子中，用户应该注意she包括he但不是全部，因此忽略了he中的REJECT动作；另外，知道哪些输入字符同时在两个类中是不必要的。

考虑两条规则

a[bc]+
 { ... ; REJECT;}
 
a[cd]+
 { ... ; REJECT;}
 

如果输入是ab，只有第一条规则匹配，而ad使得只有第二条规则匹配。输入字符串accb使得第一条规则匹配4个字符，而后第二条规则匹配3个字符。相反，输入accd先匹配规则2的4个字符，而后是规则1的3个字符。

通常，当Lex的目的不是分隔输入流而是查找输入中的所有项目的实例时，REJECT是有用的；此时不同项目之间可以覆盖或者包含。假设需要统计输入中的一张连字表；通常连字是重叠的。比如单词the包括th和he。假设一个叫做diagram的二维数组不断递增，适当的源文件如下

%%
  
[a−z][a−z]
 {digram[yytext[0]][yytext[1]]++; REJECT;}
 
/n
 ;
 

这里REJECT需要以每一个字符为开始识别字母对，而不是从其后的字母开始。

6．Lex代码中的定义
记住Lex代码的格式：

{definitions}

%%

{rules}

%%

{user routines}

到目前为止只介绍了rules。但是使用者需要额外的选择来为程序和Lex定义变量。变量可以在定义部分或者规则部分实现。请记住Lex是将规则转换为一个程序。任何不能被Lex解释的代码会被直接拷贝到生成的程序中。这样的情况有三类。

任何如下的一行被直接拷贝到Lex生成的程序中：不符合Lex规则，或者是以空白符、制表符开始的动作（action）。这样的代码如果出现在第一个%%之前，则可以扩展为生成代码中的任意函数；如果紧跟在第一个%%后面，则会出现在Lex写成的、包含动作的函数中声明的适当位置。此时它更像程序代码片断，并且应该在第一条Lex规则之前。
上面情况的副作用是，以空白符或者制表符开始、并且包含注释的行，将会直接移入生成程序。这种方法可以被用作在Lex代码或者生成代码中添加注释。注释必须符合宿主语言的规范。

任何包括在只含有%{和%}的行之间的内容被复制到生成代码中。%{和%}被忽略。这种格式允许用户加入起始于列1的预处理程序，或者拷贝不像程序的代码。
任何在第三个%%以后的内容被直接拷贝到Lex输出，无论它具有什么样的格式。
Lex中的定义在第一个%%限制符以前。这一部分的任何一行，如果它不在%{和%}之间，并且起始于列1，那么会被认为是Lex中替换字符的定义。这样的行的形式如下

name translation

它使得作为解释的字符串被关联到name。name和translation必须至少用一个空白符或者制表符分开。name必须以字母开头。translation由规则（rule）中的语法{name}调用。例如，使用{D}表示数字，{E}表示指数，可以缩短识别数字的规则：

D
 [0−9]
 
E
 [DEde][−+]?{D}+
 
%%
  
{D}+
 printf("integer");
 
{D}+"."{D}*({E})?
 |
 
{D}*"."{D}+({E})?
 |
 
{D}+{E}
  

注意头两条识别实数的规则，它们都需要一个小数点并且含有一个可选择的指数域，但是第一条在小数点前必须有一个数字，而第二条在小数点后必须有一位数字。为了能够正确的处理Fortran表达式中的相关问题，比如不含实数的35.EQ.I，应该加入一条上下文相关文法

[0−9]+/"."EQ
 printf("integer");
 

处理整数。

定义部分也可以加入其它注释，包括宿主语言的选择、字符集合表、初始状态列表，或者对大型代码程序调节Lex内部的数组大小。这些选择将在第12节的“代码格式总结”中讨论。

7．使用
编译一个Lex源文件程序需要两步。首先，Lex源程序必须转换为宿主目标语言的程序。然后，这个程序被编译和加载，通常这一部结合Lex例程库。生成的程序在文件lex.yy.c中。I/O库的定义在C标准库中[6]。

Lex生成程序与OS/370标准稍有不同，因为OS编译器比起UNIX或者GCOS的编译器稍逊一筹。在GCOS和UNIX上生成的C程序是一样的。

UNIX。库由加载标志-ll实现。所以适当的命令集如下

lex source cc lex.yy.c –ll

结果程序是通常的a.out文件，用于以后的运行。在Yacc中使用Lex的方法见下。尽管Lex默认的I/O例程使用C标准库，但是Lex自己不进行这个操作；如果单独的input，output和unput被给定，库会被省略。

8．Lex和Yacc
如果您想在Yacc中使用Lex，请注意Lex生成的程序叫做yylex()，这个程序名称在Yacc分析中需要被使用到。通常，Lex库中默认的主程序会调用这个例程，但是如果是使用Yacc加载，并且是它的主程序使用，那么Yacc需要调用yylex()。在这种情况下，每一条Lex规则应该以

return (token);

作为结束，其中恰当的token被返回。一种简单的获得Yacc中token名字的方法是将Lex的输出文件作为Yacc输出文件的一部分，这通过在Yacc输入的最后一个部分加入行

# include "lex.yy.c"

来实现。假设某文法叫做good，而词法规则是better，那么Unix中的指令序列如下：

yacc good

lex better

cc y.tab.c −ly –ll

为了获得调用Yacc解析器的主程序，Yacc库(-ly)应该在Lex库使用前被加载。Lex和Yacc的生成程序命令可以次序颠倒。

9．实例
作为一个小问题，考虑拷贝输入文件，使得每一个可以被7整除的正数加3。这里给出一个适当的Lex源程序

%%
  
  int k;
 
[0−9]+
 {

k = atoi(yytext);

if (k%7 == 0)

printf("%d", k+3);

else

printf("%d",k);

}
 

来处理它。规则[0-9]+识别字符串数字；atoi将数字转换为二进制，并存在k中。操作符%（求余数）用于检查k是否可以被7整除；如果可以，将其加3后输出。可能有人会反对，因为这个程序会将诸如49.63或者X7的输入项目改变。而且它使得任何绝对值可以被7整除的负数也被加3。为了避免这个，只需要增加一些规则，比如：

%%
  
  int k;
 
−?[0−9]+
 {

k = atoi(yytext);

printf("%d", k%7 == 0 ? k+3 : k);

}
 
−?[0−9.]+
 ECHO;
 
[A-Za-z][A-Za-z0-9]+
 ECHO;
 

含有“.”和由字母前导的数字字符串被后面两条规则截获，并且不会改变。if-else被一条C语言条件表达式替换以节省空间；形如a?b:c的表达式表示“如果a那么b，否则c”。

作为一个统计的实例，下面的程序柱状计算单词的长度，这里的单词被定义为字母字符串。   int lengs[100];
 
%%
  
[a−z]+
 lengs[yyleng]++;
 
.
 |
 
/n
 ;
 
%%
  
yywrap()

{

int i;

printf("Length No. words/n");

for(i=0; i<100; i++)

if (lengs[i] > 0)

printf("%5d%10d/n",i,lengs[i]);

return(1);

}
 

这个程序计算柱状图时没有输出。在输入的最后打印表格。最后的语句return(1);表示Lex进行最后处理。如果yywrap返回0（错误），它表示还有输入，程序会继续读取、处理。提供一个从不返回真的yywrap会造成无限循环。

作为一个更大的例子，下面的程序片断由N. L. Schryer撰写，用于将双精度的Fortran转换为单精度Fortran。因为Fortran不区分字母的大小写，所以这个例程的开始部分定义了包括每个字母大小写的类集合：

a [aA]

b [bB]

c [cC]

...

z [zZ]

一个附加的类识别空白符：

W [ /t]*

第一条规则将“double precision”转换为“real”，或者“DOUBLE PRECISION”转换为“REAL”。 {d}{o}{u}{b}{l}{e}{W}{p}{r}{e}{c}{i}{s}{i}{o}{n}
 {printf(yytext[0]==¢d¢? "real" : "REAL");}
 

在整个程序中都注意保留了原始程序的大小写。条件操作符用于选择恰当的关键字。下一条规则拷贝后续的卡片，并避免他们与常量混淆： ^" "[^ 0]
 ECHO;
 

正则表达式中，引号括住了空白符。其被解释为“行首的连续5个空白符，然后是除去空白和0的任何字符。”请注意^的两种不同用法。下面的几条规则将双精度常数转换为一般的浮点常数。 [0−9]+{W}{d}{W}[+−]?{W}[0−9]+
 |
 
[0−9]+{W}"."{W}{d}{W}[+−]?{W}[0−9]+
 |
 
"."{W}[0−9]+{W}{d}{W}[+−]?{W}[0−9]+
 {
 
  /* convert constants */

for(p=yytext; *p != 0; p++)

{

if (*p == ¢d¢ || *p == ¢D¢)

*p=+ ¢e¢− ¢d¢;

ECHO;

}

}
 

在识别出浮点常数以后，由for循环扫描字母d或者D。程序而后插入’e’-‘d’用于将其转换为字母表中的下一个字母。修改后的常量，现在是单精度的，再次输出。有一些名字必须重复拼写并除去起始的d。用数组yytext，同样的动作可以处理所有的名字（这里仅给出长长列表中的一个例子）。 {d}{s}{i}{n}
 |
 
{d}{c}{o}{s}
 |
 
{d}{s}{q}{r}{t}
 |
 
{d}{a}{t}{a}{n}
 |
 
…
  
{d}{f}{l}{o}{a}{t}
 printf("%s",yytext+1);
 

另一个名字列表需要将起始的d转换为a： {d}{l}{o}{g}
 |
 
{d}{l}{o}{g}10
 |
 
{d}{m}{i}{n}1
 |
 
{d}{a}{t}{a}{n}
 |
 
{d}{m}{a}{x}1
 {

yytext[0] =+ ‘a’ – ‘d’;

ECHO;

}
 

而一个例程需要将起始的d转换为r： {d}1{m}{a}{c}{h}
 {yytext[0] =+ ‘r’ – ‘d’;
 

为了避免像dsinx的名字被当成dsin的实例，最后的几条规则截获更长的单词，把它们作为标识符然后拷贝一些还应该存在的字符： [A−Za−z][A−Za−z0−9]*
 |
 
[0−9]+
 |
 
/n
 |
 
.
 ECHO;
 

注意，这个程序没有结束；它没有处理Fortran中的空白符，或者将关键字作为标识符。

10．上下文左侧有关
有时候需要在输入的不同时刻使用不同的词法规则集合。例如，编译预处理程序需要区分预处理语句，并且分析它们与一般语句的不同。这就需要上下文的识别，处理这一类的方法有很多。例如，操作符^是一个前导上下文符号，识别紧跟在左侧的上下文，而$识别紧跟在右侧的上下文。邻近的左侧上下文可以被扩展，以生成类似于上下文右侧相关的机制，但是它不如后者那样有效，这是因为，相对而言左相关出现在某一时刻的前面，比如一行的起始。

下面的部分将介绍3种处理不同环境的方法：在环境改变时只有少数规则改变，此时简单的使用标志符；使用规则中的开始状态；以及使多个词法分析器同时运行。每一种情况都有部分规则识别是否需要改变环境后再分析后续的输入文本，并且设定一些参数来反映这种改变。可以在用户定义的动作中用一个显式的标志来进行测试；这是处理这类问题最简单的方法，因为Lex并不参与其中。而令Lex记住该标志以作为规则的起始状态，可能是更方便的。任何一条规则都可以与一个开始状态联系。只有当Lex处于开始状态时，该条规则才可以被识别。当前的开始状态可以在任一时刻被更改。最后，如果对于不同环境的规则集合大不相同，写出不同特定的词法分析器可能是最清楚地解决问题的方法，然后根据需要在它们之间转换。

考虑如下问题：将输入拷贝到输出，将以字母a起始的行中的magic变为first，将以字母b起始的行中的magic变为second，将以字母c起始的行中的magic变为third。其他的单词和其他行不变。

规则十分简单，最简洁的方法是加入标志：   int flag;
 
%%
  
^a
 {flag = ‘a’; ECHO;}
 
^b
 {flag = ‘b’; ECHO;}
 
^c
 {flag = ‘c’; ECHO;}
 
/n
 {flag = 0 ; ECHO;}
 
magic
 {

switch (flag)

{

case ‘a’: printf("first"); break;

case ‘b’: printf("second"); break;

case ‘c’: printf("third"); break;

default: ECHO; break;

}

}
 

这就足够了。

用起始状态处理这个问题，每一个起始状态必须在定义部分引入到Lex中，使用一行

%Start name1 name2 ...

这里状态可以用任意顺序声明。关键字Start可以简写成s或者S。状态的引用可以在每一条规则的头部用<>给出：

expression

这是一条只有当Lex进入起始状态name1时才执行的规则。为了进入起始状态，执行动作语句

BEGIN name1;

可以使得状态转移到name1。若想重新开始状态，

BEGIN 0;

重新初始化Lex自动机的状态。一条规则可以在若干初始状态被激活：

是一个合法的前缀。任何一条不以<>前缀符开始的规则永远会被激活。

同样的例子也可以被写成： %START AA BB CC
  
%%
  
^a
 {ECHO;BEGIN AA;}
 
^b
 {ECHO;BEGIN BB;}
 
^c
 {ECHO;BEGIN CC;}
 
/n
 {ECHO;BEGIN 0;}
 
magic
 printf("first");
 
magic
 printf("second");
 
magic
 printf("third");
 

这里的逻辑与前一种处理问题的方法一样，但是Lex代替用户代码进行了处理。

11．字符集
Lex生成的程序仅通过input，output和unput来处理I/O中的字符。因此这些例程中支持的字符能够被Lex接受，并且通过yytext返回。在内部，一个字符由一个短整数表示，如果使用标准库，这个整数的值表示为宿主机上字符的位模式值。通常，字母a与常量’a’的形式一样。如果通过提供I/O例程翻译字符使得翻译模式改变，那么Lex必须被由给定的转换表通告。这张表必须在定义部分中，并且必须被只包含“%T”的行包括。表格包含形如

{integer} {character string}

的行，它表示了每一个字符对应的值。因此，下一个例子

%T

1 Aa

2 Bb

...

26 Zz

27 /n

28 +

29 −

30 0

31 1

...

39 9

%T

将大写和小写字母合并到整数1到26中，换行符为27，+和-为28和29，数字为30到39。注意换行符的转移字符。如果提供一个表格，每一个无论在规则中还是在任何输入中出现的合法字符必须包含在内。不能定义字符为0，并且不能用大于硬件字符集的整数定义字符。

12．源代码格式总结
一般的Lex代码文件格式为：

{definitions}

%%

{rules}

%%

{user subroutines}

定义部分由以下部分组成：

1．定义，形式为“name space translation”

2．被包含的代码，形式为“space code”

3．被包含的代码，形式为

%{

code

%}

4．开始条件，形式为

%S name1 name2 ...

5．字符集合表，形式为

%T

number space character-string

...

%T

6．转换成内置数组长度，形式为

%x nnn

这里nnn是一个十进制整数，表示数组的长度。而x是下列参数之一： 字母
 参数
 
p
 位置positions
 
n
 状态states
 
e
 树节点tree nodes
 
a
 转移transitions
 
k
 打包的字符类packed character classes
 
o
 输出数组的长度output array size
 

规则部分的每行具有形式“expression action”，这里action可以在大括号中使用多行。

Lex中的正则表达式使用如下的操作符： x
 字符"x"
 
"x"
 符号"x"，即使x是操作符
 
/x
 符号"x"，即使x是操作符
 
[xy]
 字符x或者y
 
[x−z]
 字符x、y或者z
 
[^x]
 除了x和换行符的所有字符
 
^x
 在一行开始处的x
 
x
 当Lex在开始条件y时的x
 
x$
 在一行末尾处的x
 
x?
 可选择的x
 
x*
 0,1,2, ...个x实例
 
x+
 1,2,3, ...个x实例
 
x|y
 x或者y
 
(x)
 x
 
x/y
 x，当且仅当x后面是y
 
{xx}
 将定义部分的xx进行翻译
 
x{m,n}
 m到n个x
 

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

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

14．感谢
由上可以明显地感觉到，Lex的外延是Yacc，而内涵是Aho的字符串匹配理论。因此S. C. Johnson和A. V. Aho是Lex中绝大部分的始创者，包括其调试器。对他们二人表示由衷的感谢。

当前版本的Lex由Eric Schmidt设计、编写和调试。

15．参考资料
B. W. Kernighan and D. M. Ritchie, The C Programming Language, Prentice-Hall, N. J. (1978).
B. W. Kernighan, Ratfor: A Preprocessor for a Rational Fortran, Software − Practice and Experience, 5, pp. 395-496 (1975).
S. C. Johnson, Yacc: Yet Another Compiler Compiler, Computing Science Technical Report No. 32, 1975, Bell Laboratories, Murray Hill, NJ 07974.
V. Aho and M. J. Corasick, Effificient String Matching: An Aid to Bibliographic Search, Comm. ACM 18, 333-340 (1975).
W. Kernighan, D. M. Ritchie and K. L. Thompson, QED Text Editor, Computing Science Technical Report No. 5, 1972, Bell Laboratories, Murray Hill, NJ 07974.
M. Ritchie, private communication. See also M. E. Lesk, The Portable C Library, Computing Science Technical Report No. 31, Bell Laboratories, Murray Hill, NJ 07974.

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/flankerfc/archive/2007/06/14/1651342.aspx