词法分析器生成工具flex的简单使用

1．FLEX简介

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

   +------------+       +------------+       +----------------+ 

   | 输入文件*.l |------>|flex工具     |------>|输出文件lex.yy.c |

   +------------+       +------------+       +----------------+ 

   

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

2. LEX源文件的格式

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

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

定义部份
%%
规则部份　
%%
用户附加C语言部份

下面以统计单词出现的次数的源程序count.l做说明，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)\n",atoi(yytext));/*打印数字值*/
    /*数字数加一*/
}

{ID} { num_id++;
    printf("(id=%s)\n",yytext);
    }

{SPACE} |
. {
   /*什么也不做,滤掉白字符和其它字符*/
   }
%%

int main()
{
   yylex();
   printf("num=%d,id=%d\n",num_num,num_id);
   return 0;
}

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

{
    return 1;
}


2.1定义部分：

%{
   #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]

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

其中，C代码部份由顶行的%{和}%引入，LEX扫描源文件时将%{和}%之间的部分原封不动的拷贝到输出文件lex.yy.c中。上面的定义部分没有条件模式的开始条件说明部分，只有C语言代码、模式的宏定义。

模式宏定义是一个正则表达式的定义，如上面所示的

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

正则表达式的匹配如下：

模式	解 释
x	配置单个字母x
.	匹配除换行符’\n’之外的任意字符
[xyz]	匹配x、y或z
[abj-oz]	匹配a、b、z及j至o之间的字母
[^A-Z]	除大写字母A-Z之外的其它字符
[^A-Z\n]	除大写字母A-Z和换行符之外的其它字符
r*	匹配0个或多个r
r+	匹配1个或多个r
r?	匹配0个或1个r

2.2规则部分

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

C语言代码
模式1 动作1
模式2 |
模式3 动作3

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

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

2.3 用户附加C语言部份

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

3.生成源代码和编译运行

flex count.l

gcc -g lex.yy.c -o count

运行:

osdba@osdba-laptop:~/tmp$ ./count <

aaa bbb ccc 999

EOF

(id=aaa)

(id=bbb)

(id=ccc)

(num=999)

num=1,id=3

osdba@osdba-laptop:~/tmp$ 

4. 模式匹配说明

   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中。

5. 常用全局变量和宏

   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:放弃当前匹配的字符串和当前的模式，让分析器重新扫描当前的字符串，并选择另一个最佳的模式再次进行匹配。

6. 条件模式

   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”);}
%%

阅读(8487) | 评论(1) | 转发(0) |

0

上一篇：http://www.pgsqldb.org/mwiki/index.php/MapReduce:_

下一篇：用Lex和Yacc做一个简单的SQL解释器