正規(guī)文法在詞法分析器建模中的應(yīng)用研究

羅海麗

(內(nèi)蒙古科技大學(xué) 信息工程學(xué)院，內(nèi)蒙古 包頭 014010)

1.引言

軟件所對應(yīng)的問題域可看作信息的集合，信息就是符號串，問題域就是符號串的集合。問題域中的符號串都應(yīng)遵從該問題域中的特定規(guī)則，即問題域可看作符合某種規(guī)則的符號串的集合。語言可定義為符合某種規(guī)則的符號串的集合，所以問題域可看作某種語言。文法是語言的一種建模工具，因此文法也是問題域的建模工具。建模是詞法分析器構(gòu)造的基礎(chǔ)，對詞法分析器建模的核心是選擇一種恰當(dāng)?shù)墓ぞ呙枋鲈~法，正規(guī)文法是描述詞法的最佳工具。利用正規(guī)文法可對詞法分析器進(jìn)行建模，進(jìn)而構(gòu)造詞法分析器，用這種方法構(gòu)造的詞法分析器形式化程度更高、更高效，這種構(gòu)造詞法分析器的方法比其它方法更為簡潔。

2.利用正規(guī)文法對詞法分析器建模

2.1 正規(guī)文法的概念

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

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

2.2 詞法分析器的功能

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

詞法分析器可應(yīng)用于語言編譯器、文檔編輯器等軟件中進(jìn)行詞法檢查。

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

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

<標(biāo)識(shí)符>→l∣l<字母數(shù)字>

<字母數(shù)字>→l∣d∣l<字母數(shù)字>∣d<字母數(shù)字>

<無符號整數(shù)>→d∣d<無符號整數(shù)>

<運(yùn)算符>→+∣-∣*∣/∣=∣#∣<∣>∣<<等號>∣><等號>∣：<等號>

<等號>→=

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

其中l(wèi)表示a——z中的任何一個(gè)字母，d表示0——9中的任何一個(gè)數(shù)字。

關(guān)鍵字也是一種單詞，關(guān)鍵字集合是標(biāo)識(shí)符集合的子集，關(guān)鍵字與標(biāo)識(shí)符的構(gòu)詞原則相同。

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

3.詞法分析器的構(gòu)造

以PL/0語言為例，構(gòu)造PL/0語言的詞法分析器。

3.1 將詞法模型轉(zhuǎn)化為DFA

將2.3中給出的用正規(guī)文法建立的PL/0語言的詞法模型轉(zhuǎn)化為一個(gè)確定的有窮自動(dòng)機(jī)（DFA）。

(1)將各類單詞的正規(guī)文法轉(zhuǎn)化為DFA

2.3中給出用正規(guī)文法建立的PL/0語言的詞法模型，將各類單詞的正規(guī)文法轉(zhuǎn)化為一個(gè)DFA。

例如，標(biāo)識(shí)符的正規(guī)文法為：<標(biāo)識(shí)符>→l∣l<字母數(shù)字>，<字母數(shù)字>→l∣d∣l<字母數(shù)字>∣d<字母數(shù)字>。首先，將該標(biāo)識(shí)符的正規(guī)文法轉(zhuǎn)化為一個(gè)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轉(zhuǎn)化為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化簡為一個(gè)最小的DFA=（{0,1},{l,d},f3,0,{1}）,其中f3(0,l)=1,f3(1,l)=1,f3(1,d)=1。初態(tài)0表示準(zhǔn)備識(shí)別單詞的狀態(tài)，0狀態(tài)下接收到字母轉(zhuǎn)向狀態(tài)1，狀態(tài)1為正在識(shí)別標(biāo)識(shí)符的狀態(tài)。[3]

同理，常數(shù)的正規(guī)文法<無符號整數(shù)>→d∣d<無符號整數(shù)>經(jīng)過一系列轉(zhuǎn)化可得一個(gè)最小的DFA=({0,2},j5i0abt0b,f4,0,{2}),其中f4(0,d)=2,f4(2,d)=2,初態(tài)0表示準(zhǔn)備識(shí)別單詞的狀態(tài)，0狀態(tài)下接收到數(shù)字轉(zhuǎn)向狀態(tài)2，狀態(tài)2表示正在識(shí)別常數(shù)的狀態(tài)。

其它各類單詞的正規(guī)文法均可按相同方法構(gòu)造DFA，所有這些DFA都有相同的初態(tài)0，初態(tài)0均為準(zhǔn)備識(shí)別單詞的狀態(tài)。

(2)將各類單詞正規(guī)文法對應(yīng)的DFA按相同的初態(tài)0連接成一個(gè)完整的DFA M

其中，映射f定義如下：

該DFA M表示在準(zhǔn)備識(shí)別單詞的狀態(tài)下,根據(jù)所接收到的符號轉(zhuǎn)向不同的后繼狀態(tài)，若后繼狀態(tài)為終態(tài)則終態(tài)之前接收到的符號串構(gòu)成一個(gè)單詞，此時(shí)識(shí)別出一個(gè)PL/0語言的合法單詞。該DFA M能識(shí)別的符號串的全體即為所有PL/0語言的合法單詞。

3.2 構(gòu)造控制程序

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

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

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

圖1 控制程序

3.3 詞法分析器進(jìn)行詞法分析的過程

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

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

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

詞法分析時(shí)，首先啟動(dòng)控制程序，DFA初態(tài)0作為當(dāng)前狀態(tài)，從源文件中讀入一個(gè)字符X，接收到的第一個(gè)符號是字母，說明開始識(shí)別一個(gè)標(biāo)識(shí)符，查DFA，0狀態(tài)下接收符號X轉(zhuǎn)向后繼狀態(tài)1，由于當(dāng)前已接收符號個(gè)數(shù)為1不大于3，所以不滿足限制條件，后繼狀態(tài)1變?yōu)楫?dāng)前狀態(tài)，繼續(xù)讀下一個(gè)符號：，查DFA，1狀態(tài)下接收符號：，無后繼狀態(tài)，當(dāng)前狀態(tài)1為終態(tài)，此時(shí)終態(tài)1之前接收的符號串X即為一個(gè)單詞。至此控制程序執(zhí)行完一次，識(shí)別出一個(gè)單詞X。繼續(xù)調(diào)用一次控制程序，與上一次過程類似，又可識(shí)別出下一個(gè)單詞：=,調(diào)用一次控制程序，便可識(shí)別出一個(gè)單詞，這樣不斷調(diào)用控制程序，便可不斷從源文件中識(shí)別單詞，達(dá)到詞法分析的目的。

4.結(jié)論

利用正規(guī)文法對詞法分析器建模，就是用正規(guī)文法描述詞法。描述詞法的正規(guī)文法可轉(zhuǎn)化為一個(gè)確定的有窮自動(dòng)機(jī)，該有窮自動(dòng)機(jī)表達(dá)了識(shí)別單詞的動(dòng)態(tài)過程。有窮自動(dòng)機(jī)配合控制程序便可構(gòu)成詞法分析器，這種構(gòu)造詞法分析器的方法更為簡潔、高效。

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

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

[3]葛寒松.正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性研究[J].商丘師范學(xué)院學(xué)報(bào)，2010，26（12）：75-77.

[4]羅海麗.基于LEX語言的詞法分析程序自動(dòng)構(gòu)造過程[J].內(nèi)蒙古科技大學(xué)學(xué)報(bào)，2005，24（4）：314-317.