Lex和Yacc——Lex学习

一，什么是Lex？

引用度娘上面的介绍：

Lex是LEXical compiler的缩写，是Unix环境下非常著名的工具,主要功能是生成一个词法分析器(scanner)的C源码,描述规则采用正则表达式(regular expression)。
OK，我们先来介绍Lex中的正则表达式。

二，Lex中的正则表达式

基本上，Lex中的正则表达式和UNIX bash里面的正则表达式是一致的。我们看一些例子：

• abc：匹配abc
• [abc]：匹配a、b、c三者之一
• [A-Z]：匹配A～Z的所有大写字母
• [A-Z]：匹配A、-、Z三者之一
• [-AZ]：和[A-Z]相同
• ¹：匹配除ab之外的任意字符
• [a^b]：匹配a、^、b三者之一
• [a|b]：匹配a、|、b三者之一
• a|b：匹配a或者b
• abc+：匹配abcc、abccc、abcccc、...
• a(bc)+：匹配abcbc、abcbcbc、abcbcbcbc、...
• ^abc$：匹配只有abc的行
• [0-9]+：匹配整数。
• -?[0-9]：匹配带符号的整数。
• -?[0-9]*.[0-9]+：匹配带符号的小数。
  从上面的一些例子我们可以总结出一些注意点：

（1） []表示一个集合，匹配集合里面的某个元素；不加[]时则匹配一个串。
（2）“-”只有在方括号的中间时，才表示范围，否则只是普通字符。类似的还有“^”（只有在首部时，才表示否定）、“$”（只有在末尾时，才表示行尾）、“|”（只有在方括号外使用时才表示或）.
（3）“*”、“+”、“?”只匹配之前离他们最近的那个元素，如果要匹配多个，就需要加括号。

PS：C语言中的一些转义字符也可以出现在正则式中，比如\t \n \b等。

三，Lex的基本原理和方法

Lex的基本工作原理为：由正则表达式生成NFA，将NFA变换成DFA，DFA经化简后，模拟生成词法分析器。

什么是NFA呢？NFA全称Nondeterministic Finite Automata，表示不确定有穷自动机，一般采用tompson构造来构建NFA。

一个不确定的有穷自动机T是一个五元组，M={K，∑，f,S,Z}

⒈K是一个有穷集他的每一个元素称作一个状态。
⒉∑是一个字母表，他的每一个元素称为一个输入符号。
⒊f是一个从Kx∑到K的子集映射即K∑*->2^K，其中2^K表示K的幂集。
⒋S包含于K集，是一个非空初态集合。
⒌Z包含于K是一个非空的终态集合。

DFA英文全称：Deterministic Finite Automaton

定义：一个确定有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中

① K是一个有穷集，它的每个元素称为一个状态；

② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；
③ f是转换函数，是K×Σ→K上的映射(且可以是部分函数)，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
④ S ∈ K是唯一的一个初态；
⑤ Z⊂K是一个终态集，终态也称可接受状态或结束状态。

其中正则表达式由开发者使用Lex语言编写，其余部分由Lex翻译器（比如GUN下面的flex工具）完成。翻译器将Lex源程序翻译成一个名为lex.yy.c的C语言源文件（所以Lex是和C强相关的），此文件含有两部分内容：一部分是根据正则表达式所构造的DFA状态转移表，另一部分是用来驱动该表的总控程序yylex()。当主程序需要从输入流中识别一个记号时，只需要调用一次yylex()就可以了。为了使用Lex所生成的词法分析器，我们需要将lex.yy.c程序用C编译器进行编译，并将相关支持库函数连入目标代码。Lex的使用步骤如下图所示：

四，Lex的语法

Lex源程序必须按照Lex语言的规范来写，其核心是一组词法规则（正则表达式）。一般而言，一个Lex源程序分为三个部分，三部分之间用"%%"分隔：

第一部分：定义段

%%

第二部分：词法规则段

%%

第三部分：辅助函数段

当然，第一部分和第三部分使可以省略的，也就是说Lex程序段也可以精简成下面这样：

%%      /* 不能少 */

第二部分：词法规则段

一般以%开头的符号和关键字，或者是词法规则段的各个规则一般顶行来写，前面没有空格。这个很重要，如果不这样，往往会编译失败。Lex程序中支持C的/**/格式注释，但是写在第二部分（词法规则段）的注释的行首必须要有前导空格（即不能顶格写）。好的习惯是所有%和关键字都顶格写，所有注释都不要顶格写。

下面我们看各个段落如何写。

1. 第一部分定义段写法

定义段可以分为两部分：

第一部分以符号%{和%}包裹，里面以C语法写一些定义和声明：例如，头文件，宏定义，常数定义，全局变量以及外部变量定义，函数声明等。这一部分被Lex翻译器处理之后会全部拷贝到文件lex.yy.c中。注意，特殊括号%{和%}必须顶着行首写。例如：

%{
#include <stdio.h>

#define MAX_LINE 1024
extern int yylval;
%}

第二部分是一组正则定义和状态定义。正则定义是为了简化后面的词法规则而给部分正则式定义了名字。每条正则定义一定要顶格写。例如：

letter        [A-Za-z]
digit         [0-9]
id            [letter]({letter}|{digit})*

注意，上面正则定义中出现的小括号表示分组，而不是被匹配的字符。而大括号括起的部分表示正规定义名。

状态定义也叫环境定义，它定义了匹配正则式时所处的状态的名字。状态定义以%s开始，后跟所定义的状态的名字，注意%s也要顶格写。例如下面一行就定义了一个名为COMMENT的状态和一个名为BAD的状态，状态之间用空白隔开：

%s COMMENT BAD

2. 第二部分词法规则段的写法

词法规则段列出的是词法分析器需要匹配的正则式，以及匹配该正则式后需要进行的相关动作。例子如下：

while        { return (WHILE); }
do           { return (DO); }
{id}         { yylval = installID(); return (ID); }

每行都是一条规则，该规则的前一部分是正则式，需要顶行来写，后一部分是匹配该正则式后需要进行的动作，这个动作是用C语法来写的，被包裹在{}之内，被Lex翻译器翻译后会被直接拷贝进lex.yy.c。正则式和语义动作之间要有空白隔开。其中用{}扩住的正则式表示正则定义的名字。也可以若干个正则式匹配同一条语义动作，此时正则式之间要用|分隔。

3. 第三部分辅助函数的写法

辅助函数段用C语言语法来写，辅助函数一般是在词法规则段中用到的函数。这一部分一般会被直接拷贝到lex.yy.c中。比如：

main ()
{
    yylex();
}

4. Lex内置的变量及函数

• yyin和yyout：这是Lex中已经定义的输入和输出文件指针。这两个变量指明了lex生成的词法分析器从哪里获取输入和输出到哪里。默认是标准输入（stdin）和标准输出（stdout）。
• yytext：指向当前识别的词法单元（词文）的指针，即C里面的char*，一般可以直接用%s打印。
• yyleng：当前词法单元的长度。
• ECHO：Lex中预定义的宏，可以出现在（第二部分的）动作中，相当于fprintf(yyout, "%s", yytext)，即输出当前匹配的词法单元。
• yylex()：词法分析器驱动程序，用Lex翻译器生成的lex.yy.c内必然包含这个函数。
• yywrap()：词法分析器遇到文件结尾时会调用yywrap()来决定下一步怎么做：若yywrap()返回0，则继续扫描，若返回1，则返回报告文件结尾的0标记。由于词法分析器总会调用yywrap，因此辅助寒素中最好提供yywrap，如果不提供，则在C编译器编译lex.yy.c时，需要链接相应的库，库中会给出标准的yywrap函数（标准函数返回1）。

5. 词法分析器的状态（环境）

词法分析器在匹配正则式时，可以在不同状态（或环境）下进行。我们可以规定在不同的状态下有不同的匹配方式。每个词法分析器都至少有一个状态，这个状态叫做初始状态，可以用INITIAL或0来表示，如果还需要使用其他状态，可以在定义段用%s来定义。使用状态时，可以用如下方式写词法规则：

<state1, state2> p0     { action0; }
<state1> p1             { action1; }

这两行词法规则表示：在状态state1和state2下，匹配正则式p0后执行动作action0，而只有在状态state1下，才可以在匹配正则式p1后执行动作action1。如果不指明状态，默认情况下处于初始状态INITIAL。

要想进入某个特定状态，可以在动作中写上这样一句：BEGIN state；执行这个动作后，就进入状态state。下面是一段处理C语言注释的例子，里面用到了状态的转换，在这个例子里，使用不同的状态，可以让词法分析器在处于注释中和处于注释外时使用不同的匹配规则：

...
%s c_comment
...

%%

<INITIAL>"/*"      { BEGIN c_comment; }
...
<c_comment>"*/"    { BEGIN 0; }
<c_comment>.       { ; }

6. Lex的匹配策略

• 按最长匹配原则确定被选中的单词。
• 如果一个字符串能被若干正则式匹配，则先匹配排在前面的正则式。

五，一个实例

Lex常常与语法分析器的生成工具yacc同时使用。此时，一般来说，语法分析器每次都调用一次yylex()获取一个记号。如果想自己写一个程序使用lex生成的词法分析器，则只需要在自己的程序中按需要调用yylex()函数即可。需要注意的是，yylex()函数调用结束后，输入缓冲区并不会被重置，而是仍然停留在刚才读到的地方。并且，词法分析器当前所处的状态（%s定义的那些状态）也不会改变。

exam1.l

/* 这是注释部分，与C中的/*...* /注释相同 */
/* 第一部分是定义、声明部分。这部分内容可以为空 */

%{

/* 写在 %{...%}这对特殊括号内的内容会被直接拷贝到C文件中。
 *
 * 这部分通常进行一些头文件声明，变量、常量的定义，用C语法。
 *
 * %{和%}两个符号都必须位于行首
 */

/* 下面定义了需要识别的记号名，如果和yacc联合使用，这些记号名应该在yacc中定义 */

#include <stdio.h>

#define LT          1
#define LE          2
#define GT          3
#define GE          4
#define EQ          5
#define NE          6

#define WHILE       18
#define DO          19
#define ID          20
#define NUMBER      21
#define RELOP       22

#define NEWLINE     23
#define ERRORCHAR   24

int yylval;
/* yylval是yacc中定义的变量，用来保存记号的属性值，默认是int类型。
 * 在用lex实现的词法分析器中可以使用这个变量将记号的属性传递给yacc
 * 实现的语法分析器。
 * 
 * 注意：该变量只有在联合使用lex和yacc编写词法和语法分析器时才可以
 * 在lex中使用，此时该变量不需要定义即可使用。单独使用lex时，编译器
 * 找不到这个变量。所以这里定义了该变量。
 */
int installID();
int installNum();

%}

 /*
 * 这里进行正则定义和状态定义。下面就是正则定义，注意，正则定义和状态
 * 定义都要顶格写。
 */

delim       [ t n]
ws          {delim}+
letter      [A-Za-z_]
digit       -?[0-9]
id          {letter}({letter}|{digit})*
number      {digit}+(.{digit}+)?(E[+-]?{digit}+)?

 /* %%作为lex文件三个部分的分隔符，必须位于行首。下面这个%%不能省略 */
%%

 /* 第二部分是翻译规则部分。
  * 写在这一部分的注释要有前导空格，否则lex编译出错。
  * 翻译规则形式是：正则式 {动作}
  * 其中，正则式要顶行写，动作以C语法写（动作会被拷贝到yylex()函数中），
  * 正则式和动作之间要用空白分隔。
  */

{ws}        { ; /* 此时词法分析器没有动作，也不返回，而是继续分析 */}

 /* 正则式部分用大括号扩住表示正则定义名，例如{ws}
  * 没有扩住的直接表示正则式本身。
  * 一些正则元字符没办法表示它本身，此时可以用转义字符或双引号
  * 括起来，例如"<"
  */
while       { return (WHILE); }
do          { return (DO); }
{id}        { yylval = installID(); return (ID); }
{number}    { yylval = installNum(); return (NUMBER); }
"<"          { yylval = LT; return (RELOP); }
"<="     { yylval = LE; return (RELOP); }
"="         { yylval = EQ; return (RELOP); }
"<>"      { yylval = NE; return (RELOP); }
">"          { yylval = GT; return (RELOP); }
">="     { yylval = GE; return (RELOP); }

.           { yylval = ERRORCHAR; return ERRORCHAR; }
    /* .匹配除换行符以外的任何字符，一般可作为最后一条翻译规则 */

%%
/* 第三部分是辅助函数部分，这部分内容个以及前面的%%都可以省略。
 * 辅助函数可以定义“动作”中使用的一些函数。这些函数使用C语言编写，
 * 并会被直接拷贝到lex.yy.c中。
 */
int installID()
{
    /* 把词法单元装入符号表并返回指针 */
    return ID;
}

int installNum()
{
    return NUMBER;
}

/* yywrap这个辅助函数是词法分析器遇到输入文件结尾时会调用的，用来
 * 决定下一步怎么做：若yywrap返回0，则继续扫描；返回1，则词法分析
 * 器返回报告文件已结束的0。
 * lex库中的标准yywrap程序就是返回1，你也可以定义自己的yywrap。
 */
int yywrap()
{
    return 1;
}

void writeout(int c)
{
    switch(c)
    {
        case ERRORCHAR: 
            fprintf(yyout, "(ERRORCHAR, "%s") ", yytext);
            break;
        case RELOP: 
            fprintf(yyout, "(RELOP, "%s") ", yytext);
            break;    
        case WHILE:
            fprintf(yyout, "(WHILE, "%s") ", yytext);
            break;
        case DO: 
            fprintf(yyout, "(DO, "%s") ", yytext);
            break;
        case NUMBER: 
            fprintf(yyout, "(NUM, "%s") ", yytext);
            break;
        case ID: 
            fprintf(yyout, "(ID, "%s") ", yytext);
            break;
        case NEWLINE: 
            fprintf(yyout, "n");
            break;

        default:
            break;
    }

    return;
}

/* 如果你的词法分析器并不是作为语法分析器的子程序，而是有自己的输入
 * 输出，你可以在这里定义你的词法分析器的main函数，main函数里可以调
 * 用yylex().
 */
int main(int argc, char **argv)
{
    int c, j = 0;
    if (argc >= 2)
    {
        if ((yyin = fopen(argv[1], "r")) == NULL)
        {
            printf("can not open file %sn", argv[1]);
            return 1;
        }

        if (argc >= 3)
        {
            yyout = fopen(argv[2], "w");
        }
    }

    while (c = yylex())
    {
        writeout(c);
        j++;

        if (j%5 == 0)
            writeout(NEWLINE);
    }

    if (argc >= 2)
    {
        fclose(yyin);
        if (argc >= 3)
            fclose(yyout);

    }

    return 0;
}

exam2.l：

%{

#include <stdio.h>
#define LT                  1
#define LE                  2
#define GT                  3
#define GE                  4
#define EQ                  5
#define NE                  6
#define LLK                 7
#define RLK                 8
#define LBK                 9
#define RBK                 10
#define IF                  11
#define ELSE                12
#define EQU                 13
#define SEM                 14

#define WHILE               18
#define DO                  19
#define ID                  20
#define NUMBER              21
#define RELOP               22

#define NEWLINE             23
#define ERRORCHAR           24
#define ADD                 25
#define  DEC                26
#define  MUL                27
#define  DIV                28

%}

delim       [ t n]
ws          {delim}+
letter      [A-Za-z]
digit       [0-9]
id          {letter}({letter}|{digit})*
number      {digit}+(.{digit}+)?(E[+-]?{digit}+)?

%s COMMENT
%s COMMENT2

%%

<INITIAL>"/*"           {BEGIN COMMENT;}
<COMMENT>"*/"           {BEGIN INITIAL;}
<COMMENT>.|n            {;}
<INITIAL>"//"           {BEGIN COMMENT2;}
<COMMENT2>n             {BEGIN INITIAL;}
<COMMENT2>.                 {;}

<INITIAL>{ws}           {;}
<INITIAL>while              {return (WHILE);}
<INITIAL>do                 {return (DO);}
<INITIAL>if                 {return (IF);}
<INITIAL>else           {return (ELSE);}
<INITIAL>{id}           {return (ID);}
<INITIAL>{number}       {return (NUMBER);}
<INITIAL>"<"             {return (RELOP);}
<INITIAL>"<="            {return (RELOP);}
<INITIAL>"="            {return (RELOP);}
<INITIAL>"!="           {return (RELOP);}
<INITIAL>">"             {return (RELOP);}
<INITIAL>">="            {return (RELOP);}
<INITIAL>"("            {return (RELOP);}
<INITIAL>")"            {return (RELOP);}
<INITIAL>"{"            {return (RELOP);}
<INITIAL>"}"            {return (RELOP);}
<INITIAL>"+"            {return (RELOP);}
<INITIAL>"-"            {return (RELOP);}
<INITIAL>"*"            {return (RELOP);}
<INITIAL>"/"            {return (RELOP);}
<INITIAL>";"            {return (RELOP);}

<INITIAL>.                  {return ERRORCHAR;}

%%

int yywrap()
{
    return 1;
}

void writeout(int c)
{
    switch(c)
    {
        case ERRORCHAR: 
            fprintf(yyout, "(ERRORCHAR, "%s") ", yytext);
            break;
        case RELOP: 
            fprintf(yyout, "(RELOP, "%s") ", yytext);
            break;    
        case WHILE: 
            fprintf(yyout, "(WHILE, "%s") ", yytext);
            break;
        case DO: 
            fprintf(yyout, "(DO, "%s") ", yytext);
            break;
        case IF: 
            fprintf(yyout, "(IF, "%s") ", yytext);
            break;
        case ELSE: 
            fprintf(yyout, "(ELSE, "%s") ", yytext);
            break;
        case NUMBER: fprintf(yyout, "(NUM, "%s") ", yytext);
            break;
        case ID: 
            fprintf(yyout, "(ID, "%s") ", yytext);
            break;
        case NEWLINE: 
            fprintf(yyout, "n");
            break;

        default:
            break;

    }
    return;
}

int main (int argc, char ** argv)
{
    int c,j=0;
    if (argc>=2)
    {
        if ((yyin = fopen(argv[1], "r")) == NULL)
        {
            printf("Can't open file %sn", argv[1]);
                return 1;
        }

        if (argc>=3)
        {
            yyout=fopen(argv[2], "w");
        }
    }

    while (c = yylex())
    {
        writeout(c);
        j++;

        if (j%5 == 0) 
            writeout(NEWLINE);
                            }
        if(argc>=2)
        {
            fclose(yyin);
            if (argc>=3) 
                fclose(yyout);
        }
        return 0;
}

使用lex/flex和gcc工具编译：

flex exam1.l   // 会生成lex.yy.c
gcc lex.yy.c -o exam1 -ll  // 可以去掉后面链接lex库的操作(-ll)，因为我们自己定义了yywrap()函数

flex exam2.l
gcc lex.yy.c -o exam2

下面分别是两组测试数据：

test1.sample：

while a >= -1.2E-2
do b<=2

test2.sample：

while a >= -1.2E-2
do b <= 2
if else
+
-
*
/
;   //的发生过
/* 请注意：测试文件的格式必须符合要求，比如文件格式必须是UNIX格式 */

测试结果如下：

allan@NYC:~/test/lex_yacc$ ./exam1 < test1.sample 
(WHILE, "while") (ID, "a") (RELOP, ">=") (NUM, "-1.2E-2") (DO, "do") 
(ID, "b") (RELOP, "<=") (NUM, "2") allan@NYC:~/test/lex_yacc$ 
allan@NYC:~/test/lex_yacc$ 
allan@NYC:~/test/lex_yacc$ ./exam2 < test2.sample 
(WHILE, "while") (ID, "a") (RELOP, ">=") (RELOP, "-") (NUM, "1.2E-2") 
(DO, "do") (ID, "b") (RELOP, "<=") (NUM, "2") (IF, "if") 
(ELSE, "else") (RELOP, "+") (RELOP, "-") (RELOP, "*") (RELOP, "/") 

本文整理自网络。