【正文】 e)。 return 39。 //標識符的單詞種別為 39。 } begin } end { integer a real c 0 1 2 3 正規(guī)式、自動機及詞法分析器的自動生成 基本概念 ㈠ 有窮字母表 ∑ 符號有限集，它的每個元素稱為字符。 ① 空字 不包含任何字符的字，稱為空字，記為 ε（空字相當于高級語言中的空串“”）。 例： ∑={0， 1} ∑*={ε， 0， 1， 00， 01， 10， 11， 000， 001， ……} ③ （集合的）積運算 定義：設 U、 V ∑*， U和 V的積記為 U V（或 UV）且定義為 UV={αβ|（ α∈ U） ∧ （ β∈ V） } ?積不滿足交換律 UV≠VU ?積滿足結(jié)合律 (UV)W=U(VW) 證明見本書 38頁 ?積滿足分配律 X(Y∪ Z)=XY∪ XZ ④ （集合的）閉包 設 V Σ*， V的閉包記為 V*且定義為 V自身的任意有限次積，即V*= V0∪ V1∪ V2∪ …… ∪ Vn，規(guī)定 V0 = {ε}。 ⑤ （集合的）正則閉包 定義：設 V Σ*， V的正則閉包記為 V+，且定義 V+=VV*。 設 V={0, 1}，則 V+ = V1∪ V2∪ …… ∪ Vn={ 0, 1, 00, 01, 10, 11,000,001, …… } ， V+可理解為二進制數(shù)的全體。 ?若字符 a∈ ∑，則字符 a是正規(guī)式，相應正規(guī)集為 {a}。 ?若 α、 β為正規(guī)式，相應正規(guī)集分別記為 L(α)和 L(β)，則 αβ(或 α若 α=β，則 L(αβ)= L(αα)= L(α2)=L(α)2。） ?若 α為正規(guī)式，相應正規(guī)集記為 L(α)，則 α*= α0|α1| α2 | ……|α n是正規(guī)式，規(guī)定 α0 =ε，其相應正規(guī)集記為 L(α*)，且令 L(α*) =L(α) *。、 ︱ ,可用園括號改變運算順序。 例：設 α是正規(guī)式，求證 α|α = α。 ?描述標識符的正規(guī)式： α (α|β)* ?描述二進制數(shù)的正規(guī)式： (0|1)(0|1) * ?描述無符號整常數(shù)的正規(guī)式： ββ* ?描述無符號實常數(shù)的正規(guī)式： ββ*.β*|.ββ* |(ββ*.β*|.ββ*|ββ* )(E|e) (+||ε) ββ* 123. 確定有限自動機（ DFA） ㈠ DFA定義 一個確定有限自動機 M是一個五元式 M = ( S， Σ， f， s0， Z ) ?S是一個有限集，它的每一個元素稱為狀態(tài)。 ?f是一個從 S Σ至 S的映照，即 f： S Σ→S （單值函數(shù)） 例 f (si,a) = sj，表示當現(xiàn)行狀態(tài)為 si，若輸入字符為 a，則轉(zhuǎn)移到下一狀態(tài) sj， sj稱為 si的后繼狀態(tài)。 ?Z S，是一個終態(tài)集。039。139。039。139。039。139。只要對初態(tài)和終態(tài)作適當標記，可用一個狀態(tài)轉(zhuǎn)換矩陣來表示 DFA。039。139。 ?若 DFA M的初態(tài)結(jié)同時又是終態(tài)結(jié)，則稱空字 ε可為 DFA M所識別或接受。 設 α= 1012 = 5 因從初態(tài) 0出發(fā)，存在一條到終態(tài) 1的路徑。 L(M) = {α |α為二進制數(shù) }。 ?Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。 ?S0 S，是一個非空初態(tài)集，即 NFA的初態(tài)不一定唯一。 DFA和 NFA的主要區(qū)別為：映照 f（函數(shù)）， DFA的映照 f是從狀態(tài) 字符 映射到 狀態(tài) ， f為單值函數(shù)；而 NFA的映照 f是從狀態(tài) 字 映射到 狀態(tài)子集 ， f為多值函數(shù)。 ?若 M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的 ε道路，那么空字 ε可為 M所接受。 ?對于任何二個有限自動機 M和 M39。)，則稱二個有限自動機 M和 M39。 ?DFA是 NFA的特例，對于每個 NFA M存在一個 DFA M39。)。 ㈠ V?NFA ① 將 V表示成拓廣 NFA ② 根據(jù)下面三條規(guī)則對 V進行分裂（規(guī)則基于識別的語言不變），直至每條弧上的標記為 Σ上的一個字符或 ε。 ③ a a a ○ x ε ① ε ② b b b ④ ㈡ NFA?DFA 為了便于描述 NFA確定化算法，我們引進二個概念。 ?若狀態(tài) s∈ I，則從狀態(tài) s出發(fā)，經(jīng)一條或多條 ε弧所能到達的狀態(tài) s39。 ② Ia I NFA M狀態(tài)集的一個子集 Ja 從 I出發(fā)經(jīng)一條 a弧所能到達的狀態(tài)全體 Ia ε_CLOSURE(Ja) 設 I={1}，則 CLOSURE(I)= CLOSURE({1})={1,2}。 接上例設 I={1， 2}，則 Ja ={4,5}∪ {3}={3,4,5} Ia = CLOSURE ({3,4,5})={5,4,3,6,2,8,7} 例 : ⑤ ε ⑥ a ε ① ε ② a ③ ε ⑧ a ④ ε ⑦ ③ NFA確定化算法 I Ia（ a∈ ∑） Ib（ b∈ ∑） CLOSURE({X}) 1）數(shù)據(jù)結(jié)構(gòu)及初始狀態(tài) 手工計算 2）算法描述 0. procedure NFA_TO_DFA 1. p_cur←1 //當前指針，指示當前處理的狀態(tài)子集。 因 NFA M具有 6個狀態(tài)，狀態(tài)子集個數(shù)（包括空集）最多為 64，故表的長度不會超過 261=63，循環(huán)必然在有限步中結(jié)束。的一個狀態(tài)。的初態(tài)。狀態(tài)視為終態(tài)。 4）重新標記 狀態(tài) /字符 a b 0 1 2 1 3 2 2 1 4 3 3 2 4 1 4 0是初態(tài)， 3和 4為終態(tài)。和 NFA M是等價的。 詞法分析器 的 自動生成器 輸入正規(guī)式 輸出 DFA （狀態(tài)轉(zhuǎn)換矩陣） ㈠ 自動生成過程概述 ①構(gòu)造描述每個單詞的正規(guī)式 Pi(1≤i≤N)。在構(gòu)造NFA Mi的同時，逐步并且最終形成識別全部單詞的 NFA M。 ㈡ 實例（模型語言的詞法） ①模型語言字符集 {39。..39。 39。..39。 39。 39。 39。 39。 ， 39。 ， 39。 39。 39。 } ② 模型語言單詞集 ?基本字： begin、 end、 integer、 real ?標識符：以字母開始的數(shù)字字母串 ?無符號整常數(shù)：數(shù)字串 ?運算符： +、 * 、 ++、 = ?界符： , 、 。{39。}39。a39。c39。i39。x39。=39。+39。*39。$39。,39。(39。,NUL)、 ( ( 39。,NUL)、 ) ( 39。,NUL)、(39。,NUL) ② 構(gòu)造 NFA M 實例解： ①構(gòu)造正規(guī)式 （令 α= a|b|c|d|……|z 、 β= 0|1|2|3|4|5|6|7|8|9） ?標識符 α(α|β)* ?無符號整常數(shù) ββ* ?運算符 單詞本身（例 39。的正規(guī)式為 39。++的正規(guī)式為 ++） ?界符 單詞本身（例 39。的正規(guī)式為 39。） ?基本字通常是由字母構(gòu)成，符合標識符規(guī)則，將基本字作為一種特殊標識符來處理（可設置保留字表，二者區(qū)分可通過查表）。 I( I) I {0} {1,12,13} {2,14,15} {3} {4,5} {6} {7} {8} {9} {10} {11} {1,12,13} {12,13} {12,13} {2,14,15} {14,15} {3} {4,5} {16} {6} {7} {8} {9} {10} {11} {12,13} {12,13} {12,13} {14,15} {14,15} {16} ④ 重新標記，構(gòu)造 DFA M39。 ( ) 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)。 ?在狀態(tài)遷移過程中，需用 Token數(shù)組保存讀入字符。 ?事先設置一個單詞二元式編碼表，它包括除標識符和整常數(shù)以外的所有單詞（基本字、運算符和界符）。 ?若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為標識符和整常數(shù)二者之一，只要稍加判斷即可區(qū)分。 ?DFA每次只能識別一個單詞，需多次使用 DFA來識別源程序中單詞，直到源程序中的字符全部處理完。此時，需調(diào)整單詞二元式編碼表中的單詞排列順序，將需優(yōu)先匹配的單詞排在表的較前面，這樣在單詞查找過程，讓其先得到匹配。 ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。無法前進。查表未果，由于首字符為字母，故單詞 x為標識符，返回單詞二元式編碼 (39。,x)并退回 39。 ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 4，在狀態(tài) 4讀入 39。進入終態(tài)13，在狀態(tài) 13讀入 39。無法前進。查表，確認識別出單詞為 ++，返回單詞二元式編碼 (39。,NUL)并退回 39。 ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 4，在狀態(tài) 4讀入 39。無法前進。查表，確認識別出單詞為 +，返回單詞二元式編碼 (39。,NUL)并退回 39。； ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。無法前進。查表未果，由于首字符為字母，故單詞 y為標識符，返回單詞二元式編碼 (39。,y)并退回 39。 ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 10。39。識別出單詞 意味著整個源程序中字符全部處理完畢。 ?在預處理中，空格作為界符被保留下來。 ?因 26個字母作用相同，故可用一列表示。a39。在查表時可將 10個數(shù)字轉(zhuǎn)換成 1個，例 39。 狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如下頁所示： a 0 = + * , 。a39。039。 。但此情況屬于特例，通常需設置終態(tài)集，供程序判斷。 39。手工構(gòu)造的掃描器是利用程序控制流程的改變來實現(xiàn)狀態(tài)遷移，而使用 DFA的控制程序是利用狀態(tài)轉(zhuǎn)換矩陣來實現(xiàn)狀態(tài)遷移。所謂自動構(gòu)造詞法分析器，實際上就是構(gòu)造 DFA。 ?借助于上述原理（正規(guī)式 → NFA→DFA ）， 1972年貝爾實驗室的 Unix操作系統(tǒng)上首先實現(xiàn)了這樣的程序，稱之為詞法分析器生成工具，簡稱 LEX。 LEX源程序經(jīng) LEX編譯程序（詞法分析器生成工具）加工，編譯的結(jié)果就是與正規(guī)式等價的確定有限自動機（狀態(tài)轉(zhuǎn)換矩陣形式）。 文法的引入 先討論自然語言的文法。 ?處于根結(jié)點位置的結(jié)點又稱為開始符號。 句子 主語 謂語 冠詞 形容詞 名詞 動詞 直接賓語 t he bi g el ephant at e 冠詞 名詞 a bana na ㈡ 規(guī)則 可以通過建立一組規(guī)則，來描述上述句子的語法結(jié)構(gòu)，規(guī)則在形式語言中稱為產(chǎn)生式。從開始符號出發(fā)，若能從規(guī)則推導出某符號串，則該符號串就是該文法的合法的句子，反之語法錯誤。 值得注意的是用上述規(guī)則可推導出多個句子，因存在推導 句子 a big banana ate the elephant 所以， a big banana ate the elephant也是文法的一個合法的句子。 一個語法正確的句子不能保證其語義是正確的，故一個句子是否正確，需要進行語法和語義兩方面檢查。從開始符號出發(fā)，根據(jù)產(chǎn)生式能推導出的句子全體稱為文法所規(guī)定的語言 ㈣ 遞歸規(guī)則和遞歸文法 遞歸是編譯技術中的一個重要概念。 ②遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。 ?左遞歸規(guī)則： x=ε， U→Uy （ ε表示空串） ?右遞歸規(guī)則： y=ε， U→xU ③ 間接遞歸：由規(guī)則推導產(chǎn)生。 ?間接左遞歸：若 x=ε，則 V Vy。 ④遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱為遞歸文法。 上下文無關文法 形式語言的奠基人喬姆斯基（ Chomsky）將文法分為 4種類型，它們是： ?短語文法（ 0型文法） ?上下文有關文法（ 1型文法） ?上下文無關文法（ 2型文法） ?正規(guī)文法（ 3型文法） 這四種文法在形式語言中都有嚴格的定義。以后，“文法”一詞若無特別說明，則指“上下文無關文法”。 ?VN是一個非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母表示。 ?P是一個產(chǎn)生式（規(guī)則）的有限集合，每個產(chǎn)生式的形式是A→α ，其中 A∈ VN， α∈ (VT∪ V