LEX/FLEX词法分析器

CONTENTS：


LEXFLEX词法分析器
LexFlex词法分析器
Flex的安装和使用
Lex语法格式
definitions
rules
user subroutines

FLEX实例





这篇文章的内容包括：

lex语法格式
linux下flex的安装和使用
flex实例
flex源代码的编译和使用
Lex/Flex词法分析器


  
Lex是LEXical compiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式(regular expression)。描述词法分析器的文件*.l，经过lex编译后，生成一个lex.yy.c 的文件，然后由C编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符(token)，转化后的标识符 很容易被后续阶段处理。    ——  [ 百度百科 ]




Flex的安装和使用

在使用apt软件包管理器linux系统上我们可以非常方便地安装并使用flex。在终端中输入以下代码安装flex：（可能需要root权限）

$> sudo apt-get install flex

flex代码的源文件往往是以.l为后缀名的。 

.l文件通过以下命令编译（以文件名为scanner.l为例）：



$> flex scanner.l

编译后在源代码相同目录下会生成一个lex.yy.c，这就是生成的能够执行上述scanner.l功能的c语言代码。使用gcc编译即可生成词法分析程序：



$> gcc lex.yy.c -o scanner

然后将需要分析的文件（以input.txt为例）作为参数传递给scanner执行分析：



$> ./scanner input.txt



Lex语法格式

flex的语法被分为三个部分：



{definitions}
%%
{rules}
%%
{user subroutines}



definitions:



LABEL REGULAR_EXPRESSION

LABEL是这里类字符串的名称，REGULAR_EXPRESSION则是匹配这种字符串的正则表达式。正则表达式的语法主要包括：

符号
  
含义
|
  
或
[]
  
括号中的字符取其一
-
  
a-z表示ascii码中介于a-z包括a.z的字符
\
  
转义（flex不能识别除字母外的字符）
*
  
0或多个字符
?
  
0或1个字符
+
  
1或多个字符
^
  
除此之外的其余字符
.
  
除\n外的所有字符，等价于^\n
示例：



1. INT [1-9][0-9]*|[0]  /*整数类型，0或不以0开头的由0-9组成的字符串*/
2. FLOAT [0-9]*[.][0-9]+([eE][+-]?[0-9]*|[0])?f?    /*浮点数格式*/
3. LP \(    /*一个左圆括号*/


  
注：用%{    %}括起来的语句将被完全写入编译后的c语言文件中。 

  例如  
%{ 

      #include <stdio.h> 

      int num_id = 0; 

  %}




rules:

规则部分的语法如下：



{LABEL1} |
{LABLE2} |
...
{ 
/*TODO*/
}

TODO部分是告诉编译器在匹配到字符串之后程序需要做些什么。 

例如在匹配到整数后打印这个整数：



{INT} {
    printf("Pick up an integer, value is %d", atoi(yytext));
    printf("Pick up an integer, value is %s", yytext);
}

其中atoi()函数将字符串转换为整数。



user subroutines

此处主要是放置用户需要执行的c语言代码。他们会被原封不动地加入到lex.yy.c文件的末尾。 

这里一般用来存放main函数，详细会在后面说明。



FLEX实例

下面通过一个实例来具体展示flex的使用方式，主要功能是扫描并匹配文件中的字符串，并回显其类型和内容，代码如下：



/************************
 * scanner.l
 * @author mist
 * 2015-9-21 23:08
 ************************/
%{
#include "stdio.h"
#include "stdlib.h"
%}

INT_DEX [1-9][0-9]*|[0]
INT_HEX [0][Xx]([1-9][0-9]*|[0])
INT_OCT [0][0-7]
FLOAT [0-9]*[.][0-9]+([eE][+-]?[0-9]*|[0])?f?
SEMI [;]
COMMA [,]
ASSIGNOP [=]
RELOP [>]|[<]|[>][=]|[<][=]|[=][=]|[!][=](^[=])
PLUS [+]
MINUS [-]
STAR [*]
DIV [/]
AND [&][&]
OR [|][|]
DOT [.]
NOT [!]
TYPE int|float
LP \(
RP \)
LB \[
RB \]
LC \{
RC \}
STRUCT struct
RETURN return
IF if
ELSE else 
WHILE while
SPACE [ \n\t]
ID [a-zA-Z_][a-zA-Z_0-9]*
/*end of definition*/

%%
{SEMI} {
    printf("get semmi : %s\n", yytext);

}

{COMMA} {
    printf("get comma : %s\n", yytext);
}
{ASSIGNOP} {
    printf("get assignop : %s\n", yytext);
}

{INT_DEX} |
{INT_HEX} |
{INT_OCT} {
    printf("get an integer: %s\n", yytext);
}

{FLOAT} {
    printf("get a float: %s\n", yytext);
}

{PLUS} | 
{MINUS} |
{DIV} |
{STAR} {
    printf("get an operator: %s\n", yytext);
}

{RELOP} {
    printf("get a relop: %s\n", yytext);
}

{AND} |
{OR} |
{NOT} {
    printf("get a logic operator: %s\n", yytext);
}

{DOT} {
    printf("get a dot: %s\n", yytext);
}
{STRUCT} |
{RETURN} |
{IF} |
{ELSE} |
{WHILE} {
    printf("get keyword: %s\n", yytext);
}

{TYPE} {
    printf("get type: %s\n", yytext);
}

{LP} |
{RP} |
{LB} |
{RB} |
{LC} |
{RC} {
    printf("get brackets : %s\n", yytext);
}

{SPACE} |
. {
/*ABANDON THESE CHARACTORS*/
}

{ID} {
    printf("get an ID: %s\n", yytext);
}
%%
int yywrap() {
  return 1;
}

int main(int argc, char** argv) {
   if (argc > 1) {
       if (!(yyin = fopen(argv[1], "r"))) {   
           perror(argv[1]);
           return 1;
       }
   }
   while (yylex());
   return 0;

我们需要为生成的分析程序编写main函数。首先需要通过yyin来获取指向被分析文件的文件FILE指针，一般文件的路径通过控制台的第二个参数获得。分析部分的实体在函数yylex()中。 

yywrap()用于判断是否已经扫描完了所有的文件。如果它在最后一个文件的末尾被调用，则返回值为1。此时程序将停止分析，可以用来扫描多个文件。

输入文本： 
int float {}()[] 0 

0x0 0x123 

123.5 

.3e-10f 

= >= || && ! ; , 

this_is_an_id 

id123 

if then else  
 

输出：



get type: int
get type: float
get brackets : {
get brackets : }
get brackets : (
get brackets : )
get brackets : [
get brackets : ]
get an integer: 0
get an integer: 0x0
get an integer: 0x123
get a float: 123.5
get a float: .3e-10f
get assignop : =
get a relop: >=
get a logic operator: ||
get a logic operator: &&
get a logic operator: !
get semmi : ;
get comma : ,
get an ID: this_is_an_id
get an ID: id123
get keyword: if
get an ID: then
get keyword: else

另外附上词法要求： 

INT  /* A sequence of digits without spaces1 */ 

FLOAT  /* A real number consisting of digits and one decimal point. The deci- 

mal point must be surrounded by at least one digit2 */ 

ID  /* A character string consisting of 52 upper- or lower-case alphabetic, 10 

numeric and one underscore characters. Besides, an identifier must not start 

with a digit3 */ 

SEMI  ; 

COMMA  , 

ASSIGNOP  = 

RELOP  > | < | >= | <= | == | != 

PLUS  + 

MINUS  - 

STAR  * 

DIV  / 

AND  && 

OR  || 

DOT  . 

NOT  ! 

TYPE  int | float 

LP  ( 

RP  ) 

LB  [ 

RB  ] 

LC  { 

RC  } 

STRUCT  struct 

RETURN  return 

IF  if 

ELSE  else 

WHILE  while

1) 词法单元INT表示的是所有(无符号)整型常数。一个十进制整数由0~9十个数字组 

成,数字与数字中间没有如空格之类的分隔符。除“0”之外,十进制整数的首位数字 

不为0。例如,下面几个串都表示十进制整数:0、234、10000。为方便起见,你可以 

假设(或者只接受)输入的整数都在32bits位之内。

2) 整型常数还可以以八进制或十六进制的形式出现。八进制整数由0~7八个数字组成并以 

数字0开头,十六进制整数由0~9、A~F(或a~f)十六个数字组成并以0x或者0X开头。 

例如,0237(表示十进制的159)、0xFF32(表示十进制的65330)。

3) 词法单元FLOAT表示的是所有(无符号)浮点型常数。一个浮点数由一串数字与一个 

小数点组成,小数点的前后必须有数字出现。例如,下面几个串都是浮点数:0.7、 

12.43、9.00。为方便起见,你可以假设(或者只接受)输入的浮点数都符合IEEE754单 

精度标准(即都可以转换成C语言中的float类型)。

4) 浮点型常数还可以以指数形式(即科学记数法)表示。指数形式的浮点数必须包括基 

数、指数符号和指数三个部分,且三部分依次出现。基数部分由一串数字(0~9)和一 

个小数点组成,小数点可以出现在数字串的任何位置;指数符号为“E”或“e”;指 

数部分由可带“+”或“”(也可不带)的一串数字(0~9)组成,“+”或“”(如 

果有)必须出现在数字串之前。例如01.23E12(表示1.23  1012)、43.e-4(表示43.0  

10-4)、.5E03(表示0.5  103)。

5) 词法单元ID表示的是除去保留字以外的所有标识符。标识符可以由大小写字母、数字 

以及下划线组成,但必须以字母或者下划线开头。为方便起见,你可以假设(或者只 

接受)标识符的长度小于32个字符。

6) 除了INT、FLOAT和ID这三个词法单元以外,其它产生式中箭头右边都表示具体的字 

符串。例如,产生式TYPE  int | float表示:输入文件中的字符串“int”和“float”都 

将被识别为词法单元TYPE。 

2.2 

 High-level Definitions

生成词法分析程序 可能会发生yywrap未定义的错误。yywrap必须由用户亲自编写，一般按如下形式即可： 

void yywrap() { return 1; } ↩

大多数情况下，flex词法分析器从文件或STDIN（终端用户）中读取输入。从文件读取和从终端读取存在着一个微小但是重要的差异——预读机制。如果词法分析器从文件读取，它可以通过大段的读操作来提高工作效率。但是如果它从终端读取，用户可能一次只输入一行，并且期望每行输入完成时，词法分析器能够立刻处理。在这种情况下处理效率不再是一个问题。幸运的是，flex词法恩稀奇会检查当前输入是否来自终端并决定使用哪种读取方式。
flex处理输入的数据结构为yy_buffer_state，而YY_BUFFER_STATE是typedef定义的yy_buffer_state结构体的指针类型。
#ifndef YY_TYPEDEF_YY_BUFFER_STATE
#define YY_TYPEDEF_YY_BUFFER_STATE
typedef struct yy_buffer_state *YY_BUFFER_STATE;
#endif
#ifndef YY_STRUCT_YY_BUFFER_STATE
#define YY_STRUCT_YY_BUFFER_STATE
struct yy_buffer_state
	{
	FILE *yy_input_file; /* 输入文件的句柄 */

	char *yy_ch_buf;		/* 输入缓冲区 */
	char *yy_buf_pos;		/* 在输入缓冲区中当前读取的位置 */

	/* 输入缓冲区的字节数，不包括终结符（EOB）字符。EOB为End of Block的缩写 */
	int yy_buf_size; 

	/* yy_ch_buf中已经读取了的字符数，不包括终结符（EOB）字符 */
	int yy_n_chars;

	/* 我们是否“拥有”缓冲区。也就是说，我们知道已经创建了缓冲区，并且可以重新分配以增长缓冲区，并应该适时释放缓冲区 */
	int yy_is_our_buffer;

	/* 是否是“交互性”的输入。如果是交互性输入或者以STDIN作为输入，用getc()函数代替fread()函数，使得每行结束后词法分析器可以立即处理 */
	int yy_is_interactive;

	/* 是否在行首。若是，则下次匹配时"^"规则将生效；若不是，反之 */
	int yy_at_bol;

    int yy_bs_lineno; /* 行号 */
    int yy_bs_column; /* 列号 */

	/* 在到达输入结束时，是否填充输入缓冲区 */
	int yy_fill_buffer;

    /* 缓冲区状态 */
	int yy_buffer_status;

#define YY_BUFFER_NEW 0 /* 当遇到EOF后，使用yyrestart()函数，可以将yy_buffer_status置为YY_BUFFER_NEW。这样允许用户可以重新指定下一个输入继续词法分析*/
#define YY_BUFFER_NORMAL 1 /* 一般正常情况下，yy_buffer_status是这个状态*/
#define YY_BUFFER_EOF_PENDING 2 /*当遇到了EOF但仍有一些文本要处理，yy_buffer_status置为YY_BUFFER_EOF_PENDING，以表明不应该再尝试从输入源读取数据了。但由于可能还有一些已经读取的输入还没有处理完，可能仍有许多token要匹配，直到所有为处理的字符被“耗尽”。*/
	};
#endif /* !YY_STRUCT_YY_BUFFER_STATE */

该结构定义了一个单一输入源。它包含一个字符串缓冲区，以及一些变量和标记。通常它会有一个指向所读文件的FILE*，但是我们也可以创建一个与文件无关的YY_BUFFER_STATE实例来分析已经在内存中的字符串。
默认的flex词法分析器的输入行为大致如下:
YY_BUFFER_STATE bp;
extern FILE* yyin;

// ..... 省略，此处包含任何在第一次调用词法分析器之前所需要做的事情

if(!yyin){
	yyin = stdin; // 默认输入设备是stdin
}
bp = yy_create_buffer(yyin, YY_BUFFER_SIZE); // YY_BUFFER_SIZE由flex定义，大小通常是16k
yy_switch_to_buffer(bp); // 告诉它使用我们刚刚创建的缓冲区

如果yyin还没有被设置，就把stdin设置给它。然后使用yy_create_buffer函数创建一个读取yyin的新缓冲区，通过yy_switch_to_buffer函数来将新缓冲区切换为当前读取的输入，以便于词法分析器从最新的缓冲区读取开始分析。
当需要顺序读取多个文件时，每次打开一个文件需要调用一次yyrestart(fp)函数，把词法分析器的输入切换到输入文件fp。
其他一些函数也可以用来创建缓冲区，包括yy_scan_string(“This is a string.”)用于分析以空字符’\0’结尾的字符串，和yy_scan_buffer(char *base, size)分析长度确定的数据流。
flex提供了两个动作代码中比较有用的宏，input()和unput()。每次input()的调用将返回输入流的下一个字符。它可以帮助我们读取一小段输入而不用定义相应的模式。每次对unput©的调用把字符c推回到输入流。这个功能可以向前查看输入但不做处理。
总结以下，输入管理的三个层次是：

设置yyin来读取所需文件
创建并使用YY_BUFFER_STATE输入缓冲区
重定义YY_INPUT

词法分析器的输出管理比输入管理简单得多，而且完全可选的。同样可以追溯到最早的lex版本，除非你另行设定，否则flex总会执行一条默认的规则：所有没有被匹配的输入都拷贝yyout然后输出。
%{
/* ...省略部分 */
#define ECHO fwrite(yytext, yyleng, 1, yyout)
%}

%%
/* ...省略部分 */
. ECHO; // flex默认的规则：所有没有被匹配的输入都拷贝yyout然后输出
%%

    
// 注意：由于目前还没有学到起始条件（start condition）相关的知识，以上flex默认的规则只是一个简版。
// 实际上它应该为：<*>.|\n     ECHO;

注意：这对于那些仅处理一部分输入而保持剩余部分不变的flex程序来说可能有些作用，比如在英式英语转换到美式英语的翻译器中，但大多数情况下它更容易导致一些错误。flex允许你在词法分析器顶端设置%option nodefault，使它不要添加默认的规则，这样当输入无法被给定的规则完全匹配时，词法分析器可以报告一个错误。
建议词法分析器总是使用nodefault选项，并在必要情况下包含自己的默认规则。

一. flex格式文件 test.l
 
%{ 
#include "stdio.h" 
#include "stdlib.h" 
void print();                           
int _tmain(int argc,_TCHAR*argv[]);       
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++;} 
. {/*其它字符不作处理*/} 
%% 
int _tmain(int argc, _TCHAR* argv[])
{ 
yyin=fopen("ccx_test1.c","r"); 
yylex(); 
printf("num=%d,letter=%d,enter=%d", 
num_digit,num_letter,num_enter); 
return 0;
} 
int yywrap()
{
return 1;
} 
 
二.有了这个文件利用命令行生成c文件，格式如下：
E:/Tools/flex>flex.exe test.l
然后生成LEXYY.C文件。
 
三.在vs2003下建立一个空的console程序testlex
将testlex.cpp文件从工程中删除。然后加载LEXYY.C，编译运行生成可执行文件即可。