一個Lex/Yacc完整的示例(可使用C++)

relipmoc

完整代碼下載頁面：http://blog.csdn.net/huyansoft/article/details/8860224
本框架是一個lex/yacc完整的示例，包括詳細的注釋，用于學(xué)習(xí)lex/yacc程序基本的搭建方法，在linux/cygwin下敲入make就可以編譯和執(zhí)行。大部分框架已經(jīng)搭好了，你只要稍加擴展就可以成為一個計算器之類的程序，用于《編譯原理》的課程設(shè)計，或者對照理解其它lex/yacc項目的代碼。

本例子演示了lex/yacc程序最重要和常用的特征：

1. * lex/yacc程序組成結(jié)構(gòu)、文件格式。
   
2. * 如何在lex/yacc中使用C++和STL庫，用extern "C"聲明那些lex/yacc生成的、要鏈接的C函數(shù)，如yylex(), yywrap(), yyerror()。
   
3. * 重定義YYSTYPE/yylval為復(fù)雜類型。
   
4. * lex里多狀態(tài)的定義和使用，用BEGIN宏在初始態(tài)和其它狀態(tài)間切換。
   
5. * lex里正則表達式的定義、識別方式。
   
6. * lex里用yylval向yacc返回數(shù)據(jù)。
   
7. * yacc里用%token<>方式聲明yacc記號。
   
8. * yacc里用%type<>方式聲明非終結(jié)符的類型。
   
9. * 在yacc嵌入的C代碼動作里，對記號屬性($1, $2等)、和非終結(jié)符屬性($$)的正確引用方法。
   
10. * 對yyin/yyout重賦值，以改變yacc默認的輸入/輸出目標(biāo)。

復(fù)制代碼

本例子功能是，對當(dāng)前目錄下的file.txt文件，解析出其中的標(biāo)識符、數(shù)字、其它符號，顯示在屏幕上。linux調(diào)試環(huán)境是Ubuntu 10.04。

文件列表：

1. lex.l:                lex程序文件。
   
2. yacc.y:                yacc程序文件。
   
3. main.h:                lex.l和yacc.y共同使用的頭文件。
   
4. Makefile:                makefile文件。
   
5. lex.yy.c:                用lex編譯lex.l后生成的C文件。
   
6. yacc.tab.c:        用yacc編譯yacc.y后生成的C文件。
   
7. yacc.tab.h:        用yacc編譯yacc.y后生成的C頭文件，內(nèi)含%token、YYSTYPE、yylval等定義，供lex.yy.c和yacc.tab.c使用。
   
8. file.txt:                被解析的文本示例。
   
9. README.txt:        本說明。

復(fù)制代碼

下面列出主要的代碼文件：

main.h: lex.l和yacc.y共同使用的頭文件

1. #ifndef MAIN_HPP
   
2. #define MAIN_HPP
   
3. 
   
4. #include <iostream>//使用C++庫
   
5. #include <string>
   
6. #include <stdio.h>//printf和FILE要用的
   
7. 
   
8. using namespace std;
   
9. 
   
10. /*當(dāng)lex每識別出一個記號后，是通過變量yylval向yacc傳遞數(shù)據(jù)的。默認情況下yylval是int類型，也就是只能傳遞整型數(shù)據(jù)。
    
11. yylval是用YYSTYPE宏定義的，只要重定義YYSTYPE宏，就能重新指定yylval的類型(可參見yacc自動生成的頭文件yacc.tab.h)。
    
12. 在我們的例子里，當(dāng)識別出標(biāo)識符后要向yacc傳遞這個標(biāo)識符串，yylval定義成整型不太方便(要先強制轉(zhuǎn)換成整型，yacc里再轉(zhuǎn)換回char*)。
    
13. 這里把YYSTYPE重定義為struct Type，可存放多種信息*/
    
14. struct Type//通常這里面每個成員，每次只會使用其中一個，一般是定義成union以節(jié)省空間(但這里用了string等復(fù)雜類型造成不可以)
    
15. {
    
16.         string m_sId;
    
17.         int m_nInt;
    
18.         char m_cOp;
    
19. };
    
20. 
    
21. #define YYSTYPE Type//把YYSTYPE(即yylval變量)重定義為struct Type類型，這樣lex就能向yacc返回更多的數(shù)據(jù)了
    
22. 
    
23. #endif

復(fù)制代碼

lex.l: lex程序文件

1. %{
   
2. /*本lex的生成文件是lex.yy.c
   
3. lex文件由3段組成，用2個%%行把這3段隔開。
   
4. 第1段是聲明段，包括：
   
5. 1-C代碼部分：include頭文件、函數(shù)、類型等聲明，這些聲明會原樣拷到生成的.c文件中。
   
6. 2-狀態(tài)聲明，如%x COMMENT。
   
7. 3-正則式定義，如digit ([0-9])。
   
8. 第2段是規(guī)則段，是lex文件的主體，包括每個規(guī)則(如identifier)是如何匹配的，以及匹配后要執(zhí)行的C代碼動作。
   
9. 第3段是C函數(shù)定義段，如yywrap()的定義，這些C代碼會原樣拷到生成的.c文件中。該段內(nèi)容可以為空*/
   
10. 
    
11. //第1段：聲明段
    
12. #include "main.h"//lex和yacc要共用的頭文件，里面包含了一些頭文件，重定義了YYSTYPE
    
13. #include "yacc.tab.h"//用yacc編譯yacc.y后生成的C頭文件，內(nèi)含%token、YYSTYPE、yylval等定義(都是C宏)，供lex.yy.c和yacc.tab.c使用
    
14. 
    
15. extern "C"//為了能夠在C++程序里面調(diào)用C函數(shù)，必須把每一個需要使用的C函數(shù)，其聲明都包括在extern "C"{}塊里面，這樣C++鏈接時才能成功鏈接它們。extern "C"用來在C++環(huán)境下設(shè)置C鏈接類型。
    
16. {        //yacc.y中也有類似的這段extern "C"，可以把它們合并成一段，放到共同的頭文件main.h中
    
17.         int yywrap(void);
    
18.         int yylex(void);//這個是lex生成的詞法分析函數(shù)，yacc的yyparse()里會調(diào)用它，如果這里不聲明，生成的yacc.tab.c在編譯時會找不到該函數(shù)
    
19. }
    
20. %}
    
21. 
    
22. /*lex的每個正則式前面可以帶有"<狀態(tài)>"，例如下面的"<COMMENT>\n"。每個狀態(tài)要先用%x聲明才能使用。
    
23. 當(dāng)lex開始運行時，默認狀態(tài)是INITIAL，以后可在C代碼里用"BEGIN 狀態(tài)名;"切換到其它狀態(tài)(BEGIN是lex/yacc內(nèi)置的宏)。
    
24. 這時，只有當(dāng)lex狀態(tài)切換到COMMENT后，才會去匹配以<COMMENT>開頭的正則式，而不匹配其它狀態(tài)開頭的。
    
25. 也就是說，lex當(dāng)前處在什么狀態(tài)，就考慮以該狀態(tài)開頭的正則式，而忽略其它的正則式。
    
26. 其應(yīng)用例如，在一段C代碼里，同樣是串"abc"，如果它寫在代碼段里，會被識別為標(biāo)識符，如果寫在注釋里則就不會。所以對串"abc"的識別結(jié)果，應(yīng)根據(jù)不同的狀態(tài)加以區(qū)分。
    
27. 本例子需要忽略掉文本中的行末注釋，行末注釋的定義是：從某個"//"開始，直到行尾的內(nèi)容都是注釋。其實現(xiàn)方法是：
    
28. 1-lex啟動時默認是INITIAL狀態(tài)，在這個狀態(tài)下，串"abc"會識別為標(biāo)識符，串"123"會識別為整數(shù)等。
    
29. 2-一旦識別到"//"，則用BEGIN宏切換到COMMENT狀態(tài)，在該狀態(tài)下，abc這樣的串、以及其它字符會被忽略。只有識別到換行符\n時，再用BEGIN宏切換到初始態(tài)，繼續(xù)識別其它記號。*/
    
30. %x COMMENT
    
31. 
    
32. /*非數(shù)字由大小寫字母、下劃線組成*/
    
33. nondigit        ([_A-Za-z])
    
34. 
    
35. /*一位數(shù)字，可以是0到9*/
    
36. digit                ([0-9])
    
37. 
    
38. /*整數(shù)由1至多位數(shù)字組成*/
    
39. integer                ({digit}+)
    
40. 
    
41. /*標(biāo)識符，以非數(shù)字開頭，后跟0至多個數(shù)字或非數(shù)字*/
    
42. identifier        ({nondigit}({nondigit}|{digit})*)
    
43. 
    
44. /*一個或一段連續(xù)的空白符*/
    
45. blank_chars        ([ \f\r\t\v]+)
    
46. 
    
47. /*下面%%后開始第2段：規(guī)則段*/
    
48. %%
    
49. 
    
50. {identifier}        {        //匹配標(biāo)識符串，此時串值由yytext保存
    
51.                         yylval.m_sId=yytext;//通過yylval向yacc傳遞識別出的記號的值，由于yylval已定義為struct Type，這里就可以把yytext賦給其m_sId成員，到了yacc里就可以用$n的方式來引用了
    
52.                         return IDENTIFIER;        //向yacc返回: 識別出的記號類型是IDENTIFIER
    
53.                 }
    
54. 
    
55. {integer}                {        //匹配整數(shù)串
    
56.                         yylval.m_nInt=atoi(yytext);//把識別出的整數(shù)串，轉(zhuǎn)換為整型值，存儲到y(tǒng)ylval的整型成員里，到了yacc里用$n方式引用
    
57.                         return INTEGER;//向yacc返回: 識別出的記號類型是INTEGER
    
58.                 }
    
59. 
    
60. {blank_chars}        {        //遇空白符時，什么也不做，忽略它們
    
61.                 }
    
62.                                
    
63. \n                {        //遇換行符時，忽略之
    
64.                 }
    
65. "//"                {        //遇到串"//"，表明要開始一段注釋，直到行尾
    
66.                         cout<<"(comment)"<<endl;//提示遇到了注釋
    
67.                         BEGIN COMMENT;//用BEGIN宏切換到注釋狀態(tài)，去過濾這段注釋，下一次lex將只匹配前面帶有<COMMENT>的正則式
    
68.                 }
    
69. 
    
70. .                {        //.表示除\n以外的其它字符，注意這個規(guī)則要放在最后，因為一旦匹配了.就不會匹配后面的規(guī)則了(以其它狀態(tài)<>開頭的規(guī)則除外)
    
71.                         yylval.m_cOp=yytext[0];//由于只匹配一個字符，這時它對應(yīng)yytext[0]，把該字符存放到y(tǒng)ylval的m_cOp成員里，到了yacc里用$n方式引用
    
72.                         return OPERATOR;//向yacc返回: 識別出的記號類型是OPERATOR
    
73.                 }
    
74. 
    
75. <COMMENT>\n        {        //注釋狀態(tài)下的規(guī)則，只有當(dāng)前切換到COMMENT狀態(tài)才會去匹配
    
76.                         BEGIN INITIAL;//在注釋狀態(tài)下，當(dāng)遇到換行符時，表明注釋結(jié)束了，返回初始態(tài)
    
77.                 }
    
78. 
    
79. <COMMENT>.        {        //在注釋狀態(tài)下，對其它字符都忽略，即：注釋在lex(詞法分析層)就過濾掉了，不返回給yacc了
    
80.                 }
    
81. 
    
82. %%
    
83. 
    
84. //第3段：C函數(shù)定義段
    
85. int yywrap(void)
    
86. {
    
87.         puts("-----the file is end");
    
88.         return 1;//返回1表示讀取全部結(jié)束。如果要接著讀其它文件，可以這里fopen該文件，文件指針賦給yyin，并返回0
    
89. }

復(fù)制代碼

yacc.y: yacc程序文件

1. %{
   
2. /*本yacc的生成文件是yacc.tab.c和yacc.tab.h
   
3. yacc文件由3段組成，用2個%%行把這3段隔開。
   
4. 第1段是聲明段，包括：
   
5. 1-C代碼部分：include頭文件、函數(shù)、類型等聲明，這些聲明會原樣拷到生成的.c文件中。
   
6. 2-記號聲明，如%token
   
7. 3-類型聲明，如%type
   
8. 第2段是規(guī)則段，是yacc文件的主體，包括每個產(chǎn)生式是如何匹配的，以及匹配后要執(zhí)行的C代碼動作。
   
9. 第3段是C函數(shù)定義段，如yyerror()的定義，這些C代碼會原樣拷到生成的.c文件中。該段內(nèi)容可以為空*/
   
10. 
    
11. //第1段：聲明段
    
12. #include "main.h"//lex和yacc要共用的頭文件，里面包含了一些頭文件，重定義了YYSTYPE
    
13. 
    
14. extern "C"//為了能夠在C++程序里面調(diào)用C函數(shù)，必須把每一個需要使用的C函數(shù)，其聲明都包括在extern "C"{}塊里面，這樣C++鏈接時才能成功鏈接它們。extern "C"用來在C++環(huán)境下設(shè)置C鏈接類型。
    
15. {        //lex.l中也有類似的這段extern "C"，可以把它們合并成一段，放到共同的頭文件main.h中
    
16.         void yyerror(const char *s);
    
17.         extern int yylex(void);//該函數(shù)是在lex.yy.c里定義的，yyparse()里要調(diào)用該函數(shù)，為了能編譯和鏈接，必須用extern加以聲明
    
18. }
    
19. 
    
20. %}
    
21. 
    
22. /*lex里要return的記號的聲明
    
23. 用token后加一對<member>來定義記號，旨在用于簡化書寫方式。
    
24. 假定某個產(chǎn)生式中第1個終結(jié)符是記號OPERATOR，則引用OPERATOR屬性的方式：
    
25. 1-如果記號OPERATOR是以普通方式定義的，如%token OPERATOR，則在動作中要寫$1.m_cOp，以指明使用YYSTYPE的哪個成員
    
26. 2-用%token<m_cOp>OPERATOR方式定義后，只需要寫$1，yacc會自動替換為$1.m_cOp
    
27. 另外用<>定義記號后，非終結(jié)符如file, tokenlist，必須用%type<member>來定義(否則會報錯)，以指明它們的屬性對應(yīng)YYSTYPE中哪個成員，這時對該非終結(jié)符的引用，如$$，會自動替換為$$.member*/
    
28. %token<m_nInt>INTEGER
    
29. %token<m_sId>IDENTIFIER
    
30. %token<m_cOp>OPERATOR
    
31. %type<m_sId>file
    
32. %type<m_sId>tokenlist
    
33. 
    
34. %%
    
35. 
    
36. file:        //文件，由記號流組成
    
37.         tokenlist        //這里僅顯示記號流中的ID
    
38.         {
    
39.                 cout<<"all id:"<<$1<<endl;        //$1是非終結(jié)符tokenlist的屬性，由于該終結(jié)符是用%type<m_sId>定義的，即約定對其用YYSTYPE的m_sId屬性，$1相當(dāng)于$1.m_sId，其值已經(jīng)在下層產(chǎn)生式中賦值(tokenlist IDENTIFIER)
    
40.         };
    
41. tokenlist://記號流，或者為空，或者由若干數(shù)字、標(biāo)識符、及其它符號組成
    
42.         {
    
43.         }
    
44.         | tokenlist INTEGER
    
45.         {
    
46.                 cout<<"int: "<<$2<<endl;//$2是記號INTEGER的屬性，由于該記號是用%token<m_nInt>定義的，即約定對其用YYSTYPE的m_nInt屬性，$2會被替換為yylval.m_nInt，已在lex里賦值
    
47.         }
    
48.         | tokenlist IDENTIFIER
    
49.         {
    
50.                 $$+=" " + $2;//$$是非終結(jié)符tokenlist的屬性，由于該終結(jié)符是用%type<m_sId>定義的，即約定對其用YYSTYPE的m_sId屬性，$$相當(dāng)于$$.m_sId，這里把識別到的標(biāo)識符串保存在tokenlist屬性中，到上層產(chǎn)生式里可以拿出為用
    
51.                 cout<<"id: "<<$2<<endl;//$2是記號IDENTIFIER的屬性，由于該記號是用%token<m_sId>定義的，即約定對其用YYSTYPE的m_sId屬性，$2會被替換為yylval.m_sId，已在lex里賦值
    
52.         }
    
53.         | tokenlist OPERATOR
    
54.         {
    
55.                 cout<<"op: "<<$2<<endl;//$2是記號OPERATOR的屬性，由于該記號是用%token<m_cOp>定義的，即約定對其用YYSTYPE的m_cOp屬性，$2會被替換為yylval.m_cOp，已在lex里賦值
    
56.         };
    
57. 
    
58. %%
    
59. 
    
60. void yyerror(const char *s)        //當(dāng)yacc遇到語法錯誤時，會回調(diào)yyerror函數(shù)，并且把錯誤信息放在參數(shù)s中
    
61. {
    
62.         cerr<<s<<endl;//直接輸出錯誤信息
    
63. }
    
64. 
    
65. int main()//程序主函數(shù)，這個函數(shù)也可以放到其它.c, .cpp文件里
    
66. {
    
67.         const char* sFile="file.txt";//打開要讀取的文本文件
    
68.         FILE* fp=fopen(sFile, "r");
    
69.         if(fp==NULL)
    
70.         {
    
71.                 printf("cannot open %s\n", sFile);
    
72.                 return -1;
    
73.         }
    
74.         extern FILE* yyin;        //yyin和yyout都是FILE*類型
    
75.         yyin=fp;//yacc會從yyin讀取輸入，yyin默認是標(biāo)準輸入，這里改為磁盤文件。yacc默認向yyout輸出，可修改yyout改變輸出目的
    
76. 
    
77.         printf("-----begin parsing %s\n", sFile);
    
78.         yyparse();//使yacc開始讀取輸入和解析，它會調(diào)用lex的yylex()讀取記號
    
79.         puts("-----end parsing");
    
80. 
    
81.         fclose(fp);
    
82. 
    
83.         return 0;
    
84. }

復(fù)制代碼

Makefile: makefile文件

1. LEX=flex
   
2. YACC=bison
   
3. CC=g++
   
4. OBJECT=main #生成的目標(biāo)文件
   
5. 
   
6. $(OBJECT): lex.yy.o  yacc.tab.o
   
7.         $(CC) lex.yy.o yacc.tab.o -o $(OBJECT)
   
8.         @./$(OBJECT) #編譯后立刻運行
   
9. 
   
10. lex.yy.o: lex.yy.c  yacc.tab.h  main.h
    
11.         $(CC) -c lex.yy.c
    
12. 
    
13. yacc.tab.o: yacc.tab.c  main.h
    
14.         $(CC) -c yacc.tab.c
    
15. 
    
16. yacc.tab.c  yacc.tab.h: yacc.y
    
17. # bison使用-d參數(shù)編譯.y文件
    
18.         $(YACC) -d yacc.y
    
19. 
    
20. lex.yy.c: lex.l
    
21.         $(LEX) lex.l
    
22. 
    
23. clean:
    
24.         @rm -f $(OBJECT)  *.o

復(fù)制代碼

file.txt: 被解析的文本示例

1. abc defghi
   
2. //this line is comment, abc 123 !@#$
   
3. 123        45678        //comment until line end
   
4. !        @        #        $

復(fù)制代碼

使用方法：
1-把lex_yacc_example.rar解壓到linux/cygwin下。
2-命令行進入lex_yacc_example目錄。
3-敲入make，這時會自動執(zhí)行以下操作：
(1) 自動調(diào)用flex編譯.l文件，生成lex.yy.c文件。
(2) 自動調(diào)用bison編譯.y文件，生成yacc.tab.c和yacc.tab.h文件。
(3) 自動調(diào)用g++編譯、鏈接出可執(zhí)行文件main。
(4) 自動執(zhí)行main。

運行結(jié)果如下所示：

1. bison -d yacc.y
   
2. g++ -c lex.yy.c
   
3. g++ -c yacc.tab.c
   
4. g++ lex.yy.o yacc.tab.o -o main                       
   
5. -----begin parsing file.txt
   
6. id: abc
   
7. id: defghi
   
8. (comment)
   
9. int: 123
   
10. int: 45678
    
11. (comment)
    
12. op: !
    
13. op: @
    
14. op: #
    
15. op: $
    
16. -----the file is end
    
17. all id: abc defghi
    
18. -----end parsing

復(fù)制代碼

參考資料：《Lex和Yacc從入門到精通(6)-解析C-C++包含文件》http://blog.csdn.net/pandaxcl/article/details/1321552
[END]