词法分析器生成工具FLEX简介

1．FLEX简介

   单词的描述称为模式(Lexical Pattern)，模式一般用正规表达式进行精确描述。FLEX通过读取一个有规定格式的文本文件，输出一个如下所示的C语言源程序。

   FLEX的输入文件称为LEX源文件，它内含正规表达式和对相应模式处理的C语言代码。LEX源文件的扩展名习惯上用.l表示。FLEX通过对源文件的扫描自动生成相应的词法分析函数 int yylex()，并将之输出到名规定为lex.yy.c的文件中。实用时，可将其改名为lexyy.c。该文件即为LEX的输出文件或输出的词法分析器。也可将 int yylex()加入自已的工程文件中使用。

2． 模式简介

   LEX的模式的格式(也称为规则)是机器可读的正规表达式，正规表达工是用连接、并、闭包运算递归生成的。为了方便处理，LEX在此基础上增加了一些运算。下列是按运算优先级由高往低排列的LEX的正规表达式的运算符。

“\[]^-?.*+|()/${}%<>

   关于LEX的模式定义，可参见下页附表1.1

3．LEX源文件格式

   LEX对源文件的格式要求非常严格，比如若将要求顶行书写的语句变成非顶行书写就会产生致命错误。而LEX本身的查错能力很弱，所以书写时一定要注意。

   LEX的源文件由三个部份组成，每个部分之间用顶行的“%%”分割，其格式如下：

   定义部份

   ％％

   规则部份　

   ％％

   用户附加C语言部份

3.1定义部份

   定义部份由C语言代码、模式的宏定义、条件模式的开始条件说明三部份组成。

   其中，C代码部份由顶行的%{和}%引入，LEX扫描源文件时将%{和}%之间的部分原封不动的拷贝到输出文件lex.yy.c中.

附表1.1 LEX 的模式定义

模 式	解 释
X	匹配单个字符x。(也可将模式写为”x”)
.	匹配除换行符’\n’之外的任意字符
[xyz]	匹配x、y或z
[abj-oZ]	匹配字符集:a、b、Z以及j到o之间的字母(包括j和o)
[^A-Z]	匹配字符集A到Z之间字符集的补集。即除大写字母的其它字符
[^A-Z\n]	匹配除大写字母和换行符之外的其它字符
r*	R是正规表达式，r*匹配0个或多个r
r+	R是正规表达式，r+匹配1个或多个r
r?	R是正规表达式，r?匹配0个或1个r
r{2,5}	R是正规表达式，r{2,5}匹配2个到5个r
r{2,}	R是正规表达式，r{2,}匹配2个或以上r
r{4}	R是正规表达式，r{4}匹配4个r
{name}	name是在定义部份出现的模式宏名，在规则部份将之替换为模式
“[xyz]\”foo”	匹配字符串[xyz]”foo
\x	如x是’a’、’b’、’f’、’n’、’r’或’t’，\x为转义字符，定义同ANSI C,否则，匹配字符x.此方法用于匹配正规表达式的运算符
\123	匹配八进制ASCII码为123的字符
\x2a	匹配十六进制ASCII码为2a的字符
(r)	匹配r,优先运算正规式r
Rs	匹配正规式r和s的连接
r|s	匹配正规式r或s
r/s	匹配正规式r,但是，r之后一定要出现正规式s。称s为r的尾部条件
^r	匹配正规式r,但是，r一定要出现在行首
r$	匹配正规式r,但是，r一定要出现在行尾
<s>r	匹配正规表达式r,但是一定要在开始条件s激活之后
<<EOF>>	匹配文件结束标志

   模式的宏定义部份如同C语言中的宏定义，通过宏名定义一个模式，这样，可以简化在源文件中多次出现的正规表达式的书写。格式为：

   宏名1 宏定义1

   宏名2 宏定义2　

   ……

   例如：

   DIGIT [0-9]

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

   宏名是以字母和下划线”_”开始，以字母、数字和下划线组成的字符串，且大小写敏感。宏名必须顶行写，宏名和宏定义必须写在同一行上。宏名和宏定义之间以不包括换行符的白字符(空格符、TAB符、换行符)隔开。

   条件模式的开始条件说明格式如下：

   ％start s1 s2 s3

   其中，s1、s2、s3为条件名。必须为大小写敏感的标识符。关于条件模式的使用，我们将在后面作说明。

3.2 规则部份

   规则部份是LEX源文件的核心部份，它包括一组模式和在生成分析器识别相应模式后对相应模式进行处理的C语言动作(Action)。格式如下

   C语言代码

   模式1 动作1

   模式2 |

   模式3 动作3

   ……

   同定义部分一样，C语言代码必须出现在第一个模式之前，包括在%{和}%之中，且%{必须顶行书写。%{和}%之间的代码部份可用来定义yylex()用到的局部变量。

   模式必须顶行书写。模式可为正规式或用{}括起且在定义部份定义过的宏名。动作为用{}括起的C代码。且开始括号{与模式之间用白字符隔开，且须和模式在同一行上。注意，在模式后加一|表示模式2和3采用同一动作3.|和模式2以白字符隔开。

3.3用户附加C语言部份

   LEX对此部份不作任何处理，仅仅将之直接拷贝到输出文件lex.yy.c的尾部。在些部份，可定义对模式进行处理的C语言函数、主函数和yylex要调用的函数yywrap()等。如果用户在其它C模块中提供这些函数，用户代码部份可以省略。

3.4 源文件格式小结

　　综上所述，LEX源文件详细格式如下：

　%{

   /*此模块为定义模块中Ｃ语言代码部份，在下面填入相应C代码*/

   }%

   模式宏名1 模式1

   模式宏名2 模式2

   ……

   %start s1 s2 s3

   %%

   %{

   /*此模块为规则模块中Ｃ语言代码部份，在下面填入相应C代码*/

   }%

   模式1 动作1

   模式2 动作2

   ……

   %%

   /*此模块为用户附加C语言部份，在下面填入相应C代码*/

   注意：以上三部份及其中任何一子部份，均可省去。且如无第三部分，第二个%%也可省去，但第一个%%决不可省。

４．LEX的工作原理

   LEX通过对源文件的扫描，经过宏替换后，将规则部份的正规表达式转换成与之相应的DFA，并由之产生一个名为int yylex()的词法分析函数，将之拷贝到输出文件lex.yy.c中。由于考虑到C代码的可移植性和运行效率问题，lex.yy.c中大量使用了宏定义，且文件较大(30-50kb)。因此，几乎是不可读的。但是，其可移植性相当好。

   lex.yy.c中定义了很多用户可定义的全局变量，以及在LEX源文件的动作中可调用的函数和宏。但是，由于lex.yy.c太过复杂，建议初学者不要随意修改它。用户在了解其的前提下，可在其它C模块中引用之。

５．二义性问题的解决

   yylex()函数被调用之后，它首先检查全局文件指针变量yyin是否有定义，如有，则将之设置为将要扫描的文件指针。如无，则设置为标准输入文件stdin.同理，如全局文件指针变量yyout无定义，则将之设置为标准输出文件stdout。

   若有多个模式与被扫描文件中的字符串相匹配，则yylex()执行能匹配最长字符串的模式，称为“最长匹配原则”；若还有多个模式匹配长度相同的字符串，则yylex()选择在LEX源文件中排列最前面的模式进行匹配，称为“最先匹配原则”。yylex()常通过超前搜索一个字符来实现这样的原则，如果使用超前搜索匹配了某一模式，则yylex()在进行下一次分析前，将回退一个字符。见下例：

   %%

   program {printf(“keyword:%s!\n”,yytext); /*模式一*/}

   procedure {printf(“keyword:%s!\n”,yytext); /*模式二*/}

   [a-z][a-z0-9]* {printf(“identifier:%s!\n”,yytext); /*模式三*/}

   %%

   如输入串为”programming”，yylex()分析到子串”program”时，有模式一和三可以匹配，但根据最长搜索原则，发现在继续读入输入串时，还可匹配模式三。这样，将输出”identifier:programming!”。如输入串为”program”,则按最先匹配原则，模式一与之匹配，输出”keyword:program!”。注意，若将模式一和模式三在源文件中次序弄反，则模式一永远也得不到匹配。若无模式可匹配输入串，则使用缺省规则，即将输入串原样拷贝至输出文件yyout中。

６．常用全局变量和宏

   lex.yy.c中常用全局变量、函数和宏很多，在此仅指出一些最常用的，若需要更详细信息，请阅读源文件。

   (1) FILE *yyin,*yyout:为指向字符输入和结果输出文件的指针。如用户未对其定义，则设为标准输入文件stdin和stdout。

   (2) int yylex():为词法分析程序，它自动移动文件指针yyin和yyout。在定义模式动作时，用户可用return语句结束yylex(),return 必须返回一整数。由于yylex()的运行环境都是以全局变量的方式保存，因此，在下一次调用yylex()时，yylex()可从上次扫描的断点处继续扫描，在语法分析时，可利用这一特性。若用户未定义相应的return语句，则yylex()继续分析被扫描的文件，直到碰到文件结束标志EOF。在读到EOF时，yylex()调用int yywrap()函数(该函数用户必须提供)，若该函数返回非0值，则yylex()返回0而结束。否则，yylex()继续对yyin指向的文件扫描。

   (3) char *yytext:存放当前被识别的词形。

   (4) int yyleng:存放字符串yytext的长度。

   (5) int yywrap():参见(2)

   (6) yymore()：将当前识别的词形保留在yytext中，分析器下次扫描时的词形将加追加在yytext中。例模式定义如下

   ……

   hello {printf(“%s!”,yytext);yymore();}

   world {printf(“%s!”,yytext);}

   ……

   当输入串为”helloworld”时，将输出”hello!helloworld!”

   (7) yyless(int n):回退当前识别的词形中n个字符到输入中

   (8) unput(char c):回退字符c到输入，它将作为下一次扫描的开始字符

   (9) input():让分析器从输入缓冲区中读取当前字符，并将yyin指向下一字符

   (10)yyterminate():中断对当前文件的分析，将yyin指向EOF。

   (11)yyrestart(FILE * file):重新设置分析器的扫描文件为file

   (12)ECHO:将当前识别的字符串拷贝到yyout

   (13)BEGIN:激活开始条件对应的模式

   (14)REJECT:放弃当前匹配的字符串和当前的模式，让分析器重新扫描当前的字符串，并选择另一个最佳的模式再次进行匹配。

7.条件模式

   LEX提供控制模式在一定状态下使用的功能，称为条件模式。LEX首先在定义部份通过%start来定义条件句。在规则部份可通过宏

   BEGIN 条件名　来激活条件。BEGIN　INITIAL或BEGIN 0将休眠所有的条件模式，使分析器回到开始状态。

   例：将输入文件中的单词”magic” 作如下处理：识别”magic”时，如”magic”所在行行首为字符’a’,则输出”first”;若为’b’,则输出”second”;否则，输出”magic”。如不用条件模式，LEX源文件可这样写：

   %{int flag;}%

   %%

   ^a {flag=’a’;ECHO;}

   ^b {flag=’b’;ECHO;}

   \n {flag=0;ECHO;}

   magic {

   switch(flag)

   {

   case ‘a’:printf(“first”);break;

   case ‘b’:printf(“second”);break;

   default :ECHO;break;

   }

   }

   %%

   如使用条件模式,则上述源文件可简化为 %start AA BB CC

   %%

   ^a {ECHO;BEGIN AA;}

   ^b {ECHO;BEGIN BB;}

   \n {ECHO;BEGIN 0;}

   <AA>magic {printf(“first”);}

   <BB>magic {printf(“second”);}

   %%

8. 示例

   例一：编制LEX源程序,分别统计文本文件a.txt中出现的标识符和整数个数,并显示之。标识符定义为字母开头，后跟若干个字母，数字或下划线。整数可以带+或-号，也可不带，且不以0开头。非单词和非整数则忽略不记，将之滤掉不显示。

   设LEX源文件名为count.l.文件内容如下

   %{

   #include "stdio.h"

   #include "stdlib.h"

   int num_num=0,num_id=0;

   %}

   INTEGER [-+]?[1-9][0-9]*

   ID [a-zA-Z][a-zA-Z_0-9]*

   SPACE [ \n\t]

   %%

   {INTEGER} { num_num++;

   printf("(num=%d)",atoi(yytext));//打印数字值

   /*数字数加一*/

   }

   {ID} {

   num_id++;

   printf("(id=%s)",yytext);

   }

　　　　{SPACE} |

   . {

   //什么也不做,滤掉白字符和其它字符

   }

   %%

   void main()

   {

   yylex();

   printf("num=%d,id=%d",num_num,num_id);

   }

   int yywrap()//此函数必须由用户提供

   {return 1;}

   设count.l所在目录为c:\test，且已用path命令指定flex.exe所在目录。则调用命令

   c:\test> flex count.l后可在c:\test目录下得到一文件lex.yy.c，打开C环境，新建工程文件my.prj(TURBOC 或BORLAND C下后缀为.prj，VC下后缀为.dsw),将lex.yy.c加入工程文件中,编译运行可得可执行文件my.exe.若需分析从标准输入中输入的字符串,运行my.exe即可.若需分析放在其它文件中的串,如设在文件hello.txt中,则运行my.exe<hello.txt即可.

   例2:编制一LEX源程序,分别求出文件hh.c中字母,数字,回车符的个数.源程序如下:

   %{

   #include "stdio.h"

   #include "stdlib.h"

   int num_digit=0,num_letter=0,num_enter=0;

   %}

   DIGIT [0-9]

   LETTER [A-Za-z]

   %%

   {DIGIT} {num_digit++;}

   {LETTER} {num_letter++;}

   \n {num_enter++;}

   . {/*其它字符不作处理*/}

   %%

   void main()

   {

   yyin=fopen(”hh.c”,r);

   yylex();

   printf("num=%d,letter=%d,enter=%d",

   num_digit,num_letter,num_enter);

   }

   int yywrap()//此函数必须由用户提供

   {　

　 return 1;

   }