朱朝霞

（長江大學(xué)計算機科學(xué)學(xué)院，荊州434023）

0 引言

編譯原理是計算機學(xué)科的一門專業(yè)核心課程，在計算機科學(xué)領(lǐng)域中具有重要地位，學(xué)習(xí)編譯原理課程的目的在于讓學(xué)生系統(tǒng)地了解并掌握程序設(shè)計語言編譯器的構(gòu)造原理及實現(xiàn)技術(shù)。詞法分析是編譯程序的第一步，其主要任務(wù)是掃描源程序，按構(gòu)詞規(guī)則識別單詞，并報告發(fā)現(xiàn)的詞法錯誤。構(gòu)造程序設(shè)計語言的詞法分析程序有手工生成和自動生成2種方法，在本課程的教學(xué)中筆者發(fā)現(xiàn)很多同學(xué)不能理解詞法分析的2種生成方法的實質(zhì)，以至于很難真正掌握詞法分析技術(shù)。本文以詞法分析程序的實現(xiàn)為主線，剖析手工實現(xiàn)與自動生成的本質(zhì)與區(qū)別，以對編譯原理教學(xué)有所啟發(fā)。

1 單詞的描述

為構(gòu)造識別語言單詞符號的詞法分析程序，必須先對單詞進行結(jié)構(gòu)描述。目前，多數(shù)程序設(shè)計語言的單詞符號都能使用正規(guī)文法或正規(guī)式進行描述。

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

＜標識符＞→l｜l＜字母數(shù)字＞

＜字母數(shù)字＞→l｜d｜l＜字母數(shù)字＞｜d＜字母數(shù)字＞

用正規(guī)式描述可寫為：字母（字母｜數(shù)字）＊

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

2 詞法分析程序的實現(xiàn)

構(gòu)造詞法分析程序有2種方法：一是通過手工方式實現(xiàn)，即根據(jù)識別語言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級語言直接編寫詞法分析程序；二是利用詞法分析程序的自動生成工具自動生成。

2.1 詞法分析程序的手工實現(xiàn)

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

（1）根據(jù)語言的詞法規(guī)則寫出描述單詞的正規(guī)文法或正規(guī)式；

（2）將正規(guī)文法或正規(guī)式轉(zhuǎn)換成相應(yīng)的狀態(tài)轉(zhuǎn)換圖NFA（Nondeterministic Finite Automata）；

（3）將NFA確定化并最小化轉(zhuǎn)換為DFA（Deterministic Finite Automata）；

（4）將最小化的DFA轉(zhuǎn)換成算法的流程圖，進而實現(xiàn)詞法分析程序。

用圖1可描述為：

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

可見，詞法分析程序的手工生成其實質(zhì)是通過有窮自動機來實現(xiàn)詞法分析程序，只要構(gòu)造出識別語言單詞符號的有窮自動機，就很容易構(gòu)造出識別語言單詞符號的詞法分析程序。狀態(tài)轉(zhuǎn)換圖實際上是詞法分析程序的流程圖。

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

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

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

LEX的使用流程為：

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

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

（3）lex.yy.c程序經(jīng)由C編譯，并和其他 C模塊連接產(chǎn)生執(zhí)行文件a.out（即詞法分析程序）；

（4）調(diào)試執(zhí)行文件，直至將輸入字符流變換成正確的單詞流。

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

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

例：下面以C語言的標識符、部分關(guān)鍵字、運算符和分界符為例構(gòu)造其LEX源程序。

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

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

3 結(jié)語

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

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

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

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

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

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

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

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