[e-mail]

从lex&yacc说到编译器(二)flex的使用

从lex&yacc说到编译器(二)flex的使用

[原创] tangl_99 2004-01-31 
--------------------------------------------------------------------------------
 
    看了第一篇的关于正则表达式的说明后，下面我们就来通过它，使用flex这个词法治龉ぞ呃垂乖煳颐堑谋嘁肫鞯拇史ǚ治銎鳌?
    关于lex的教程应该是很多，这里我就简单地介绍一下，然后着重后面的lex和yacc的配合使用以及其技巧。所以，如果你不看了后还是不太明白lex或者yacc的使用，请你自己上网去查查，这方面的教程是很多的。我知道的一篇常见的就是
Yacc 与 Lex 快速入门
Lex 与 Yacc 介绍
它的作者就是Ashish Bansal。

    Flex就是fast lex的意思。而lex就是Lexical Analyzar的意思。flex可以在cygwin或者gnupro中找到。它是unix的一个工具，属于GNU组织产品。网上也可以找到单独可以在windows下用的版本。
    我们一般把我们的词法扫描程序要扫描的一些单词(token)用正则表达式写好，然后作为lex的输入文件，输入命令flex xxx.l(xxx.l就是输入文件)，lex经过处理后，就能得到一个名字叫lex.yy.c的C源代码。这个C源代码文件，就是我们的词法扫描程序。通常lex为我们生成的词法分析器的C源代码都是十分复杂而且庞大的，我们一般根本不会去查看里面的代码(放心好了，flex这个东西不会出错的)。

    下面让我们看看几个我已经使用过的几个lex输入文件。
    这是一个前段时间我为GBA上的一个RPG游戏写的脚本引擎所使用的lex输入文件(部分)

例2.1
%{
/* need this for the call to atof() below */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "globals.h"

%}
digit        [0-9]
number       ("-"|"+")?{digit}+
hexnumber    "0x"({digit}|[a-fA-F])+
letter       [a-zA-Z]
identifier   ({letter}|_)({number}|{letter}|_)* 
newline      [\n]
whitespace   [ \t]+
string       \"[^">*\"
comment      "#"[^#]*"#"
%%

{string}        { return VM_STRING;           }
"Logo"          { return VMIN_LOGO;           }
"FaceIn"        { return VMIN_FACEIN;         }
"FaceOut"       { return VMIN_FACEOUT;        }
"LoadTile"      { return VMIN_LOAD_TILE;      }
"CreateRole"    { return VMIN_CREATE_ROLE;    }
"ReleaseRole"   { return VMIN_RELEASE_ROLE;   }
"CreateMap"     { return VMIN_CREATE_MAP;     }
"ReleaseMAP"    { return VMIN_RELEASE_MAP;    }
"ShowBitmap"    { return VMIN_SHOWBITMAP;     }
"CreateDialog"  { return VMIN_CREATE_DIALOG;  }
"ReleaseDialog" { return VMIN_RELEASE_DIALOG; }
"Fight"         { return VMIN_FIGHT;          }
"Delay"         { return VMIN_DELAY;          }
"PressA"        { return VMIN_PRESS_A;        }
"PressB"        { return VMIN_PRESS_B;        }
"PressR"        { return VMIN_PRESS_R;        }
"PressL"        { return VMIN_PRESS_L;        }
"PressStart"    { return VMIN_PRESS_START;    }
"PressSelect"   { return VMIN_PRESS_SELECT;   }
{number}        { return VM_NUMBER;           }
{whitespace}    { /* skip whitespace */       }
{identifier}    { return VM_ID;               }
{newline}    ;
.            ;
%%
int yywrap()
{
    return 1;
}

    这里的lex输入文件一共有三个部分，用%%分开。第一部分中的%{和}%中的内容就是直接放在lex输出C代码中的顶部。我们通过它可以来定义一些所需要的宏，函数和include一些头文件等等。我的这个lex输入文件中也没什么特别的东西，就是常规的C源文件的include头文件。
%{
/* need this for the call to atof() below */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "globals.h"
%}

    第一部分中，除了前面的%{和}%包含的部分，下面的就是正则表达式的定义。
    看了第一篇的正则表达式，这样你就能够在这里派上用场了。
    让我们来看看我这里定义的正则表达式:
digit        [0-9]
number       ("-"|"+")?{digit}+
hexnumber    "0x"({digit}|[a-fA-F])+
letter       [a-zA-Z]
identifier   ({letter}|_)({number}|{letter}|_)* 
newline      [\n]
whitespace   [ \t]+
string       \"[^">*\"
comment      "#"[^#]*"#"

    digit就不用说了，就是0-9的阿拉伯数字定义，第一篇文章中也举了这个例子。number就是digit的1到无限次的重复，再在其前面加上“+”和“-”符号。
    注意:

“a” : 即使a是元字符，它仍是字符a
\a    : 当a是元字符时候，为字符a
a?    : 一个可选的a，也就是说可以是a，也可以没有a
a|b   : a或b
(a)   : a本身
[abc] : 字符a，b或c中的任一个
[a-d] : a，b，d或者d中的任一个
[^ab] : 除了a或b外的任何一个字符
.     : 除了新行之外的任一个字符
{xxx} : 名字xxx表示的正则表达式

    这里需要特别说明的就是
newline      [\n]
    newline就是新行，这里我使用了[]把\n换行号括起来。因为如果我直接用\n表示的话，那么按照上面的规则，那就会看成\和n两个字符，所以我使用了[\n]。有些时候newline也被写成[\n]|[\r\n]。因为在文本文件中，一般换行一次，那么就是一个\n(0xA)，可是在二进制文件中，换行有时候又是\r\n(0xD，0xA)一共两个字符号。

    第二部分就是定义扫描到正则表达式的动作。
    这些动作其实就是C代码，它们将会被镶嵌在lex输出的C文件中的yylex()函数中。
    上面的例子的动作其实十分平常，就是返回一个值。
    我们在外部使用这个lex为我们生成C代码的时候，只需要使用它的int yylex()函数。当我们使用一次yylex()，那么就会自动去扫描一个匹配的正则表达式，然后完成它相应的动作。这里的动作都是返回一值，那么yylex就会返回这个值。通常默认yylex返回0时候，表示文件扫描结束，所以你的动作中最好不要返回0，以免发生冲突。当然，动作中也可以不返回一值，那么yylex就会完成这个动作后自动扫描下一个可以被匹配的字符串，一直到扫描到文件结束。
    当扫描到一个可以被匹配的字符串，那么这个时候，全局变量yytext就等于这个字符串

    请大家一定记住这些正则表达式的顺序。
    如果出现一个字符串，可以同时匹配多个正则表达式，那么它将会被定义在前面的正则表达式匹配。所以我一般把字符串string定义在最前面。
    如果文件中的字符没有被lex输入文件中任何一个字符匹配，那么它会自动地被标准输出。所以大家一定要记住在每个正则表达式处理完毕后，一定要加上{newline}和.这两个正则表达式的动作。

    好，让我们看看lex为我们输出C文件中提供一些常量
Lex 变量
yyin FILE* 类型。它指向 lexer 正在解析的当前文件。 
yyout FILE* 类型。它指向记录 lexer 输出的位置。
缺省情况下，yyin 和 yyout 都指向标准输入和输出。 
yytext 匹配模式的文本存储在这一变量中（char*）。 
yyleng 给出匹配模式的长度。 
yylineno 提供当前的行数信息。（lexer不一定支持。） 


例2.2
    这是《编译原理与实践》书中配套的源代码的lex输入文件。大家可以参考一下，作者为它自己定义的一个Tiny C编译所做的词法扫描器。
/****************************************************/
/* File: tiny.l                                     */
/* Lex specification for TINY                       */
/* Compiler Construction: Principles and Practice   */
/* Kenneth C. Louden                                */
/****************************************************/

%{
#include "globals.h"
#include "util.h"
#include "scan.h"
/* lexeme of identifier or reserved word */
char tokenString[MAXTOKENLEN+1];
%}

digit       [0-9]
number      {digit}+
letter      [a-zA-Z]
identifier  {letter}+
newline     \n
whitespace  [ \t]+

%%

"if"            {return IF;}
"then"          {return THEN;}
"else"          {return ELSE;}
"end"           {return END;}
"repeat"        {return REPEAT;}
"until"         {return UNTIL;}
"read"          {return READ;}
"write"         {return WRITE;}
":="            {return ASSIGN;}
"="             {return EQ;}
"<"            {return LT;}
"+"             {return PLUS;}
"-"             {return MINUS;}
"*"             {return TIMES;}
"/"             {return OVER;}
"("             {return LPAREN;}
")"             {return RPAREN;}
";"             {return SEMI;}
{number}        {return NUM;}
{identifier}    {return ID;}
{newline}       {lineno++;}
{whitespace}    {/* skip whitespace */}
"{"             { char c;
                  do
                  { c = input();
                    if (c == EOF) break;
                    if (c == '\n') lineno++;
                  } while (c != '}');
                }
.               {return ERROR;}

%%

TokenType getToken(void) {
    static int firstTime = TRUE;
    TokenType currentToken;
    if (firstTime) {
        firstTime = FALSE;
        lineno++;
        yyin = source;
        yyout = listing;
    }
    currentToken = yylex();
    strncpy(tokenString，yytext，MAXTOKENLEN);
    if (TraceScan) {
        fprintf(listing，"\t%d: "，lineno);
        printToken(currentToken，tokenString);
    }
    return currentToken;
}

    这里有点不同的就是，作者用了另外一个getToken函数来代替yylex作为外部输出函数。其中getToken里面也使用了lex默认的输出函数yylex()，同时还做了一些其它的事情。不过我建议大家不要像作者那样另外写自己的结果输出函数，因为在后面，需要和yacc搭配工作的时候，yacc生成的语法分析程序只认名字叫yylex()的词法结果输出函数。
if (firstTime) {
    firstTime = FALSE;
    lineno++;
    yyin = source;
    yyout = listing;
}
    其中的yyin，yyout，source，listing都是FILE*类型。yyin就是要lex生成的词法扫描程序要扫描的文件，yyout就是基本输出文件(其实我们通常都不用yyout，即使要生成一些输出信息，我们都是自己通过fprintf来输出)。
"{"             { char c;
                  do
                  { c = input();
                    if (c == EOF) break;
                    if (c == '\n') lineno++;
                  } while (c != '}');
                }
    其中，作者的这个Tiny C是以{}来包括注释信息。作者并没有写出注释信息的正则表达式，但是它可以通过检索“{”，然后用lex内部函数input()一一检查 { 后面的字符是不是 } 来跳过注释文字。(C语言的/* */注释文字正则表达式十分难写，所以很多时候我们都用这种方法直接把它的DFA(扫描自动机)写出来)。

    本文就是通过简单地举出两个比较实际的例子来讲解flex输入文件的。再次说明，如果你是第一次接触lex，那么请看看前面我推荐的文章，你可以在IBM的开发者网上查到。下一篇关于yacc于BNF文法的说明也是如此。请大家先参考一下其它标准的教程。