【正文】 控制點(diǎn)在用戶程序自身。 ③ 二種翻譯方式比較 解釋方式和編譯方式的主要區(qū)別是：目標(biāo)代碼的執(zhí)行方式不同，基本原理和方法沒有本質(zhì)上的區(qū)別。 ?使用變量可不預(yù)先定義。 2）解釋方式的缺點(diǎn) ?在執(zhí)行時(shí)需動(dòng)態(tài)地對程序進(jìn)行分析翻譯，開銷大，其執(zhí)行速度相當(dāng)于編譯方式的 1/10至 1/100。 ④對任何一種高級語言，既可采用編譯方式，也可采用解釋方式，包括匯編語言在內(nèi)（ MASM方式和 DEBUG方式）。整個(gè)過程相當(dāng)復(fù)雜，從數(shù)據(jù)加工的角度來看，可將其分成 4個(gè)邏輯階段，它們是： ?詞法分析 ?語法分析 ?語義分析（中間代碼產(chǎn)生） ?目標(biāo)代碼生成 詞法 分析 語法 分析 語義分析 (中間代碼產(chǎn)生 ) 目標(biāo)代碼 生成 源程序 目標(biāo)程序 編譯程序基本上是按照這個(gè)流程來設(shè)計(jì)的。 ㈠詞法分析 (Lexical Analysis) 執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器。 ?單詞值：在本書中用字符串表示，語義分析時(shí)用。為了便于輸入處理，無意義的單詞值用 NUL表示。x39。+39。i39。*39。x39。 任務(wù)：檢查源程序的語法結(jié)構(gòu)是否正確 依據(jù)：語言的語法規(guī)則 在語法分析時(shí)，算術(shù)表達(dá)式 3+abc*128的語法結(jié)構(gòu)應(yīng)表示為x+i*x，語法分析器最終應(yīng)識別出這是一個(gè)算術(shù)表達(dá)式。 任務(wù)：建立符號表和常數(shù)表，記錄源程序中標(biāo)識符屬性和常數(shù)值，根據(jù)語言的語義規(guī)定生成中間代碼。integer B。 end 語法正確，不同的語言有不同的語義解釋。 ?C語言認(rèn)為是正確的，允許混合運(yùn)算，但需轉(zhuǎn)換成相同類型的量，然后再進(jìn)行運(yùn)算。 ② 語義翻譯 1)說明語句的翻譯 將標(biāo)識符及其屬性填入符號表。 ?中間代碼 結(jié)構(gòu)簡單、意義明確的記號系統(tǒng)，非常接近機(jī)器指令，又獨(dú)立于具體機(jī)器。 表達(dá)式 3+abc*128可譯成如下四元式： (*,amp。128,amp。3,amp。T2) 其中， amp。T1和amp。128表示常數(shù) 128在常數(shù)表中的地址。每個(gè)標(biāo)識符在符號表中有一項(xiàng)記錄，用于記錄標(biāo)識符的各種語義值，而在四元式中填寫的是標(biāo)識符在符號表中的記錄地址，通常稱為符號表入口。假定，每個(gè)整常數(shù)在常數(shù)表中占 2個(gè)字節(jié)，每個(gè)實(shí)常數(shù)在常數(shù)表中占 4個(gè)字節(jié)。 任務(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ù)。 ?在發(fā)現(xiàn)錯(cuò)誤后，不中斷編譯程序工作。 編譯程序的前端和后端 由于在編譯程序的內(nèi)部引入了中間代碼，這樣可將編譯程序分為二個(gè)相互獨(dú)立部分。 ㈡編譯程序后端 (The Back End) 組成：目標(biāo)代碼生成器 特點(diǎn)：和源語言無關(guān)，以中間代碼形式的源程序?yàn)檩斎脒M(jìn)行處理，輸出結(jié)果依賴于目標(biāo)機(jī)器。相反，若已構(gòu)造了一個(gè)高質(zhì)量的后端，若要在同一臺目標(biāo)機(jī)器上為另一源語言構(gòu)造編譯程序時(shí)，只要構(gòu)造該源語言的前端即可。 ㈡用高級語言手工編寫 利用已有的高級語言的編譯系統(tǒng)，編寫另一高級語言的全部或部分編譯程序。 ㈣自動(dòng)構(gòu)造 ①詞法分析器的自動(dòng)構(gòu)造 輸入詞法規(guī)則，編譯結(jié)果為詞法分析器，例 LEX系統(tǒng) (Lexical Analyzer Generator) 。 結(jié) 束 第 2章 詞法分析 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造 單詞類型及二元式編碼 源程序的輸入及預(yù)處理 基本字的識別和超前搜索 遍 狀態(tài)轉(zhuǎn)換圖和詞法分析器的手工構(gòu)造 正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成 基本概念 正規(guī)式與正規(guī)集 確定有限自動(dòng)機(jī)（ DFA） 非確定有限自動(dòng)機(jī) （ NFA） 正規(guī)式與確定有限自動(dòng)機(jī)的等價(jià)性 詞法分析器的自動(dòng)生成 詞法分析器的設(shè)計(jì)考慮及 手工構(gòu)造 詞法分析任務(wù)： 從文件讀入源程序，去除源程序中與編譯無關(guān)的編輯字符、注釋等，由字符拼接單詞。執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器。 、 (、 )、 …… ㈡ 單詞的性質(zhì) ?基本字、運(yùn)算符和界符對于某一程序設(shè)計(jì)語言來說是確定的，而源程序中的標(biāo)識符和常數(shù)的個(gè)數(shù)是不確定的，隨源程序而異。 ㈢ 單詞二元式編碼 經(jīng)詞法分析后，單詞用二元式 (code,val) 表示。單詞種別表示單詞的語法特性，在語法分析時(shí)使用。單詞值表示了單詞的語義特性，在語義分析時(shí)使用。 ?如果一個(gè)種別僅包含一個(gè)單詞，那么單詞種別就可代表該單詞，無需給出單詞值。若一個(gè)種別含有多個(gè)單詞，除給出種別外，還需給出它的值。 。 s=2**r*(r+h) End 根據(jù)單詞二元式編碼，上述程序的單詞二元式序列應(yīng)為： (39。,NUL) ………… 源程序的輸入及預(yù)處理 ㈠ 源程序的輸入 ?分段讀入處理（早期） ?全部讀入后處理 源程序以文件形式存于外存，首先要將其讀入內(nèi)存才可進(jìn)行詞法分析。在編制程序時(shí)，必須考慮由于源程序分段讀入所產(chǎn)生的問題。目前計(jì)算機(jī)所使用的的內(nèi)存已超過若干年前硬盤容量，計(jì)算機(jī)內(nèi)存足以容納源程序的全部，故源程序可一次全部讀入內(nèi)存進(jìn)行處理。\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 。 ?源程序通常帶有注釋，注釋不是程序的必要組成部分。\39。 ?對于 Fortran和 Cobol之類語言，源程序還受到書寫格式的限制。 ② 預(yù)處理主要工作 ?刪除注釋 ?刪除續(xù)行符，以及后續(xù)換行符 (0AH)。在后面的分析中可以看到，它們的存在反而給后續(xù)的單詞識別帶來方便。 ?大多數(shù)語言（除 C語言）不區(qū)分大小寫，可在預(yù)處理時(shí)，將大寫字母變換成小寫字母，或相反，以方便后續(xù)處理。識別續(xù)行標(biāo)志，把相繼行捻接在一起，給出語句結(jié)束符。 s = 2 * 3 . 1 4 * r * ( r + h ) e n d \0 . . . \0 上述源程序經(jīng)預(yù)處理后，掃描緩沖區(qū)中的內(nèi)容如下所示： ㈢ 預(yù)處理例 用偽代碼編寫一個(gè)預(yù)處理程序，要求如下： ?去除源程序中注釋（源程序中的注釋用 /*……*/ 標(biāo)記，不允許嵌套使用） ?去除源程序中續(xù)行符（ \） ?將 TAB和換行符替換為空格 ?將大寫字母變換成小寫 ?在源程序尾部添加字符 39。這是編譯程序內(nèi)部的一個(gè)特殊的單詞，以示源程序結(jié)束。 ① 算法說明 ?用偽代碼編寫預(yù)處理程序，輸入和預(yù)處理可同時(shí)進(jìn)行，無需輸入緩沖區(qū)，將讀入后經(jīng)預(yù)處理的源程序直接送掃描緩沖區(qū) buf[1..n]。 ?若 in_ment 的值為 false，則表示當(dāng)前讀入字符未處于注釋中，此時(shí)應(yīng)將當(dāng)前處理字符存入掃描緩沖區(qū)；若in_ment 的值為 true，則表示當(dāng)前處理字符處于注釋中，此時(shí)無需將該字符存入 buf中，相當(dāng)于掉棄。可用變量 cur_c記錄當(dāng)前正在處理的字符，用old_c記錄剛處理過的字符。/39。*39。\39。A39。Z39。*39。/39。39。 ②基本字、用戶定義的標(biāo)識符和常數(shù)之間可能沒有分隔符。讓我們來觀察下面三個(gè) Fortran語言語句。 ?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)識符。若該字符為字母 G或 g，則為邏輯 IF；若為數(shù)字，則為算術(shù) IF；若為 =，則為標(biāo)識符。為了降低詞法分析器的復(fù)雜性，避免超前搜索，在實(shí)際實(shí)現(xiàn)中，大多數(shù)語言的編譯程序?qū)τ脩舨扇×硕l限制措施： ①所有基本字均為保留字，用戶不得使用它們作為標(biāo)識符。在基本字、用戶定義的標(biāo)識符和常數(shù)之間，若沒有運(yùn)算符或界符，則至少用一個(gè)空格（或 TAB、換行符）加以分隔。采用上述二條限制措施，對用戶來講是完全可接受的，并且已成為程序員進(jìn)行程序設(shè)計(jì)的慣例。 遍 ㈠ 遍的基本概念 由外存獲得前一遍的工作結(jié)果 (對于第一遍而言，從外存獲得源程序 )，完成它所含的有關(guān)階段工作之后，再把結(jié)果存于外存。使用遍技術(shù)的優(yōu)點(diǎn)在于，可根據(jù)當(dāng)前遍的工作，裝入相應(yīng)的工作程序。當(dāng)下一遍進(jìn)入后，幾乎可以使用全部存儲空間。但是，遍數(shù)多勢必增加輸入輸出所耗費(fèi)的時(shí)間。在本書中，詞法分析器是以函數(shù)形式書寫的，函數(shù)的返回值是一個(gè)單詞的二元式。 直接編寫識別無符號實(shí)型常數(shù)的程序有一定難度，狀態(tài)轉(zhuǎn)換圖是構(gòu)造單詞識別程序（掃描器）的一種較好工具。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用園圈表示。箭弧上的標(biāo)記代表在射出結(jié)狀態(tài)下可能出現(xiàn)的合法的輸入字符。 例，識別標(biāo)識符的狀態(tài)轉(zhuǎn)換圖如下所示： ○ j x ○ i y ○ k 其中 0為初態(tài)， 2為終態(tài)。此時(shí)應(yīng)將其退回，下次識別單詞從該字符開始。 在詞法分析預(yù)處理中，空格作為界符被保留下來。由于空格的特殊性，狀態(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)換圖識別出的單詞。+39。 3 1 ③ . ④ + * 4 ⑥ 一個(gè)程序設(shè)計(jì)語言單詞的識別，可以用若干張狀態(tài)轉(zhuǎn)換圖予以描述，雖然用一張圖也可以，但用若干張圖，有時(shí)會(huì)有助于概念的清晰化。從初態(tài) 0出發(fā)，若當(dāng)前輸入字符是字母，則進(jìn)入狀態(tài) 1；若為數(shù)字，則進(jìn)入狀態(tài) 3；若為小數(shù)點(diǎn)，則進(jìn)入狀態(tài) 7。否則，或進(jìn)入其它單詞的識別（若有的話），或出錯(cuò)（非法字符）。 空格 + ⑩ + 非 + * ㈢ 利用狀態(tài)轉(zhuǎn)換圖識別單詞 狀態(tài)轉(zhuǎn)換圖每次只能識別一個(gè)單詞，若源程序中有 N個(gè)單詞，則需使用狀態(tài)轉(zhuǎn)換圖 N次。39。 ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入狀態(tài) 1，在狀態(tài) 1讀入 39。進(jìn)入終態(tài) 2，識別出標(biāo)識符 x，退回 39。； ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入狀態(tài) 10，在狀態(tài) 10讀入 39。進(jìn)入終態(tài) 11，識別出運(yùn)算符 ++； ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入狀態(tài) 10，在狀態(tài) 10讀入 39。進(jìn)入終態(tài) 12，識別出運(yùn)算符 +，退回 39。； ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入狀態(tài) 1，在狀態(tài) 1讀入 39。進(jìn)入終態(tài) 2，識別出標(biāo)識符 y，退回 39。； ?從初態(tài) 0出發(fā)，讀入 39。進(jìn)入狀態(tài) 13，識別出單詞 ，識別出單詞 意味著整個(gè)源程序中字符處理完畢。 ?分叉結(jié)點(diǎn)： if語句或 switch語句 ?含自回路結(jié)點(diǎn)： while語句 ?終態(tài)結(jié)點(diǎn)： return語句返回單詞的二元式。*39。 下面是根據(jù)識別標(biāo)識符的狀態(tài)轉(zhuǎn)換圖編制的部分掃描程序。char val[20]。 struct code_val scanner(char *buf)。 void concat(char token[],char c)。 //查基本字表函數(shù) struct code_val{ char code。 }。 static int i=0。 struct code_val t={39。,NUL}。 char token[20]=。 //去除前導(dǎo)空格 while(buf[i]==39。) i++。a39。amp。z39。a39。amp。z39。039。amp。939。 //拼接函數(shù) =reserve(token)。i39。 //是標(biāo)識符 return t。設(shè)在調(diào)用前 token[]內(nèi)容為 beg, 輸入字符ch為 39。則調(diào)用拼接函數(shù) concat后， token的內(nèi)容為 begi。token[i]!=39。i++)。token[++i]=39。 } ② 查基本字表函數(shù) reserve(token[]) 基本字通常是由字母構(gòu)成，符合標(biāo)識符規(guī)則。設(shè)置一個(gè)基本字表（包括相應(yīng)二元式編），當(dāng)狀態(tài)轉(zhuǎn)換圖識別出一個(gè)標(biāo)識符時(shí)，就去查對這張表，確定它是基本字還是標(biāo)識符。 const char code[]={{}ac}。istrlen(cod