正規文法在詞法分析器建模中的應用研究

羅海麗

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010)

1.引言

軟件所對應的問題域可看作信息的集合，信息就是符號串，問題域就是符號串的集合。問題域中的符號串都應遵從該問題域中的特定規則，即問題域可看作符合某種規則的符號串的集合。語言可定義為符合某種規則的符號串的集合，所以問題域可看作某種語言。文法是語言的一種建模工具，因此文法也是問題域的建模工具。建模是詞法分析器構造的基礎，對詞法分析器建模的核心是選擇一種恰當的工具描述詞法，正規文法是描述詞法的最佳工具。利用正規文法可對詞法分析器進行建模，進而構造詞法分析器，用這種方法構造的詞法分析器形式化程度更高、更高效，這種構造詞法分析器的方法比其它方法更為簡潔。

2.利用正規文法對詞法分析器建模

2.1 正規文法的概念

文法 G 可定義為四元組（VN，VT，P，S），其中 VN為非終結符的集合，VT為終結符的集合，P為產生式的集合，S為開始符號。若P中的每個產生式的形式都是A→аB或A→а，其中A、B都是非終結符，а∈VT*,則G是正規文法。[1]

文法可用來描述某種語言中的句子所遵從的規則，用正規文法所描述的規則更適于被計算機進行高效的處理。

2.2 詞法分析器的功能

詞法分析器的任務是從左到右逐個字符地讀入源程序或文檔，對構成源程序或文檔的字符流進行掃描和分解，從而識別出一個個單詞。這里所謂的單詞是指邏輯上緊密相連的一組字符，這些字符具有集體的含義。比如程序設計語言中的標識符是以字母開頭，后跟字母、數字字符的字符序列組成的一種單詞。關鍵字是一種單詞，此外還有運算符、界符等。[2]

詞法分析器可應用于語言編譯器、文檔編輯器等軟件中進行詞法檢查。

2.3 用正規文法建立PL/0語言的詞法模型

以PL/0語言為例，用正規文法建立其詞法模型。用正規文法建立PL/0語言的詞法模型如下：

<標識符>→l∣l<字母數字>

<字母數字>→l∣d∣l<字母數字>∣d<字母數字>

<無符號整數>→d∣d<無符號整數>

<運算符>→+∣-∣*∣/∣=∣#∣<∣>∣<<等號>∣><等號>∣：<等號>

<等號>→=

< 界符 >→,∣;∣.∣（∣）

其中l表示a——z中的任何一個字母，d表示0——9中的任何一個數字。

關鍵字也是一種單詞，關鍵字集合是標識符集合的子集，關鍵字與標識符的構詞原則相同。

整數前面的正負號在詞法分析中可看作運算符，因此只定義無符號整數的詞法。

3.詞法分析器的構造

以PL/0語言為例，構造PL/0語言的詞法分析器。

3.1 將詞法模型轉化為DFA

將2.3中給出的用正規文法建立的PL/0語言的詞法模型轉化為一個確定的有窮自動機（DFA）。

(1)將各類單詞的正規文法轉化為DFA

2.3中給出用正規文法建立的PL/0語言的詞法模型，將各類單詞的正規文法轉化為一個DFA。

例如，標識符的正規文法為：<標識符>→l∣l<字母數字>，<字母數字>→l∣d∣l<字母數字>∣d<字母數字>。首先，將該標識符的正規文法轉化為一個NFA=({X,Q0,Q1,Y},{l,d},f1,{X},{Y})，其中，映射為 f1，f1(x,l)={Q0},f1(Q0,ε)=Q1,f1(Q1,l)=Q1,f1(Q1,d)=Q1,f1(Q1,ε)=Y。

然后，用子集法將該NFA轉化為DFA=({0,1,2},{l,d},f2,0,{1,2}),其中 f2(0,l)=1,f2(1,l)=2,f2(1,d)=2,f2(2,l)=2,f2(2,d)=2。

最后，將該DFA化簡為一個最小的DFA=（{0,1},{l,d},f3,0,{1}）,其中f3(0,l)=1,f3(1,l)=1,f3(1,d)=1。初態0表示準備識別單詞的狀態，0狀態下接收到字母轉向狀態1，狀態1為正在識別標識符的狀態。[3]

同理，常數的正規文法<無符號整數>→d∣d<無符號整數>經過一系列轉化可得一個最小的DFA=({0,2},g0gggggg,f4,0,{2}),其中f4(0,d)=2,f4(2,d)=2,初態0表示準備識別單詞的狀態，0狀態下接收到數字轉向狀態2，狀態2表示正在識別常數的狀態。

其它各類單詞的正規文法均可按相同方法構造DFA，所有這些DFA都有相同的初態0，初態0均為準備識別單詞的狀態。

(2)將各類單詞正規文法對應的DFA按相同的初態0連接成一個完整的DFA M

其中，映射f定義如下：

該DFA M表示在準備識別單詞的狀態下,根據所接收到的符號轉向不同的后繼狀態，若后繼狀態為終態則終態之前接收到的符號串構成一個單詞，此時識別出一個PL/0語言的合法單詞。該DFA M能識別的符號串的全體即為所有PL/0語言的合法單詞。

3.2 構造控制程序

詞法分析器中的控制程序如圖1所示。

圖1中的限制條件是指控制程序已讀入的符號串的長度是否大于正在識別的單詞的最大長度。

當控制程序識別出一個以字母開頭的字母數字串時，須區分該單詞是標識符還是關鍵字，此時控制程序中識別出一個單詞的后續處理部分須完成區分工作。例如，可建立一張關鍵字表，其中存放PL/0語言中的所有關鍵字，當識別出一個字母數字串時，則查關鍵字表，若此單詞在關鍵字表中，則為關鍵字，否則為標識符。[4]

圖1 控制程序

3.3 詞法分析器進行詞法分析的過程

DFA M和圖1的控制程序配合即為PL/0語言的詞法分析程序，它可以對PL/0源程序進行詞法分析。下面以一例說明詞法分析過程。

例如一段PL/0語言源程序…X：=a09+90；…

假設，PL/0語言中標識符最大長度為3，則當識別標識符時，控制程序中的限制條件為已接收字符串長度是否大于3；常數最大長度為2，則當識別常數時，控制程序中的限制條件為已接收字符串長度是否大于2；>=，<=,：=長度為2，識別這三個單詞時，控制程序中的限制條件為已接收字符串長度是否大于2；剩余其它運算符分界符長度均為1，識別這些單詞時，控制程序中的限制條件為已接收字符串長度是否大于1。

詞法分析時，首先啟動控制程序，DFA初態0作為當前狀態，從源文件中讀入一個字符X，接收到的第一個符號是字母，說明開始識別一個標識符，查DFA，0狀態下接收符號X轉向后繼狀態1，由于當前已接收符號個數為1不大于3，所以不滿足限制條件，后繼狀態1變為當前狀態，繼續讀下一個符號：，查DFA，1狀態下接收符號：，無后繼狀態，當前狀態1為終態，此時終態1之前接收的符號串X即為一個單詞。至此控制程序執行完一次，識別出一個單詞X。繼續調用一次控制程序，與上一次過程類似，又可識別出下一個單詞：=,調用一次控制程序，便可識別出一個單詞，這樣不斷調用控制程序，便可不斷從源文件中識別單詞，達到詞法分析的目的。

4.結論

利用正規文法對詞法分析器建模，就是用正規文法描述詞法。描述詞法的正規文法可轉化為一個確定的有窮自動機，該有窮自動機表達了識別單詞的動態過程。有窮自動機配合控制程序便可構成詞法分析器，這種構造詞法分析器的方法更為簡潔、高效。

[1]何炎祥，伍春香，王漢飛.編譯原理[M].北京：機械工業出版社，2010.

[2]張素琴，呂映芝，蔣維杜.編譯原理（第2版）[M].北京：清華大學出版社，2005.

[3]葛寒松.正規文法與有限自動機的等價性研究[J].商丘師范學院學報，2010，26（12）：75-77.

[4]羅海麗.基于LEX語言的詞法分析程序自動構造過程[J].內蒙古科技大學學報，2005，24（4）：314-317.