編譯器詞法分析程序實現探討

朱朝霞

（長江大學計算機科學學院，荊州434023）

0 引言

編譯原理是計算機學科的一門專業核心課程，在計算機科學領域中具有重要地位，學習編譯原理課程的目的在于讓學生系統地了解并掌握程序設計語言編譯器的構造原理及實現技術。詞法分析是編譯程序的第一步，其主要任務是掃描源程序，按構詞規則識別單詞，并報告發現的詞法錯誤。構造程序設計語言的詞法分析程序有手工生成和自動生成2種方法，在本課程的教學中筆者發現很多同學不能理解詞法分析的2種生成方法的實質，以至于很難真正掌握詞法分析技術。本文以詞法分析程序的實現為主線，剖析手工實現與自動生成的本質與區別，以對編譯原理教學有所啟發。

1 單詞的描述

為構造識別語言單詞符號的詞法分析程序，必須先對單詞進行結構描述。目前，多數程序設計語言的單詞符號都能使用正規文法或正規式進行描述。

例如以“標識符”為例，用正規文法描述可寫為：

＜標識符＞→l｜l＜字母數字＞

＜字母數字＞→l｜d｜l＜字母數字＞｜d＜字母數字＞

用正規式描述可寫為：字母（字母｜數字）＊

其中l代表a～z中任一英文字母；d代表0～9中任一數字。2種定義方式各有不同的特點，用正規式定義簡潔清晰，用正規文法定義單詞易于識別。

2 詞法分析程序的實現

構造詞法分析程序有2種方法：一是通過手工方式實現，即根據識別語言單詞的狀態轉換圖，使用某種高級語言直接編寫詞法分析程序；二是利用詞法分析程序的自動生成工具自動生成。

2.1 詞法分析程序的手工實現

一個詞法分析程序手工生成可通過以下步驟得到：

（1）根據語言的詞法規則寫出描述單詞的正規文法或正規式；

（2）將正規文法或正規式轉換成相應的狀態轉換圖NFA（Nondeterministic Finite Automata）；

（3）將NFA確定化并最小化轉換為DFA（Deterministic Finite Automata）；

（4）將最小化的DFA轉換成算法的流程圖，進而實現詞法分析程序。

用圖1可描述為：

圖1 詞法分析程序的手工生成

可見，詞法分析程序的手工生成其實質是通過有窮自動機來實現詞法分析程序，只要構造出識別語言單詞符號的有窮自動機，就很容易構造出識別語言單詞符號的詞法分析程序。狀態轉換圖實際上是詞法分析程序的流程圖。

編譯程序的詞法分析采用手工實現具有工作量大，維護困難等缺點，現在多數編譯器的詞法分析程序都是利用自動生成工具來完成，從而省掉了手工編寫詞法分析程序的煩瑣工作。

2.2 詞法分析程序的自動生成

詞法分析程序的自動生成是指由一個自動生成程序來生成詞法分析程序。目前，詞法分析程序自動生成工具有1972年美國Bell實驗室用C語言研制的詞法分析程序自動生成工具LEX（Lexical Analyzer Generator），可在 UNIX、Linux、DOS、Windows等環境下運行。其工作原理是將LEX源程序中的正規式轉換成相應的DFA，并將相應的動作插入到輸出的詞法分析器中適當的地方，控制流由該DFA的解釋掌握。其中LEX源程序用來描述各類語言的語法，由說明部分、識別規則和輔助過程3部分組成。

LEX的使用流程為：

（1）使用正規式描述語言的詞法并編寫LEX源文件；

（2）編譯運行LEX源文件，產生LEX語言目標程序文件lex.yy.c；

（3）lex.yy.c程序經由C編譯，并和其他 C模塊連接產生執行文件a.out（即詞法分析程序）；

（4）調試執行文件，直至將輸入字符流變換成正確的單詞流。

LEX必須和C一起使用，LEX源文件含有大量的C語言程序，并且LEX不能檢測源文件中C代碼的任何錯誤。詞法分析自動生成的流程可用圖2表示。

圖2 使用LEX生成詞法分析程序

例：下面以C語言的標識符、部分關鍵字、運算符和分界符為例構造其LEX源程序。

程序中1～4行為插入到LEX產生的C程序中，位于任何過程的外部；5～8行為正規式的定義；9～15行為識別規則部分；11～13行表示在識別標識符、關鍵字、運算符和界符時輸出不同的內容。22～26行為主函數，打開輸入輸出文件。此LEX源程序經過LEX編譯器運行，產生一個C語言程序lex.yy.c，經過C語言編譯器編譯后生成詞法分析程序a.out，此時輸入下段C語言源程序

由上例可見，對于任何一種高級語言，若要構造其詞法分析程序，只須用LEX源程序描述該語言的語法，LEX編譯系統對LEX源程序處理后，便可產生這種高級語言的詞法分析程序。

3 結語

詞法分析程序使用高級語言手工生成，程序結構復雜，不易修改。詞法分析程序利用自動工具實現，程序結構簡單，并將詞法分析的重點放在正規表達式的描述和識別正規表達式之后的處理上，更易于維護詞法分析器。正確理解詞法分析程序手工生成與自動生成2種方法的實質及區別，對于正確理解程序設計語言編譯程序的構造原理及編譯原理課程的教學具有重要意義。

[1]朱朝霞，周云才.編譯技術語法分析實踐教學探討[J].北京教育學院學報，2008，3（3）：11－14.

[2]李冬梅，施?；?編譯原理[M].北京：人民郵電出版社，2006：50－100.

[3]張素琴，呂映芝.編譯原理[M].北京：清華大學出版社，2005：50－67.

[4]張幸兒.編譯原理編譯程序構造與實踐[M].北京：機械工業出版社，2008：46－81.

[5]胡倫駿，徐蘭芳.編譯原理[M].北京：電子工業出版社，2004：173－177.

[6]張昱，陳意云.編譯原理與技術[M].北京：高等教育出版社，2010：13－37.

[7]蔣宗禮，姜守旭.編譯原理[M].北京：高等教育出版社，2010：64－112.