Lex 和 Yacc 是 Unix 和Linux 下詞法和語法的分析，解析工具，有了這兩個(gè)工具，你可以自己制作想要的編譯器，也可以重新制作已有程序語言的解析器。需要注意的是linux下的這兩個(gè)工具生成的程序源碼只能是C和C++語言，當(dāng)然現(xiàn)在早已有類似可以生成Java源碼的語法分析器，如較常用的JavaCC(Java Compiler Compiler)，相關(guān)內(nèi)容可以去網(wǎng)上搜索。Lex和Yacc已被移植到windows下，現(xiàn)在常用的工具有Parser Generator。本文只介紹Linux 下Lex和Yacc的使用方法。
Lex介紹
Lex 通過對(duì).lex或.l文件定義的格式生成一個(gè)C語言源碼文件，通過編譯這個(gè)源碼，就生成了.lex文件或.l文件定義的編譯器。.lex或.l文件的格式分三段:
1.全局變量聲明部分
2.詞法規(guī)則部分
3.函數(shù)定義部分
以下是一個(gè)簡單的例子：lex_example.l文件
%{ //全局聲明部分
/*林木100 linux
www.linmu100.com
*/
#include <stdio.h>
extern char *yytext;
extern FILE *yyin;
int sem_count = 0;
%}
//規(guī)則定義部分，
%%
[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 */;
%%
//以下為函數(shù)定義部分
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 常用格式如下表，常規(guī)表達(dá)式：
|
字符
|
含義
|
|
A-Z, 0-9, a-z
|
構(gòu)成了部分模式的字符和數(shù)字。
|
|
.
|
匹配任意字符，除了 \n。
|
|
-
|
用來指定范圍。例如：A-Z 指從 A 到 Z 之間的所有字符。
|
|
[ ]
|
一個(gè)字符集合。匹配括號(hào)內(nèi)的任意 字符。如果第一個(gè)字符是 ^ 那么它表示否定模式。例如: [abC] 匹配 a, b, 和 C中的任何一個(gè)。
|
|
*
|
匹配0個(gè)或者多個(gè)上述的模式。
|
|
+
|
匹配1個(gè)或者多個(gè)上述模式。
|
|
?
|
匹配0個(gè)或1個(gè)上述模式。
|
|
$
|
作為模式的最后一個(gè)字符匹配一行的結(jié)尾。
|
|
{ }
|
指出一個(gè)模式可能出現(xiàn)的次數(shù)。 例如: A{1,3} 表示 A 可能出現(xiàn)1次或3次。
|
|
\
|
用來轉(zhuǎn)義元字符。同樣用來覆蓋字符在此表中定義的特殊意義，只取字符的本意。
|
|
^
|
否定。
|
|
|
|
表達(dá)式間的邏輯或。
|
|
"<一些符號(hào)>"
|
字符的字面含義。元字符具有。
|
|
/
|
向前匹配。如果在匹配的模版中的“/”后跟有后續(xù)表達(dá)式，只匹配模版中“/”前面的部分。如：如果輸入 A01，那么在模版 A0/1 中的 A0 是匹配的。
|
|
( )
|
將一系列常規(guī)表達(dá)式分組。
|
常規(guī)表達(dá)式舉例
|
常規(guī)表達(dá)式
|
含義
|
|
joke[rs]
|
匹配 jokes 或 joker。
|
|
A{1,2}shis+
|
匹配 AAshis, Ashis, AAshi, Ashi。
|
|
(A[b-e])+
|
匹配在 A 出現(xiàn)位置后跟隨的從 b 到 e 的所有字符中的 0 個(gè)或 1個(gè)。
|
使用lex掃描上述舉例文件 lex_example.l：
lex lex_example.l
缺省會(huì)生成lex.yy.c文件，然后用gcc編譯這個(gè)文件，注意要有-ll選項(xiàng):
gcc lex.yy.c -o analyse -ll
這樣就生成了一個(gè)簡單的詞法分析器analyse，假設(shè)有文件demo，其內(nèi)容如下所示:
firstword;
secondword;
thirdword
fourthword{
fifthword
}
輸入命令:
./analyse demo
會(huì)有如下顯示：
WORD[firstword] SEMICOLON
WORD[secondword] SEMICOLON
WORD[thirdword]
WORD[fourthword] OBRACE
WORD[fifthword]
EBRACE
sem_count : 2
實(shí)際上，對(duì)于上述lex_example.l文件，函數(shù)定義部分可以完全省略，因?yàn)閘ex會(huì)自動(dòng)為你生成main函數(shù)。這時(shí)仍然按上述方法生成analyse，輸入命令:
./analse < demo
結(jié)果如下：
WORD[firstword] SEMICOLON
WORD[secondword] SEMICOLON
WORD[thirdword]
WORD[fourthword] OBRACE
WORD[fifthword]
EBRACE
在上述lex_example.l文件中我們還使用了兩個(gè)變量：
extern char *yytext;
extern FILE *yyin;
這兩個(gè)變量是lex提供的外部借口，用戶可以根據(jù)自己需要自己更改，lex提供了以下接口：
Lex 變量
|
yyin
|
FILE* 類型。 它指向 lexer 正在解析的當(dāng)前文件。
|
|
yyout
|
FILE* 類型。 它指向記錄 lexer 輸出的位置。 缺省情況下，yyin 和 yyout 都指向標(biāo)準(zhǔn)輸入和輸出。
|
|
yytext
|
匹配模式的文本存儲(chǔ)在這一變量中（char*）。
|
|
yyleng
|
給出匹配模式的長度。
|
|
yylineno
|
提供當(dāng)前的行數(shù)信息。（lexer不一定支持。）
|
Lex 函數(shù)
|
yylex()
|
這一函數(shù)開始分析。 它由 Lex 自動(dòng)生成。
|
|
yywrap()
|
這 一函數(shù)在文件（或輸入）的末尾調(diào)用。如果函數(shù)的返回值是1，就停止解析。 因此它可以用來解析多個(gè)文件。代碼可以寫在第三段，這就能夠解析多個(gè)文件。 方法是使用 yyin 文件指針（見上表）指向不同的文件，直到所有的文件都被解析。最后，yywrap() 可以返回 1 來表示解析的結(jié)束。
|
|
yyless(int n)
|
這一函數(shù)可以用來送回除了前憂? 個(gè)字符外的所有讀出標(biāo)記。
|
|
yymore()
|
這一函數(shù)告訴 Lexer 將下一個(gè)標(biāo)記附加到當(dāng)前標(biāo)記后。
|
以下是一個(gè)計(jì)算字符個(gè)數(shù)的.l文件內(nèi)容，有興趣的朋友可以編譯試試
%{
/*
林木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 后綴。
實(shí)際上，yacc才是真正分析語法的核心，.y文件格式和.l文件一樣分三段，但每一段的意義有所不同：
1.全局變量聲明，終結(jié)符號(hào)(終端符號(hào))聲明
2.語法定義
3.函數(shù)定義
以下是一個(gè)簡單的yacc_example.y文件，定義了一個(gè)簡單的計(jì)算器：
%{
//全局變量聲明
#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 );
}
%}
//終結(jié)符聲明
%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
;
%%
//以上部分為語法定義，以下部分為函數(shù)定義
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掃描這個(gè)文件：
yacc yacc_example.y
缺省會(huì)生成一個(gè)y.tab.c文件，然后用gcc編譯這個(gè)文件，注意要有選項(xiàng) -ll 或 -ly：
gcc y.tab.c -o analyse -ll
運(yùn)行./analyse：結(jié)果如下圖所示:
現(xiàn)在對(duì)照yacc_example.y文件講解一下.y文件的規(guī)則：
1.在全局變量聲明部分，聲明了一個(gè)接口函數(shù)yyerror，這個(gè)函數(shù)是用來在出錯(cuò)時(shí)調(diào)用的。這一段主要是聲明一些變量，數(shù)據(jù)結(jié)構(gòu)，函數(shù)用。
2.%token NUMBER則聲明了一個(gè)終端符(終結(jié)符)，這個(gè)符號(hào)是由Lex返回的，會(huì)在yacc語法規(guī)則中用到。
3.語法規(guī)則部分則聲明了語法：
3.1語法規(guī)則對(duì)外只有一個(gè)接口，這一點(diǎn)要注意，初學(xué)者常常會(huì)犯語法對(duì)外有多個(gè)接口的錯(cuò)誤。
3.2無論是lex文件還是yacc文件都要注意最大可能性的詞法和語法規(guī)則要放在沖突規(guī)則的前面，這樣保證了最大可能規(guī)則會(huì)被最先匹配，比如lex文件中：
temperator return T1;
temp return T2;
在yacc文件中，例子如下
command:
NUMBER CHAR
| NUMBER
;
對(duì)于.y文件還要注意全局語法，以及遞歸的調(diào)用。
初學(xué)者對(duì)于yacc文件規(guī)則可能會(huì)較為生疏，關(guān)鍵還要多做一些練習(xí)。
Lex 和 Yacc 的結(jié)合
lex和yacc結(jié)合時(shí)需要注意的是
lex文件頭要引用yacc生成的頭文件:"y.tab.h"
以下是一個(gè)lex和yacc結(jié)合的實(shí)例：
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三個(gè)文件：
lex lex_yacc_exp.l
yacc -d lex_yacc_exp.y
gcc lex.yy.c y.tab.c -o analyse -ll
創(chuàng)建一個(gè)語法用例demo，內(nèi)容如下:
heat on
target temperature 99
heater asdfsieiwef99adsf
輸入./analyse <demo分析demo文件，會(huì)得到以下結(jié)果:
結(jié)語：
Lex 和 Yacc 是很強(qiáng)大的工具，這里只簡單介紹了一些入門知識(shí)。
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技術(shù),makefile----*/
/
/*----------------------@xiaolin--------------------*/
/