FlexBison 使用教程

1、Flex & Bison 使用教程使用說明· 本文需要讀者對C語言有一定的了解作為基礎 · 本文中所涉及的例子可以用本站提供的全自動化Makefile一文中提供的Makefile進行編譯 · 讀者如果在Linux下，可以直接使用，Windows用戶需要Cygwin()環(huán)境 · 本文中的工具，需要用戶安裝flex和bison軟件包 1.介紹編譯器是軟件開發(fā)中的核心部件，其作用是其他任何軟件所不能取代的。編譯器在工作過程中，往往完成如下的任務： 1. 讀取源代碼并且獲得程序的結構描述 2. 分析程序結構，并且生成相應的目標代碼 在UNIX早期時代，編

2、寫一個編譯器是一件非常耗時的工作。人們?yōu)榱撕喕_發(fā)過程，開發(fā)了Lex和YACC程序來解決第一個任務，根據用戶描述的語言，生成能夠解決問題的C/C+語言代碼，供開發(fā)者使用。 1. 將源代碼文件分解為各種詞匯（Lex） 2. 找到這些詞匯的組成方式（YACC） GNU軟件協(xié)會開發(fā)了Flex和BISON，其功能與LEX和YACC基本兼容，并且在Lex和YACC提供的功能的基礎上進行了各種擴展。 2.Flex入門Lex能夠用來編寫那些輸入數據流（字符串）能夠用正則表達式描述的程序，它可以根據正則表達式的描述，將輸入數據流分類為各類詞匯，為后來的語法分析做準備。 2.1.正則表達式正則表達式是通過對各種

3、詞組類型所包含的字符類型的歸納，描述所需詞組組成格式的方法，比如下面的例子描述了所有數字類型的字符串，表明無論在何時起，只要有0-9字符出現，就進入該狀態(tài)，說明是字符，直到非0-9字符結束： 0123456789+為了簡化書寫起見，也可以寫成如下的格式： 0-9+對于任意單詞，其中只能包含字母，所以單詞的正則表達式為： a-zA-Z+Flex支持如下類型的正則表達式： x          符合字符串"x".          除了換行以外的任何字符xyz   &#

4、160;  一個字符類，在這個例子中，輸入必須符合要么是'x要么是'y'要么是'z'abj-oZ   一個帶范圍的字符類，符合任何滿足'a', 'b', 從'j'到'o'還有'Z'A-Z     一個取反的字符類，比如任何字母除了大寫字母。 A-Zn   任何字符除了大寫字母和換行r*         零個或更多r，r可以是任意正則表達式r+       &

5、#160; 一個或更多rr?         零個或最多一個rr2,5     任何2到5個rr2,      2個或更多rr4       正好4個rname     對name的擴展"xyz"foo"           符合正則表達式 xyz"foo 的字符串X         如果X是一個'a'

6、, 'b', 'f', 'n', 'r', 't', 或者'v',             則按照ASCII碼x轉義符進行處理，否則，其他的'X'將用來做取消處理符處理0         一個ASCII碼空字符123       內容為八進制123的char型x2a       內容為十六進制0x2a的char型(r

7、)        符合一個r，括號是用來越過優(yōu)先級的rs         正則表達式r，緊跟著一個r|s        要么是r要么是sr         一個r，但是必須是在一行的開始r$         一個r，但是必須是在行末<s>r       一個r，但是之前字符串必須符合條件s<s1,s2,s3>r   

8、60;      同上，但是必須之前字符串符合s1或者s2或者s3<*>r       不考慮開始字符串類型，只符合r<<EOF>>    文件末尾<s1,s2><<EOF>>           前面符合s1或者s2的文件末尾2.2.第一個Lex代碼按照上一節(jié)我們講述的正則表達式例子，我們嘗試第一次使用Lex來產生我們所需要的程序，實踐一遍Lex的使用以及gcc編譯器如何編譯和生成所

9、需的二進制。 Flex甚至Bison代碼都有如下的編寫格式： /* 定義段 */%/* Flex、Bison代碼段（規(guī)則） */%/* 輔助代碼段，C語言 */首先，使用vi編譯器，輸入以下代碼（test.l）: / 定義段代碼%                                  / 這種括號說明內部的代碼不許flex處理，直接進入.C文件#include <stdio.h>%/ 詞法規(guī)則段代碼01

10、23456789+    printf("NUMBER");  / 數字類型字符串a-zA-Z+                           printf("WO");    / 單詞類型字符串（WORD）                   printf(&q

11、uot;RD");                 %/ 輔助C語言函數代碼（直接寫C語言，無須括號，我們這里無內容）下面我們首先使用lex程序生成所需的狀態(tài)機代碼： flex -otest.c test.l    # 從正則表達式聲稱對應的C語言代碼，注意-o后不要有空格（flex bug？）gcc test.c -o test -lfl # 從C語言代碼生成二進制，從而運行，-lfl說明鏈接libfl.a庫文件./test      

12、60;          # 運行剛剛生成的二進制下面我們來對剛生成的二進制進行試驗，以弄清楚flex到底是做什么的，在test程序中輸入以下內容，按下Ctrl-D可以退出test程序： 3505hellowhat is 3505通過這些試驗，相信您已經明白了Flex的用途，每當一個正則表達式符合時，flex生成的代碼就會自動調用對應的函數，或者運行對應的程序。下面我們對這個例子進行一些深入研究，處理一個類似C語言的程序配置腳本代碼。首先，一個演示腳本如下： logging     category lame-servers

13、 null; ;    category cname null; ;zone "."     type hint;    file "/etc/bind/db.root"在這個腳本中，我們可以看到一系列的詞匯類型： · 單詞(WORD)，比如'zone', 'type' · 文件名(FILENAME)，比如'/etc/bind/db.root' · 引號(QUOTE)，比如文件名兩邊的 · 左花括號(OBRA

14、CE)，'' · 右花括號(EBRACE)，'' · 分號(SEMICOLON)，'' 我們修改后的Lex代碼如下： %#include <stdio.h>%a-zA-Za-zA-Z0-9*  printf("WORD ");       /* 字符串 */a-zA-Z0-9/.-+      printf("FILENAME ");   /* 文件名 */"    

15、                printf("QUOTE ");      /* 引號" */                    printf("OBRACE ");     /* 左花括號 */                 &#

16、160;  printf("EBRACE ");     /* 右花括號 */;                     printf("SEMICOLON ");  /* 分號 */n                    printf("n");      

17、60;  /* 換行 */ t+                /* 忽略空白字符 */%int yywrap(void)      /* 當詞法分析器到了文件末尾做什么 */        return 1;     /* 返回1，說明停止前進，0則繼續(xù) */void yyerror(char *s) /* 錯誤信息打印函數 */        fprintf(stderr,

18、 "%sn", s);        return 0;int main(int argc, char *argv)        FILE *fp;        fp = fopen(argv1, "r"); /* 首先打開要被處理的文件（參數1） */        yyin = fp;              

19、60;/* yyin是lex默認的文件輸入指針，則不處理控制臺輸入 */        yylex();                  /* 調用lex的工作函數，從這里開始，lex的詞法分析器開始工作 */        fclose(fp);        return 0;到 這里，我們已經完全可以對一個包含各種類型詞組的源代碼文件進行分析，得出其中各類型詞組的排列順序。在一個

20、規(guī)范的基于語法的源代碼中，詞組的順序從一定 意義上來說，就是語法。對于源代碼，lex的處理能力也就到這里為止，但是我們并沒有完全展示lex的所有功能，讀者如果有興趣，可以繼續(xù)深入閱讀本文提 供的參考文獻。如何進行語法分析？我們在下面的章節(jié)中講開始講述Bison的基本使用方法，以及如何使用Bison進行語法分析。 3.Bison入門3.1.基礎理論Bison 采用與YACC相同的描述語言，這種語言是BNF語法(Backus Naur Form)的一種，最早被John Backus和Peter Naur用于ALGOL60語言的開發(fā)工作。BNF語法可以用來表達與內容無關的，基于語法的語言，幾乎所有的

21、現代編程語言都可以用BNF進行描述。作為 一個例子，一個進行加法和乘法的數學表達式語法可以如下表達： E : E '+' EE : E '*' EE : id在這三句中，E在Bison語言中代表表達式，一個表達式可以是一個數字，也可以是一個變量名稱，也可以是幾個變量名稱的組合，比如： 11+2aa+b*c而以上三句Bison語言就能夠表達這些語法結構。 3.2.Bison初探我們在下面作一個計算器，通過這個實例讓大家明白Flex和Bison的相互關系和如何共同工作。首先，建立test2ll.l文件，并輸入以下內容： /* 計算器的詞法分析器描述，Flex語言 *

22、/%                        /* 直接翻譯為C語言 */#include <stdlib.h>       /* 包含標準庫文件 */void yyerror(char *);     /* 這是我們上面用到的錯誤報告函數 */#include "test2yy.h"      /* 這個頭文件由Bison自動生成 */%0-9+  

23、;                yylval = atoi(yytext);    /* yytext是flex內部用于指向當前詞匯的字符串指針 */              return INTEGER;           /* INTEGER是從test2yy.h中包含過來的，在Bison中定義 */         

24、 -+n    return *yytext; t     ; /* 跳過空白字符 */.         yyerror("invalid character"); /* 產生一個錯誤，說明是無效字符 */%int yywrap(void)    return 1;                           /* 文件結束時退出 */以

25、 上就是計算器使用的Flex語言，描述了我們將會遇到的各種詞匯的格式，比如0-9+說明了，只有連續(xù)的從'0'到'9'的字符串，才被分析為 INTEGER類型，如果遇到制表符、空格等，直接忽略，遇到加減符號則返回字符指針，其它的則報告語法錯誤。下面是我們的Bison語法文件 test2yy.y： /* 注：您先抄寫，注解見下文 */%#include <stdio.h>int yylex(void);void yyerror(char *);%token INTEGER            

26、              /* Flex語言中INTEGER定義在此 */%program:        program expr 'n'     printf("%dn", $2);         |        ;expr:        INTEGER       &#

27、160;       $ = $1;         | expr '+' expr       $ = $1 + $3;  /* (1) */        | expr '-' expr       $ = $1 - $3;  /* (2) */        ;%void yyerror(char *s)   

28、 fprintf(stderr, "%sn", s);int main(void)    yyparse();    return 0;編譯過程： flex -otest2ll.c test2ll.lbison -otest2yy.c test2yy.y -d      # 注意-d，用于產生對應的頭文件gcc test2yy.c test2ll.c -o test2在 這個例子中，我們遇到了許多沒有見過的用法，Bison的書寫格式基本與Flex的相同，只是規(guī)則的定義語法不同。其中，$N（N為數字）代表語

29、法描述 中，第N個詞匯的內容，比如(1)中的$1代表'+'左邊的expr，$3代表右邊expr的內容，其中的N是指當前語法的詞匯順序，從1開始計數。 而$則代表這一段語法處理完后的結果，每一個語法對應的處理都有輸入$N和輸出$。 該例子中還有一個特殊的地方，就是第歸調用，在Bison中，語法規(guī)則可以是第歸的，這也是Bison之處（或者說是YACC的強大之處）。舉個例子： program:        program expr 'n'     printf("%dn", $2); &

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

31、究以上我們設計的計算器只能進行加減計算，并且里面還有一些軟件缺陷，對于一個實用的計算器來說，我們必須能夠支持： 1. 變量定義 2. 變量賦值 3. 變量與數字立即處理 于是我們假想設計出來的計算器能有如下的操作過程（輸入和輸出）： 輸入：3 * (4 + 5)結果：27輸入：x = 3 * (4 + 5)輸入：y = 5輸入：x結果：27輸入：y結果：5輸入：x + 2 * y結果：37這樣看，這個計算器的功能已經相當強大了，下面我們著手實現，首先修改上面例子的Flex文件為如下： %    #include <stdlib.h>    v

32、oid yyerror(char *);    #include "test2yy.h"%a-z                                    /* 變量類型詞匯，限制：變量只能用一個字符 */                 yylval = *yytext -

33、'a'                 return VARIABLE;             0-9+                                  /* 整數 */        

34、0;        yylval = atoi(yytext);                 return INTEGER;             +-()=/*n   return *yytext;          /* 數學計算符號 */ t            

35、                       /* 跳過空白符號 */%int yywrap(void)    return 1;下面是我們新的Bison文件： %token INTEGER VARIABLE%left '+' '-'%left '*' '/'%    void yyerror(char *);    int yylex(void);&#

36、160;   int sym26；%program:    program statement 'n'    |    ;statement:    expr                       printf("%dn", $1);     | VARIABLE '=' expr      

37、;   sym$1 = $3;     ;expr:    INTEGER    | VARIABLE                 $ = sym$1;     | expr '+' expr             $ = $1 + $3;     | expr '-' expr     &

38、#160;       $ = $1 - $3;     | expr '*' expr             $ = $1 * $3;     | expr '/' expr             $ = $1 / $3;     | '(' expr ')'         &

39、#160;   $ = $2;     ;%void yyerror(char *s)    fprintf(stderr, "%sn", s);    return 0;int main(void)    yyparse();    return 0;現 在我們對該例子中引入的新功能介紹，%left，%right，%token都是用來聲明詞匯的，區(qū)別在于，%token聲明的詞匯與左右優(yōu)先級無關， 而%left的處理時，先處理左邊的，%right先處理右邊的，例如遇

40、到字符串"1 - 2 - 5"，到底是處理為"(1 - 2) - 5"，還是處理為"1 - (2 - 5)"？%left處理為前者，而%right處理為后者（注：第一個計算器代碼中就有這個缺陷，比如執(zhí)行1-2+3，得到的結果就是-4，作為一個練 習，讀者可以使用這里講解的%left自行更正）。 4.Flex和Bison高級應用在下面的例子中，我們便寫了一個更高級的計算器程序，其操作實例如下： x = 0;while(x < 3)     print(x);    x = x + 1;例子中

41、得到的輸出結果如下： 012首先是我們的全局頭文件test3.h： typedef enum         typeCon,        typeId,        typeOpr nodeEnum;/* constants */typedef struct         int value;      /* value of constant */ conNodeType;/* identifie

42、rs */typedef struct         int i;          /* subscript to sym array */ idNodeType;/* operators */typedef struct         int oper;       /* operator */        int nops;       /* number

43、 of operands */        struct nodeTypeTag *op1;      /* operands (expandable) */ oprNodeType;typedef struct nodeTypeTag         nodeEnum type;  /* type of node */        /* union must be last entry in nodeType */  &

44、#160;     /* because operNodeType may dynamically increase */        union                 conNodeType con;        /* constants */                idNodeType id;   &#

45、160;      /* identifiers */                oprNodeType opr;        /* operators */        ; nodeType;extern int sym26;下面是Flex語言文件test3ll.l： %#include <stdlib.h>#include "test3.h"#include &q

46、uot;test3yy.h"void yyerror(char *);%a-z                                   yylval.sIndex = *yytext - 'a'                        return VARIABLE

47、;                0-9+                                  yylval.iValue = atoi(yytext);                        return

48、INTEGER;                -()<>=+*/;.                         return *yytext;                ">="            retu

49、rn GE;"<="            return LE;"="            return EQ;"!="            return NE;"while"         return WHILE;"if"      

50、      return IF;"else"          return ELSE;"print"         return PRINT; tn+               /* ignore whitespace */.               yyerror("Unkno

51、wn 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);v

52、oid freeNode(nodeType *p);int yylex(void);void yyerror(char *s);int sym26;%union         int iValue;     /* integer value */        char sIndex;    /* symbol table index */        nodeType *nPtr; /* node pointer */;%toke

53、n <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:        fu

54、nction                         exit(0);         ;function:        function stmt                   ex($2); freeNode($2);         | 

55、       ;stmt:        ''                             $ = opr('', 2, NULL, NULL);         | expr ''               

56、0;       $ = $1;         | PRINT expr ''                 $ = opr(PRINT, 1, $2);         | VARIABLE '=' expr ''         $ = opr('=', 2, id($1), $3);  

57、;       | WHILE '(' expr ')' stmt       $ = opr(WHILE, 2, $3, $5);         | IF '(' expr ')' stmt %prec IFX $ = opr(IF, 2, $3, $5);         | IF '(' expr ')' stmt ELSE stmt $ = opr(I

58、F, 3, $3, $5, $7);         | '' stmt_list ''             $ = $2;         ;stmt_list:        stmt                            

59、 $ = $1;         | stmt_list stmt                 $ = opr('', 2, $1, $2);         ;expr:        INTEGER                         $ =

60、con($1);         | VARIABLE                       $ = id($1);         | '-' expr %prec UMINUS         $ = opr(UMINUS, 1, $2);         | expr '+' expr

61、                 $ = opr('+', 2, $1, $3);         | expr '-' expr                 $ = opr('-', 2, $1, $3);         | expr '*' expr    

62、60;           $ = opr('*', 2, $1, $3);         | expr '/' expr                 $ = opr('/', 2, $1, $3);         | expr '<' expr         

63、0;       $ = opr('<', 2, $1, $3);         | expr '>' expr                 $ = opr('>', 2, $1, $3);         | expr GE  expr             &#

64、160;   $ = opr(GE , 2, $1, $3);         | expr LE  expr                 $ = opr(LE , 2, $1, $3);         | expr NE  expr                 $ = opr(NE , 2, $1, $3);

65、60;       | expr EQ  expr                 $ = opr(EQ , 2, $1, $3);         | '(' expr ')'                   $ = $2;         ;%#define SIZEO

66、F_NODETYPE (char*)&p->con - (char*)p)nodeType *con(int value)         nodeType *p;        size_t nodeSize;        /* allocate node */        nodeSize = SIZEOF_NODETYPE + sizeof(conNodeType);      &#

67、160; if(p = malloc(nodeSize) = NULL)                yyerror("out of memory");        /* copy information */        p->type = typeCon;        p->con.value = value;      &

68、#160; return p;nodeType *id(int i)         nodeType *p;        size_t nodeSize;        /* allocate node */        nodeSize = SIZEOF_NODETYPE + sizeof(idNodeType);        if(p = malloc(nodeSize) = NULL

69、)                yyerror("out of memory");        /* copy information */        p->type = typeId;        p->id.i = i;        return p;nodeType *opr(int oper, int no

70、ps, .)         va_list ap;        nodeType *p;        size_t nodeSize;        int i;        /* allocate node */        nodeSize = SIZEOF_NODETYPE + sizeof(oprNodeType) +  

71、0;             (nops - 1) * sizeof(nodeType*);        if(p = malloc(nodeSize) = NULL)                yyerror("out of memory");        /* copy information */     

72、60; p->type = typeOpr;        p->opr.oper = oper;        p->opr.nops = nops;        va_start(ap, nops);        for(i = 0; i < nops; i+)                p->opr.opi = v

73、a_arg(ap, nodeType*);        va_end(ap);        return p;void freeNode(nodeType *p)         int i;        if(!p) return;        if(p->type = typeOpr)              

74、;   for(i=0; i<p->opr.nops; i+)                        freeNode(p->opr.opi);                free(p);void yyerror(char *s)         fprintf(stdout, "%sn", s);

75、int main(void)         yyparse();        return 0;上面的Flex和Bison代碼所作的工作是根據語法建立語意描述樹結構。延續(xù)我們上面計算器的例子，我們寫出如何翻譯這些語言的實現部分（對生成的樹進行第歸分析）： #include <stdio.h>#include "test3.h"#include "test3yy.h"int ex(nodeType *p)        

76、if(!p) return 0;        switch(p->type)         case typeCon:                return p->con.value;        case typeId:                return symp->id.i;

77、        case typeOpr:                switch(p->opr.oper)                 case WHILE:                        while(ex(p->opr.op0) 

78、                               ex(p->opr.op1);                        return 0;                case IF:     

79、;                   if(ex(p->opr.op0)                                ex(p->opr.op1);                        e

80、lse if(p->opr.nops > 2)                                ex(p->opr.op2);                        return 0;             

81、   case PRINT:                        printf("%dn", ex(p->opr.op0);                        return 0;                case &

82、#39;':                        ex(p->opr.op0);                        return ex(p->opr.op1);                case '=': 

83、                       return symp->opr.op0->id.i = ex(p->opr.op1);                case UMINUS:                        return -ex(p->

84、opr.op0);                case '+':                        return ex(p->opr.op0) + ex(p->opr.op1);                case '-':    &#

85、160;                   return ex(p->opr.op0) - ex(p->opr.op1);                case '*':                        return ex(p->opr.op0) * ex(

86、p->opr.op1);                case '/':                        return ex(p->opr.op0) / ex(p->opr.op1);                case '<': 

87、                      return ex(p->opr.op0) < ex(p->opr.op1);                case '>':                        return ex(p->

88、;opr.op0) > ex(p->opr.op1);                case GE:                        return ex(p->opr.op0) >= ex(p->opr.op1);                case LE: 

89、                       return ex(p->opr.op0) <= ex(p->opr.op1);                case NE:                        return ex(p->opr.op0)

90、!= ex(p->opr.op1);                case EQ:                        return ex(p->opr.op0) = ex(p->opr.op1);                        &#

91、160;                       一般實際的編譯器都是以匯編代碼輸出的，所以我們在這里進行一些深入研究，得出了另一個版本的ex函數實現，能夠實現匯編代碼的輸出（compiler.c）： #include <stdio.h>#include "test3.h"#include "test3yy.h"static int lbl;int ex(nodeType *p)       

92、0; int lbl1, lbl2;        if(!p) return 0;        switch(p->type)         case typeCon:                printf("tpusht%dn", p->con.value);             

93、;   break;        case typeId:                printf("tpusht%cn", p->id.i + 'a');                break;        case typeOpr:        &#

94、160;       switch(p->opr.oper)                 case WHILE:                        printf("L%03d:n", lbl1 = lbl+);               

95、60;       ex(p->opr.op0);                        printf("tjstL%03dn", lbl2 = lbl+);                        ex(p->opr.op1);       

96、                 printf("tjztL%03dn", lbl1);                        printf("L%03d:n", lbl2);                        brea

97、k;                case IF:                        ex(p->opr.op0);                        if(p->opr.nops > 2)       &

98、#160;                         /* if else */                                printf("tjstL%03dn", lbl1 = lbl+);           

99、                     ex(p->opr.op1);                                printf("tjmptL%03dn", lbl2 = lbl+);               

100、;                 printf("L%03d:n", lbl1);                                ex(p->opr.op2);                                printf("L%03d:n", lbl2);                        else                             &#