本節書摘來自華章社群《編譯與反編譯技術實戰》一書中的第3章，第3.3節詞法分析器的lex實作，作者劉曉楠 陶紅偉 嶽峰 戴超，更多章節内容可以通路雲栖社群“華章社群”公衆号檢視
3.3 詞法分析器的lex實作
由于程式設計語言中的單詞基本上都可用一組正規式來描述，是以，人們希望構造一個自動生成系統：對于一個給定的進階語言，隻要給出用來描述其各類單詞詞法結構的一組正規表達式，以及識别各類單詞時詞法分析程式應采取的語義動作，該系統便可自動産生此語言的詞法分析程式。1975年美國貝爾實驗室的m. lesk和schmidt基于正規式與有限自動機的理論研究，用c語言研制了一個詞法分析程式的自動生成工具lex。對任何進階程式語言，使用者隻需用正規式描述該語言的各個詞法類（這一描述稱為lex的源程式），lex就可以自動生成該語言的詞法分析程式。
3.3.1 lex源檔案結構
lex 的輸入是用lex源語言編寫的程式，它是擴充名為.l的檔案。lex源程式經lex 系統處理後輸出一個c 程式檔案，此檔案含有兩部分内容: 一個是依據正規式所建構的狀态轉移表； 另一個是用來驅動該狀态轉移表的總控程式yylex ()。該檔案再經過Ｃ編譯器的編譯就産生一個實際可以運作的詞法分析程式，其使用方法如圖3-4所示。
一般而言，一個lex 源程式由“% %”分隔的三個部分組成，其書寫格式為：
其中，定義部分和輔助函數部分是任選的，識别規則部分則是必備的。如果輔助函數部分預設， 則第二個分隔号“% %”可以省略；但由于第一個分隔号% %用來訓示識别規則部分的開始，故即使沒有定義部分， 也不能将其省略。下面将對這三部分的内容及其書寫格式作一概括性介紹。
1.定義部分
定義部分對規則部分要引用的檔案和變量進行說明，通常可包含頭檔案表、常數定義、全局變量定義、外部變量定義以及正規式定義等。正規式定義用來定義在規則部分引用的正規式，類似于Ｃ語言中的宏定義，是以也稱為宏定義。每一個宏定義由分隔符（适當個數的空格或制表字元） 連接配接的宏名字和宏内容組成：
其中，每個pi都是定義在Σ∪{d1 ，d2 ，… ,dn }上的正規式（ di 是定義部分所定義的宏名字），用來描述一種單詞模式；ai是一段c語言源代碼，用來指出當從輸入字元串中識别出詞型為pi的單詞時詞法分析器應執行的操作。每個pi都必須頂行書寫，并用分隔符（若幹個空格或tab字元）與其後的代碼段ai分開。每個代碼段ai可引用已定義的符号常量、全局變量和外部變量，并能調用輔助函數部分所定義的函數，必要時也可在ai中定義自己的局部變量。ai一般不必用花括号括起來，但若ai多于一行或者需要在其中定義局部變量，則應使用花括号并且左括号“{”一定要與相應的pi在同一行，以便确定這些局部變量的作用域。
3.輔助函數部分
在識别規則部分中所調用的函數若不是庫函數，則需要給出這些函數的定義。這些函數在輔助函數部分給出，由使用者用Ｃ語言編寫，它們由lex系統直接複制到輸出的c程式檔案之中。
表3-2中列出了lex中常用的一些變量和函數，在與正規式比對的動作或輔助過程中都可以使用。
例3.1 下面給出了一個lex源檔案，其功能是統計文本檔案中的字元數和行數。該程式首先定義了num_chars 和num_lines 兩個計數器，分别記錄文本檔案的字元數和行數。在lex 源檔案中定義兩個正規式“n”和“.”，分别用來比對換行符和任意字元，并且在識别這兩個正規式後其相應的計數器累加1，進而完成對檔案的字元數和行數的統計。
3.3.2 lex系統中的正規式
lex 源程式中在宏定義及識别規則部分都涉及許多正規式。這些正規式除應遵循正規式基本定義的規定外，為了便于使用者靈活、緊湊地構造複雜的正規式，lex還增添了若幹個運算符和新的構造規則，下面将結合這些新增的内容對lex系統中的正規式進行扼要說明。
lex系統中的正規式由通常的文字字元（下面稱為正文字元）和元字元組成。元字元一般用作運算符或控制符，常用的元字元有*、 +、 ?、 | 、{ }、 [ ]、() 、. ^ 、＄ 、” 、、 -、 / 、
<、 >。利用正文字元和元字元組成正規式的規則及其比對輸入串的規則分述如下。
（1）單個正文字元
單個正文字元c是正規式，用于比對與其相同的單個正文字元c。
如果上述元字元需要以正文字元的形式出現于正規式中，則需使用雙引号（"）或反斜線（）作為轉義字元将其變為正文字元，如" +"（或 +）和"-"（或-）在正規式中分别表示加号和減号。此外，c語言中的一些轉義字元序列也可出現在正規式中，如 b、 f 、 n 、
r、 s和 t 分别表示倒退、換頁、換行、回車、空格和制表。
（2）字元類
字元類是正規式，用于比對該字元類所确定的字元集合中的任一字元。
需要注意的是， 除^、 和-外，其餘元字元在方括号内失去其特殊含義。如果使一個字元類含有這3個字元中的某個字元，隻需要将其放在方括号内首字元或末字元的位置上，如[ - + .0 - 9 ] 和[ + .0 - 9 - ]均比對正号、負号、小數點和十進制數字中的任何字元。
（3）“連接配接”與“或”
設r1和r2是正規式，則r1r2（表示r1 和r2 的連接配接）和r1 | r2（表示r1或r2）也都是正規式。
（4）重複
設r為正規式，則“r *”表示r 可重複零次或任意多次，“r +”表示r可重複一次或任意多次，“r ?”表示r可有可無。
（5）通配符
“·”為通配符， 用來比對除換行之外的任何字元。例如，b·c 不但可以比對bnc、 bdc 及bvc 等， 而且還可比對rbyca 中的byc。
（6）行首字元串或行末字元串
以元字元上箭頭“^”開頭的字元串用于比對行首字元串，以元符号“＄”為末尾的字元串用于比對行末字元串。例如，^begin表示僅當字元串begin 出現在某一行的開頭才能獲得比對；end$表示僅當字元串end出現在一行的結尾才能獲得比對。這裡所說的一行的開頭， 是指整個輸入字元流的開始，或者緊跟在一個換行字元之後的位置，一行的結尾則指緊靠換行字元之左的位置。
（7）超前搜尋
“/”為超前搜尋符。設r1 和r2 是正規式，則r1/r2也都是正規式，其r1是否與一個字元串相比對取決于緊跟其後的超前搜尋部分是否與r2相比對。也就是說，r2僅作為r1獲得比對的條件，而非所要識别單詞詞型的一部分。例如， 為了識别fortran源程式中的關鍵字do，需采用超前搜尋技術， 相應的詞型可寫成
表示詞法分析程式在輸入緩沖區中超前掃描一串字母或數字，接着掃描等号以及後面的一串字母或者數字，最後掃描到逗号，才能确認關鍵字do得到識别。
3.3.3 lex 的使用方式
lex 通常有兩種使用方式：一種是将lex作為一個單獨的工具，用以生成所需的識别程式，這些識别程式多被用在諸如編輯器設計、指令行解釋、模式識别、資訊檢索以及開關系統等一些非開發編譯器的應用領域中；另一種是将lex和文法分析器自動生成工具（如yacc）結合起來使用，以生成一個編譯程式的掃描器和文法分析器。
lex 和yacc 的最初版本都是作為unix 系統下的工具軟體來運作的。假定已有命名為scanner.l 的lex 源檔案，則可在unix 系統下通過指令lex scanner.1調出lex 對其進行處理，處理結果是輸出名字為lex.yy.c 的c語言檔案。再用指令cc lex.yy.c-11調用c 編譯器對其進行編譯，編譯所得到的檔案a.out 便是可執行的詞法分析程式，其中選擇項“-11”表示需調用lex的庫。如果使用者需對所得目标代碼檔案命名，如将其命名為cifafenxi，則可用下面的指令進行編譯：
lex和yacc已經成功移植到windows系統下，parser generator便是其中常用的工具之一，該工具是windows 平台下的lex 和yacc內建環境，其利用lex 和yacc能夠生成visual c++、borland c++等c++代碼以及相關java代碼。parser generator 非常适合于與visual c++（簡稱vc++）內建，下面對該工具如何生成代碼并使用visual c++進行編譯做一簡要介紹。
在安裝了parser generator 後，在vc++中進行以下兩項設定，即可使vc++編譯和連結由parser generator 産生的檔案。
1.目錄設定
為了在vc++中可以找到lex 和yacc 的頭檔案lex.h 和yacc.h，以及lex 和yacc 的庫檔案，需要對vc++進行相關的目錄設定。
1）選擇tools菜單中的options 指令，打開options 對話框。
2）選擇directories 頁籤。
3）在show directories for 下拉清單框中選擇include files，在directories 框中單擊最後的空目錄，并填入c:pargeninclude（其中c:pargen 是parser generator 的安裝路徑，下同）。
4）在show directories for 下拉清單框中選擇library files，在directories 框中單擊最後的空目錄，并填入c:pargenlibmsvc32。
5）在show directories for 下拉清單框中選擇source files，在directories 框中單擊最後的空目錄，并填入c:pargen source。
6）單擊ok 按鈕，options 對話框設定完畢。
2.項目設定
對每個vc++項目，都需進行以下設定，以使vc++可以從特定的庫中接收lex和yacc所需要的函數和變量。
1）選擇project菜單中的settings 指令，打開project settings 對話框。
2）在settings for 下拉清單框中選擇win32 debug。
3）選擇c/c++頁籤，在category下拉清單框中選擇general。在preprocessor definitions框中，在目前文本的最後輸入“,yydebug”。
4）選擇link 頁籤，在category 下拉清單框中選擇general。在object/library modules框中，在目前文本的最後輸入“yl.lib”。
5）單擊ok 按鈕，project settings 對話框設定完畢。
3.3.4 lex 源檔案示例——c語言詞法分析器
在本小節，我們給出一個針對c 語言單詞識别的lex 源程式檔案c.lex， 以供參考。該源程式所涉及的各種單詞符号和種别編碼參見表3-1，在該源程式中針對常數類單詞隻考慮了十進制整型常數。該檔案已在parser generator 環境下編譯調試通過。為便于閱讀， 特作以下說明：
1）程式前面的行号是為了便于下面的說明而給出的，真正的lex 程式不能書寫行号。
2）第1行到第84行介于“%{”和“%}”之間的内容将直接插入由lex産生的Ｃ程式中，第5行至第83行列出了c 語言各類單詞的名字及其相應的種别編碼定義。
3）第85行到第89行為正規式的宏定義，white代表制表、換行及空格三個字元中的任一字元，把它們均視為“空白字元”。digit代表0到9中的任一數字，letter代表任一大寫或者小寫字母，number代表十進制整數，id代表c語言中的辨別符。
4）第91行到第174行之間為識别規則部分。第91行表示在遇到空白符時，不需要進行任何語義處理，用一個空語句表示，這樣就可以将輸入字元串的全部空白符過濾掉。第92行和第93行對注釋進行處理。第94 行到第173行表示在識别出辨別符、十進制整型常數、關鍵字和運算符時輸出其相應的種别編碼。第174 行中的“.”表示不能與第91行到第173行正規式比對的其他字元。
5）第176行到第180行為主函數，打開輸入輸出檔案。其中，yylex()是詞法分析程式的入口點，每次調用yylex()，就可以從被編譯的源程式中得到一個單詞。如果正規式的相關動作中無return語句，則yylex()并不傳回值，如此例中第94行到第174行，相關的動作隻是向檔案result.txt中輸出某些提示資訊。
下面為c 語言掃描器的lex 源檔案c.lex。