從lex&yacc說到編譯器(二)flex的使用

[原創(chuàng)] tangl_99 2004-01-31 
--------------------------------------------------------------------------------
 
    看了第一篇的關于正則表達式的說明后，下面我們就來通過它，使用flex這個詞法治齬ぞ呃垂乖煳頤塹謀嘁肫韉拇史ǚ治銎鰲?
    關于lex的教程應該是很多，這里我就簡單地介紹一下，然后著重后面的lex和yacc的配合使用以及其技巧。所以，如果你不看了后還是不太明白lex或者yacc的使用，請你自己上網(wǎng)去查查，這方面的教程是很多的。我知道的一篇常見的就是
Yacc 與 Lex 快速入門
Lex 與 Yacc 介紹
它的作者就是Ashish Bansal。

    Flex就是fast lex的意思。而lex就是Lexical Analyzar的意思。flex可以在cygwin或者gnupro中找到。它是unix的一個工具，屬于GNU組織產(chǎn)品。網(wǎng)上也可以找到單獨可以在windows下用的版本。
    我們一般把我們的詞法掃描程序要掃描的一些單詞(token)用正則表達式寫好，然后作為lex的輸入文件，輸入命令flex xxx.l(xxx.l就是輸入文件)，lex經(jīng)過處理后，就能得到一個名字叫l(wèi)ex.yy.c的C源代碼。這個C源代碼文件，就是我們的詞法掃描程序。通常lex為我們生成的詞法分析器的C源代碼都是十分復雜而且龐大的，我們一般根本不會去查看里面的代碼(放心好了，flex這個東西不會出錯的)。

    下面讓我們看看幾個我已經(jīng)使用過的幾個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輸入文件一共有三個部分，用%%分開。第一部分中的%{和}%中的內(nèi)容就是直接放在lex輸出C代碼中的頂部。我們通過它可以來定義一些所需要的宏，函數(shù)和include一些頭文件等等。我的這個lex輸入文件中也沒什么特別的東西，就是常規(guī)的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的阿拉伯數(shù)字定義，第一篇文章中也舉了這個例子。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表示的話，那么按照上面的規(guī)則，那就會看成\和n兩個字符，所以我使用了[\n]。有些時候newline也被寫成[\n]|[\r\n]。因為在文本文件中，一般換行一次，那么就是一個\n(0xA)，可是在二進制文件中，換行有時候又是\r\n(0xD，0xA)一共兩個字符號。

    第二部分就是定義掃描到正則表達式的動作。
    這些動作其實就是C代碼，它們將會被鑲嵌在lex輸出的C文件中的yylex()函數(shù)中。
    上面的例子的動作其實十分平常，就是返回一個值。
    我們在外部使用這個lex為我們生成C代碼的時候，只需要使用它的int yylex()函數(shù)。當我們使用一次yylex()，那么就會自動去掃描一個匹配的正則表達式，然后完成它相應的動作。這里的動作都是返回一值，那么yylex就會返回這個值。通常默認yylex返回0時候，表示文件掃描結束，所以你的動作中最好不要返回0，以免發(fā)生沖突。當然，動作中也可以不返回一值，那么yylex就會完成這個動作后自動掃描下一個可以被匹配的字符串，一直到掃描到文件結束。
    當掃描到一個可以被匹配的字符串，那么這個時候，全局變量yytext就等于這個字符串

    請大家一定記住這些正則表達式的順序。
    如果出現(xiàn)一個字符串，可以同時匹配多個正則表達式，那么它將會被定義在前面的正則表達式匹配。所以我一般把字符串string定義在最前面。
    如果文件中的字符沒有被lex輸入文件中任何一個字符匹配，那么它會自動地被標準輸出。所以大家一定要記住在每個正則表達式處理完畢后，一定要加上{newline}和.這兩個正則表達式的動作。

    好，讓我們看看lex為我們輸出C文件中提供一些常量
Lex 變量
yyin FILE* 類型。它指向 lexer 正在解析的當前文件。 
yyout FILE* 類型。它指向記錄 lexer 輸出的位置。
缺省情況下，yyin 和 yyout 都指向標準輸入和輸出。 
yytext 匹配模式的文本存儲在這一變量中（char*）。 
yyleng 給出匹配模式的長度。 
yylineno 提供當前的行數(shù)信息。（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函數(shù)來代替yylex作為外部輸出函數(shù)。其中getToken里面也使用了lex默認的輸出函數(shù)yylex()，同時還做了一些其它的事情。不過我建議大家不要像作者那樣另外寫自己的結果輸出函數(shù)，因為在后面，需要和yacc搭配工作的時候，yacc生成的語法分析程序只認名字叫yylex()的詞法結果輸出函數(shù)。
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內(nèi)部函數(shù)input()一一檢查 { 后面的字符是不是 } 來跳過注釋文字。(C語言的/* */注釋文字正則表達式十分難寫，所以很多時候我們都用這種方法直接把它的DFA(掃描自動機)寫出來)。

    本文就是通過簡單地舉出兩個比較實際的例子來講解flex輸入文件的。再次說明，如果你是第一次接觸lex，那么請看看前面我推薦的文章，你可以在IBM的開發(fā)者網(wǎng)上查到。下一篇關于yacc于BNF文法的說明也是如此。請大家先參考一下其它標準的教程。