【正文】 ?VN是一個非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母表示。 ?間接左遞歸：若 x=ε，則 V Vy。 一個語法正確的句子不能保證其語義是正確的，故一個句子是否正確，需要進行語法和語義兩方面檢查。 ?處于根結(jié)點位置的結(jié)點又稱為開始符號。所謂自動構(gòu)造詞法分析器，實際上就是構(gòu)造 DFA。 。在查表時可將 10個數(shù)字轉(zhuǎn)換成 1個，例 39。識別出單詞 意味著整個源程序中字符全部處理完畢。,y)并退回 39。； ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 4，在狀態(tài) 4讀入 39。無法前進。,x)并退回 39。 ?從初態(tài) 0出發(fā)，讀入 39。 ?事先設(shè)置一個單詞二元式編碼表，它包括除標(biāo)識符和整常數(shù)以外的所有單詞（基本字、運算符和界符）。） ?基本字通常是由字母構(gòu)成，符合標(biāo)識符規(guī)則，將基本字作為一種特殊標(biāo)識符來處理（可設(shè)置保留字表，二者區(qū)分可通過查表）。,NUL) ② 構(gòu)造 NFA M 實例解： ①構(gòu)造正規(guī)式 （令 α= a|b|c|d|……|z 、 β= 0|1|2|3|4|5|6|7|8|9） ?標(biāo)識符 α(α|β)* ?無符號整常數(shù) ββ* ?運算符 單詞本身（例 39。(39。+39。c39。 } ② 模型語言單詞集 ?基本字： begin、 end、 integer、 real ?標(biāo)識符：以字母開始的數(shù)字字母串 ?無符號整常數(shù)：數(shù)字串 ?運算符： +、 * 、 ++、 = ?界符： , 、 。 ， 39。 39。 ㈡ 實例（模型語言的詞法） ①模型語言字符集 {39。 4）重新標(biāo)記 狀態(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具有 6個狀態(tài)，狀態(tài)子集個數(shù)（包括空集）最多為 64，故表的長度不會超過 261=63，循環(huán)必然在有限步中結(jié)束。 ③ a a a ○ x ε ① ε ② b b b ④ ㈡ NFA?DFA 為了便于描述 NFA確定化算法，我們引進二個概念。)，則稱二個有限自動機 M和 M39。 ?S0 S，是一個非空初態(tài)集，即 NFA的初態(tài)不一定唯一。 ?若 DFA M的初態(tài)結(jié)同時又是終態(tài)結(jié)，則稱空字 ε可為 DFA M所識別或接受。139。139。 ?描述標(biāo)識符的正規(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)。若 α=β，則 L(αβ)= L(αα)= L(α2)=L(α)2。 ⑤ （集合的）正則閉包 定義：設(shè) V Σ*， V的正則閉包記為 V+，且定義 V+=VV*。 //標(biāo)識符的單詞種別為 39。設(shè)置一個基本字表（包括相應(yīng)二元式編），當(dāng)狀態(tài)轉(zhuǎn)換圖識別出一個標(biāo)識符時，就去查對這張表，確定它是基本字還是標(biāo)識符。token[i]!=39。i39。039。z39。 //去除前導(dǎo)空格 while(buf[i]==39。 static int i=0。 struct code_val scanner(char *buf)。 ?分叉結(jié)點： if語句或 switch語句 ?含自回路結(jié)點： while語句 ?終態(tài)結(jié)點： return語句返回單詞的二元式。進入狀態(tài) 1，在狀態(tài) 1讀入 39。進入終態(tài) 11，識別出運算符 ++； ?從初態(tài) 0出發(fā)，讀入 39。進入狀態(tài) 1，在狀態(tài) 1讀入 39。否則，或進入其它單詞的識別（若有的話），或出錯（非法字符）。 ⑤ 一個狀態(tài)轉(zhuǎn)換圖可用于識別單詞，從初態(tài)出發(fā)，經(jīng)一條通路到達某一終態(tài)，路徑上的標(biāo)記依次連接而成的字符串，即為狀態(tài)轉(zhuǎn)換圖識別出的單詞。此時應(yīng)將其退回，下次識別單詞從該字符開始。 直接編寫識別無符號實型常數(shù)的程序有一定難度，狀態(tài)轉(zhuǎn)換圖是構(gòu)造單詞識別程序（掃描器）的一種較好工具。使用遍技術(shù)的優(yōu)點在于，可根據(jù)當(dāng)前遍的工作，裝入相應(yīng)的工作程序。為了降低詞法分析器的復(fù)雜性，避免超前搜索，在實際實現(xiàn)中，大多數(shù)語言的編譯程序?qū)τ脩舨扇×硕l限制措施： ①所有基本字均為保留字，用戶不得使用它們作為標(biāo)識符。 ②基本字、用戶定義的標(biāo)識符和常數(shù)之間可能沒有分隔符。Z39。/39。這是編譯程序內(nèi)部的一個特殊的單詞，以示源程序結(jié)束。在后面的分析中可以看到，它們的存在反而給后續(xù)的單詞識別帶來方便。 ?源程序通常帶有注釋，注釋不是程序的必要組成部分。在編制程序時，必須考慮由于源程序分段讀入所產(chǎn)生的問題。若一個種別含有多個單詞，除給出種別外，還需給出它的值。 ㈢ 單詞二元式編碼 經(jīng)詞法分析后，單詞用二元式 (code,val) 表示。 ㈣自動構(gòu)造 ①詞法分析器的自動構(gòu)造 輸入詞法規(guī)則，編譯結(jié)果為詞法分析器，例 LEX系統(tǒng) (Lexical Analyzer Generator) 。 編譯程序的前端和后端 由于在編譯程序的內(nèi)部引入了中間代碼，這樣可將編譯程序分為二個相互獨立部分。每個標(biāo)識符在符號表中有一項記錄，用于記錄標(biāo)識符的各種語義值，而在四元式中填寫的是標(biāo)識符在符號表中的記錄地址，通常稱為符號表入口。3,amp。 ② 語義翻譯 1)說明語句的翻譯 將標(biāo)識符及其屬性填入符號表。 任務(wù)：建立符號表和常數(shù)表，記錄源程序中標(biāo)識符屬性和常數(shù)值，根據(jù)語言的語義規(guī)定生成中間代碼。i39。 ?單詞值：在本書中用字符串表示，語義分析時用。 2）解釋方式的缺點 ?在執(zhí)行時需動態(tài)地對程序進行分析翻譯，開銷大，其執(zhí)行速度相當(dāng)于編譯方式的 1/10至 1/100。程序在運行過程中讀入數(shù)據(jù)，經(jīng)處理加工后輸出計算結(jié)果。 解釋程序 Interpreter 源程序 結(jié)果 輸入數(shù)據(jù) 解釋、執(zhí)行 解釋方式主要特點是：用戶程序是消極的。 ㈡文本文件 (Text File) 文本文件的內(nèi)容由 94個圖形字符‘ !??~?(33126)和 4個控制字符換行 (10)、回車 (13)、空格 (32)、 TAB(9)構(gòu)成，文本文件又稱為 ASCII碼文件，擴展名通常為 TXT，文件尾用控制字符EOF(26)指示。 ①優(yōu)點 ?獨立于具體計算機，面向過程（函數(shù)）或?qū)ο蟆? ?性能較好的匯編語言，可用符號名來表示存儲地址和匯編語句序號，這樣避免了在匯編語句中絕對地址的出現(xiàn)。目標(biāo)計算機的系統(tǒng)結(jié)構(gòu)和匯編語言的使用方法詳見本書第 7章。 ?編程者需協(xié)調(diào)內(nèi)存的使用 所以，機器語言形式的程序編制和維護困難，限制了計算機的推廣和應(yīng)用。 ㈢ 程序設(shè)計語言 程序設(shè)計語言又稱高級語言。 ?對硬件操作困難，高級語言通常提供匯編語言接口。 ㈣二進制文件 (Binary File) 二進制文件由機器指令即二進制數(shù)構(gòu)成，因二進制數(shù)可能是 26，故文件尾用文件長度 (文件的字節(jié)數(shù) )指示，擴展名通常為 EXE。從整體上來看，程序是不完整的，程序中的部分地址尚未確定（例系統(tǒng)函數(shù)的調(diào)用）。 1）解釋方式的優(yōu)點 ?提供一種直接的交互調(diào)試功能，容易獲得較好的動態(tài)調(diào)試效果。 圖示如下： 以算術(shù)表達式 3+abc*128 為例，來說明編譯程序工作過程。,3) (39。,128) ㈡ 語法分析 (Parsing) 執(zhí)行語法分析任務(wù)的程序稱為語法分析器。 ?標(biāo)準(zhǔn) Fortran語言認(rèn)為是錯誤的，其不允許不同類型的量進行混合運算。abc,amp。T2分別表示 T1和 T2在符號表中入口； 而 amp。 表達式 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)錯誤，暫停編譯程序工作，指出錯誤的地點和類型。 編譯程序的實現(xiàn)方式 ㈠ 用機器指令或匯編語言手工編寫 傳統(tǒng)方式，能充分發(fā)揮機器的硬件性能，但費時，工作量大。 單詞類型及二元式編碼 ㈠ 單詞類型 任何程序設(shè)計語言的單詞都可將其分為 5種類型，它們是： ?基本字 real、 integer、 …… ?標(biāo)識符 通常為以字母開始的數(shù)字字母串（簡單變量、標(biāo)號、 …… ） ?常數(shù) 整常數(shù)（ 123）、實常數(shù)（ ）、 …… ?運算符 +、 *、 /、 …… ?界符 。 ㈣ 編碼原則 ?通常將標(biāo)識符歸為一種，常數(shù)按類型分種，基本字、運算符及界符采用一符一種。{39。為續(xù)行符。 詞法分析器可在輸入緩沖區(qū)上直接識別單詞，但從程序設(shè)計的角度來看，若把源程序預(yù)處理一下，則單詞識別就比較容易。 b e g i n r e a l r , h , s 。 ?當(dāng)讀入 “ /*” ，布爾變量 in_ment的值由 false變?yōu)閠rue；當(dāng)讀入 “ */” ， 布爾變量 in_ment的值由 true變?yōu)?false。 and cur_c=換行符 then i←i 1 //是續(xù)行符 8. else 9. if cur_c≥39。 then in_ment←false //離開注釋 16. end if 17. old_c←cur_c: cur_c← 文件下一個字符 18. end while 19. i←i+1:buf[i] ←39。 解決辦法是超前搜索，一直掃描到右括號后面的字符。詞法分析器對于所有單詞的識別，最多只要向前看一個字符就足夠了。 ㈢ 遍和編譯程序的結(jié)構(gòu) 遍決定了編譯程序的結(jié)構(gòu)。 ② 一個狀態(tài)轉(zhuǎn)換圖包含若干個狀態(tài)（結(jié)點），其中有一個是初態(tài)，用符態(tài)轉(zhuǎn)換圖至少有一個終態(tài)，表示已識別出一個字符串（單詞），終態(tài)用雙圈表示。在識別標(biāo)識符的過程中，當(dāng)讀入的字符不是字母或數(shù)字，可能是空格，說明當(dāng)前正在識別的單詞已完全讀入。 將上述三個圖合并視為一個圖，初始狀態(tài)為 0。是預(yù)處理程序添加的），單詞識別程序（掃描器）共使用狀態(tài)轉(zhuǎn)換圖 5次。+39。y39。39。 struct code_val{ //結(jié)構(gòu)用于存放單詞二元式 char code。char val[20]。//用于存放單詞二元式，識別前清空。 amp。 buf[i]=39。) concat(token,buf[i++])。i39。\039。i++) if(strcmp(token,table[i])==0) return code[i]。 ε 空字 { } 空集 {ε} 集合僅有一個元素 ε ② ∑* ∑上所有字的全體，包括 ε。 ?若 α、 β為正規(guī)式，相應(yīng)正規(guī)集分別記為 L(α)和 L(β)，則 α|β是正規(guī)式，其相應(yīng)正規(guī)集記為 L(α|β) ，且令 L(α|β)=L(α)∪ L(β)。 例子詳見本書第 21頁 ㈡ 實際意義 ?有窮字母表 Σ是程序設(shè)計語言所使用的字符集的抽象 ?正規(guī)集是程序設(shè)計語言單詞集的抽象 ?正規(guī)式是程序設(shè)計語言構(gòu)詞規(guī)則的抽象 ㈢ 正規(guī)式相等原理 二個正規(guī)式是相等的，當(dāng)且僅當(dāng)二個正規(guī)式所表示的正規(guī)集是相等的。 例：一個識別二進制數(shù)的確定有限自動機 M=（ {0， 1}， {39。) = f(1, 39。 39。 0 1 1 非確定有限自動機（ NFA） ㈠ NFA定義 一個非確定的有限自動機 M是一個五元式 M=（ S， Σ， f， S0， Z） ?S是一個有限集，它的每一個元素稱為狀態(tài)。 ?非確定有限自動機 M所識別的字全體記為 L(M)。 對于 Σ上的每個正規(guī)式 V，存在一個 Σ上的確定有限自動機 M，使得 L(V)=L(M)。 設(shè) I={5,4,3}，則 CLOSURE(I) = CLOSURE({5,4,3}) = {5, 4, 3, 6, 2, 8, 7}。 ?將所有含有原 NFA終態(tài) (即 Y)的 DFA M39。 ②根據(jù)正規(guī)式 Pi構(gòu)造 NFA Mi(1≤i≤N)，假定初態(tài)均為 0。039。*39。