Parser 開發工具 - lex 與 yacc
lex (Lexical Analyzar) 及 yacc(Yet Another Compiler Compiler) 是用來輔助程式設計師製作語法剖析器(Parser)的程式工具。程式開發中，只要是在輸入中搜尋樣式(pattern)，或是需要在命令列中處理輸入的程式，都會用到lex和yacc。
- lex的工作主要是幫助我們將輸入的資料文字串流分解成一個個有意義的標記(token)，也就是處理構詞學(morphology)上的問題。
- yacc的工作主要是幫我們分析這些標記和我們定義的規則作匹配，也就是處理句法學(syntax)上的問題。
和傳統其他 UNIX 工具一樣，lex 和 yacc 的功能強大，操作變化多端，包含許多抽象的用法，學習曲線陡峭，但一學起來便有功力大增的感覺！
Lex (Lexical Analyzar)
Lex 是一種生成掃描器(Scanner)的工具，主要功能是切出所有的標記(token)。
具體而言，掃描器是一種識別文本中字串樣式(pattern)的程式，這些字串樣式在一種特殊的句構中定義，該句構稱為正則表達式(Regular Expression)。
當 Lex 接收到文本輸入時，他會試圖將文本與正則表達式進行匹配。 它一次讀一個字符，直到找到一個匹配的樣式。
- 如果能夠找到一個匹配的樣式，Lex就執行相關的動作，而這個動作通常包括返回一個標記。
- 如果沒有可以匹配的正則表達式，將會停止進一步的處理，Lex 將顯示一個錯誤消息。
Lex 和 C 是強耦合的，一個 .lex 文件通過lex公用程式來傳遞，並生成C的輸出文件。這些文件被編譯為詞法分析器(parser)的可執行版本。
1. lex檔案內容
lex定義的檔案內容以符號%%分為三大區塊
- 定義區 : lex載入定義檔為我們產生字彙剖析器的程式碼時，會原封不動的把這一區塊個的程式碼複製過去，而不會對這部份程式碼作任何處理。
- 樣式區 : 主要區塊，放置正則表達式定義的樣式以及對應的動作程式碼。
- 程式碼區 : 和定義區一樣，lex在最後為我們產生字彙剖析器(parser)的程式碼時也會原封不動的複製過去，而不作任何處理。
%{
... 定義 ...
%}
%%
... 樣式 ...
%%
... 程式 ...
2. lex各區整合範例：統計字串長度
int lengs[100]; %% [a-z]+ lengs[yyleng]++; . | \n ; %% yywrap() { int i; printf("Length No. words\n"); for(i=0; i<100; i++) if (lengs[i] > 0) printf("%5d%10d\n",i,lengs[i]); return(1); }
注意事項：
- 如果要將變數值紀錄下來，則要將該值放在yylval中，剖析器Yacc才能在 $NUMBER 中得到變數值。
- 例如: ([-]?)[0-9]+ {sscanf(yytext, "%f", &yylval.floatVal); return NUMBER;}
- 如果在匹配字串時兩條的前綴(prefix)相同(產生相同的token)，則會選擇長的那一條為優先。如果長度仍相同的話，則不一定。
Reference
很讚的遊戲編輯器 - 以lex/yacc實作算式計算機
IBM - Yacc 與 Lex 快速入門
發表文章
