【正文】 。 ㈡文本文件 (Text File) 文本文件的內(nèi)容由 94個(gè)圖形字符‘ !??~?(33126)和 4個(gè)控制字符換行 (10)、回車 (13)、空格 (32)、 TAB(9)構(gòu)成，文本文件又稱為 ASCII碼文件，擴(kuò)展名通常為 TXT，文件尾用控制字符EOF(26)指示。 目標(biāo)程序是經(jīng)翻譯程序加工后用目標(biāo)語言表示的程序。 解釋程序 Interpreter 源程序 結(jié)果 輸入數(shù)據(jù) 解釋、執(zhí)行 解釋方式主要特點(diǎn)是：用戶程序是消極的。 ?編譯程序以 ASCII碼形式的源程序?yàn)檩斎?，它的工作結(jié)果是二進(jìn)制形式的目標(biāo)程序，但并未包括用戶程序中所使用的系統(tǒng)函數(shù)的目標(biāo)代碼。程序在運(yùn)行過程中讀入數(shù)據(jù)，經(jīng)處理加工后輸出計(jì)算結(jié)果。 ③ 二種翻譯方式比較 解釋方式和編譯方式的主要區(qū)別是：目標(biāo)代碼的執(zhí)行方式不同，基本原理和方法沒有本質(zhì)上的區(qū)別。 2）解釋方式的缺點(diǎn) ?在執(zhí)行時(shí)需動態(tài)地對程序進(jìn)行分析翻譯，開銷大，其執(zhí)行速度相當(dāng)于編譯方式的 1/10至 1/100。整個(gè)過程相當(dāng)復(fù)雜，從數(shù)據(jù)加工的角度來看，可將其分成 4個(gè)邏輯階段，它們是： ?詞法分析 ?語法分析 ?語義分析（中間代碼產(chǎn)生） ?目標(biāo)代碼生成 詞法 分析 語法 分析 語義分析 (中間代碼產(chǎn)生 ) 目標(biāo)代碼 生成 源程序 目標(biāo)程序 編譯程序基本上是按照這個(gè)流程來設(shè)計(jì)的。 ?單詞值：在本書中用字符串表示，語義分析時(shí)用。x39。i39。x39。 任務(wù)：建立符號表和常數(shù)表，記錄源程序中標(biāo)識符屬性和常數(shù)值，根據(jù)語言的語義規(guī)定生成中間代碼。 end 語法正確，不同的語言有不同的語義解釋。 ② 語義翻譯 1)說明語句的翻譯 將標(biāo)識符及其屬性填入符號表。 表達(dá)式 3+abc*128可譯成如下四元式： (*,amp。3,amp。T1和amp。每個(gè)標(biāo)識符在符號表中有一項(xiàng)記錄，用于記錄標(biāo)識符的各種語義值，而在四元式中填寫的是標(biāo)識符在符號表中的記錄地址，通常稱為符號表入口。 任務(wù)：中間代碼 ? 目標(biāo)代碼（機(jī)器指令或匯編語言） 依據(jù)：目標(biāo)機(jī)器的系統(tǒng)結(jié)構(gòu) 假設(shè)模型機(jī)器的指令格式為： op Ri , M （ Ri） op（ M） → Ri op Ri , Rj （ Ri） op（ Rj） → Ri op Ri , C （ Ri） op C → Ri 其中 Ri表示寄存器， M表示內(nèi)存地址（可用符號表示）， C表示常數(shù)。 編譯程序的前端和后端 由于在編譯程序的內(nèi)部引入了中間代碼，這樣可將編譯程序分為二個(gè)相互獨(dú)立部分。相反，若已構(gòu)造了一個(gè)高質(zhì)量的后端，若要在同一臺目標(biāo)機(jī)器上為另一源語言構(gòu)造編譯程序時(shí)，只要構(gòu)造該源語言的前端即可。 ㈣自動構(gòu)造 ①詞法分析器的自動構(gòu)造 輸入詞法規(guī)則，編譯結(jié)果為詞法分析器，例 LEX系統(tǒng) (Lexical Analyzer Generator) 。執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器。 ㈢ 單詞二元式編碼 經(jīng)詞法分析后，單詞用二元式 (code,val) 表示。單詞值表示了單詞的語義特性，在語義分析時(shí)使用。若一個(gè)種別含有多個(gè)單詞，除給出種別外，還需給出它的值。 s=2**r*(r+h) End 根據(jù)單詞二元式編碼，上述程序的單詞二元式序列應(yīng)為： (39。在編制程序時(shí)，必須考慮由于源程序分段讀入所產(chǎn)生的問題。\39。 ?源程序通常帶有注釋，注釋不是程序的必要組成部分。 ?對于 Fortran和 Cobol之類語言，源程序還受到書寫格式的限制。在后面的分析中可以看到，它們的存在反而給后續(xù)的單詞識別帶來方便。識別續(xù)行標(biāo)志，把相繼行捻接在一起，給出語句結(jié)束符。這是編譯程序內(nèi)部的一個(gè)特殊的單詞，以示源程序結(jié)束。 ?若 in_ment 的值為 false，則表示當(dāng)前讀入字符未處于注釋中，此時(shí)應(yīng)將當(dāng)前處理字符存入掃描緩沖區(qū)；若in_ment 的值為 true，則表示當(dāng)前處理字符處于注釋中，此時(shí)無需將該字符存入 buf中，相當(dāng)于掉棄。/39。\39。Z39。/39。 ②基本字、用戶定義的標(biāo)識符和常數(shù)之間可能沒有分隔符。 ?IF(5)=55 IF為數(shù)組名， IF(5)為下標(biāo)變量 ?IF(X+Y)110,120,130 算術(shù) IF，當(dāng) X+Y0，轉(zhuǎn)標(biāo)號為 110的語句；當(dāng) X+Y等于 0，轉(zhuǎn) 標(biāo)號為 120的語句；當(dāng) X+Y0，轉(zhuǎn)標(biāo)號為 130的語句 顯然僅根據(jù) IF無法判斷其為何種單詞，可能是基本字，也可能是標(biāo)識符。為了降低詞法分析器的復(fù)雜性，避免超前搜索，在實(shí)際實(shí)現(xiàn)中，大多數(shù)語言的編譯程序?qū)τ脩舨扇×硕l限制措施： ①所有基本字均為保留字，用戶不得使用它們作為標(biāo)識符。采用上述二條限制措施，對用戶來講是完全可接受的，并且已成為程序員進(jìn)行程序設(shè)計(jì)的慣例。使用遍技術(shù)的優(yōu)點(diǎn)在于，可根據(jù)當(dāng)前遍的工作，裝入相應(yīng)的工作程序。但是，遍數(shù)多勢必增加輸入輸出所耗費(fèi)的時(shí)間。 直接編寫識別無符號實(shí)型常數(shù)的程序有一定難度，狀態(tài)轉(zhuǎn)換圖是構(gòu)造單詞識別程序（掃描器）的一種較好工具。箭弧上的標(biāo)記代表在射出結(jié)狀態(tài)下可能出現(xiàn)的合法的輸入字符。此時(shí)應(yīng)將其退回，下次識別單詞從該字符開始。由于空格的特殊性，狀態(tài)轉(zhuǎn)換圖中用虛線表示（若當(dāng)前輸入字符是空格，重新進(jìn)入 1狀態(tài)）。 ⑤ 一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識別單詞，從初態(tài)出發(fā)，經(jīng)一條通路到達(dá)某一終態(tài)，路徑上的標(biāo)記依次連接而成的字符串，即為狀態(tài)轉(zhuǎn)換圖識別出的單詞。 3 1 ③ . ④ + * 4 ⑥ 一個(gè)程序設(shè)計(jì)語言單詞的識別，可以用若干張狀態(tài)轉(zhuǎn)換圖予以描述，雖然用一張圖也可以，但用若干張圖，有時(shí)會有助于概念的清晰化。否則，或進(jìn)入其它單詞的識別（若有的話），或出錯(cuò)（非法字符）。39。進(jìn)入狀態(tài) 1，在狀態(tài) 1讀入 39。； ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入終態(tài) 11，識別出運(yùn)算符 ++； ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入終態(tài) 12，識別出運(yùn)算符 +，退回 39。進(jìn)入狀態(tài) 1，在狀態(tài) 1讀入 39。； ?從初態(tài) 0出發(fā)，讀入 39。 ?分叉結(jié)點(diǎn)： if語句或 switch語句 ?含自回路結(jié)點(diǎn)： while語句 ?終態(tài)結(jié)點(diǎn)： return語句返回單詞的二元式。 下面是根據(jù)識別標(biāo)識符的狀態(tài)轉(zhuǎn)換圖編制的部分掃描程序。 struct code_val scanner(char *buf)。 //查基本字表函數(shù) struct code_val{ char code。 static int i=0。,NUL}。 //去除前導(dǎo)空格 while(buf[i]==39。a39。z39。amp。039。939。i39。設(shè)在調(diào)用前 token[]內(nèi)容為 beg, 輸入字符ch為 39。token[i]!=39。token[++i]=39。設(shè)置一個(gè)基本字表（包括相應(yīng)二元式編），當(dāng)狀態(tài)轉(zhuǎn)換圖識別出一個(gè)標(biāo)識符時(shí)，就去查對這張表，確定它是基本字還是標(biāo)識符。istrlen(code)。 //標(biāo)識符的單詞種別為 39。 ① 空字 不包含任何字符的字，稱為空字，記為 ε（空字相當(dāng)于高級語言中的空串“”）。 ⑤ （集合的）正則閉包 定義：設(shè) V Σ*， V的正則閉包記為 V+，且定義 V+=VV*。 ?若字符 a∈ ∑，則字符 a是正規(guī)式，相應(yīng)正規(guī)集為 {a}。若 α=β，則 L(αβ)= L(αα)= L(α2)=L(α)2。、 ︱ ,可用園括號改變運(yùn)算順序。 ?描述標(biāo)識符的正規(guī)式： α (α|β)* ?描述二進(jìn)制數(shù)的正規(guī)式： (0|1)(0|1) * ?描述無符號整常數(shù)的正規(guī)式： ββ* ?描述無符號實(shí)常數(shù)的正規(guī)式： ββ*.β*|.ββ* |(ββ*.β*|.ββ*|ββ* )(E|e) (+||ε) ββ* 123. 確定有限自動機(jī)（ DFA） ㈠ DFA定義 一個(gè)確定有限自動機(jī) M是一個(gè)五元式 M = ( S， Σ， f， s0， Z ) ?S是一個(gè)有限集，它的每一個(gè)元素稱為狀態(tài)。 ?Z S，是一個(gè)終態(tài)集。139。139。139。039。 ?若 DFA M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則稱空字 ε可為 DFA M所識別或接受。 L(M) = {α |α為二進(jìn)制數(shù) }。 ?S0 S，是一個(gè)非空初態(tài)集，即 NFA的初態(tài)不一定唯一。 ?若 M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的 ε道路，那么空字 ε可為 M所接受。)，則稱二個(gè)有限自動機(jī) M和 M39。)。 ③ a a a ○ x ε ① ε ② b b b ④ ㈡ NFA?DFA 為了便于描述 NFA確定化算法，我們引進(jìn)二個(gè)概念。 ② Ia I NFA M狀態(tài)集的一個(gè)子集 Ja 從 I出發(fā)經(jīng)一條 a弧所能到達(dá)的狀態(tài)全體 Ia ε_CLOSURE(Ja) 設(shè) I={1}，則 CLOSURE(I)= CLOSURE({1})={1,2}。 因 NFA M具有 6個(gè)狀態(tài)，狀態(tài)子集個(gè)數(shù)（包括空集）最多為 64，故表的長度不會超過 261=63，循環(huán)必然在有限步中結(jié)束。的初態(tài)。 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)。 詞法分析器 的 自動生成器 輸入正規(guī)式 輸出 DFA （狀態(tài)轉(zhuǎn)換矩陣） ㈠ 自動生成過程概述 ①構(gòu)造描述每個(gè)單詞的正規(guī)式 Pi(1≤i≤N)。 ㈡ 實(shí)例（模型語言的詞法） ①模型語言字符集 {39。 39。 39。 39。 ， 39。 39。 } ② 模型語言單詞集 ?基本字： begin、 end、 integer、 real ?標(biāo)識符：以字母開始的數(shù)字字母串 ?無符號整常數(shù)：數(shù)字串 ?運(yùn)算符： +、 * 、 ++、 = ?界符： , 、 。}39。c39。x39。+39。$39。(39。,NUL)、 ) ( 39。,NUL) ② 構(gòu)造 NFA M 實(shí)例解： ①構(gòu)造正規(guī)式 （令 α= a|b|c|d|……|z 、 β= 0|1|2|3|4|5|6|7|8|9） ?標(biāo)識符 α(α|β)* ?無符號整常數(shù) ββ* ?運(yùn)算符 單詞本身（例 39。++的正規(guī)式為 ++） ?界符 單詞本身（例 39。） ?基本字通常是由字母構(gòu)成，符合標(biāo)識符規(guī)則，將基本字作為一種特殊標(biāo)識符來處理（可設(shè)置保留字表，二者區(qū)分可通過查表）。 ( ) 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)。 ?事先設(shè)置一個(gè)單詞二元式編碼表，它包括除標(biāo)識符和整常數(shù)以外的所有單詞（基本字、運(yùn)算符和界符）。 ?DFA每次只能識別一個(gè)單詞，需多次使用 DFA來識別源程序中單詞，直到源程序中的字符全部處理完。 ?從初態(tài) 0出發(fā)，讀入 39。無法前進(jìn)。,x)并退回 39。進(jìn)入狀態(tài) 4，在狀態(tài) 4讀入 39。無法前進(jìn)。,NUL)并退回 39。進(jìn)入狀態(tài) 4，在狀態(tài) 4讀入 39。查表，確認(rèn)識別出單詞為 +，返回單詞二元式編碼 (39。； ?從初態(tài) 0出發(fā)，讀入 39。無法前進(jìn)。,y)并退回 39。進(jìn)入狀態(tài) 10。識別出單詞 意味著整個(gè)源程序中字符全部處理完畢。 ?因 26個(gè)字母作用相同，故可用一列表示。在查表時(shí)可將 10個(gè)數(shù)字轉(zhuǎn)換成 1個(gè)，例 39。a39。 。 39。所謂自動構(gòu)造詞法分析器，實(shí)際上就是構(gòu)造 DFA。 LEX源程序經(jīng) LEX編譯程序（詞法分析器生成工具）加工，編譯的結(jié)果就是與正規(guī)式等價(jià)的確定有限自動機(jī)（狀態(tài)轉(zhuǎn)換矩陣形式）。 ?處于根結(jié)點(diǎn)位置的結(jié)點(diǎn)又稱為開始符號。從開始符號出發(fā)，若能從規(guī)則推導(dǎo)出某符號串，則該符號串就是該文法的合法的句子，反之語法錯(cuò)誤。 一個(gè)語法正確的句子不能保證其語義是正確的，故一個(gè)句子是否正確，需要進(jìn)行語法和語義兩方面檢查。 ②遞歸規(guī)則（直接遞歸）：在規(guī)則的左部和右部有相同的非終結(jié)符。 ?間接左遞歸：若 x=ε，則 V Vy。 上下文無關(guān)文法 形式語言的奠基人喬姆斯基（ Chomsky）將文法分為 4種類型，它們是： ?短語文法（ 0型文法） ?上下文有關(guān)文法（ 1型文法） ?上下文無關(guān)文法（ 2型文法） ?正規(guī)文法（ 3型文法） 這四種文法在形式語言中都有嚴(yán)格的定義。 ?VN是一個(gè)非終結(jié)符的非空有限集，非終結(jié)符通常用大寫字母