編譯原理文檔第一章

1、編譯原理第一章 編譯程序概論使用過(guò)計(jì)算機(jī)的人都知道，多數(shù)用戶是應(yīng)用高級(jí)語(yǔ)言來(lái)實(shí)現(xiàn)他們所需要的計(jì)算的。在計(jì)算機(jī)上執(zhí)行高級(jí)語(yǔ)言程序一般分為兩步：第一步，用一個(gè)編譯程序把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言程序；第二步，運(yùn)行所得的機(jī)器語(yǔ)言程序求得計(jì)算結(jié)果。計(jì)算機(jī)語(yǔ)言由單一的機(jī)器語(yǔ)言發(fā)展到現(xiàn)今內(nèi)容迥異的數(shù)千種高級(jí)語(yǔ)言，就是因?yàn)橛辛司幾g技術(shù)。因此，對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來(lái)說(shuō)，理解編譯程序的工作原理顯得尤其重要。本章重點(diǎn)：編譯程序概念、編譯過(guò)程概述、編譯程序的結(jié)構(gòu)。第一節(jié) 什么是編譯程序通常所說(shuō)的翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語(yǔ)言（稱為源語(yǔ)言）改造為另一種語(yǔ)言（稱為目標(biāo)語(yǔ)言），而后者與前者在邏輯上是等價(jià)的。如

2、果源語(yǔ)言是諸如FORTRAN、PASCAL、ALGOL或COBOL這樣的“高級(jí)語(yǔ)言”，而目標(biāo)語(yǔ)言是諸如匯編語(yǔ)言或機(jī)器語(yǔ)言之類的“低級(jí)語(yǔ)言”，這樣的一個(gè)翻譯程序就稱為編譯程序。它所執(zhí)行過(guò)程可用圖1-1-1來(lái)說(shuō)明高級(jí)語(yǔ)言程序 低級(jí)語(yǔ)言程序（源程序）（目標(biāo)程序） 圖1-1-1編譯程序第二節(jié) 編譯過(guò)程概述第二節(jié) 編譯過(guò)程概述目標(biāo)程序源程序詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成表格管理出錯(cuò)處理圖1-2-1編譯程序完成從源程序到目標(biāo)程序的翻譯工作，是一個(gè)復(fù)雜的整體的過(guò)程。從概念上來(lái)說(shuō)，一個(gè)編譯程序的整個(gè)工作過(guò)程是劃分成階段進(jìn)行的，每個(gè)階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個(gè)階

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

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

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

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

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

8、表達(dá)式。（2）任何常數(shù)（整常數(shù)、實(shí)常數(shù)）是表達(dá)式。（3）若表達(dá)式1和表達(dá)式2都是表達(dá)式，那么：表達(dá)式1+表達(dá)式2 表達(dá)式1 * 表達(dá)式2（表達(dá)式1）都是表達(dá)式類似地，語(yǔ)句也可以遞歸地定義，如（1）標(biāo)識(shí)符：=表達(dá)式 是語(yǔ)句。（2）while （表達(dá)式） do 語(yǔ)句和if （表達(dá)式） then 語(yǔ)句else 語(yǔ)句都是語(yǔ)句。上述賦值語(yǔ)句id1：=id2 + id3 * 10之所以能表示成圖1-2-3的語(yǔ)法樹，依據(jù)的是賦值語(yǔ)句和表達(dá)式的定義規(guī)則。詞法分析和語(yǔ)法分析本質(zhì)上都是對(duì)源程序的結(jié)構(gòu)進(jìn)行分析。但詞法分析的任務(wù)僅對(duì)源程序進(jìn)行線性掃描即可完成，比如識(shí)別標(biāo)識(shí)符，因?yàn)闃?biāo)識(shí)符的結(jié)構(gòu)是字母打頭的字母和數(shù)字串，

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

10、count * 10中，* 的兩個(gè)運(yùn)算對(duì)象：count是實(shí)型，10是整型，則語(yǔ)義分析階段進(jìn)行類型審查之后，在語(yǔ)法分析所得到的分析樹上增加一語(yǔ)義處理結(jié)點(diǎn)，表示整型變成實(shí)型的一目算符inttoreal，則圖1-2-3的樹變成圖1-2-4所示的那樣。：=+id1*id2di3inttoreal10圖 1-2-4 插入語(yǔ)義處理結(jié)點(diǎn)的樹中間代碼生成 ： 在進(jìn)行了上述的語(yǔ)法分析和語(yǔ)義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜃兂梢环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語(yǔ)言或中間代碼。所謂“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)可以設(shè)計(jì)為多種多樣的形式，重要的設(shè)計(jì)原則為兩點(diǎn)：一是容易生成

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

12、和省空間，比如圖1-2-5的代碼可變換成圖1-2-6的代碼，僅剩下兩個(gè)四元式而執(zhí)行同樣的計(jì)算。也就是編譯程序的這個(gè)階段已經(jīng)把將10轉(zhuǎn)換成實(shí)型數(shù)的代碼化簡(jiǎn)掉了，同時(shí)因?yàn)閠3僅僅用來(lái)將其值傳遞給id1，也可以被化簡(jiǎn)掉，這只是優(yōu)化工作的兩個(gè)方面，此外諸如公共子表達(dá)式的刪除、強(qiáng)度削弱、循環(huán)優(yōu)化等優(yōu)化工作將在第十章詳細(xì)介紹。（*id310.0t1）（+ id2 t1id1）圖1-2-6 優(yōu)化后的中間代碼 目標(biāo)代碼生成：這一階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功

13、能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。第三節(jié) 編譯程序的結(jié)構(gòu)上述編譯過(guò)程的六個(gè)階段的任務(wù)，再加上用表格管理程序建立變量、常量和過(guò)程標(biāo)識(shí)符的說(shuō)明與引用之間的信息聯(lián)系等，用出錯(cuò)處理程序?qū)υ~法和語(yǔ)法分析遇到的錯(cuò)誤給出在源程序中出錯(cuò)的 錯(cuò)誤性質(zhì)、位置等，可分別由幾個(gè)模塊或程序完成，它們分別稱作詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和出錯(cuò)處理程序。從而可給出一個(gè)典型的編譯程序結(jié)構(gòu)框圖，如圖1-3-1所示。源程序目標(biāo)程序詞法分析程序語(yǔ)法分析程序語(yǔ)義分析程序中間代碼生成程序代碼優(yōu)化程序目標(biāo)

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