《編譯與反編譯技術》—第2章2.5詞法分析器的生成器

本節書摘來自華章出版社《編譯與反編譯技術》一書中的第2章，第2.5節詞法分析器的生成器，作者龐建民，陶紅偉，劉曉楠，嶽峰，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

2.5　詞法分析器的生成器

鑒于各種不同的進階程式語言中單詞的總體結構大緻相同，基本上都可用一組正規式來描述，是以，人們希望構造一個自動生成系統：對于一個給定的進階語言，隻要給出用來描述其各類單詞詞法結構的一組正規表達式，以及識别各類單詞時詞法分析程式應采取的語義動作，則該系統便可自動産生此語言的詞法分析程式。

1975年美國bell實驗室的m.lesk和schmidt基于正規式與有限自動機的理論研究，用c語言研制了一個詞法分析程式的自動生成工具lex。對任何進階程式語言，使用者隻需用正規式描述該語言的各個詞法類（這一描述稱為lex的源程式），lex就可以自動生成該語言的詞法分析程式。lex及其編譯系統的作用如圖2-29所示。

一般而言，lex源程式由用“%%”分隔的三部分組成：第一部分為聲明，第二部分為識别規則，最後一部分為輔助過程。其書寫格式為：

聲明部分

%%

識别規則部分

輔助過程部分

其中，聲明部分和輔助過程部分是任選的，而識别規則部分是必需的。如果輔助過程部分預設，則第二個分隔符号“%%”可以省去；但如果無聲明部分，第一個分隔符号“%%”不能省去，因為第一個分隔符号是用于訓示識别規則部分的開始。下面将對這三部分的内容及其書寫格式進行概括介紹。

聲明部分包括變量說明、辨別符常量說明和正規定義等。正規定義中的名字可在識别規則中用作正規式的成分。其中除了正規定義式之外的聲明必須用“%{”和“}%”括起來。

識别規則部分是具有如下形式的語句序列：

p1 { 動作1 }

p2 { 動作2 }

…

pn { 動作n }

其中，pi是一個正規式，描述一種單詞模式；動作i是c語言的程式段，表示當一個串比對模式pi時，詞法分析器應執行的動作。

輔助過程是對識别規則的補充，識别規則部分中某些動作需要調用的過程，如果不是c 語言的庫函數，則要在此給出具體的定義。

下面給出一個簡單語言的單詞符号的lex源程式例子，其輸出單詞的類别編碼用整數編碼表示。

例2.28　下面是識别表2-1中單詞符号的lex源程式。

/該過程負責把單詞插入符号表并傳回指針，yytext 指向該單詞的第一個字元，yyleng 給出它的長度。如果該單詞已經出現在符号表中，則傳回指向該單詞所在表項的指針，否則為它建立一個新表項，将單詞填入該表項中，并傳回指向新表項的指針/

lex可以用兩種方式來使用：一種是将lex作為一個單獨的工具，用以生成所需的識别程式；另一種是将lex與文法分析器自動生成工具（如yacc）結合起來使用，以生成一個編譯程式的掃描器和文法分析器。