【正文】 2,13} {14,15} {14,15} {16} ④ 重新標(biāo)記，構(gòu)造 DFA M39。 狀態(tài) /字符 α β = + * , 。 ( ) 0 1 2 3 4 5 6 7 8 9 10 1 11 11 2 12 3 4 13 5 6 7 8 9 10 11 11 11 12 12 13 注： 0為初態(tài)，其余均為終態(tài)。 ㈢ 掃描器控制程序工作原理 ?每次識(shí)別單詞，控制程序總是從初態(tài)出發(fā)，不斷讀入字符，進(jìn)入下一狀態(tài)，尋求最長(zhǎng)匹配，直到無(wú)法前進(jìn)為止，這樣始終多讀一個(gè)字符。 ?在狀態(tài)遷移過(guò)程中，需用 Token數(shù)組保存讀入字符。 ?在無(wú)法前進(jìn)時(shí)，若發(fā)現(xiàn)當(dāng)前狀態(tài)為終態(tài)，則認(rèn)為識(shí)別出一個(gè)單詞，反之出錯(cuò)，即 Token數(shù)組所保存的字符串不構(gòu)成一個(gè)單詞，而是源程序中的一個(gè)錯(cuò)誤詞形。 ?事先設(shè)置一個(gè)單詞二元式編碼表，它包括除標(biāo)識(shí)符和整常數(shù)以外的所有單詞（基本字、運(yùn)算符和界符）。當(dāng) DFA識(shí)別出一個(gè)單詞，就根據(jù) Token數(shù)組所保存的字符串去查表。 ?若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為標(biāo)識(shí)符和整常數(shù)二者之一，只要稍加判斷即可區(qū)分。首字符為字母的是標(biāo)識(shí)符，首字符為數(shù)字的是無(wú)符號(hào)整常數(shù)。 ?DFA每次只能識(shí)別一個(gè)單詞，需多次使用 DFA來(lái)識(shí)別源程序中單詞，直到源程序中的字符全部處理完。 ?由于構(gòu)造的方法不同，在 DFA某一個(gè)終態(tài)中，有可能包含原 NFA中的二個(gè)終態(tài)或更多，即在該狀態(tài)可識(shí)別出二個(gè)詞形相似的單詞，這就存在一個(gè)優(yōu)先匹配問(wèn)題。此時(shí)，需調(diào)整單詞二元式編碼表中的單詞排列順序，將需優(yōu)先匹配的單詞排在表的較前面，這樣在單詞查找過(guò)程，讓其先得到匹配。 設(shè)源程序?yàn)椤?x+++y”（‘ ?是預(yù)處理程序添加的），掃描器共使用確定有限自動(dòng)機(jī) 5次（見(jiàn)下頁(yè)）。 ?從初態(tài) 0出發(fā)，讀入 39。x39。進(jìn)入狀態(tài) 1，在狀態(tài) 1讀入 39。+39。，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài) 1為終態(tài)，故識(shí)別出一個(gè)單詞。查表未果，由于首字符為字母，故單詞 x為標(biāo)識(shí)符，返回單詞二元式編碼 (39。i39。,x)并退回 39。+39。 ?從初態(tài) 0出發(fā)，讀入 39。+39。進(jìn)入狀態(tài) 4，在狀態(tài) 4讀入 39。+39。，進(jìn)入終態(tài)13，在狀態(tài) 13讀入 39。+39。，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài) 13為終態(tài)，故識(shí)別出一個(gè)單詞。查表，確認(rèn)識(shí)別出單詞為 ++，返回單詞二元式編碼 (39。$39。,NUL)并退回 39。+39。 ?從初態(tài) 0出發(fā)，讀入 39。+39。進(jìn)入狀態(tài) 4，在狀態(tài) 4讀入 39。y39。，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài) 4為終態(tài)，故識(shí)別出一個(gè)單詞。查表，確認(rèn)識(shí)別出單詞為 +，返回單詞二元式編碼 (39。+39。,NUL)并退回 39。y39。； ?從初態(tài) 0出發(fā)，讀入 39。y39。進(jìn)入狀態(tài) 1，在狀態(tài) 1讀入 39。39。，無(wú)法前進(jìn)。因當(dāng)前所處狀態(tài) 1為終態(tài)，故識(shí)別出一個(gè)單詞。查表未果，由于首字符為字母，故單詞 y為標(biāo)識(shí)符，返回單詞二元式編碼 (39。i39。,y)并退回 39。39。 ?從初態(tài) 0出發(fā)，讀入 39。39。，進(jìn)入狀態(tài) 10。由于無(wú)法再讀入字符，即查表，確認(rèn)識(shí)別出單詞為 ，返回單詞二元式編碼 (39。39。,NUL)。識(shí)別出單詞 意味著整個(gè)源程序中字符全部處理完畢。 ㈣ 掃描器控制程序的實(shí)現(xiàn) ?狀態(tài)轉(zhuǎn)換矩陣的數(shù)字化 ?控制程序是根據(jù) DFA來(lái)工作的，首先要將狀態(tài)轉(zhuǎn)換矩陣數(shù)字化，空白用 0表示。 ?在預(yù)處理中，空格作為界符被保留下來(lái)。單詞的前導(dǎo)空格在識(shí)別一個(gè)單詞前被濾去，單詞的尾部空格用作單詞的終止標(biāo)志，故在狀態(tài)轉(zhuǎn)換矩陣中，應(yīng)增加空格列，該列每個(gè)元素的值均標(biāo)記為 0。 ?因 26個(gè)字母作用相同，故可用一列表示。在查表時(shí)可將 26個(gè)字母轉(zhuǎn)換成 1個(gè)，例 39。a39。 ?因 10個(gè)數(shù)字作用相同，故可用一列表示。在查表時(shí)可將 10個(gè)數(shù)字轉(zhuǎn)換成 1個(gè)，例 39。039。 狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如下頁(yè)所示： a 0 = + * , 。 ( ) 空格 0 1 2 3 4 5 6 7 8 9 10 0 1 11 11 0 0 0 0 0 0 0 0 0 2 0 12 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 13 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 11 11 11 0 0 0 0 0 0 0 0 0 12 0 12 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如右所示： ? 轉(zhuǎn)換函數(shù) 0． procedure Tra(c) 1. if c是字母 then c←39。a39。 2. if c是數(shù)字 then c←39。039。 3. return c 4. end procedure 單詞 code 單詞 code 1 begin { 8 * * 2 end } 9 ， , 3 integer a 10 。 。 4 real c 11 ( ( 5 = = 12 ) ) 6 + + 13 7 ++ $ 14 ? DFA終態(tài)集 Z={1,2,3,4,5,6,7,8,9,10,11,12,13} 在上例中，除初態(tài) 0外，其余狀態(tài)均為終態(tài)，故終態(tài)集可不設(shè)置。但此情況屬于特例，通常需設(shè)置終態(tài)集，供程序判斷。 ?單詞二元式編碼表 0. procedur scanner( ) 1. ←39。 39。:←Nul:Token[]← 2. i←i+1:c←buf[i]: 當(dāng)前狀態(tài) ← 初態(tài) 3． while DFA[當(dāng)前狀態(tài) ,c]≠0 do 4. Token←Token,c //將 Token中字符串拼接字符 c后送 Token 5. 當(dāng)前狀態(tài) ← DFA[當(dāng)前狀態(tài) ,Tra(c)] 6. i←i+1 //指向下一字符 7. if buf[i]為空 then break 8. else c←buf[i] 9. end if 10. end while 11． if not(當(dāng)前狀態(tài) ∈ 終態(tài)集 ) then output Error:exit 12. ← 根據(jù) Token[]查表的結(jié)果 13. if =??? then //?表示單詞二元式編碼表中無(wú) 14. if Token首字符是字母 then =?i? //是標(biāo)識(shí)符 15. if Token首字符是數(shù)字 then =?x? //是整常數(shù) 16. ←Token[] //此時(shí)單詞有值 17. end if 18. return t 19. end procedure ?控制程序的工作原理和手工構(gòu)造相類(lèi)似，差異在于如何實(shí)現(xiàn)狀態(tài)遷移。手工構(gòu)造的掃描器是利用程序控制流程的改變來(lái)實(shí)現(xiàn)狀態(tài)遷移，而使用 DFA的控制程序是利用狀態(tài)轉(zhuǎn)換矩陣來(lái)實(shí)現(xiàn)狀態(tài)遷移。 ?使用 DFA的控制程序遠(yuǎn)較手工構(gòu)造的掃描器簡(jiǎn)單，并且控制程序與源語(yǔ)言的單詞集無(wú)關(guān)。所謂自動(dòng)構(gòu)造詞法分析器，實(shí)際上就是構(gòu)造 DFA。所以，自動(dòng)構(gòu)造詞法分析器的難點(diǎn)在于構(gòu)造 DFA，對(duì)于實(shí)際程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，用人工構(gòu)造 DFA是不可能的，必須由程序來(lái)實(shí)現(xiàn)。 ?借助于上述原理（正規(guī)式 → NFA→DFA ）， 1972年貝爾實(shí)驗(yàn)室的 Unix操作系統(tǒng)上首先實(shí)現(xiàn)了這樣的程序，稱(chēng)之為詞法分析器生成工具，簡(jiǎn)稱(chēng) LEX。 ?用戶(hù)可使用 LEX提供的語(yǔ)言編寫(xiě)源程序，源程序由描述單詞的正規(guī)式和單詞的二元式編碼構(gòu)成。 LEX源程序經(jīng) LEX編譯程序（詞法分析器生成工具）加工，編譯的結(jié)果就是與正規(guī)式等價(jià)的確定有限自動(dòng)機(jī)（狀態(tài)轉(zhuǎn)換矩陣形式）。 結(jié)論 結(jié) 束 第 3章 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法描述 文法的引入 上下文無(wú)關(guān)文法 文法舉例（略） 使用文法對(duì)程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)進(jìn)行定義和描述。 文法的引入 先討論自然語(yǔ)言的文法。例： the big elephent ate a banana ㈠ 語(yǔ)法樹(shù) 根據(jù)英語(yǔ)的語(yǔ)法，上述句子的語(yǔ)法結(jié)構(gòu)可用圖（語(yǔ)法樹(shù)）表示如下： ?非葉結(jié)點(diǎn)稱(chēng)為語(yǔ)法單位，在形式語(yǔ)言中稱(chēng)為非終結(jié)符。 ?處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱(chēng)為開(kāi)始符號(hào)。 ?葉結(jié)點(diǎn)稱(chēng)為單詞符號(hào)，在形式語(yǔ)言中稱(chēng)為終結(jié)符。 句子 主語(yǔ) 謂語(yǔ) 冠詞 形容詞 名詞 動(dòng)詞 直接賓語(yǔ) t he bi g el ephant at e 冠詞 名詞 a bana na ㈡ 規(guī)則 可以通過(guò)建立一組規(guī)則，來(lái)描述上述句子的語(yǔ)法結(jié)構(gòu)，規(guī)則在形式語(yǔ)言中稱(chēng)為產(chǎn)生式。 1. 句子 → 主語(yǔ) 謂語(yǔ) 2. 主語(yǔ) → 冠詞 形容詞 名詞 3. 冠詞 →the|a 4. 形容詞 →big 5. 名詞 →elephant|banana 6. 謂語(yǔ) → 動(dòng)詞 直接賓語(yǔ) 7. 直接賓語(yǔ) → 冠詞 名詞 8. 動(dòng)詞 →ate ㈢ 由規(guī)則推導(dǎo)句子 可用規(guī)則來(lái)推導(dǎo)出句子。從開(kāi)始符號(hào)出發(fā)，若能從規(guī)則推導(dǎo)出某符號(hào)串，則該符號(hào)串就是該文法的合法的句子，反之語(yǔ)法錯(cuò)誤。 上述英文句子可用下述規(guī)則來(lái)描述： 句子 主語(yǔ) 謂語(yǔ) 冠詞 形容詞 名詞 謂語(yǔ) the 形容詞 名詞 謂語(yǔ) the big 名詞 謂語(yǔ) the big elephant 謂語(yǔ) the big elephant 動(dòng)詞 直接賓語(yǔ) the big elephant ate 直接賓語(yǔ) the big elephant ate 冠詞 名詞 the big elephant ate a 名詞 the big elephant ate a banana 上述推導(dǎo)可簡(jiǎn)單表示為： 句子 the big elephant ate a banana。 值得注意的是用上述規(guī)則可推導(dǎo)出多個(gè)句子，因存在推導(dǎo) 句子 a big banana ate the elephant 所以， a big banana ate the elephant也是文法的一個(gè)合法的句子。但意義是荒謬的，也就是說(shuō)句子的語(yǔ)義是錯(cuò)誤的。 一個(gè)語(yǔ)法正確的句子不能保證其語(yǔ)義是正確的，故一個(gè)句子是否正確，需要進(jìn)行語(yǔ)法和語(yǔ)義兩方面檢查。 綜上所述，語(yǔ)言結(jié)構(gòu)通常是用文法來(lái)定義和描述，文法是由終結(jié)符、非終結(jié)符、開(kāi)始符號(hào)（特殊非終結(jié)符）及產(chǎn)生式四個(gè)要素構(gòu)成。從開(kāi)始符號(hào)出發(fā)，根據(jù)產(chǎn)生式能推導(dǎo)出的句子全體稱(chēng)為文法所規(guī)定的語(yǔ)言 ㈣ 遞歸規(guī)則和遞歸文法 遞歸是編譯技術(shù)中的一個(gè)重要概念。 ①遞歸定義：定義某事物，又用到該事物本身。 ②遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。 例： U→xUy ，通常用大寫(xiě)字母表示非終結(jié)符，用小寫(xiě)字母表示終結(jié)符。 ?左遞歸規(guī)則： x=ε， U→Uy （ ε表示空串） ?右遞歸規(guī)則： y=ε， U→xU ③ 間接遞歸：由規(guī)則推導(dǎo)產(chǎn)生。 例： V→Uy|Z ， U→xV 因存在推導(dǎo) V Uy xVy，故存在間接遞歸。 ?間接左遞歸：若 x=ε，則 V Vy。 ?間接右遞歸：若 y=ε，則 V xU。 ④遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱(chēng)為遞歸文法。 利用遞歸文法，可以用有窮的規(guī)則來(lái)描述無(wú)窮的語(yǔ)言，這不但解決了語(yǔ)言的定義問(wèn)題，而且使得對(duì)語(yǔ)言的語(yǔ)法檢查成為可能。 上下文無(wú)關(guān)文法 形式語(yǔ)言的奠基人喬姆斯基（ Chomsky）將文法分為 4種類(lèi)型，它們是： ?短語(yǔ)文法（ 0型文法） ?上下文有關(guān)文法（ 1型文法） ?上下文無(wú)關(guān)文法（ 2型文法） ?正規(guī)文法（ 3型文法） 這四種文法在形式語(yǔ)言中都有嚴(yán)格的定義。但對(duì)于程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，上下文無(wú)關(guān)文法已經(jīng)夠用了，上下文無(wú)關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)。以后，“文法”一詞若無(wú)特別說(shuō)明，則指“上下文無(wú)關(guān)文法”。 ㈠ 文法和語(yǔ)言 一個(gè)文法 G是一個(gè)四元式 (VT,VN,S,P)，其中 ?VT是一個(gè)終結(jié)符的非空有限集，終結(jié)符通常用小寫(xiě)字母表示。 ?VN是一個(gè)非終結(jié)符的非空有限集，非終結(jié)符通常用大寫(xiě)字母表示。 ?S是一個(gè)特殊的非終結(jié)符（ S∈ VN），稱(chēng)為開(kāi)始符號(hào)。 ?P是一個(gè)產(chǎn)生式（規(guī)則）的有限集合，每個(gè)產(chǎn)生式的形式是A→α ，其中 A∈ VN， α∈ (VT∪ VN)*。 ① 終結(jié)符是語(yǔ)言的基本符號(hào)，即程序設(shè)計(jì)語(yǔ)言的單詞