第1章 編譯程序概論

1、編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理1 語言和翻譯：語言和翻譯：語言是人類交流思想和信息的工具。如自然語言，世界上存在著許多種語言，各國之間要交流信息,就要有各種語言之間的翻譯。計算機語言同樣是豐富多彩的。 由于計算機硬件的器件特性，決定了計算機本身只能直接接受由0和1編碼的二進制指令和數(shù)據(jù)，這種二進制形式的指令集合稱為該計算機的機器語機器語言言，它是計算機惟一能夠直接識別并接受的語言。它是計算機惟一能夠直接識別并接受的語言。1.1 什么是編譯程序什么是編譯程序返回目錄第第1 1章章 編譯程序概論編譯程序概論編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理2 用機器語言編寫程序很不

2、方便且容易出錯，編寫出來的程序也難以調試、閱讀和交流。為此，出現(xiàn)了用助記符代替機器語言二進制編碼的另外一種語言，這就是匯編語言。匯編語言是建立在機器語言之上的，因為它是機器語言的符號化形式，所以較機器語言直觀；但是計算機并不能直接識別這種符號化語言，用匯編語言編寫的程序必須翻譯成機器語言之后才能執(zhí)行，這種“翻譯”是通過專門的軟件匯編程序實現(xiàn)的。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理3 盡管匯編語言與機器語言相比在閱讀和理解上有了長足的進步，但其依賴具體機器的特性是無法改變的，這給程序設計增加了難度。隨著計算機應用需求的不斷增長，出現(xiàn)了更加接近人類自然語言的功能更強、抽象級別更高的面向

3、各種應用的高級語言，如： C 、 FORTRAN、Pascal 、Java、C+等。高級語言已經從具體機器中抽象出來，擺脫了依賴具體機器的問題。用高級語言編制的程序幾乎能夠在不改動的情況下在不同種類的計算機上運行且不易出錯，這是匯編語言難以做到的，但高級語言程序翻譯（編譯）成最終能夠直接執(zhí)行的機器語言程序的難度卻大大增加了。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理4 由于匯編語言和機器語言一樣都是面向機器的，故相對于面向用戶的高級語言來說，它們都稱之為低級語言，而FORTRAN、PASCAL、C、ADA、Java這類面向應用的語言則稱之為高級語言。因此，編譯程序就是指這樣一種程序，通過

4、它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序，編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理5 編譯程序：編譯程序：從功能上看，一個編譯程序就是一個語言翻譯程序。它把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作目標語言)的等價的程序。 源語言通常是一個高級語言，如FORTRAN，C 或Pascal。目標語言通常是一個低級語言,如匯編或機器語言。編譯程序的功能下圖所示。 編譯程序編譯程序高級語言程序高級語言程序（源程序）（源程序）低級語言程序低級語言程序（目標程序）（目標程序）編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理6 如果從計算機系統(tǒng)的角度看

5、，什么是編譯程序呢？我們說編譯程序是一種軟件，是系統(tǒng)軟件。通常認為系統(tǒng)軟件是居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。系統(tǒng)軟件和具體的應用領域無關，如編譯系統(tǒng)和操作系統(tǒng)等。編譯程序也是一種語言處理系統(tǒng)，即把軟件語言書寫的各種程序處理成可在計算機上執(zhí)行的程序。 一個編譯程序的重要性體現(xiàn)在它使得多數(shù)計算機用戶不必考慮與機器有關的繁瑣細節(jié)，使程序員和程序設計專家獨立于機器，這對于當今機器的數(shù)量和種類持續(xù)不斷地增長的年代尤為重要。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理7編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理8可再裝配目標文件可再裝配目標文件需預處理的源程

6、序需預處理的源程序預處理程序預處理程序源程序源程序編譯程序編譯程序匯編程序匯編程序裝配裝配/連接編輯程序連接編輯程序目標匯編程序目標匯編程序可再裝配的機器代碼可再裝配的機器代碼絕對機器代碼絕對機器代碼編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理9 一個高級語言程序的執(zhí)行通常分為兩個階段，即編譯階段和運行階段，如圖所示。編譯階段將源程序變換成目標程序；運行階段則由所生成的目標程序連同運行系統(tǒng)（數(shù)據(jù)空間分配子程序、標準函數(shù)程序等）接受程序的初始數(shù)據(jù)作為輸入，運行后輸出計算結果。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理10源程序源程序編譯程序編譯程序運行系統(tǒng)運行系統(tǒng)目標程序目標程序輸入數(shù)

7、據(jù)輸入數(shù)據(jù)計算結果計算結果編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理11 用高級語言編寫的程序也可通過解釋程序來執(zhí) 行。解釋程序也是一種翻譯程序。 解釋解釋:按源語言的定義邊解釋邊執(zhí)行。解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計算結果計算結果編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理12 優(yōu) 點：交互方便，移植性好。 缺 點：效率低，如循環(huán)語句部分要反復解釋執(zhí)行。 共同點：都需要進行詞法、語法、語義分析。 應 用：數(shù)據(jù)庫系統(tǒng)中的動態(tài)查詢語句（交互性） Java(移植性)。 區(qū) 別：編譯產生目標程序 ， 比喻：筆譯。 解釋不產生目標程序，比喻：口譯。 很多語言如BASIC,LIS

8、P和PROLOG等等最初都是解釋執(zhí)行的，后來也都有了編譯系統(tǒng)。號稱最具生命力的Java環(huán)境同時需要解釋和編譯系統(tǒng)的支持。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理13 編譯程序的工作過程是指從輸入源程序開始到輸出目標程序為止的整個過程，此過程是非常復雜的。一般來說，整個編譯過程可以劃分成五個階段：詞法分析階段、語法分析階段、語義分析和中間代碼生成階段、優(yōu)化階段和目標代碼生成階段。1.2 編譯過程概述編譯過程概述編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理141詞法分析詞法分析詞法分析的任務從左到右讀入源程序的每個字符，對構成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也叫單詞

9、符號或符號）。將所識別出的單詞用統(tǒng)一長度的標準形式（也稱內部碼）來表示，以便于后繼語法工作的進行。因此，詞法分析工作是將源程序中字符串變換成單詞符號流的過程，詞法分析階段工作遵循的是語言的構詞規(guī)則單詞：邏輯上緊密相連的一組字符，這些字符具有集體含義。如：標識符、保留字（關鍵字或基本字）、算符、界符等。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理15例. 某源程序片斷如下：begin var sum , first , count : real ; sum := first + count * 10end.掃描后得到如下單詞序列：1.保 留字var2.標識符sum3.保留字begin3. 逗

10、號,4. 標識符first5. 逗號,6. 標識符count7. 冒號:8. 保留字real9. 分號;10. 標識符sum11. 賦值號:=12. 標識符first13. 加號+14. 標識符count15. 乘號*16. 整數(shù)1017. 保留字end18. 界符.編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理16 2 2語法分析語法分析 語法分析的任務是在詞法分析的基礎上，根據(jù)語言的語法規(guī)則（文法規(guī)則）把單詞符號流分解成各類語法單位（語法范疇），如“短語”、“子句”、“句子（語句）”、“程序段”和“程序”。 通過語法分析確定整個輸入串是否構成一個通過語法分析確定整個輸入串是否構成一個語法

11、上正確的程序。語法上正確的程序。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理17賦值語句賦值語句標識符標識符表達式表達式表達式表達式表達式表達式表達式表達式標識符標識符整數(shù)整數(shù)標識符標識符表達式表達式編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理18id1:=id2+id3*10 的語法樹的另一種形式：編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理19程序結構的遞歸表示表達式的表示：1. 任何標識符是表達式。2. 任何常數(shù)（整常數(shù)、實常數(shù)）是表達式。3. 若表達式1和表達式2都是表達式，那么表達式1+表達式2表達式1*表達式2（表達式1）都是表達式。編譯原理編譯原理編譯原理編譯原理編譯

12、原理編譯原理20 語句的表示： 1.標識符:=表達式 是語句。 2.while (表達式) do 語句和if (表達式) then 語句 else 語句都是語句。 3. 語義分析語義分析 語義分析階段的任務是審查源程序有無語義錯誤。源程序中有些語法成分，按照語法規(guī)則去判斷，它是正確的，但它不符合語義規(guī)則。比如使用了沒有聲明的變量；或者給一個過程名賦值；或者調用函數(shù)時參數(shù)類型不合適或者參加運的兩個變量類型不匹配等等。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理21比如下邊的程序片段：int arr2,c;c = arr1 * 10 ;其中的賦值語句是符合語法規(guī)則的，但是因為沒有聲明變量arr

13、1，而存在語義錯。 一般，語義分析的工作還包括類型審查，類型提升以及為代碼生成階段收集類型信息. 比如審查每個算符是否實施于具有語言規(guī)范允許的運算對象，當不符合語言規(guī)范時，編譯程序應報告錯誤。又比如對實數(shù)用作數(shù)組下標的情況報告錯誤。又比如某些語言規(guī)定運算對象可被強制，那么當二目運算施于一個整型量和編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理22 和一個實型量時，編譯程序應將整型量自動轉換成實型量而不能認為是源程序的錯誤，或者給出警告信息后將整型量自動轉換成實型量。假如在賦值語句sum =first+count*10中，算符*的兩個運算對象分別是count和10,而count是實型變量，10

14、是整型量.語義分析階段進行類型審查之后，將整型量提升為實型量.在語法分析所得到的分析樹上增加一個一目算符結點，這個結點的名稱為inttoreal，表示進行將整型量變成實型量的語義處理，那么，前圖的樹變成下圖所示：編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理23如：類型檢查。如：類型檢查。:=id1+id2*id310sum := first + count * 10編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理24 4.4.中間代碼生成階段中間代碼生成階段在進行了上述的詞法分析，語法分析和語義分析階段的工作之后，有的編譯程序將源程序變成一種內部表示形式，這種內部表示形式叫做中間語言或中間

15、代碼。所謂中間代碼是一種結構簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設計為多種多樣的形式，重要的設計原則為兩點：一是容易生成；二是容易將它翻譯成目標代碼。很多編譯程序采用了一種近似三地址指令的四元式中間代碼，這種四元式的形式為：(運算符，運算對象1，運算對象2，結果)。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理25 如：源程序 sum := first + count * 10 生成的四元式可以是： ( inttoreal 10-t1 ) ( *id3t1t2 ) ( +id2t2t3 ) ( :=t3-id1) 其中ti(i=1,2,3)是編譯程序生成的臨時名字，用于存放運算結果的。

16、編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理26 5代碼優(yōu)化代碼優(yōu)化 優(yōu)化的任務是對前階段產生的中間代碼進行等價變換或改造，以期獲得更為高效（節(jié)省時間和空間）的目標代碼。常用的優(yōu)化措施有刪除冗余運算、刪除無用賦值、合并已知量、循環(huán)優(yōu)化等。例如，其值并不隨循環(huán)而發(fā)生變化的運算可提到進入循環(huán)前計算一次，而不必在循環(huán)中每次循環(huán)都進行計算。優(yōu)化所遵循的原則是程序的等價變換規(guī)則。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理27如：如：( inttoreal10-t1 )( *id3t1t2 )( +id2t2t3 )( :=t3-id1)優(yōu)化后代碼：優(yōu)化后代碼：( * id310.0t1 )(

17、+ id2t1id1 )編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理28 6.目標代碼生成目標代碼生成 任務：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。 特點：與硬件系統(tǒng)結構和指令含義有關，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調度等。 編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理29優(yōu)化代碼：( *id310.0t1 )( +id2t1id1 )例：sum := first + count * 10 匯編代碼：MOVFid3,R2MULF#10.0, R2MOVFid2,R1ADDFR1,

18、R2MOVR1,id1編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理30 編譯過程中源程序的各種信息被保留在不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關的表格，編譯過程的絕大部分時間是用在造表、查表和更新表格的事務上，因此，編譯程序中還應包括一個表格管理程序。 出錯處理與編譯的各個階段都有聯(lián)系，與前三個階段的聯(lián)系尤為密切。出錯處理程序應在發(fā)現(xiàn)錯誤后，將錯誤的有關信息如錯誤類型、出錯地點等向用戶報告。此外，為了盡可能多地發(fā)現(xiàn)錯誤，應在發(fā)現(xiàn)錯誤后還能繼續(xù)編譯下去，以便發(fā)現(xiàn)更多的錯誤。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理31 編譯的各個階段表格管理詞法分析器語法分析器語義

19、分析與中間代碼生成器優(yōu)化目標代碼生成器出錯處理源程序目標程序單詞符號語法單位四元式四元式編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理32源程序源程序表表 格格 管管 理理 程程 序序詞法分析程序詞法分析程序語法分析程序語法分析程序語義分析程序語義分析程序中間代碼生成程序中間代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序目標代碼生成程序目標代碼生成程序出出 錯錯 處處 理理 程程 序序目標程序目標程序1.3 編譯程序的結構編譯程序的結構編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理33 前端（front end）：主要依賴于源語言而與目標機器無關的編譯階段。如：詞法分析、語法分析、語義分析、中間代碼

20、生成、部分優(yōu)化工作、與前端有關的出錯處理工作和符號表管理工作。 后端（后端（back endback end）：）：依賴于目標機而一般不依賴于源語言，只與中間代碼有關的編譯階段。如：目標代碼生成，以及相關出錯處理和符號表操作。 遍（趟）：遍（趟）：對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務的過程。每一遍掃視可完成上述一個階段或多個階段的工作1.4 編譯階段的組合編譯階段的組合編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理34 在實際的編譯系統(tǒng)的設計中，編譯的幾個階段的工作究竟應該怎樣組合，即編譯程序究竟分成幾遍，參考的因素主要是源語言和機器(目標機)的特征。比如源語言的結構直接

21、影響編譯的遍的劃分；像PL/1或ALGOL 68 那樣的語言，允許名字的說明出現(xiàn)在名字的使用之后，那么在看到名字之前是不便為包含該名字的表達式生成代碼的，這種語言的編譯程序至少分成兩遍才容易生成代碼。另外機器的情況，即編譯程序工作的環(huán)境也影響編譯程序的遍數(shù)的劃分。遍數(shù)多一點，整個編譯程序的邏輯結構可能清晰些，但遍數(shù)多即意味著增加讀寫中間文件的次數(shù)，勢必消耗較多時間，一般會比一遍的編譯要慢。 編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理35 雖然從編譯器工作效率的角度講，一遍掃描是最好的。但是，由于各種原因，若干遍掃描也是不可少的。例如，由于中間代碼界定了前端和后端，并且兩個部分的工作有很大

22、區(qū)別，因此，往往至少將前端作為一遍掃描。另外，為了生成高質量的目標代碼，需要對中間代碼進行優(yōu)化，而全局性的控制流和數(shù)據(jù)流分析也應該是對中間代碼的一遍掃描?？傊瑢σ粋€具體的編譯器，要確定用幾遍掃描來完成，需要綜合考慮各種因素，從中取得最佳折中。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理36 編譯技術的發(fā)展編譯技術的發(fā)展 據(jù)說第一個編譯程序的出現(xiàn)是在20世紀50年代早期，很難講出確切的時間，因為當初大量的實驗和實現(xiàn)工作是由不同的小組獨立完成的，多數(shù)早期的編譯工作是將算術公式翻譯成機器代碼。用現(xiàn)在的標準來衡量，當時的編譯程序能完成的工作十分初步，如只允許簡單的單目運算，數(shù)據(jù)元素的命名方式有很

23、多限制。然而它們奠定了對高級語言編譯系統(tǒng)的研究和開發(fā)的基礎。20世紀50年代中期出現(xiàn)了FORTRAN等一批高級語言，相應的一批編譯系統(tǒng)開發(fā)成功。隨著編譯技術的發(fā)展和社會對編譯程序需求的不斷增長，20世紀50年代末有人開始研究編譯程序的自動生成工具，提出并研制編譯程序的編譯程序。它的功能是以任一語言的詞法規(guī)則、語法規(guī)則和語義解釋出發(fā)，自動產生該語言的編譯程序。1.4 編譯技術的發(fā)展和應用編譯技術的發(fā)展和應用編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理37 目前很多自動生成工具已廣泛使用，如詞法分析程序的生成系統(tǒng)LEX，語法分析程序的生成系統(tǒng)YACC等。20世紀60年代起，不斷有人使用自展技術

24、來構造編譯程序。自展的主要特征是用被編譯的語言來書寫該語言自身的編譯程序。1971年，PASCAL的編譯程序用自展技術生成后，其影響就越來越大。隨著并行技術和并行語言的發(fā)展，處理并行語言的并行編譯技術，將串行程序轉換成并行程序的自動并行編譯技術也正在深入研究之中。 另外嵌入式應用迅速增長的需求，推動了交叉編譯技術的發(fā)展.還有系統(tǒng)芯片設計方法和關鍵EDA技術的研究，也帶動了專用語言VHDL等及其編譯技術的不斷深化。 編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理38 應用應用： 1.語言的結構化編輯器 2.語言程序的調試工具 3.語言程序測試工具 4.高級語言之間的轉換工具編譯原理編譯原理編譯

25、原理編譯原理編譯原理編譯原理39 語言的結構化編輯器語言的結構化編輯器 結構化編輯器是引導用戶在語言的語法制導下編制程序，能自動地提供關鍵字和與其匹配的關鍵字，如if后必須有then，begin和end的配對，左右括號的配對等，這樣可以減少語法上的錯誤，可加快對源程序的調試，提高效率和質量。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理40 語言程序的調試工具語言程序的調試工具 調試是軟件開發(fā)過程中一個重要環(huán)節(jié)，結構化編輯器只能解決語法錯誤的問題，而對一個已通過編譯的程序來說，需進一步了解的是程序執(zhí)行的結果與編程人員的意圖是否一致，程序的執(zhí)行是否實現(xiàn)預計的算法和功能。這種對算法的錯誤或程序沒

26、能反應算法的功能等錯誤就需用調試器來協(xié)助解決。調試器的功能愈強，實現(xiàn)愈復雜，但它必須與語法分析、語義處理有緊密聯(lián)系。 編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理41 語言程序測試工具語言程序測試工具 語言程序的測試工具有兩種：靜態(tài)分析器和動態(tài)測試器靜態(tài)分析器和動態(tài)測試器。靜態(tài)分析器是對源程序進行靜態(tài)地分析。它對源程序進行語法分析并制定相應表格，檢查變量定值與引用的關系。如某變量未被賦值就被引用，或定值后未被引用，或多余的源代碼等一些編譯程序的語法分析發(fā)現(xiàn)不了的錯誤。動態(tài)測試工具是在源程序的適當位置插入某些信息，并用測試用例記錄(顯示語句或函數(shù))程序運行時的實際路徑。將運行結果與期望的結果進行比較分析，幫助編程人員查找問題。這種測試工具在國內已有開發(fā)，如FORTRAN語言和C語言的測試工具。編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理42 高級語言之間的轉換工具高級語言之間的轉換工具 由于計算機硬件的不斷更新?lián)Q代，更新更好的程序設計語言的推出為提高計算機的使用效率提供了良好條件，然而一些已有的非常成熟的軟件如何在新機器新語言情況下使用呢?為了減少重新編制程序所耗費的人力和