【正文】 9。,NUL) ?界符： ,(39。,NUL)、 *(39。,字符串 ) ?運算符 :=(39。,NUL) ?標識符： (39。,NUL)、 integer (39。 、 ( 、 ) 、 ③ 單詞編碼 ?基本字： begin (39。)39。39。*39。+39。039。a39。 ②根據(jù)正規(guī)式 Pi構(gòu)造 NFA Mi(1≤i≤N)，假定初態(tài)均為 0。 5）用（確定的）狀態(tài)轉(zhuǎn)換圖表示 構(gòu)造過程采用子集法，從字的識別角度來看， DFA M39。 ?將所有含有原 NFA終態(tài) (即 Y)的 DFA M39。 3）結(jié)果處理 ?將 I中的每個子集視為 DFA M39。 設(shè) I={5,4,3}，則 CLOSURE(I) = CLOSURE({5,4,3}) = {5, 4, 3, 6, 2, 8, 7}。 ① I的 ε閉包 I的 ε閉包記為 ε_CLOSURE(I)或 CLOSURE(I)，設(shè) I是 NFA M狀態(tài)集的一個子集， I的 ε閉包定義為： ?若狀態(tài) s∈ I，則 s∈ ε_CLOSURE(I)。 對于 Σ上的每個正規(guī)式 V，存在一個 Σ上的確定有限自動機 M，使得 L(V)=L(M)。等價。 ?非確定有限自動機 M所識別的字全體記為 L(M)。 ?Z S，是一個終態(tài)集。 0 1 1 非確定有限自動機（ NFA） ㈠ NFA定義 一個非確定的有限自動機 M是一個五元式 M=（ S， Σ， f， S0， Z） ?S是一個有限集，它的每一個元素稱為狀態(tài)。 ?DFA M所識別的字全體記為 L(M)。 39。) = 1 ㈡ 狀態(tài)轉(zhuǎn)換矩陣 函數(shù) f可用矩陣表示，行表示狀態(tài)，列表示輸入字符，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。) = f(1, 39。}， f， 0， {1}） 其中 f的定義如下： f(0, 39。 例：一個識別二進制數(shù)的確定有限自動機 M=（ {0， 1}， {39。 ?Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。 例子詳見本書第 21頁 ㈡ 實際意義 ?有窮字母表 Σ是程序設(shè)計語言所使用的字符集的抽象 ?正規(guī)集是程序設(shè)計語言單詞集的抽象 ?正規(guī)式是程序設(shè)計語言構(gòu)詞規(guī)則的抽象 ㈢ 正規(guī)式相等原理 二個正規(guī)式是相等的，當且僅當二個正規(guī)式所表示的正規(guī)集是相等的。推廣到一般，正規(guī)式 α自身的 n次積αα…α 是正規(guī)式，可記為 αn，其相應(yīng)正規(guī)集記為 L(αn)，顯然 L(αn)= L(α) n。 ?若 α、 β為正規(guī)式，相應(yīng)正規(guī)集分別記為 L(α)和 L(β)，則 α|β是正規(guī)式，其相應(yīng)正規(guī)集記為 L(α|β) ，且令 L(α|β)=L(α)∪ L(β)。 ?根據(jù)定義可以證明 V+ = V1∪ V2∪ …… ∪ Vn(詳見本書 18頁 )。 ε 空字 { } 空集 {ε} 集合僅有一個元素 ε ② ∑* ∑上所有字的全體，包括 ε。i39。i++) if(strcmp(token,table[i])==0) return code[i]。 char reserve(char token[]) {//基本字及編碼表 const char *table[]={begin,end,integer,real}。\039。\039。i39。)strcpy(,token)。) concat(token,buf[i++])。 amp。 buf[i]=39。){ while(buf[i]=39。 amp。 39。//用于存放單詞二元式，識別前清空。 //靜態(tài)局部變量，掃描緩沖區(qū)指示器。char val[20]。 //單詞識別程序 (掃描器 )，每調(diào)用一次返回一個單詞的二元式。 struct code_val{ //結(jié)構(gòu)用于存放單詞二元式 char code。若終態(tài)結(jié)點帶有星號 39。39。39。y39。+39。+39。+39。是預(yù)處理程序添加的），單詞識別程序（掃描器）共使用狀態(tài)轉(zhuǎn)換圖 5次。 下圖是識別 、 +和 ++的狀態(tài)轉(zhuǎn)換圖。 將上述三個圖合并視為一個圖，初始狀態(tài)為 0。 例，識別實常數(shù)和整常數(shù)的狀態(tài)轉(zhuǎn)換圖如下所示： 空格 數(shù)字 數(shù)字 數(shù)字 ③ 小數(shù)點 ④ 非數(shù)字 * 非數(shù)字非小數(shù)點 小數(shù)點 * 數(shù)字 ⑦ 數(shù)字 ⑧ 非數(shù)字 * 非數(shù)字 （出錯） 設(shè)輸入串為 134.+ …… ，從初態(tài) 0出發(fā)，經(jīng)路徑 到達終態(tài) 5，路徑上標記依次連接而成的字符串為 134.+，退回多讀的字符 39。在識別標識符的過程中，當讀入的字符不是字母或數(shù)字，可能是空格，說明當前正在識別的單詞已完全讀入。 ④單詞的尾部空格作為單詞的結(jié)束標志，單詞的前導(dǎo)空格在識別單詞前濾去，所以在初態(tài) 0有一個標記為空格的自回路。 ② 一個狀態(tài)轉(zhuǎn)換圖包含若干個狀態(tài)（結(jié)點），其中有一個是初態(tài)，用符態(tài)轉(zhuǎn)換圖至少有一個終態(tài)，表示已識別出一個字符串（單詞），終態(tài)用雙圈表示。 ㈡ 狀態(tài)轉(zhuǎn)換圖基本概念及應(yīng)用 ①狀態(tài)轉(zhuǎn)換圖是一個有向圖。 ㈢ 遍和編譯程序的結(jié)構(gòu) 遍決定了編譯程序的結(jié)構(gòu)。當一遍工作完之后，內(nèi)存空間大部分被釋放。詞法分析器對于所有單詞的識別，最多只要向前看一個字符就足夠了。 ②將空格、 TAB和換行符視為界符。 解決辦法是超前搜索，一直掃描到右括號后面的字符。 例標準 Fortran對基本字不加保護，用戶可以把它們用作普通標識符。 then in_ment←false //離開注釋 16. end if 17. old_c←cur_c: cur_c← 文件下一個字符 18. end while 19. i←i+1:buf[i] ←39。 then cur_c← cur_c+32 10. if cur_c=制表符 or cur_c=換行符 then cur_c← 空格 11. i←i+1:buf[i]← cur_c //送入掃描緩沖區(qū) 12. end if 13. end if 14. else //當前字符處于注釋中 15. if old_c=39。 and cur_c=換行符 then i←i 1 //是續(xù)行符 8. else 9. if cur_c≥39。 and cur_c=39。 ?當讀入 “ /*” ，布爾變量 in_ment的值由 false變?yōu)閠rue；當讀入 “ */” ， 布爾變量 in_ment的值由 true變?yōu)?false。 ?每調(diào)用一次，將經(jīng)預(yù)處理的源程序全部送入內(nèi)存中的掃描緩沖區(qū)，供掃描器識別單詞。 b e g i n r e a l r , h , s 。為了簡化判斷，可在預(yù)處理時，將換行符和 TAB統(tǒng)一替換為空格。 詞法分析器可在輸入緩沖區(qū)上直接識別單詞，但從程序設(shè)計的角度來看，若把源程序預(yù)處理一下，則單詞識別就比較容易。 ?有些語言還提供續(xù)行功能（例 C語言中的續(xù)行符 39。為續(xù)行符。例如，由多個字符構(gòu)成的單詞有可能被緩沖區(qū)邊界所打斷（留作習題）。{39。 ㈤ 實例 設(shè)有某一程序設(shè)計語言，其部分單詞二元式編碼如下所示： 單詞 單詞種別 單詞值 integer a NUL real c NUL begin { NUL end } NUL 標識符 i 字符串形式符號名 無符號整常數(shù) x 字符串形式數(shù)字 無符號實常數(shù) y 字符串形式數(shù)字 = = NUL * * NUL + + NUL ( ( NUL ) ) NUL , , NUL 。 ㈣ 編碼原則 ?通常將標識符歸為一種，常數(shù)按類型分種，基本字、運算符及界符采用一符一種。 ?code表示單詞的種別，用整數(shù)碼表示。 單詞類型及二元式編碼 ㈠ 單詞類型 任何程序設(shè)計語言的單詞都可將其分為 5種類型，它們是： ?基本字 real、 integer、 …… ?標識符 通常為以字母開始的數(shù)字字母串（簡單變量、標號、 …… ） ?常數(shù) 整常數(shù)（ 123）、實常數(shù)（ ）、 …… ?運算符 +、 *、 /、 …… ?界符 。 ②語法分析器的自動構(gòu)造 輸入語法規(guī)則，編譯結(jié)果為語法分析器，例 YACC系統(tǒng) (Yet Another CompilerCompiler)。 編譯程序的實現(xiàn)方式 ㈠ 用機器指令或匯編語言手工編寫 傳統(tǒng)方式，能充分發(fā)揮機器的硬件性能，但費時，工作量大。 ㈠編譯程序前端 (The Front End) 組成：詞法分析器、語法分析器和中間代碼產(chǎn)生器 特點：依賴于被編譯的源語言，輸出結(jié)果用中間代碼描述，和目標機器無關(guān)。 表達式 3+abc*128最終形成的匯編語言程序示意如下： Load R0,abc Mul R0,128 Store R0,T1 Load R0,3 Add R0,T1 Store R0,T2 編譯程序在工作過程中可發(fā)現(xiàn)源程序中各種錯誤，錯誤類型及錯誤處理對策簡述如下： ㈠錯誤類型 ?詞法錯誤（可在詞法分析階段發(fā)現(xiàn)） ?語法錯誤（可在語法分析階段發(fā)現(xiàn)） ?語義錯誤（可在語義分析階段發(fā)現(xiàn)） 出錯處理 (Error Handle) ㈡ 出錯處理 ?一旦發(fā)現(xiàn)錯誤，暫停編譯程序工作，指出錯誤的地點和類型。 內(nèi)存地址 符號名 種屬 類型 …… …… 未分配 abc 簡單變量 整型 未分配 T1 簡單變量 整型 未分配 T2 簡單變量 整型 …… …… 符號表的結(jié)構(gòu)示意如下： ?常數(shù)表 (Constant Table) 常數(shù)表用于記錄在源程序中出現(xiàn)的常數(shù)。T2分別表示 T1和 T2在符號表中入口； 而 amp。T1,amp。abc,amp。 2)執(zhí)行語句的翻譯 根據(jù)不同語句的語義，生成邏輯上等價的中間代碼。 ?標準 Fortran語言認為是錯誤的，其不允許不同類型的量進行混合運算。 依據(jù)：語言的語義內(nèi)涵 語義分析（中間代碼產(chǎn)生）主要工作為： ?語義正確性檢查 ?語義翻譯 ①語義正確性檢查 例 2： begin real A。,128) ㈡ 語法分析 (Parsing) 執(zhí)行語法分析任務(wù)的程序稱為語法分析器。,abc) (39。,3) (39。當一個單詞種別中可能有多個單詞時，單詞的值才有意義。 圖示如下： 以算術(shù)表達式 3+abc*128 為例，來說明編譯程序工作過程。 ?解釋方式占用內(nèi)存大 顯然解釋程序的優(yōu)點就是編譯程序的缺點，反之亦然，對于編譯程序的優(yōu)缺點不再重復(fù)敘述。 1）解釋方式的優(yōu)點 ?提供一種直接的交互調(diào)試功能，容易獲得較好的動態(tài)調(diào)試效果。 編譯方式主要特點是：用戶程序是積極的。從整體上來看，程序是不完整的，程序中的部分地址尚未確定（例系統(tǒng)函數(shù)的調(diào)用）。用戶程序運行時，控制點在解釋程序，即用戶程序的執(zhí)行離不開解釋程序。 ㈣二進制文件 (Binary File) 二進制文件由機器指令即二進制數(shù)構(gòu)成，因二進制數(shù)可能是 26，故文件尾用文件長度 (文件的字節(jié)數(shù) )指示，擴展名通常為 EXE。當換行和回車二個控制字符從文本文件讀入內(nèi)存，在 C語言中是用一個字符（換行）表示。 ?對硬件操作困難，高級語言通常提供匯編語言接口。 ?程序設(shè)計語言接近于英語，可理解性好。 ㈢ 程序設(shè)計語言 程序設(shè)計語言又稱高級語言。 ?可充分利用硬件特性 所以，匯編語言在一定程度上降低了程序編制和維護的難度。 ?編程者需協(xié)調(diào)內(nèi)存的使用 所以，機器語言形式的程序編制和維護困難，限制了計算機的推廣和應(yīng)用。 2203 8210 2602 6101 1000 f000 Load R0,3 Mul R0,10 Load R1,2 Add R0,R1 Write R0 Halt void main(void) { cout3*16+2。目標計算機的系統(tǒng)結(jié)構(gòu)和匯編語言的使用方法詳見本書第 7章。 ①優(yōu)點 ?計算機可直接識別執(zhí)行 ?可充分利用硬件特性 ② 缺點 ?可讀性差 ?指令系統(tǒng)隨機種而異 ?由于機器指令直接或間接含有絕對地址，增加或減少一條指令，可能會引起多條指令的修改。 ?性能較好的匯編語言，可用符號名來表示存儲地址和匯編語句序號，這樣避免了在匯編語句中絕對地址的出現(xiàn)。 ?需匯編程序，將匯編語言譯成機器語言。 ①優(yōu)點 ?獨立于具體計算機，面向過程（函數(shù)）或?qū)ο蟆? ②缺點 ?需翻譯程序，將高級語言譯成機器語言或匯編語言