[0123456789]+

為了簡化書寫起見，也可以寫成如下的格式：

[0-9]+

對于任意單詞，其中只能包含字母，所以單詞的正則表達式為：

[a-zA-Z]+

Flex支持如下類型的正則表達式：

x          符合字符串"x"
.          除了換行以外的任何字符
[xyz]      一個字符類，在這個例子中，輸入必須符合要么是'x’要么是'y'要么是'z'
[abj-oZ]   一個帶范圍的字符類，符合任何滿足'a', 'b', 從'j'到'o'還有'Z'
[^A-Z]     一個取反的字符類，比如任何字母除了大寫字母。 
[^A-Z\n]   任何字符除了大寫字母和換行
r*         零個或更多r，r可以是任意正則表達式
r+         一個或更多r
r?         零個或最多一個r
r{2,5}     任何2到5個r
r{2,}      2個或更多r
r{4}       正好4個r
{name}     對name的擴展
"[xyz]\"foo"
           符合正則表達式 [xyz]"foo 的字符串
\X         如果X是一個'a', 'b', 'f', 'n', 'r', 't', 或者'v',
             則按照ASCII碼\x轉(zhuǎn)義符進行處理，否則，其他的'X'將用來做取消處理符處理
\0         一個ASCII碼空字符
\123       內(nèi)容為八進制123的char型
\x2a       內(nèi)容為十六進制0x2a的char型
(r)        符合一個r，括號是用來越過優(yōu)先級的
rs         正則表達式r，緊跟著一個
r|s        要么是r要么是s
^r         一個r，但是必須是在一行的開始
r$         一個r，但是必須是在行末
<s>r       一個r，但是之前字符串必須符合條件s
<s1,s2,s3>r
           同上，但是必須之前字符串符合s1或者s2或者s3
<*>r       不考慮開始字符串類型，只符合r
<<EOF>>    文件末尾
<s1,s2><<EOF>>
           前面符合s1或者s2的文件末尾

Flex甚至Bison代碼都有如下的編寫格式：

/* 定義段 */
%%
/* Flex、Bison代碼段（規(guī)則） */
%%
/* 輔助代碼段，C語言 */

首先，使用vi編譯器，輸入以下代碼（test.l）:

// 定義段代碼
%{                                  // 這種括號說明內(nèi)部的代碼不許flex處理，直接進入.C文件
#include <stdio.h>
%}
%%
// 詞法規(guī)則段代碼
[0123456789]+    printf("NUMBER");  // 數(shù)字類型字符串
[a-zA-Z]+        {
                   printf("WO");    // 單詞類型字符串（WORD）
                   printf("RD");
                 }
%%
// 輔助C語言函數(shù)代碼（直接寫C語言，無須括號，我們這里無內(nèi)容）

下面我們首先使用lex程序生成所需的狀態(tài)機代碼：

flex -otest.c test.l    # 從正則表達式聲稱對應的C語言代碼，注意-o后不要有空格（flex bug？）
gcc test.c -o test -lfl # 從C語言代碼生成二進制，從而運行，-lfl說明鏈接libfl.a庫文件
./test                  # 運行剛剛生成的二進制

下面我們來對剛生成的二進制進行試驗，以弄清楚flex到底是做什么的，在test程序中輸入 以下內(nèi)容，按下Ctrl-D可以退出test程序：

3505
hello
what is 3505

通過這些試驗，相信您已經(jīng)明白了Flex的用途，每當一個正則表達式符合時，flex生成的代 碼就會自動調(diào)用對應的函數(shù)，或者運行對應的程序。下面我們對這個例子進行一些深入研究，處理一個類似C語言的程序配置腳本代碼。首先，一個演示腳本如下：

logging {
    category lame-servers { null; };
    category cname { null; };
};
zone "." {
    type hint;
    file "/etc/bind/db.root";
}

在這個腳本中，我們可以看到一系列的詞匯類型：

• 單詞(WORD)，比如'zone', 'type'
• 文件名(FILENAME)，比如'/etc/bind/db.root'
• 引號(QUOTE)，比如文件名兩邊的
• 左花括號(OBRACE)，'{'
• 右花括號(EBRACE)，'}'
• 分號(SEMICOLON)，';'

%{
#include <stdio.h>
%}
%%
[a-zA-Z][a-zA-Z0-9]*  printf("WORD ");       /* 字符串 */
[a-zA-Z0-9\/.-]+      printf("FILENAME ");   /* 文件名 */
\"                    printf("QUOTE ");      /* 引號" */
\{                    printf("OBRACE ");     /* 左花括號 */
\}                    printf("EBRACE ");     /* 右花括號 */
;                     printf("SEMICOLON ");  /* 分號 */
\n                    printf("\n");          /* 換行 */
[ \t]+                /* 忽略空白字符 */
%%
int yywrap(void)      /* 當詞法分析器到了文件末尾做什么 */
{
        return 1;     /* 返回1，說明停止前進，0則繼續(xù) */
}

int yyerror(char *s) /* 錯誤信息打印函數(shù) */
{
        fprintf(stderr, "%s\n", s);
        return 0;
}

int main(int argc, char *argv[])
{
        FILE *fp;
        fp = fopen(argv[1], "r"); /* 首先打開要被處理的文件（參數(shù)1） */

        yyin = fp;                /* yyin是lex默認的文件輸入指針，則不處理控制臺輸入 */

        yylex();                  /* 調(diào)用lex的工作函數(shù)，從這里開始，lex的詞法分析器開始工作 */

        fclose(fp);
        return 0;
}

到這里，我們已經(jīng)完全可以對一個包含各種類型詞組的源代碼文件進行分析，得出其中各類型詞組的 排列順序。在一個規(guī)范的基于語法的源代碼中，詞組的順序從一定意義上來說，就是語法。對于源代碼，lex的處理能力也就到這里為止，但是我們并沒有完全展 示lex的所有功能，讀者如果有興趣，可以繼續(xù)深入閱讀本文提供的參考文獻。如何進行語法分析？我們在下面的章節(jié)中講開始講述Bison的基本使用方法， 以及如何使用Bison進行語法分析。

E : E '+' E
E : E '*' E
E : id

在這三句中，E在Bison語言中代表表達式，一個表達式可以是一個數(shù)字，也可以是一個變量名 稱，也可以是幾個變量名稱的組合，比如：

1
1+2
a
a+b*c

而以上三句Bison語言就能夠表達這些語法結(jié)構(gòu)。

/* 計算器的詞法分析器描述，F(xiàn)lex語言 */
%{                        /* 直接翻譯為C語言 */
#include <stdlib.h>       /* 包含標準庫文件 */
int yyerror(char *);      /* 這是我們上面用到的錯誤報告函數(shù) */
#include "test2yy.h"      /* 這個頭文件由Bison自動生成 */
%}
%%
[0-9]+    {
              yylval = atoi(yytext);    /* yytext是flex內(nèi)部用于指向當前詞匯的字符串指針 */
              return INTEGER;           /* INTEGER是從test2yy.h中包含過來的，在Bison中定義 */
          }
[-+\n]    return *yytext;
[ \t]     ; /* 跳過空白字符 */
.         yyerror("invalid character"); /* 產(chǎn)生一個錯誤，說明是無效字符 */
%%
int yywrap(void)
{
    return 1;                           /* 文件結(jié)束時退出 */
}

編譯過程：

flex -otest2ll.c test2ll.l
bison -otest2yy.c test2yy.y -d      # 注意-d，用于產(chǎn)生對應的頭文件
gcc test2yy.c test2ll.c -o test2

在這個例子中，我們遇到了許多沒有見過的用法，Bison的書寫格式基本與Flex的相同，只 是規(guī)則的定義語法不同。其中，$N（N為數(shù)字）代表語法描述中，第N個詞匯的內(nèi)容，比如(1)中的$1代表'+'左邊的expr，$3代表右邊expr的 內(nèi)容，其中的N是指當前語法的詞匯順序，從1開始計數(shù)。而$$則代表這一段語法處理完后的結(jié)果，每一個語法對應的處理都有輸入$N和輸出$$。 該例子中還有一個特殊的地方，就是第歸調(diào)用，在Bison中，語法規(guī)則可以是第歸的，這也是Bison之處（或者說是YACC的強大之處）。舉個例子：

program:
        program expr '\n'    { printf("%d\n", $2); }
        |
        ;

這里，program的定義就是任何符合program的表達式后面緊接著expr和 '\n'，掃描到該表達式后，將expr處理的結(jié)果打印到屏幕。最后的|是“或者”的意思，也就是說program也可以是空的，什么都不寫，分號代表該 語義定義結(jié)束。 有了第歸之后，Bison才可以說是一個能夠應對任何狀況的語法分析器，當然，這里還需要讀者對以上所提供代碼進行深入的研究和分析，考慮清楚后，會發(fā)現(xiàn) 無論是C語言，還是Bison，第歸永遠是一個神奇的解決方案。

1. 變量定義
2. 變量賦值
3. 變量與數(shù)字立即處理

輸入：3 * (4 + 5)
結(jié)果：27
輸入：x = 3 * (4 + 5)
輸入：y = 5
輸入：x
結(jié)果：27
輸入：y
結(jié)果：5
輸入：x + 2 * y
結(jié)果：37

這樣看，這個計算器的功能已經(jīng)相當強大了，下面我們著手實現(xiàn)，首先修改上面例子的Flex文件 為如下：

%{
    #include <stdlib.h>
    int yyerror(char *);
    #include "test2yy.h"
%}
%%
[a-z]        {                            /* 變量類型詞匯，限制：變量只能用一個字符 */
                 yylval = *yytext - 'a';
                 return VARIABLE;
             }
[0-9]+       {                            /* 整數(shù) */
                 yylval = atoi(yytext);
                 return INTEGER;
             }
[-+()=/*\n]  { return *yytext; }          /* 數(shù)學計算符號 */
[ \t]        ;                            /* 跳過空白符號 */
%%
int yywrap(void)
{
    return 1;
}

下面是我們新的Bison文件：

%token INTEGER VARIABLE
%left '+' '-'
%left '*' '/'
%{
    #include <stdio.h>
    int yyerror(char *);
    int yylex(void);
    int sym[26]；
%}
%%
program:
    program statement '\n'
    |
    ;
statement:
    expr                       { printf("%d\n", $1); }
    | VARIABLE '=' expr        { sym[$1] = $3; }
    ;
expr:
    INTEGER
    | VARIABLE                 { $$ = sym[$1]; }
    | expr '+' expr            { $$ = $1 + $3; }
    | expr '-' expr            { $$ = $1 - $3; }
    | expr '*' expr            { $$ = $1 * $3; }
    | expr '/' expr            { $$ = $1 / $3; }
    | '(' expr ')'             { $$ = $2; }
    ;
%%
int yyerror(char *s)
{
    fprintf(stderr, "%s\n", s);
    return 0;
}
int main(void)
{
    yyparse();
    return 0;
}

現(xiàn)在我們對該例子中引入的新功能介紹，%left，%right，%token都是用來聲明詞 匯的，區(qū)別在于，%token聲明的詞匯與左右優(yōu)先級無關(guān)，而%left的處理時，先處理左邊的，%right先處理右邊的，例如遇到字符串"1 - 2 - 5"，到底是處理為"(1 - 2) - 5"，還是處理為"1 - (2 - 5)"？%left處理為前者，而%right處理為后者（注：第一個計算器代碼中就有這個缺陷，比如執(zhí)行1-2+3，得到的結(jié)果就是-4，作為一個練 習，讀者可以使用這里講解的%left自行更正）。

x = 0;
while(x < 3) {
    print(x);
    x = x + 1;
}

例子中得到的輸出結(jié)果如下：

0
1
2

首先是我們的全局頭文件test3.h：

typedef enum {
        typeCon,
        typeId,
        typeOpr
} nodeEnum;

/* constants */
typedef struct {
        int value;      /* value of constant */
} conNodeType;

/* identifiers */
typedef struct {
        int i;          /* subscript to sym array */
} idNodeType;

/* operators */
typedef struct {
        int oper;       /* operator */
        int nops;       /* number of operands */
        struct nodeTypeTag *op[1];      /* operands (expandable) */
} oprNodeType;

typedef struct nodeTypeTag {
        nodeEnum type;  /* type of node */

        /* union must be last entry in nodeType */
        /* because operNodeType may dynamically increase */
        union {
                conNodeType con;        /* constants */
                idNodeType id;          /* identifiers */
                oprNodeType opr;        /* operators */
        };
} nodeType;

extern int sym[26];

下面是Flex語言文件test3ll.l：

%{
#include <stdlib.h>
#include "test3.h"
#include "test3yy.h"
int yyerror(char *);
%}

%%

[a-z]           {
                        yylval.sIndex = *yytext - 'a';
                        return VARIABLE;
                }

[0-9]+          {
                        yylval.iValue = atoi(yytext);
                        return INTEGER;
                }

[-()<>=+*/;{}.] {
                        return *yytext;
                }

">="            return GE;
"<="            return LE;
"=="            return EQ;
"!="            return NE;
"while"         return WHILE;
"if"            return IF;
"else"          return ELSE;
"print"         return PRINT;

[ \t\n]+        ;       /* ignore whitespace */
.               yyerror("Unknown character");

%%

int yywrap(void)
{
        return 1;
}

然后是我們的Bison文件test3yy.y：

%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "test3.h"

/* prototypes */
nodeType *opr(int oper, int nops, ...);
nodeType *id(int i);
nodeType *con(int value);
void freeNode(nodeType *p);
int yylex(void);

int yyerror(char *s);
int sym[26];
%}

%union {
        int iValue;     /* integer value */
        char sIndex;    /* symbol table index */
        nodeType *nPtr; /* node pointer */
};

%token <iValue> INTEGER
%token <sIndex> VARIABLE
%token WHILE IF PRINT
%nonassoc IFX
%nonassoc ELSE

%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%type <nPtr> stmt expr stmt_list

%%

program:
        function                        { exit(0); }
        ;

function:
        function stmt                   { ex($2); freeNode($2); }
        |
        ;

stmt:
        ';'                             { $$ = opr(';', 2, NULL, NULL); }
        | expr ';'                      { $$ = $1; }
        | PRINT expr ';'                { $$ = opr(PRINT, 1, $2); }
        | VARIABLE '=' expr ';'         { $$ = opr('=', 2, id($1), $3); }
        | WHILE '(' expr ')' stmt       { $$ = opr(WHILE, 2, $3, $5); }
        | IF '(' expr ')' stmt %prec IFX{ $$ = opr(IF, 2, $3, $5); }
        | IF '(' expr ')' stmt ELSE stmt{ $$ = opr(IF, 3, $3, $5, $7); }
        | '{' stmt_list '}'             { $$ = $2; }
        ;

stmt_list:
        stmt                            { $$ = $1; }
        | stmt_list stmt                { $$ = opr(';', 2, $1, $2); }
        ;

expr:
        INTEGER                         { $$ = con($1); }
        | VARIABLE                      { $$ = id($1); }
        | '-' expr %prec UMINUS         { $$ = opr(UMINUS, 1, $2); }
        | expr '+' expr                 { $$ = opr('+', 2, $1, $3); }
        | expr '-' expr                 { $$ = opr('-', 2, $1, $3); }
        | expr '*' expr                 { $$ = opr('*', 2, $1, $3); }
        | expr '/' expr                 { $$ = opr('/', 2, $1, $3); }
        | expr '<' expr                 { $$ = opr('<', 2, $1, $3); }
        | expr '>' expr                 { $$ = opr('>', 2, $1, $3); }
        | expr GE  expr                 { $$ = opr(GE , 2, $1, $3); }
        | expr LE  expr                 { $$ = opr(LE , 2, $1, $3); }
        | expr NE  expr                 { $$ = opr(NE , 2, $1, $3); }
        | expr EQ  expr                 { $$ = opr(EQ , 2, $1, $3); }
        | '(' expr ')'                  { $$ = $2; }
        ;

%%

#define SIZEOF_NODETYPE ((char*)&p->con - (char*)p)

nodeType *con(int value) {
        nodeType *p;
        size_t nodeSize;

        /* allocate node */
        nodeSize = SIZEOF_NODETYPE + sizeof(conNodeType);
        if((p = malloc(nodeSize)) == NULL)
                yyerror("out of memory");

        /* copy information */
        p->type = typeCon;
        p->con.value = value;

        return p;
}

nodeType *id(int i) {
        nodeType *p;
        size_t nodeSize;

        /* allocate node */
        nodeSize = SIZEOF_NODETYPE + sizeof(idNodeType);
        if((p = malloc(nodeSize)) == NULL)
                yyerror("out of memory");

        /* copy information */
        p->type = typeId;
        p->id.i = i;

        return p;
}

nodeType *opr(int oper, int nops, ...) {
        va_list ap;
        nodeType *p;
        size_t nodeSize;
        int i;

        /* allocate node */
        nodeSize = SIZEOF_NODETYPE + sizeof(oprNodeType) +
                (nops - 1) * sizeof(nodeType*);
        if((p = malloc(nodeSize)) == NULL)
                yyerror("out of memory");

        /* copy information */
        p->type = typeOpr;
        p->opr.oper = oper;
        p->opr.nops = nops;
        va_start(ap, nops);
        for(i = 0; i < nops; i++)
                p->opr.op[i] = va_arg(ap, nodeType*);
        va_end(ap);
        return p;
}

void freeNode(nodeType *p) {
        int i;

        if(!p) return;
        if(p->type == typeOpr) {
                for(i=0; i<p->opr.nops; i++)
                        freeNode(p->opr.op[i]);
        }
        free(p);
}

int yyerror(char *s) {
        fprintf(stdout, "%s\n", s);
}

int main(void) {
        yyparse();
        return 0;
}

上面的Flex和Bison代碼所作的工作是根據(jù)語法建立語意描述樹結(jié)構(gòu)。延續(xù)我們上面計算器 的例子，我們寫出如何翻譯這些語言的實現(xiàn)部分（對生成的樹進行第歸分析）：

#include <stdio.h>
#include "test3.h"
#include "test3yy.h"

int ex(nodeType *p) {
        if(!p) return 0;
        switch(p->type) {
        case typeCon:
                return p->con.value;
        case typeId:
                return sym[p->id.i];
        case typeOpr:
                switch(p->opr.oper) {
                case WHILE:
                        while(ex(p->opr.op[0]))
                                ex(p->opr.op[1]);
                        return 0;
                case IF:
                        if(ex(p->opr.op[0]))
                                ex(p->opr.op[1]);
                        else if(p->opr.nops > 2)
                                ex(p->opr.op[2]);
                        return 0;
                case PRINT:
                        printf("%d\n", ex(p->opr.op[0]));
                        return 0;
                case ';':
                        ex(p->opr.op[0]);
                        return ex(p->opr.op[1]);
                case '=':
                        return sym[p->opr.op[0]->id.i] = ex(p->opr.op[1]);
                case UMINUS:
                        return -ex(p->opr.op[0]);
                case '+':
                        return ex(p->opr.op[0]) + ex(p->opr.op[1]);
                case '-':
                        return ex(p->opr.op[0]) - ex(p->opr.op[1]);
                case '*':
                        return ex(p->opr.op[0]) * ex(p->opr.op[1]);
                case '/':
                        return ex(p->opr.op[0]) / ex(p->opr.op[1]);
                case '<':
                        return ex(p->opr.op[0]) < ex(p->opr.op[1]);
                case '>':
                        return ex(p->opr.op[0]) > ex(p->opr.op[1]);
                case GE:
                        return ex(p->opr.op[0]) >= ex(p->opr.op[1]);
                case LE:
                        return ex(p->opr.op[0]) <= ex(p->opr.op[1]);
                case NE:
                        return ex(p->opr.op[0]) != ex(p->opr.op[1]);
                case EQ:
                        return ex(p->opr.op[0]) == ex(p->opr.op[1]);
                        
                }
        }
}

一般實際的編譯器都是以匯編代碼輸出的，所以我們在這里進行一些深入研究，得出了另一個版本的 ex函數(shù)實現(xiàn)，能夠?qū)崿F(xiàn)匯編代碼的輸出（compiler.c）：

#include <stdio.h>
#include "test3.h"
#include "test3yy.h"

static int lbl;

int ex(nodeType *p) {
        int lbl1, lbl2;

        if(!p) return 0;
        switch(p->type) {
        case typeCon:
                printf("\tpush\t%d\n", p->con.value);
                break;

        case typeId:
                printf("\tpush\t%c\n", p->id.i + 'a');
                break;

        case typeOpr:
                switch(p->opr.oper) {
                case WHILE:
                        printf("L%03d:\n", lbl1 = lbl++);
                        ex(p->opr.op[0]);
                        printf("\tjs\tL%03d\n", lbl2 = lbl++);
                        ex(p->opr.op[1]);
                        printf("\tjz\tL%03d\n", lbl1);
                        printf("L%03d:\n", lbl2);
                        break;

                case IF:
                        ex(p->opr.op[0]);
                        if(p->opr.nops > 2) {
                                /* if else */
                                printf("\tjs\tL%03d\n", lbl1 = lbl++);
                                ex(p->opr.op[1]);
                                printf("\tjmp\tL%03d\n", lbl2 = lbl++);
                                printf("L%03d:\n", lbl1);
                                ex(p->opr.op[2]);
                                printf("L%03d:\n", lbl2);
                        } else {
                                /* if */
                                printf("\tjs\tL%03d\n", lbl1 = lbl++);
                                ex(p->opr.op[1]);
                                printf("L%03d:\n", lbl1);
                        }
                        break;

                case PRINT:
                        ex(p->opr.op[0]);
                        printf("\tprint\n");
                        break;

                case '=':
                        ex(p->opr.op[1]);
                        printf("\tpop\t%c\n", p->opr.op[0]->id.i + 'a');
                        break;

                case UMINUS:
                        ex(p->opr.op[0]);
                        printf("\tneg\n");
                        break;

                default:
                        ex(p->opr.op[0]);
                        ex(p->opr.op[1]);
                        switch(p->opr.oper) {
                        case '+':       printf("\tadd\n"); break;
                        case '-':       printf("\tsub\n"); break;
                        case '*':       printf("\tmul\n"); break;
                        case '/':       printf("\tdiv\n"); break;
                        case '<':       printf("\tcompLT\n"); break;
                        case '>':       printf("\tcompGT\n"); break;
                        case GE:        printf("\tcompGE\n"); break;
                        case LE:        printf("\tcompLE\n"); break;
                        case NE:        printf("\tcompNE\n"); break;
                        case EQ:        printf("\tcompEQ\n"); break;
                        }
                }
        }
        return 0;
}

使用方法：取消interpreter.c的編譯，取而代之用compiler.c即可。關(guān)于 這個計算器的代碼分析，請等待后續(xù)，（未完待續(xù)）