【正文】 r + h ) e n d \0 . . . \0 上述源程序經(jīng)預處理后，掃描緩沖區(qū)中的內(nèi)容如下所示： ㈢ 預處理例 用偽代碼編寫一個預處理程序，要求如下： ?去除源程序中注釋（源程序中的注釋用 /*……*/ 標記，不允許嵌套使用） ?去除源程序中續(xù)行符（ \） ?將 TAB和換行符替換為空格 ?將大寫字母變換成小寫 ?在源程序尾部添加字符 39。A39。若該字符為字母 G或 g，則為邏輯 IF；若為數(shù)字，則為算術(shù) IF；若為 =，則為標識符。在本書中，詞法分析器是以函數(shù)形式書寫的，函數(shù)的返回值是一個單詞的二元式。為程序處理方便起見，不管是什么字符，均將其退回。 ?從初態(tài) 0出發(fā)，讀入 39。； ?從初態(tài) 0出發(fā)，讀入 39。char val[20]。 char token[20]=。z39。則調(diào)用拼接函數(shù) concat后， token的內(nèi)容為 begi。 return 39。 ?若 α、 β為正規(guī)式，相應正規(guī)集分別記為 L(α)和 L(β)，則 αβ(或 α039。139。 ?對于任何二個有限自動機 M和 M39。 接上例設 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)子集。在構(gòu)造NFA Mi的同時，逐步并且最終形成識別全部單詞的 NFA M。 39。a39。,39。的正規(guī)式為 39。此時，需調(diào)整單詞二元式編碼表中的單詞排列順序，將需優(yōu)先匹配的單詞排在表的較前面，這樣在單詞查找過程，讓其先得到匹配。進入終態(tài)13，在狀態(tài) 13讀入 39。,NUL)并退回 39。39。039。 文法的引入 先討論自然語言的文法。 ?左遞歸規(guī)則： x=ε， U→Uy （ ε表示空串） ?右遞歸規(guī)則： y=ε， U→xU ③ 間接遞歸：由規(guī)則推導產(chǎn)生。 ?P是一個產(chǎn)生式（規(guī)則）的有限集合，每個產(chǎn)生式的形式是A→α ，其中 A∈ VN， α∈ (VT∪ VN)*。從開始符號出發(fā)，根據(jù)產(chǎn)生式能推導出的句子全體稱為文法所規(guī)定的語言 ㈣ 遞歸規(guī)則和遞歸文法 遞歸是編譯技術(shù)中的一個重要概念。 ?借助于上述原理（正規(guī)式 → NFA→DFA ）， 1972年貝爾實驗室的 Unix操作系統(tǒng)上首先實現(xiàn)了這樣的程序，稱之為詞法分析器生成工具，簡稱 LEX。 狀態(tài)轉(zhuǎn)換矩陣經(jīng)數(shù)字化后如下頁所示： a 0 = + * , 。 ?從初態(tài) 0出發(fā)，讀入 39。無法前進。 ?從初態(tài) 0出發(fā)，讀入 39。 ?若該單詞在表中存在，即可獲得二元式編碼；若不存在，則該單詞必為標識符和整常數(shù)二者之一，只要稍加判斷即可區(qū)分。的正規(guī)式為 39。*39。{39。 39。和 NFA M是等價的。 ?若狀態(tài) s∈ I，則從狀態(tài) s出發(fā)，經(jīng)一條或多條 ε弧所能到達的狀態(tài) s39。 DFA和 NFA的主要區(qū)別為：映照 f（函數(shù)）， DFA的映照 f是從狀態(tài) 字符 映射到 狀態(tài) ， f為單值函數(shù)；而 NFA的映照 f是從狀態(tài) 字 映射到 狀態(tài)子集 ， f為多值函數(shù)。只要對初態(tài)和終態(tài)作適當標記，可用一個狀態(tài)轉(zhuǎn)換矩陣來表示 DFA。 ?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)。 設 V={0, 1}，則 V+ = V1∪ V2∪ …… ∪ Vn={ 0, 1, 00, 01, 10, 11,000,001, …… } ， V+可理解為二進制數(shù)的全體。 const char code[]={{}ac}。 //是標識符 return t。a39。 struct code_val t={39。*39。進入狀態(tài) 10，在狀態(tài) 10讀入 39。 空格 + ⑩ + 非 + * ㈢ 利用狀態(tài)轉(zhuǎn)換圖識別單詞 狀態(tài)轉(zhuǎn)換圖每次只能識別一個單詞，若源程序中有 N個單詞，則需使用狀態(tài)轉(zhuǎn)換圖 N次。 在詞法分析預處理中，空格作為界符被保留下來。當下一遍進入后，幾乎可以使用全部存儲空間。讓我們來觀察下面三個 Fortran語言語句。*39。 ?大多數(shù)語言（除 C語言）不區(qū)分大小寫，可在預處理時，將大寫字母變換成小寫字母，或相反，以方便后續(xù)處理。目前計算機所使用的的內(nèi)存已超過若干年前硬盤容量，計算機內(nèi)存足以容納源程序的全部，故源程序可一次全部讀入內(nèi)存進行處理。單詞種別表示單詞的語法特性，在語法分析時使用。 ㈡編譯程序后端 (The Back End) 組成：目標代碼生成器 特點：和源語言無關(guān)，以中間代碼形式的源程序為輸入進行處理，輸出結(jié)果依賴于目標機器。T2) 其中， amp。integer B。為了便于輸入處理，無意義的單詞值用 NUL表示。用戶程序執(zhí)行時，控制點在用戶程序自身。 ㈢ 目標語言和目標程序 (Target Language and Target Program) 目標語言可以是機器語言 (二進制數(shù) )，也可以是匯編語言 (字符 )，或者是其它中間語言 (字符 )，但最終結(jié)果必定是機器語言。 ② 缺點 ?匯編語句和機器指令基本上是一對一的，所以匯編語言的編程效率并沒有質(zhì)的提高。機器指令即二進制數(shù)，通常由若干字節(jié)構(gòu)成。 所以，程序設計語言極大地提高了編程效率，大幅度地降低了編程難度。 工作方式如下圖所示： ② 編譯方式 (Compile) 將源程序全部譯為目標程序，該目標程序可在操作系統(tǒng)環(huán)境下直接執(zhí)行，相應的翻譯程序稱為編譯程序 (Compiler) ，工作方式如下圖所示： 編譯程序 Compile 連接程序 Link 裝入運行 Run 編輯程序 Edit ASCII碼 二進制 (整體未定位 ) 二進制 (整體定位 ) 源程序 結(jié)果 輸入數(shù)據(jù) ?編輯程序的工作結(jié)果是 ASCII碼形式的源程序。 編譯過程概述 典型的編譯程序工作過程是：輸入源程序，對它進行加工處理，最后輸出目標程序（機器語言或匯編語言形式）。, NUL) (39。常用的中間代碼有三元式和四元式。 常數(shù)的二進制值 0000000000000011（ 3） 0000000001000000（ 128） …… 常數(shù)表的結(jié)構(gòu)示意如下： ㈣ 目標代碼生成 (Code Generation) 執(zhí)行目標代碼生成的程序稱為目標代碼生成器。每當識別出一個單詞，就用單詞的內(nèi)部碼（單詞二元式）替換。 NUL 計算園柱體表面積的源程序（輸入輸出略）如下所示： Begin/*S=2** R* R +2** R*H */ Real r,h,s。），當一個單詞過長（例字符串常數(shù)），可分多行列出。 ?定義布爾變量 in_ment，記錄當前處理字符是否處于注釋。 and cur_c=39。 這樣空格、 TAB和換行符不再是沒有意義的了，這也就是為什么在詞法分析預處理中將空格、 TAB和換行符保留下來的原因。狀態(tài)之間用箭弧連接。識別出的字符串（單詞）為 134.。+39。39。 //拼接單詞函數(shù) char reserve(char token[])。 //進入標識符或基本字的識別 if(buf[i]=39。 buf[i]=39。 //找到尾 token[i]=c。 ㈡ 字（字符串） ∑上字符所構(gòu)成的有限序列。 ?正規(guī)式運算符優(yōu)先性依次為 :*、 ) = f(0, 39。路徑上的標記依次連接為 101，則稱 α= 101可為 M所識別或接受。使得 L(M)=L(M39。 ?ε_CLOSURE({X})視為 DFA M39。z39。(39。,字符串 ) ?無符號整常數(shù)： (39。(39。 狀態(tài) /字符 α β = + * , 。+39。$39。39。單詞的前導空格在識別一個單詞前被濾去，單詞的尾部空格用作單詞的終止標志，故在狀態(tài)轉(zhuǎn)換矩陣中，應增加空格列，該列每個元素的值均標記為 0。 ?單詞二元式編碼表 0. procedur scanner( ) 1. ←39。 1. 句子 → 主語 謂語 2. 主語 → 冠詞 形容詞 名詞 3. 冠詞 →the|a 4. 形容詞 →big 5. 名詞 →elephant|banana 6. 謂語 → 動詞 直接賓語 7. 直接賓語 → 冠詞 名詞 8. 動詞 →ate ㈢ 由規(guī)則推導句子 可用規(guī)則來推導出句子。 利用遞歸文法，可以用有窮的規(guī)則來描述無窮的語言，這不但解決了語言的定義問題，而且使得對語言的語法檢查成為可能。但對于程序設計語言來說，上下文無關(guān)文法已經(jīng)夠用了，上下文無關(guān)文法有足夠的能力描述大多數(shù)現(xiàn)今使用的程序設計語言的語法結(jié)構(gòu)。 上述英文句子可用下述規(guī)則來描述： 句子 主語 謂語 冠詞 形容詞 名詞 謂語 the 形容詞 名詞 謂語 the big 名詞 謂語 the big elephant 謂語 the big elephant 動詞 直接賓語 the big elephant ate 直接賓語 the big elephant ate 冠詞 名詞 the big elephant ate a 名詞 the big elephant ate a banana 上述推導可簡單表示為： 句子 the big elephant ate a banana。:←Nul:Token[]← 2. i←i+1:c←buf[i]: 當前狀態(tài) ← 初態(tài) 3． while DFA[當前狀態(tài) ,c]≠0 do 4. Token←Token,c //將 Token中字符串拼接字符 c后送 Token 5. 當前狀態(tài) ← DFA[當前狀態(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(當前狀態(tài) ∈ 終態(tài)集 ) then output Error:exit 12. ← 根據(jù) Token[]查表的結(jié)果 13. if =??? then //?表示單詞二元式編碼表中無 14. if Token首字符是字母 then =?i? //是標識符 15. if Token首字符是數(shù)字 then =?x? //是整常數(shù) 16. ←Token[] //此時單詞有值 17. end if 18. return t 19. end procedure ?控制程序的工作原理和手工構(gòu)造相類似，差異在于如何實現(xiàn)狀態(tài)遷移。在查表時可將 26個字母轉(zhuǎn)換成 1個，例 39。因當前所處狀態(tài) 1為終態(tài)，故識別出一個單詞。+39。因當前所處狀態(tài) 1為終態(tài)，故識別出一個單詞。 ㈢ 掃描器控制程序工作原理 ?每次識別單詞，控制程序總是從初態(tài)出發(fā)，不斷讀入字符，進入下一狀態(tài)，尋求最長匹配，直到無法前進為止，這樣始終多讀一個字符。)39。,字符串 ) ?運算符 :=(39。)39。039。 ?將所有含有原 NFA終態(tài) (即 Y)的 DFA M39。 對于 Σ上的每個正規(guī)式 V，存在一個 Σ上的確定有限自動機 M，使得 L(V)=L(M)。 0 1 1 非確定有限自動機（ NFA） ㈠ NFA定義 一個非確定的有限自動機 M是一個五元式 M=（ S， Σ， f， S0， Z） ?S是一個有限集，它的每一個元素稱為狀態(tài)。) = f(1, 39。 例子詳見本書第 21頁 ㈡ 實際意義 ?有窮字母表 Σ是程序設計語言所使用的字符集的抽象 ?正規(guī)集是程序設計語言單詞集的抽象 ?正規(guī)式是程序設計語言構(gòu)詞規(guī)則的抽象 ㈢ 正規(guī)式相等原理 二個正規(guī)式是相等的，當且僅當二個正規(guī)式所表示的正規(guī)集是相等的。 ε 空字