【正文】 ?P是一個產(chǎn)生式（規(guī)則）的有限集合，每個產(chǎn)生式的形式是A→α ，其中 A∈ VN， α∈ (VT∪ VN)*。以后，“文法”一詞若無特別說明，則指“上下文無關文法”。 ④遞歸文法：含有遞歸規(guī)則和間接遞歸的文法，稱為遞歸文法。 ?左遞歸規(guī)則： x=ε， U→Uy （ ε表示空串） ?右遞歸規(guī)則： y=ε， U→xU ③ 間接遞歸：由規(guī)則推導產(chǎn)生。從開始符號出發(fā)，根據(jù)產(chǎn)生式能推導出的句子全體稱為文法所規(guī)定的語言 ㈣ 遞歸規(guī)則和遞歸文法 遞歸是編譯技術中的一個重要概念。 值得注意的是用上述規(guī)則可推導出多個句子，因存在推導 句子 a big banana ate the elephant 所以， a big banana ate the elephant也是文法的一個合法的句子。 句子 主語 謂語 冠詞 形容詞 名詞 動詞 直接賓語 t he bi g el ephant at e 冠詞 名詞 a bana na ㈡ 規(guī)則 可以通過建立一組規(guī)則，來描述上述句子的語法結構，規(guī)則在形式語言中稱為產(chǎn)生式。 文法的引入 先討論自然語言的文法。 ?借助于上述原理（正規(guī)式 → NFA→DFA ）， 1972年貝爾實驗室的 Unix操作系統(tǒng)上首先實現(xiàn)了這樣的程序，稱之為詞法分析器生成工具，簡稱 LEX。手工構造的掃描器是利用程序控制流程的改變來實現(xiàn)狀態(tài)遷移，而使用 DFA的控制程序是利用狀態(tài)轉換矩陣來實現(xiàn)狀態(tài)遷移。但此情況屬于特例，通常需設置終態(tài)集，供程序判斷。039。 狀態(tài)轉換矩陣經(jīng)數(shù)字化后如下頁所示： a 0 = + * , 。a39。 ?在預處理中，空格作為界符被保留下來。39。 ?從初態(tài) 0出發(fā)，讀入 39。查表未果，由于首字符為字母，故單詞 y為標識符，返回單詞二元式編碼 (39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。,NUL)并退回 39。無法前進。 ?從初態(tài) 0出發(fā)，讀入 39。查表，確認識別出單詞為 ++，返回單詞二元式編碼 (39。進入終態(tài)13，在狀態(tài) 13讀入 39。 ?從初態(tài) 0出發(fā)，讀入 39。查表未果，由于首字符為字母，故單詞 x為標識符，返回單詞二元式編碼 (39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。此時，需調(diào)整單詞二元式編碼表中的單詞排列順序，將需優(yōu)先匹配的單詞排在表的較前面，這樣在單詞查找過程，讓其先得到匹配。 ?若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為標識符和整常數(shù)二者之一，只要稍加判斷即可區(qū)分。 ?在狀態(tài)遷移過程中，需用 Token數(shù)組保存讀入字符。 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} ④ 重新標記，構造 DFA M39。的正規(guī)式為 39。的正規(guī)式為 39。,NUL)、(39。,NUL)、 ( ( 39。,39。*39。=39。i39。a39。{39。 39。 ， 39。 39。 39。..39。..39。在構造NFA Mi的同時，逐步并且最終形成識別全部單詞的 NFA M。和 NFA M是等價的。狀態(tài)視為終態(tài)。的一個狀態(tài)。 接上例設 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ù)結構及初始狀態(tài) 手工計算 2）算法描述 0. procedure NFA_TO_DFA 1. p_cur←1 //當前指針，指示當前處理的狀態(tài)子集。 ?若狀態(tài) s∈ I，則從狀態(tài) s出發(fā)，經(jīng)一條或多條 ε弧所能到達的狀態(tài) s39。 ㈠ V?NFA ① 將 V表示成拓廣 NFA ② 根據(jù)下面三條規(guī)則對 V進行分裂（規(guī)則基于識別的語言不變），直至每條弧上的標記為 Σ上的一個字符或 ε。 ?DFA是 NFA的特例，對于每個 NFA M存在一個 DFA M39。 ?對于任何二個有限自動機 M和 M39。 DFA和 NFA的主要區(qū)別為：映照 f（函數(shù)）， DFA的映照 f是從狀態(tài) 字符 映射到 狀態(tài) ， f為單值函數(shù)；而 NFA的映照 f是從狀態(tài) 字 映射到 狀態(tài)子集 ， f為多值函數(shù)。 ?Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。 設 α= 1012 = 5 因從初態(tài) 0出發(fā)，存在一條到終態(tài) 1的路徑。139。只要對初態(tài)和終態(tài)作適當標記，可用一個狀態(tài)轉換矩陣來表示 DFA。039。039。039。 ?f是一個從 S Σ至 S的映照，即 f： S Σ→S （單值函數(shù)） 例 f (si,a) = sj，表示當現(xiàn)行狀態(tài)為 si，若輸入字符為 a，則轉移到下一狀態(tài) sj， sj稱為 si的后繼狀態(tài)。 例：設 α是正規(guī)式，求證 α|α = α。） ?若 α為正規(guī)式，相應正規(guī)集記為 L(α)，則 α*= α0|α1| α2 | ……|α n是正規(guī)式，規(guī)定 α0 =ε，其相應正規(guī)集記為 L(α*)，且令 L(α*) =L(α) *。 ?若 α、 β為正規(guī)式，相應正規(guī)集分別記為 L(α)和 L(β)，則 αβ(或 α 設 V={0, 1}，則 V+ = V1∪ V2∪ …… ∪ Vn={ 0, 1, 00, 01, 10, 11,000,001, …… } ， V+可理解為二進制數(shù)的全體。 例： ∑={0， 1} ∑*={ε， 0， 1， 00， 01， 10， 11， 000， 001， ……} ③ （集合的）積運算 定義：設 U、 V ∑*， U和 V的積記為 U V（或 UV）且定義為 UV={αβ|（ α∈ U） ∧ （ β∈ V） } ?積不滿足交換律 UV≠VU ?積滿足結合律 (UV)W=U(VW) 證明見本書 38頁 ?積滿足分配律 X(Y∪ Z)=XY∪ XZ ④ （集合的）閉包 設 V Σ*， V的閉包記為 V*且定義為 V自身的任意有限次積，即V*= V0∪ V1∪ V2∪ …… ∪ Vn，規(guī)定 V0 = {ε}。 } begin } end { integer a real c 0 1 2 3 正規(guī)式、自動機及詞法分析器的自動生成 基本概念 ㈠ 有窮字母表 ∑ 符號有限集，它的每個元素稱為字符。 return 39。 const char code[]={{}ac}。 } ② 查基本字表函數(shù) reserve(token[]) 基本字通常是由字母構成，符合標識符規(guī)則。i++)。則調(diào)用拼接函數(shù) concat后， token的內(nèi)容為 begi。 //是標識符 return t。 //拼接函數(shù) =reserve(token)。amp。z39。a39。amp。) i++。 char token[20]=。 struct code_val t={39。 }。 void concat(char token[],char c)。char val[20]。*39。進入狀態(tài) 13，識別出單詞 ，識別出單詞 意味著整個源程序中字符處理完畢。進入終態(tài) 2，識別出標識符 y，退回 39。； ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 10，在狀態(tài) 10讀入 39。進入狀態(tài) 10，在狀態(tài) 10讀入 39。進入終態(tài) 2，識別出標識符 x，退回 39。 ?從初態(tài) 0出發(fā)，讀入 39。 空格 + ⑩ + 非 + * ㈢ 利用狀態(tài)轉換圖識別單詞 狀態(tài)轉換圖每次只能識別一個單詞，若源程序中有 N個單詞，則需使用狀態(tài)轉換圖 N次。從初態(tài) 0出發(fā)，若當前輸入字符是字母，則進入狀態(tài) 1；若為數(shù)字，則進入狀態(tài) 3；若為小數(shù)點，則進入狀態(tài) 7。+39。為程序處理方便起見，不管是什么字符，均將其退回。 在詞法分析預處理中，空格作為界符被保留下來。 例，識別標識符的狀態(tài)轉換圖如下所示： ○ j x ○ i y ○ k 其中 0為初態(tài)， 2為終態(tài)。在狀態(tài)轉換圖中，結點代表狀態(tài)，用園圈表示。在本書中，詞法分析器是以函數(shù)形式書寫的，函數(shù)的返回值是一個單詞的二元式。當下一遍進入后，幾乎可以使用全部存儲空間。 遍 ㈠ 遍的基本概念 由外存獲得前一遍的工作結果 (對于第一遍而言，從外存獲得源程序 )，完成它所含的有關階段工作之后，再把結果存于外存。在基本字、用戶定義的標識符和常數(shù)之間，若沒有運算符或界符，則至少用一個空格（或 TAB、換行符）加以分隔。若該字符為字母 G或 g，則為邏輯 IF；若為數(shù)字，則為算術 IF；若為 =，則為標識符。讓我們來觀察下面三個 Fortran語言語句。39。*39。A39。*39?？捎米兞?cur_c記錄當前正在處理的字符，用old_c記錄剛處理過的字符。 ① 算法說明 ?用偽代碼編寫預處理程序，輸入和預處理可同時進行，無需輸入緩沖區(qū)，將讀入后經(jīng)預處理的源程序直接送掃描緩沖區(qū) buf[1..n]。 s = 2 * 3 . 1 4 * r * ( r + h ) e n d \0 . . . \0 上述源程序經(jīng)預處理后，掃描緩沖區(qū)中的內(nèi)容如下所示： ㈢ 預處理例 用偽代碼編寫一個預處理程序，要求如下： ?去除源程序中注釋（源程序中的注釋用 /*……*/ 標記，不允許嵌套使用） ?去除源程序中續(xù)行符（ \） ?將 TAB和換行符替換為空格 ?將大寫字母變換成小寫 ?在源程序尾部添加字符 39。 ?大多數(shù)語言（除 C語言）不區(qū)分大小寫，可在預處理時，將大寫字母變換成小寫字母，或相反，以方便后續(xù)處理。 ② 預處理主要工作 ?刪除注釋 ?刪除續(xù)行符，以及后續(xù)換行符 (0AH)。\39。 B e g i n / * S = 2 * 3 . 1 4 * R * R + 2 * 3 . 1 4 * R * H * / \n \t R e a l r , h , s 。目前計算機所使用的的內(nèi)存已超過若干年前硬盤容量，計算機內(nèi)存足以容納源程序的全部，故源程序可一次全部讀入內(nèi)存進行處理。,NUL) ………… 源程序的輸入及預處理 ㈠ 源程序的輸入 ?分段讀入處理（早期） ?全部讀入后處理 源程序以文件形式存于外存，首先要將其讀入內(nèi)存才可進行詞法分析。 。 ?如果一個種別僅包含一個單詞，那么單詞種別就可代表該單詞，無需給出單詞值。單詞種別表示單詞的語法特性，在語法分析時使用。 、 (、 )、 …… ㈡ 單詞的性質(zhì) ?基本字、運算符和界符對于某一程序設計語言來說是確定的，而源程序中的標識符和常數(shù)的個數(shù)是不確定的，隨源程序而異。 結 束 第 2章 詞法分析 詞法分析器的設計考慮及手工構造 單詞類型及二元式編碼 源程序的輸入及預處理 基本字的識別和超前搜索 遍 狀態(tài)轉換圖和詞法分析器的手工構造 正規(guī)式、自動機及詞法分析器的自動生成 基本概念 正規(guī)式與正規(guī)集 確定有限自動機（ DFA） 非確定有限自動機 （ NFA） 正規(guī)式與確定有限自動機的等價性 詞法分析器的自動生成 詞法分析器的設計考慮及 手工構造 詞法分析任務： 從文件讀入源程序，去除源程序中與編譯無關的編輯字符、注釋等，由字符拼接單詞。 ㈡用高級語言手工編寫 利用已有的高級語言的編譯系統(tǒng)，編寫另一高級語言的全部或部分編譯程序。 ㈡編譯程序后端 (The Back End) 組成：目標代碼生成器 特點：和源語言無關，以中間代碼形式的源程序為輸入進行處理，輸出結果依賴于目標機器。 ?在發(fā)現(xiàn)錯誤后，不中斷編譯程序工作。假定，每個整常數(shù)在常數(shù)表中占 2個字節(jié)，每個實常數(shù)在常數(shù)表中占 4個字節(jié)。128表示常數(shù) 128在常數(shù)表中的地址。T2) 其中， amp。128,amp。 ?中間代碼 結構