【正文】 可在詞法分析階段發(fā)現(xiàn)） ?語法錯誤（可在語法分析階段發(fā)現(xiàn)） ?語義錯誤（可在語義分析階段發(fā)現(xiàn)） 出錯處理 (Error Handle) ㈡ 出錯處理 ?一旦發(fā)現(xiàn)錯誤，暫停編譯程序工作，指出錯誤的地點和類型。 ?在發(fā)現(xiàn)錯誤后，不中斷編譯程序工作。采取某些措施（例錯誤局部化、錯誤校正等），使得源程序的編譯工作可繼續(xù)下去，盡可能發(fā)現(xiàn)源程序中比較多的錯誤。 編譯程序的前端和后端 由于在編譯程序的內(nèi)部引入了中間代碼，這樣可將編譯程序分為二個相互獨立部分。 ㈠編譯程序前端 (The Front End) 組成：詞法分析器、語法分析器和中間代碼產(chǎn)生器 特點：依賴于被編譯的源語言，輸出結(jié)果用中間代碼描述，和目標機器無關(guān)。 ㈡編譯程序后端 (The Back End) 組成：目標代碼生成器 特點：和源語言無關(guān)，以中間代碼形式的源程序為輸入進行處理，輸出結(jié)果依賴于目標機器。 為一個源語言構(gòu)造好前端，若要在某一個特定計算機上構(gòu)造該源語言的編譯程序，只要構(gòu)造這個目標機器的后端即可。相反，若已構(gòu)造了一個高質(zhì)量的后端，若要在同一臺目標機器上為另一源語言構(gòu)造編譯程序時，只要構(gòu)造該源語言的前端即可。 編譯程序的實現(xiàn)方式 ㈠ 用機器指令或匯編語言手工編寫 傳統(tǒng)方式，能充分發(fā)揮機器的硬件性能，但費時，工作量大。 ㈡用高級語言手工編寫 利用已有的高級語言的編譯系統(tǒng)，編寫另一高級語言的全部或部分編譯程序。 ㈢自編譯方式 先用機器或匯編語言構(gòu)造一個小的編譯程序（稱為核），然后以此為工具，構(gòu)造出一個能編譯更多語法成分的編譯程序，像滾雪球一樣逐步擴大（實質(zhì)上是上述二種方式的綜合）。 ㈣自動構(gòu)造 ①詞法分析器的自動構(gòu)造 輸入詞法規(guī)則，編譯結(jié)果為詞法分析器，例 LEX系統(tǒng) (Lexical Analyzer Generator) 。 ②語法分析器的自動構(gòu)造 輸入語法規(guī)則，編譯結(jié)果為語法分析器，例 YACC系統(tǒng) (Yet Another CompilerCompiler)。 結(jié) 束 第 2章 詞法分析 詞法分析器的設計考慮及手工構(gòu)造 單詞類型及二元式編碼 源程序的輸入及預處理 基本字的識別和超前搜索 遍 狀態(tài)轉(zhuǎn)換圖和詞法分析器的手工構(gòu)造 正規(guī)式、自動機及詞法分析器的自動生成 基本概念 正規(guī)式與正規(guī)集 確定有限自動機（ DFA） 非確定有限自動機 （ NFA） 正規(guī)式與確定有限自動機的等價性 詞法分析器的自動生成 詞法分析器的設計考慮及 手工構(gòu)造 詞法分析任務： 從文件讀入源程序，去除源程序中與編譯無關(guān)的編輯字符、注釋等，由字符拼接單詞。每當識別出一個單詞，就用單詞的內(nèi)部碼（單詞二元式）替換。執(zhí)行詞法分析任務的程序稱為詞法分析器。 單詞類型及二元式編碼 ㈠ 單詞類型 任何程序設計語言的單詞都可將其分為 5種類型，它們是： ?基本字 real、 integer、 …… ?標識符 通常為以字母開始的數(shù)字字母串（簡單變量、標號、 …… ） ?常數(shù) 整常數(shù)（ 123）、實常數(shù)（ ）、 …… ?運算符 +、 *、 /、 …… ?界符 。 、 (、 )、 …… ㈡ 單詞的性質(zhì) ?基本字、運算符和界符對于某一程序設計語言來說是確定的，而源程序中的標識符和常數(shù)的個數(shù)是不確定的，隨源程序而異。 ?有些單詞由單個字符構(gòu)成，而有些單詞由多個字符構(gòu)成。 ㈢ 單詞二元式編碼 經(jīng)詞法分析后，單詞用二元式 (code,val) 表示。 ?code表示單詞的種別，用整數(shù)碼表示。單詞種別表示單詞的語法特性，在語法分析時使用。 ?val表示單詞的值，在本書中用字符串表示。單詞值表示了單詞的語義特性，在語義分析時使用。 ㈣ 編碼原則 ?通常將標識符歸為一種，常數(shù)按類型分種，基本字、運算符及界符采用一符一種。 ?如果一個種別僅包含一個單詞，那么單詞種別就可代表該單詞，無需給出單詞值。為了輸入和處理的方便，無意義的單詞值用字符串 NUL表示。若一個種別含有多個單詞，除給出種別外，還需給出它的值。 ㈤ 實例 設有某一程序設計語言，其部分單詞二元式編碼如下所示： 單詞 單詞種別 單詞值 integer a NUL real c NUL begin { NUL end } NUL 標識符 i 字符串形式符號名 無符號整常數(shù) x 字符串形式數(shù)字 無符號實常數(shù) y 字符串形式數(shù)字 = = NUL * * NUL + + NUL ( ( NUL ) ) NUL , , NUL 。 。 NUL 計算園柱體表面積的源程序（輸入輸出略）如下所示： Begin/*S=2** R* R +2** R*H */ Real r,h,s。 s=2**r*(r+h) End 根據(jù)單詞二元式編碼，上述程序的單詞二元式序列應為： (39。{39。,NUL) ………… 源程序的輸入及預處理 ㈠ 源程序的輸入 ?分段讀入處理（早期） ?全部讀入后處理 源程序以文件形式存于外存，首先要將其讀入內(nèi)存才可進行詞法分析。早期計算機內(nèi)存較小，只能在內(nèi)存設置長度有限的緩沖區(qū)，分段讀入源程序進行處理。在編制程序時，必須考慮由于源程序分段讀入所產(chǎn)生的問題。例如，由多個字符構(gòu)成的單詞有可能被緩沖區(qū)邊界所打斷（留作習題）。目前計算機所使用的的內(nèi)存已超過若干年前硬盤容量，計算機內(nèi)存足以容納源程序的全部，故源程序可一次全部讀入內(nèi)存進行處理。 設源程序如下所示，其中 39。\39。為續(xù)行符。 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 。 \n \t s = 2 * 3 . \ \n 1 4 * r * ( r + h ) \n E n d \n \0 . . . . . . \0 源程序讀入后，輸入緩沖區(qū)的內(nèi)容如下所示： ㈡ 預處理 詞法分析器通常由二個部分構(gòu)成： 預處理程序 掃描器（單詞識別程序） ① 分成二部分的理由 ?目前使用的程序設計語言大都采用自由格式書寫，允許在單詞之間存在多余的空格、換行和制表符（ TAB）。 ?源程序通常帶有注釋，注釋不是程序的必要組成部分。 ?有些語言還提供續(xù)行功能（例 C語言中的續(xù)行符 39。\39。），當一個單詞過長（例字符串常數(shù)），可分多行列出。 ?對于 Fortran和 Cobol之類語言，源程序還受到書寫格式的限制。 詞法分析器可在輸入緩沖區(qū)上直接識別單詞，但從程序設計的角度來看，若把源程序預處理一下，則單詞識別就比較容易。 ② 預處理主要工作 ?刪除注釋 ?刪除續(xù)行符，以及后續(xù)換行符 (0AH)。 ?換行符、 TAB和空格具有界符作用，預處理時通常予以保留。在后面的分析中可以看到，它們的存在反而給后續(xù)的單詞識別帶來方便。為了簡化判斷，可在預處理時，將換行符和 TAB統(tǒng)一替換為空格。 ?大多數(shù)語言（除 C語言）不區(qū)分大小寫，可在預處理時，將大寫字母變換成小寫字母，或相反，以方便后續(xù)處理。 ?對于受書寫格式限制的語言（例 Fortran和 Cobol），還應識別標號區(qū)，正確給出語句標號。識別續(xù)行標志，把相繼行捻接在一起，給出語句結(jié)束符。 b e g i n r e a l r , h , s 。 s = 2 * 3 . 1 4 * r * ( r + h ) e n d \0 . . . \0 上述源程序經(jīng)預處理后，掃描緩沖區(qū)中的內(nèi)容如下所示： ㈢ 預處理例 用偽代碼編寫一個預處理程序，要求如下： ?去除源程序中注釋（源程序中的注釋用 /*……*/ 標記，不允許嵌套使用） ?去除源程序中續(xù)行符（ \） ?將 TAB和換行符替換為空格 ?將大寫字母變換成小寫 ?在源程序尾部添加字符 39。39。，這是編譯程序內(nèi)部的一個特殊的單詞，以示源程序結(jié)束。 ?每調(diào)用一次，將經(jīng)預處理的源程序全部送入內(nèi)存中的掃描緩沖區(qū)，供掃描器識別單詞。 ① 算法說明 ?用偽代碼編寫預處理程序，輸入和預處理可同時進行，無需輸入緩沖區(qū)，將讀入后經(jīng)預處理的源程序直接送掃描緩沖區(qū) buf[1..n]。 ?定義布爾變量 in_ment，記錄當前處理字符是否處于注釋。 ?若 in_ment 的值為 false，則表示當前讀入字符未處于注釋中，此時應將當前處理字符存入掃描緩沖區(qū)；若in_ment 的值為 true，則表示當前處理字符處于注釋中，此時無需將該字符存入 buf中，相當于掉棄。 ?當讀入 “ /*” ，布爾變量 in_ment的值由 false變?yōu)閠rue；當讀入 “ */” ， 布爾變量 in_ment的值由 true變?yōu)?false?？捎米兞?cur_c記錄當前正在處理的字符，用old_c記錄剛處理過的字符。 ΧΧΧΧΧ/*ΧΧΧΧΧ*/ΧΧΧΧΧ in_ment: f ……… f / t ………… t / f ……… f 0. procedure pro_process() //掃描緩沖區(qū) buf[ ]和掃描緩沖區(qū)指針 i 1. old_c←? \0?:in_ment←false: cur_c← 文件第一個字符 :i←1 2. while not eof(“”) do //文件尚未處理完 3. if not in_ment then //當前字符未處于注釋中 4. if old_c=39。/39。 and cur_c=39。*39。 then //進入注釋 5. i←i 1:in_ment←true 6. else 7. if old_c=39。\39。 and cur_c=換行符 then i←i 1 //是續(xù)行符 8. else 9. if cur_c≥39。A39。 and cur_c≤39。Z39。 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。*39。 and cur_c=39。/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。39。 20. end procedure 基本字的識別和超前搜索 程序設計語言單詞以基本字識別最為困難，原因如下： ①有些語言對基本字不加保護，用戶可用作普通標識符。 ②基本字、用戶定義的標識符和常數(shù)之間可能沒有分隔符。 例標準 Fortran對基本字不加保護，用戶可以把它們用作普通標識符。讓我們來觀察下面三個 Fortran語言語句。 ?IF()GOTO55 邏輯 IF，當 M等于 5轉(zhuǎn)標號為 55的語句。 ?IF(5)=55 IF為數(shù)組名， IF(5)為下標變量 ?IF(X+Y)110,120,130 算術(shù) IF，當 X+Y0，轉(zhuǎn)標號為 110的語句；當 X+Y等于 0，轉(zhuǎn) 標號為 120的語句；當 X+Y0，轉(zhuǎn)標號為 130的語句 顯然僅根據(jù) IF無法判斷其為何種單詞，可能是基本字，也可能是標識符。 解決辦法是超前搜索，一直掃描到右括號后面的字符。若該字符為字母 G或 g，則為邏輯 IF；若為數(shù)字，則為算術(shù) IF；若為 =，則為標識符。 超前搜索導致詞法分析器實現(xiàn)困難。為了降低詞法分析器的復雜性，避免超前搜索，在實際實現(xiàn)中，大多數(shù)語言的編譯程序?qū)τ脩舨扇×硕l限制措施： ①所有基本字均為保留字，用戶不得使用它們作為標識符。 ②將空格、 TAB和換行符視為界符。在基本字、用戶定義的標識符和常數(shù)之間，若沒有運算符或界符，則至少用一個空格（或 TAB、換行符）加以分隔。 這樣空格、 TAB和換行符不再是沒有意義的了，這也就是為什么在詞法分析預處理中將空格、 TAB和換行符保留下來的原因。采用上述二條限制措施，對用戶來講是完全可接受的，并且已成為程序員進行程序設計的慣例。詞法分析器對于所有單詞的識別，最多只要向前看一個字符就足夠了。 遍 ㈠ 遍的基本概念 由外存獲得前一遍的工作結(jié)果 (對于第一遍而言，從外存獲得源程序 )，完成它所含的有關(guān)階段工作之后，再把結(jié)果存于外存。 ㈡ 遍引入的歷史背景 早期的計算機