【導讀】本文介紹了語法解析基本概念，結合 實戰做了詳細介紹。
一、Lex & Yacc簡介
Lex & Yacc 是用來生成詞法分析器和語法分析器的工具，與GNU用戶所熟知Flex&Bison所對應（Flex是由Vern Paxon實現的一個Lex詞法分析器的輸出結果，Bison則是GNU版本的YACC）。除了編譯器領域，Lex & Yacc對于DSL或者SQL解析領域也大有用處。
Lex （A ）用于生成詞法分析器，用于把輸入分割成一個個有意義的詞塊（稱為token）。
Yacc（Yet -）用于生成語法解析器，用于確定上述分隔好的token之間的關聯。
下圖描述了整個處理的流程：
二、詞法分析器
詞法分析器用于獲取一個token流。通過調用yylex()讀取輸入，然后返回相應的token，之后循環調用，持續返回解析好的token。每個token有兩部分組成：
如下是計算器詞法分析器的規則定義。該定義由三部分組成，由%%分隔。
//?計算器詞法分析器
%{
????enum?yytokentype?{
????????NUMBER?=?258,
????????ADD?=?259,
????????SUB?=?260,
????????MUL?=?261,
????????DIV?=?262,
????????ABS?=?263,
????????EOL?=?264
????};
????int?yylval;
%}
%%?
"+"????????{return?ADD;}
"-"????????{return?SUB;}
"*"????????{return?MUL;}
"/"????????{return?DIV;}
"|"????????{return?ABS;}
[0-9]+?????{yylval?=?atoi(yytext);?return?NUMBER;}
\n?????????{return?EOL;}
[?\t]??????{/*忽略空白字符*/}
%%
main(int?argc,?char?**argv)?{
????int?tok;
??while(tok?=?yylex())?{
????printf("%d",?tok);
????if?(tok?==?NUMBER)?{
??????printf("?=?%d\n",?yylval);
????}?else?{
??????print("\n");
????}
??}
}
//?運行
///?輸入：
34?+?45
///?輸出：
258?=?34
259
258?=?45
三、語法分析器
語法分析器用于找出輸入token之間的關系，使用巴科斯范式（BNF, Naur Form）來書寫。同詞法分析器規則一樣，也是三部分組成。
樣例：
%{
#include
%}
/*declare tokens*/
%token NUMBER
%token ADD SUB MUL DIV ABS
%token EOL
%%
calclist: /*空規則*/
| calclist exp EOL { printf("= %d\n", $2); }
;
exp: factor defalut $$ = $1
| exp ADD factor { $$ = $1 + $3; }
| exp SUB factor { $$ = $1 - $3; }
;
factor: term default $$ = $1
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
term: NUMBER default $$ = $1
| ABS term { $$ = $2 >=0 ? $2 : - $2; }
;
%%
main(int argc, char **argv) {
yyparse();
}
yyerror(char *s) {
fprintf(stderr, "error: %s\n", s);
}
四、yacc語法規范整體結構
由三部分組成，其中前兩部分必須。
...定義部分...
%%
...規則部分...
%%
...用戶子程序...
符號
由詞法分析器產生的符號稱為終結符或者token。
在規則左側定義的的符號稱為非終結符。
定義部分規則部分
包括語法規則和語義動作代碼。動作即yacc匹配語法中的一條規則時之行的代碼。例如：
date: month '/' day '/' year { $$ = ("date %d-%d-%d", $1, $3, $5); }
用戶子程序
原樣被拷貝到C文件的代碼片段。
移進/歸約
移進（shift）：語法分析器讀取token時，當讀取的token無法匹配一條規則時，則將其壓入一個內部堆棧(union為壓入堆棧的結構體)，然后切換到一個新的狀態，這個新的狀態能夠反映出剛剛讀取的token。
歸約（）：當發現壓入的token已經能夠匹配規則時，則把匹配的符號從堆棧中取出，然后將左側符號壓入堆棧。
例如，fred = 12 + 13的處理過程：
// 規則
statement: NAME '=' expression
expression: NUMBER + NUMBER
// 處理過程
fred
fred =
fred = 12
fred = 12 +
fred = 12 + 13 //匹配expression: NUMBER + NUMBER，可以歸約
fred = expression //匹配statement: NAME '=' expression
statement
但是如果引入乘法后，可能會產生沖突，造成如下不同的語法結構。
對于這種情況需要顯示指定優先級和結合性來解決沖突：
// 意義：+ - * /都是左結合，* /的優先級高于+ -。
%left '+' '-'
%left '*' '/'
五、
/cznic/是 版的 Yacc。和 Yacc 的功能一樣， 根據輸入的語法規則文件，生成該語法規則的 go 語言版解析器。 生成的解析器 要求詞法分析器符合下面的接口：
type yyLexer interface {
Lex(lval *yySymType) int
Error(e string)
}
或者
type yyLexerEx interface {
yyLexer
// Hook for recording a reduction.
Reduced(rule, state int, lval *yySymType) (stop bool) // Client should copy *lval.
}
Lex應該返回token類型詞法分析器的輸出結果，并將token值放到放在lval中（與yacc的對應）。Error相當于原yacc中的。
六、樣例電話號碼解析
源代碼：///tree//v3
# 定義部分
%{
package jsonparser
func setResult(l yyLexer, v Result) {
l.(*lex).result = v
}
%}
%union{
result Result
part string
ch byte
}
%token D
%type phone
%type area part1 part2
%start main
%%
# 規則部分
main: phone
{
setResult(yylex, $1)
}
phone:
area part1 part2
{
$$ = Result{area: $1, part1: $2, part2: $3}
}
| area '-' part1 '-' part2
{
$$ = Result{area: $1, part1: $3, part2: $5}
}
area: D D D
{
$$ = cat($1, $2, $3)
}
part1: D D D
{
$$ = cat($1, $2, $3)
}
part2: D D D D
{
$$ = cat($1, $2, $3, $4)
}
//?對應.y中union的結構體
type?yySymType?struct?{
????yys????int
????result?Result
????part???string
????ch?????byte
}
//token類型
const?(
????yyDefault?=?57347
????yyEofCode?=?57344
????D?????????=?57346
????yyErrCode?=?57345
????yyMaxDepth?=?200
????yyTabOfs???=?-7
)
//詞法分析器接口
type?yyLexer?interface?{
????Lex(lval?*yySymType)?int
????Error(s?string)
}
type?yyLexerEx?interface?{
????yyLexer
????Reduced(rule,?state?int,?lval?*yySymType)?bool
}
//語法解析入口
func?yyParse(yylex?yyLexer)?int?{
}
//?Result?is?the?type?of?the?parser?result
type?Result?struct?{
????area??string
????part1?string
????part2?string
}
//?解析的總入口。輸入電話號碼，輸出為Result的解析結果。
func?Parse(input?[]byte)?(Result,?error)?{
????l?:=?newLex(input)
????_?=?yyParse(l)
????return?l.result,?l.err
}
//?手動定義詞法解析器
type?lex?struct?{
????input??*bytes.Buffer
????result?Result
????err????error
}
func?newLex(input?[]byte)?*lex?{
????return?&lex{
????????input:?bytes.NewBuffer(input),
????}
}
//?詞法分析器滿足Lex接口。能夠逐個讀取token。
//?如果是有效的電話號碼數字，返回D類型，并賦值lval.ch。
func?(l?*lex)?Lex(lval?*yySymType)?int?{
????b?:=?l.nextb()
????if?unicode.IsDigit(rune(b))?{
????????lval.ch?=?b
????????return?D
????}
????return?int(b)
}
func?(l?*lex)?nextb()?byte?{
????b,?err?:=?l.input.ReadByte()
????if?err?!=?nil?{
????????return?0
????}
????return?b
}
//?Error?satisfies?yyLexer.
func?(l?*lex)?Error(s?string)?{
????l.err?=?errors.New(s)
}
func?cat(bytes?...byte)?string?{
????var?out?string
????for?_,?b?:=?range?bytes?{
????????out?+=?string(b)
????}
????return?out
}