Lex 和 Yacc 是 Unix 和Linux 下詞法和語法的分析，解析工具，有了這兩個工具，你可以自己制作想要的編譯器，也可以重新制作已有程序語言的解析器。需要注意的是linux下的這兩個工具生成的程序源碼只能是C和C++語言，當然現在早已有類似可以生成Java源碼的語法分析器，如較常用的JavaCC(Java Compiler Compiler)，相關內容可以去網上搜索。Lex和Yacc已被移植到windows下，現在常用的工具有Parser Generator。本文只介紹Linux 下Lex和Yacc的使用方法。
Lex介紹
Lex 通過對.lex或.l文件定義的格式生成一個C語言源碼文件，通過編譯這個源碼，就生成了.lex文件或.l文件定義的編譯器。.lex或.l文件的格式分三段:
1.全局變量聲明部分
2.詞法規則部分
3.函數定義部分
以下是一個簡單的例子：lex_example.l文件
%{ //全局聲明部分
/*林木100 linux
www.linmu100.com
*/
#include <stdio.h>
extern char *yytext;
extern FILE *yyin;
int sem_count = 0;
%}
//規則定義部分，
%%
[a-zA-Z][a-zA-Z0-9]* {printf("WORD[%s] ", yytext);}
[a-zA-Z0-9\/.-]+ printf("FILENAME ");
\" printf("QUOTE ");
\{ printf("OBRACE ");
\} printf("EBRACE ");
; {sem_count++; printf("SEMICOLON ");}
\n printf("\n");
[ \t]+ /* ignore whitespace */;
%%
//以下為函數定義部分
int main(int avgs, char *avgr[])
{
yyin = fopen(avgr[1], "r");
if (!yyin)
{
return 0;
}
yylex();
printf("sem_count : %d\n", sem_count);
fclose(yyin);
return 1;
}
Lex 常用格式如下表，常規表達式：
|
字符
|
含義
|
|
A-Z, 0-9, a-z
|
構成了部分模式的字符和數字。
|
|
.
|
匹配任意字符，除了 \n。
|
|
-
|
用來指定范圍。例如：A-Z 指從 A 到 Z 之間的所有字符。
|
|
[ ]
|
一個字符集合。匹配括號內的任意 字符。如果第一個字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一個。
|
|
*
|
匹配0個或者多個上述的模式。
|
|
+
|
匹配1個或者多個上述模式。
|
|
?
|
匹配0個或1個上述模式。
|
|
$
|
作為模式的最后一個字符匹配一行的結尾。
|
|
{ }
|
指出一個模式可能出現的次數。 例如: A{1,3} 表示 A 可能出現1次或3次。
|
|
\
|
用來轉義元字符。同樣用來覆蓋字符在此表中定義的特殊意義，只取字符的本意。
|
|
^
|
否定。
|
|
|
|
表達式間的邏輯或。
|
|
"<一些符號>"
|
字符的字面含義。元字符具有。
|
|
/
|
向前匹配。如果在匹配的模版中的“/”后跟有后續表達式，只匹配模版中“/”前面的部分。如：如果輸入 A01，那么在模版 A0/1 中的 A0 是匹配的。
|
|
( )
|
將一系列常規表達式分組。
|
常規表達式舉例
|
常規表達式
|
含義
|
|
joke[rs]
|
匹配 jokes 或 joker。
|
|
A{1,2}shis+
|
匹配 AAshis, Ashis, AAshi, Ashi。
|
|
(A[b-e])+
|
匹配在 A 出現位置后跟隨的從 b 到 e 的所有字符中的 0 個或 1個。
|
使用lex掃描上述舉例文件 lex_example.l：
lex lex_example.l
缺省會生成lex.yy.c文件，然后用gcc編譯這個文件，注意要有-ll選項:
gcc lex.yy.c -o analyse -ll
這樣就生成了一個簡單的詞法分析器analyse，假設有文件demo，其內容如下所示:
firstword;
secondword;
thirdword
fourthword{
fifthword
}
輸入命令:
./analyse demo
會有如下顯示：
WORD[firstword] SEMICOLON
WORD[secondword] SEMICOLON
WORD[thirdword]
WORD[fourthword] OBRACE
WORD[fifthword]
EBRACE
sem_count : 2
實際上，對于上述lex_example.l文件，函數定義部分可以完全省略，因為lex會自動為你生成main函數。這時仍然按上述方法生成analyse，輸入命令:
./analse < demo
結果如下：
WORD[firstword] SEMICOLON
WORD[secondword] SEMICOLON
WORD[thirdword]
WORD[fourthword] OBRACE
WORD[fifthword]
EBRACE
在上述lex_example.l文件中我們還使用了兩個變量：
extern char *yytext;
extern FILE *yyin;
這兩個變量是lex提供的外部借口，用戶可以根據自己需要自己更改，lex提供了以下接口：
Lex 變量
|
yyin
|
FILE* 類型。 它指向 lexer 正在解析的當前文件。
|
|
yyout
|
FILE* 類型。 它指向記錄 lexer 輸出的位置。 缺省情況下，yyin 和 yyout 都指向標準輸入和輸出。
|
|
yytext
|
匹配模式的文本存儲在這一變量中（char*）。
|
|
yyleng
|
給出匹配模式的長度。
|
|
yylineno
|
提供當前的行數信息。（lexer不一定支持。）
|
Lex 函數
|
yylex()
|
這一函數開始分析。 它由 Lex 自動生成。
|
|
yywrap()
|
這 一函數在文件（或輸入）的末尾調用。如果函數的返回值是1，就停止解析。 因此它可以用來解析多個文件。代碼可以寫在第三段，這就能夠解析多個文件。 方法是使用 yyin 文件指針（見上表）指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回 1 來表示解析的結束。
|
|
yyless(int n)
|
這一函數可以用來送回除了前憂? 個字符外的所有讀出標記。
|
|
yymore()
|
這一函數告訴 Lexer 將下一個標記附加到當前標記后。
|
以下是一個計算字符個數的.l文件內容，有興趣的朋友可以編譯試試
%{
/*
林木100 linux
www.linmu100.com
*/
int wc = 0; /* word count */
%}
%%
[a-zA-Z]+ { wc++; }
\n|. { /* gobble up */ }
%%
int main(void)
{
int n = yylex();
return n;
}
int yywrap(void)
{
printf("word count: %d\n", wc);
return 1;
}
yacc介紹
Yacc 是 Yet Another Compiler Compiler的縮寫。 Yacc 的 GNU 版叫做 Bison。它是一種語法解析工具。它用巴科斯范式(BNF, Backus Naur Form)來書寫。按照慣例，Yacc 文件有 .y 后綴。
實際上，yacc才是真正分析語法的核心，.y文件格式和.l文件一樣分三段，但每一段的意義有所不同：
1.全局變量聲明，終結符號(終端符號)聲明
2.語法定義
3.函數定義
以下是一個簡單的yacc_example.y文件，定義了一個簡單的計算器：
%{
//全局變量聲明
#include <ctype.h>
#include <stdio.h>
#define YYSTYPE double /*double type for YACC stack; for yylval*/
/*林木100 www.linmu100.com */
void yyerror(const char *str)
{
fprintf(stderr, "error:%s\n", str );
}
%}
//終結符聲明
%token NUMBER
%%
lines : lines expr '\n' { printf("%g\n", $2); }
| lines '\n'
| /* e */
| error '\n' { yyerror("reenter last line:"); /*yyerrok(); */}
;
expr : expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
| term
;
term : term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
| factor
;
factor : '(' expr ')' { $$ = $2; }
| '(' expr error { $$ = $2; yyerror("missing ')'"); /*yyerrok(); */}
| '-' factor { $$ = -$2; }
| NUMBER
;
%%
//以上部分為語法定義，以下部分為函數定義
int main(void)
{
return yyparse();
}
int yylex(void)
{
int c;
while ((c = getchar()) == ' ');
if (c == '.' || isdigit(c)) {
ungetc(c, stdin);
scanf("%lf", &yylval);
return NUMBER;
}
return c;
}
使用yacc掃描這個文件：
yacc yacc_example.y
缺省會生成一個y.tab.c文件，然后用gcc編譯這個文件，注意要有選項 -ll 或 -ly：
gcc y.tab.c -o analyse -ll
運行./analyse：結果如下圖所示:
現在對照yacc_example.y文件講解一下.y文件的規則：
1.在全局變量聲明部分，聲明了一個接口函數yyerror，這個函數是用來在出錯時調用的。這一段主要是聲明一些變量，數據結構，函數用。
2.%token NUMBER則聲明了一個終端符(終結符)，這個符號是由Lex返回的，會在yacc語法規則中用到。
3.語法規則部分則聲明了語法：
3.1語法規則對外只有一個接口，這一點要注意，初學者常常會犯語法對外有多個接口的錯誤。
3.2無論是lex文件還是yacc文件都要注意最大可能性的詞法和語法規則要放在沖突規則的前面，這樣保證了最大可能規則會被最先匹配，比如lex文件中：
temperator return T1;
temp return T2;
在yacc文件中，例子如下
command:
NUMBER CHAR
| NUMBER
;
對于.y文件還要注意全局語法，以及遞歸的調用。
初學者對于yacc文件規則可能會較為生疏，關鍵還要多做一些練習。
Lex 和 Yacc 的結合
lex和yacc結合時需要注意的是
lex文件頭要引用yacc生成的頭文件:"y.tab.h"
以下是一個lex和yacc結合的實例：
lex_yacc_exp.l文件：
%{
/*林木100
www.linmu100.com
*/
#include <stdio.h>
#include <string.h>
#include "y.tab.h"
extern char *yytext;
%}
%%
[0-9]+ yylval.number=atoi(yytext); return NUMBER;
heater return TOKHEATER;
heat return TOKHEAT;
on|off yylval.number=!strcmp(yytext,"on"); return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
[a-z0-9]+ yylval.string=strdup(yytext);return WORD;
\n /* ignore end of line */;
[ \t]+ /* ignore whitespace */;
%%
lex_yacc_exp.y文件:
%{
/*林木100
www.linmu100.com
*/
#include <stdio.h>
#include <string.h>
void yyerror(const char *str)
{
fprintf(stderr,"error: %s\n",str);
}
int yywrap()
{
return 1;
}
main()
{
yyparse();
}
char *heater="xl's test";
%}
%token TOKHEATER TOKHEAT TOKTARGET TOKTEMPERATURE
%union
{
int number;
char *string;
}
%token <number> STATE
%token <number> NUMBER
%token <string> WORD
%%
commands:
| commands command
;
command:
heat_switch | target_set | heater_select
heat_switch:
TOKHEAT STATE
{
if($2)
printf("\tHeater '%s' turned on\n", heater);
else
printf("\tHeat '%s' turned off\n", heater);
}
;
target_set:
TOKTARGET TOKTEMPERATURE NUMBER
{
printf("\tHeater '%s' temperature set to %d\n",heater, $3);
}
;
heater_select:
TOKHEATER WORD
{
printf("\tSelected heater '%s'\n",$2);
heater=$2;
}
;
輸入以下命令，分別生成lex.yy.c，y.tab.c，y.tab.h三個文件：
lex lex_yacc_exp.l
yacc -d lex_yacc_exp.y
gcc lex.yy.c y.tab.c -o analyse -ll
創建一個語法用例demo，內容如下:
heat on
target temperature 99
heater asdfsieiwef99adsf
輸入./analyse <demo分析demo文件，會得到以下結果:
結語：
Lex 和 Yacc 是很強大的工具，這里只簡單介紹了一些入門知識。
The Lex & Yacc Page 中有很多有趣的歷史參考，以及 非常好的 lex 和 yacc 文檔。
參考文檔：
http://www.ibm.com/developerworks/cn/linux/l-lexyac.html
http://blog.csdn.net/ThinkinginLinux/archive/2005/03/19/323379.aspx
/
/*-----Lex & Yacc ----www.linmu100.com ----*/
/
/*-----linux工具,Lex & Yacc,基本操作----*/
/
/*-----linux配置,UNIX,開源軟件,linux技術,makefile----*/
/
/*----------------------@xiaolin--------------------*/
/