1、編譯原理第一章 編譯程序概論使用過計算機的人都知道，多數用戶是應用高級語言來實現他們所需要的計算的。在計算機上執行高級語言程序一般分為兩步：第一步，用一個編譯程序把高級語言翻譯成機器語言程序；第二步，運行所得的機器語言程序求得計算結果。計算機語言由單一的機器語言發展到現今內容迥異的數千種高級語言，就是因為有了編譯技術。因此，對于計算機專業的學生來說，理解編譯程序的工作原理顯得尤其重要。本章重點：編譯程序概念、編譯過程概述、編譯程序的結構。第一節 什么是編譯程序通常所說的翻譯程序是指這樣的一個程序，它能夠把某一種語言（稱為源語言）改造為另一種語言（稱為目標語言），而后者與前者在邏輯上是等價的。如

2、果源語言是諸如FORTRAN、PASCAL、ALGOL或COBOL這樣的“高級語言”，而目標語言是諸如匯編語言或機器語言之類的“低級語言”，這樣的一個翻譯程序就稱為編譯程序。它所執行過程可用圖1-1-1來說明高級語言程序 低級語言程序（源程序）（目標程序） 圖1-1-1編譯程序第二節 編譯過程概述第二節 編譯過程概述目標程序源程序詞法分析語法分析語義分析中間代碼生成代碼優化目標代碼生成表格管理出錯處理圖1-2-1編譯程序完成從源程序到目標程序的翻譯工作，是一個復雜的整體的過程。從概念上來說，一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序的一種表示形式轉換成另一種表示形式，各個階

3、段進行的操作在邏輯上是緊密連接在一起的，圖1-2-1給出了一個編譯過程的各個階段，這是一種典型的劃分方法。事實上，某些階段可能組合在一起，這些階段間的源程序的中間表示形式就沒必要構造出來了。圖1-2-1中將編譯過程劃分成了詞法分析、語法分析、中間代碼生成，代碼優化和目標代碼生成六個階段，我們將分別介紹各階段的任務。另外兩個重要的工作：表格管理和出錯處理與上述六個階段都有聯系。編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關的表格，因此需要有表格管理的工作。如果編譯過程中發現源程序有錯誤，編譯程序應報告錯誤的性質和錯誤發生的地點，并且將錯誤所造成的

4、影響限制在盡可有小的范圍內，使得源程序的其余部分能繼續被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。我們從源程序在不同階段所被轉換成的表示形式的不同來介紹各個階段的任務。詞法分析階段： 是編譯過程的第一個階段。這個階段的任務是從左到右一個字符一個字符地讀入源程序，對構成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或符號）。這里所謂的單詞是指邏輯上緊密相連的一組字符，這些字符具有具體含義。比如標識符是由字母字符開頭，后跟字母、數字字符的字符序列組成的一種單詞。保留字（關鍵字或基本字）是一種單詞，此外還有算符，界符等等。例如某源程序片斷如下：begin va

5、r sum, first, count: real; sum :=first + count * 10 end. 詞法分析階段將構成這段程序的字符組成了如下單詞序列：1. 保留字begin2. 保留字var 19. 界 符3. 標識符sum4. 逗 號，5. 標識符first6. 逗 號，7. 標識符count8. 冒 號：9. 保留字real10. 分 號；11. 標識符sum12. 賦值號：=13. 標識符first14. 加 號+15. 標識符fount16. 乘 號*17. 整 數1018. 保留字end 可以看出，五個字符b, e, g, i和n構成一個分類為保留字的單詞begin，

6、兩個字符即：和=構成了表示賦值運算的符號：=。這些單詞間的空格在詞法分析階段都被濾掉了。我們使id1,id2和id3分別表示sum, first和count三個標識符的內部形式，那么經過詞法分析后上述程序片斷中的賦值語句sum ：=firs t+ count * 10則表示為id1：=id2 + id3 * 10語法分析： 是編譯過程的第二個階段。語法分析的任務是在詞法分析的基礎上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達式”等等。一般這種語法短語，也稱語法單位，可表示成語法樹，比如上述程序中的單詞序列：id1：=id2 + id3 * 10 經語法分析得知其是PASCAL語言

7、的“賦值語句”，表示成如圖1-2-2所示的語法樹或是圖1-2-3所示的那種形式。語法分析所依據的是語言的語法規則，即描述程序結構的規則。通過語法分析確定整個輸入串是否構成一個語法上正確的程序。賦值語句標識符 ：=表達式 id1(sum) 表達式 +表達式標識符表達式 *表達式id2(first) 標識符 整數id3(count) 10圖1-2-2 語句id1：=id2 + id3 * 10的語法樹：=+id1*id2di3 10圖1-2-3 語句id1：=id2 + id3 * 10的語法樹的另一種形式程序的結構通常是由遞歸規則表示的，例如，我們可以用下面的規則來定義表達式：（1）任何標識符是

8、表達式。（2）任何常數（整常數、實常數）是表達式。（3）若表達式1和表達式2都是表達式，那么：表達式1+表達式2 表達式1 * 表達式2（表達式1）都是表達式類似地，語句也可以遞歸地定義，如（1）標識符：=表達式 是語句。（2）while （表達式） do 語句和if （表達式） then 語句else 語句都是語句。上述賦值語句id1：=id2 + id3 * 10之所以能表示成圖1-2-3的語法樹，依據的是賦值語句和表達式的定義規則。詞法分析和語法分析本質上都是對源程序的結構進行分析。但詞法分析的任務僅對源程序進行線性掃描即可完成，比如識別標識符，因為標識符的結構是字母打頭的字母和數字串，

9、這只要順序掃描輸入流，遇到即不是字母又不是數字字符時，將前面所發現的所有字母和數字組合在一起而成單詞標識符。但這種線性掃描則不能用于識別遞歸定義的語法成分，比如就不能用此辦法去匹配表達式中的括號。語義分析階段： 是審查源程序有無語義錯誤，為代碼生成階段收集類型信息。比如語義分析的一個工作是進行類型審查，審查每個算符是否具有語言規范允許的運算對象，當不符合語言規范時，編譯程序應報告錯誤。如有的編譯程序要對實數用作數組下標的情況報告錯誤。又比如某些語言規定運算對象可被強制，那么當二目運算施于一整型和一實型時，編譯程序應將整型轉換成實型而不能認為是源程序的錯誤，假如在語句sum：= first +

10、count * 10中，* 的兩個運算對象：count是實型，10是整型，則語義分析階段進行類型審查之后，在語法分析所得到的分析樹上增加一語義處理結點，表示整型變成實型的一目算符inttoreal，則圖1-2-3的樹變成圖1-2-4所示的那樣。：=+id1*id2di3inttoreal10圖 1-2-4 插入語義處理結點的樹中間代碼生成 ： 在進行了上述的語法分析和語義分析階段的工作之后，有的編譯程序將源程序變成一種內部表示形式，這種內部表示形式叫做中間語言或中間代碼。所謂“中間代碼”是一種結構簡單、含義明確的記號系統，這種記號系統可以設計為多種多樣的形式，重要的設計原則為兩點：一是容易生成

11、；二是容易將它翻譯成目標代碼。很多編譯程序采用了一種近似“三地址指令”的“四元式”中間代碼，這種四元式的形式為：（運算符，運算對象1，運算對象2，結果）。比如源程序 sum ：= first = count * 10 可生成四元式序列，如圖1-2-5所示，其中ti( i = 1, 2, 3 )是編譯程序生成的臨時名字，用于存放運算結果的。（1） （inttoreal10 t1）（2）（*id3 t1t2）（3） （+ id2 t2t3）（4）（：=t3id1）圖1-2- 5 中間代碼代碼優化 ： 在此階段的任務是對前階段產生的中間代碼進行變換或進行改造，目的是使生成的目標代碼更為高效，即省時間

12、和省空間，比如圖1-2-5的代碼可變換成圖1-2-6的代碼，僅剩下兩個四元式而執行同樣的計算。也就是編譯程序的這個階段已經把將10轉換成實型數的代碼化簡掉了，同時因為t3僅僅用來將其值傳遞給id1，也可以被化簡掉，這只是優化工作的兩個方面，此外諸如公共子表達式的刪除、強度削弱、循環優化等優化工作將在第十章詳細介紹。（*id310.0t1）（+ id2 t1id1）圖1-2-6 優化后的中間代碼 目標代碼生成：這一階段的任務是把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統結構和指令含義有關，這個階段的工作很復雜，涉及到硬件系統功

13、能部件的運用、機器指令的選擇、各種數據類型變量的存儲空間分配以及寄存器和后緩寄存器的調度等。第三節 編譯程序的結構上述編譯過程的六個階段的任務，再加上用表格管理程序建立變量、常量和過程標識符的說明與引用之間的信息聯系等，用出錯處理程序對詞法和語法分析遇到的錯誤給出在源程序中出錯的 錯誤性質、位置等，可分別由幾個模塊或程序完成，它們分別稱作詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優化程序、目標代碼生成程序、表格管理程序和出錯處理程序。從而可給出一個典型的編譯程序結構框圖，如圖1-3-1所示。源程序目標程序詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優化程序目標

14、代碼生成程序表格管理程序出錯處理程序圖1-3-1編譯程序結構框圖遍：一個編譯過程可由一遍、兩遍或多遍完成。所謂“遍”，也稱作“趟”，是對源程序或其等價的中間語言程序從頭到尾掃視并完成規定任務的過程。每一遍掃視可完成上述一個階段或多個階段的工作。例如一遍可以只完成詞法分析工作；一遍完成詞法分析和語法分析工作；甚至一遍完成整個編譯工作。對于多遍的編譯程序，第一遍的輸入是用戶書寫的源程序，最后一遍的輸出是目標語言程序，其余是上一遍的輸出為下一遍的輸入。在實際的編譯系統的設計中，編譯的幾個階段的工作究竟應該怎樣組合，即編譯程序究竟分成幾遍，參考的因素主要是源語言和機器（目標機）的特征。比如源語言的結構