編譯原理(第四版)第1章-緒論

1.1程序設(shè)計(jì)語言和編譯程序1.2編譯程序的歷史及發(fā)展1.3編譯程序的工作過程與結(jié)構(gòu)1.4編譯程序的開發(fā)1.5構(gòu)造編譯程序所應(yīng)掌握的內(nèi)容習(xí)題一第1章緒論1.1程序設(shè)計(jì)語言和編譯程序

計(jì)算機(jī)的誕生是科學(xué)發(fā)展史上的一個(gè)里程碑。經(jīng)過半個(gè)多世紀(jì)的發(fā)展，計(jì)算機(jī)已經(jīng)改變了人類生活、工作的各個(gè)方面，成為人類不可缺少的工具。計(jì)算機(jī)之所以能夠如此廣泛地被應(yīng)用，應(yīng)當(dāng)歸功于高級(jí)程序設(shè)計(jì)語言。計(jì)算機(jī)語言之所以能由最初單一的機(jī)器語言發(fā)展到現(xiàn)今數(shù)千種高級(jí)語言，就是因?yàn)橛辛司幾g程序。沒有高級(jí)語言，計(jì)算機(jī)的推廣應(yīng)用是難以實(shí)現(xiàn)的；而沒有編譯程序，高級(jí)語言就無法使用。編譯理論與技術(shù)也是計(jì)算機(jī)科學(xué)中發(fā)展得最迅速、最成熟的一個(gè)分支，它集中體現(xiàn)了計(jì)算機(jī)發(fā)展的成果與精華。一個(gè)高級(jí)語言程序的執(zhí)行通常分為兩個(gè)階段，即編譯階段和運(yùn)行階段，如圖1–2所示。編譯階段將源程序變換成目標(biāo)程序；運(yùn)行階段則由所生成的目標(biāo)程序連同運(yùn)行系統(tǒng)(數(shù)據(jù)空間分配子程序、標(biāo)準(zhǔn)函數(shù)程序等)接受程序的初始數(shù)據(jù)作為輸入，運(yùn)行后輸出計(jì)算結(jié)果。圖1–2源程序的編譯和運(yùn)行階段

如果編譯生成的目標(biāo)程序是匯編語言形式的，那么在編譯與運(yùn)行階段之間還要添加一個(gè)匯編階段，它將編譯生成的匯編語言目標(biāo)程序再經(jīng)過匯編程序變換成機(jī)器語言目標(biāo)程序，如圖1–3所示。圖1–3源程序的編譯、匯編和運(yùn)行階段

用高級(jí)語言編寫的程序也可通過解釋程序來執(zhí)行。解釋程序也是一種翻譯程序，它將源程序作為輸入，一條語句一條語句地讀入并解釋執(zhí)行，如圖1–4所示。解釋程序與編譯程序的主要區(qū)別是：編譯程序?qū)⒃闯绦蚍g成目標(biāo)程序后再執(zhí)行該目標(biāo)程序；而解釋程序則逐條讀出源程序中的語句并解釋執(zhí)行，即在解釋程序的執(zhí)行過程中并不產(chǎn)生目標(biāo)程序。典型的解釋型高級(jí)語言是BASIC語言。圖1–4解釋程序解釋執(zhí)行過程示意

1.2編譯程序的歷史及發(fā)展

（1）20世紀(jì)40年代，由于馮·諾伊曼在存儲(chǔ)-程序計(jì)算機(jī)方面的開創(chuàng)性工作，計(jì)算機(jī)可以執(zhí)行編寫的一串代碼或程序，這些程序最初都是用機(jī)器語言（MachineLanguage）編寫的。（2）用機(jī)器語言編寫程序很不方便且容易出錯(cuò)，因此這種代碼形式很快就被匯編語言（AssemblyLanguage）取代。在匯編語言中，指令和存儲(chǔ)地址都以符號(hào)形式給出。

（3）1954~1957年，IBMJohnBackus帶領(lǐng)的一個(gè)研究小組對(duì)FORTRAN語言及其編譯器進(jìn)行了開發(fā)。但是，由于對(duì)編譯程序的理論及技術(shù)研究剛剛開始，這個(gè)語言的開發(fā)付出了巨大的辛勞。與此同時(shí)，波蘭語言學(xué)家NoamChomsky開始了他的自然語言結(jié)構(gòu)研究。NoamChomsky根據(jù)文法（Grammar，產(chǎn)生語言的規(guī)則）的難易程度及識(shí)別它們所需的算法對(duì)語言進(jìn)行了分類，定義了0型、1型、2型和3型這四類文法及其相應(yīng)的形式語言，并分別與相應(yīng)的識(shí)別系統(tǒng)相聯(lián)系。

（4）20世紀(jì)70年代后期和80年代初，大量的研究都關(guān)注于編譯器其他部分的自動(dòng)生成，其中包括代碼生成。

（5）現(xiàn)今編譯器的發(fā)展包括了更為復(fù)雜的算法應(yīng)用程序，它用于簡化或推斷程序中的信息，這又與具有此類功能的更為復(fù)雜的程序設(shè)計(jì)語言發(fā)展結(jié)合在一起。其中典型的有用于函數(shù)語言編譯Hindley-Milner類型檢查的統(tǒng)一算法。目前，編譯器已經(jīng)越來越成為基于窗口的交互開發(fā)環(huán)境（InteractiveDevelopmentEnvironment，IDE）的一部分，這個(gè)開發(fā)環(huán)境包括了編輯器、鏈接程序、調(diào)試程序以及項(xiàng)目管理程序。盡管近年來對(duì)IDE進(jìn)行了大量的研究，但是基本的編譯器設(shè)計(jì)在近20年中都沒有多大的改變。（6）現(xiàn)代編譯技術(shù)已轉(zhuǎn)向并行編譯的研究。1.3編譯程序的工作過程與結(jié)構(gòu)

1．詞法分析詞法分析的任務(wù)是輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞符號(hào)，如基本字(if、for、begin等)、標(biāo)識(shí)符、常數(shù)、運(yùn)算符和界符(如“(”、“)”、“=”、“；”)等，將所識(shí)別出的單詞用統(tǒng)一長度的標(biāo)準(zhǔn)形式(也稱內(nèi)部碼)來表示，以便于后繼語法工作的進(jìn)行。因此，詞法分析工作是將源程序中的字符串變換成單詞符號(hào)流的過程，詞法分析所遵循的是語言的構(gòu)詞規(guī)則。

2．語法分析語法分析的任務(wù)是在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則(文法規(guī)則)把單詞符號(hào)流分解成各類語法單位(語法范疇)，如“短語”、“子句”、“句子(語句)”、“程序段”和“程序”。通過語法分析可以確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的“程序”。語法分析所遵循的是語言的語法規(guī)則，語法規(guī)則通常用上下文無關(guān)文法描述。

3．語義分析和中間代碼生成這一階段的任務(wù)是對(duì)各類不同語法范疇按語言的語義進(jìn)行初步翻譯，包含兩個(gè)方面的工作：一是對(duì)每種語法范疇進(jìn)行靜態(tài)語義檢查，如變量是否定義、類型是否正確等；二是在語義檢查正確的情況下進(jìn)行中間代碼的翻譯。注意，中間代碼是介于高級(jí)語言的語句和低級(jí)語言的指令之間的一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，它既有一定程度的抽象，又與低級(jí)語言的指令十分接近，因此轉(zhuǎn)換為目標(biāo)代碼比較容易。把語法范疇翻譯成中間代碼所遵循的是語言的語義規(guī)則，常見的中間代碼有四元式、三元式、間接三元式和逆波蘭記號(hào)等。

4．優(yōu)化優(yōu)化的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得更為高效(節(jié)省時(shí)間和空間)的目標(biāo)代碼。常用的優(yōu)化措施有刪除冗余運(yùn)算、刪除無用賦值、合并已知量、循環(huán)優(yōu)化等。例如，其值并不隨循環(huán)而發(fā)生變化的運(yùn)算可提到進(jìn)入循環(huán)前計(jì)算一次，而不必在循環(huán)中每次循環(huán)都進(jìn)行計(jì)算。優(yōu)化所遵循的原則是程序的等價(jià)變換規(guī)則。

5．目標(biāo)代碼生成這一階段的任務(wù)是把中間代碼(或經(jīng)優(yōu)化處理之后)變換成特定機(jī)器上的機(jī)器語言程序或匯編語言程序，實(shí)現(xiàn)最終的翻譯工作。最后階段的工作因?yàn)槟繕?biāo)語言的關(guān)系而十分依賴硬件系統(tǒng)，即如何充分利用機(jī)器現(xiàn)有的寄存器，合理地選擇指令，生成盡可能短且有效的目標(biāo)代碼，這些都與目標(biāo)機(jī)器的硬件結(jié)構(gòu)有關(guān)。上述編譯過程的五個(gè)階段是編譯程序工作時(shí)的動(dòng)態(tài)特征，編譯程序的結(jié)構(gòu)可以按照這五個(gè)階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。編譯程序的結(jié)構(gòu)示意如圖1–5所示。圖1–5編譯程序結(jié)構(gòu)示意

編譯過程中源程序的各種信息被保留在不同的表格里，編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格，編譯過程的絕大部分時(shí)間都用在造表、查表和更新表格的事務(wù)上，因此，編譯程序中還應(yīng)包括一個(gè)表格管理程序。出錯(cuò)處理與編譯的各個(gè)階段都有聯(lián)系，與前三個(gè)階段的聯(lián)系尤為密切。出錯(cuò)處理程序應(yīng)在發(fā)現(xiàn)錯(cuò)誤后，將錯(cuò)誤的有關(guān)信息如錯(cuò)誤類型、出錯(cuò)地點(diǎn)等向用戶報(bào)告。此外，為了盡可能多地發(fā)現(xiàn)錯(cuò)誤，應(yīng)在發(fā)現(xiàn)錯(cuò)誤后還能繼續(xù)編譯下去，以便發(fā)現(xiàn)更多的錯(cuò)誤。1.4編譯程序的開發(fā)編譯程序的開發(fā)常常采用自編譯、交叉編譯、自展和移植等技術(shù)實(shí)現(xiàn)。

1．自編譯用某種高級(jí)語言書寫自己的編譯程序稱為自編譯。例如，假定A機(jī)器上已有一個(gè)PASCAL語言可以運(yùn)行，則可以用PASCAL語言編寫出一個(gè)功能更強(qiáng)的PASCAL語言編譯程序，然后借助于原有的PASCAL編譯程序?qū)π戮帉懙腜ASCAL編譯程序進(jìn)行編譯，從而在編譯后即得到一個(gè)能在A機(jī)器上運(yùn)行的功能更強(qiáng)的PASCAL編譯程序。

2．交叉編譯交叉編譯是指用A機(jī)器上的編譯程序來產(chǎn)生可在B機(jī)器上運(yùn)行的目標(biāo)代碼。例如，若A機(jī)器上已有C語言可以運(yùn)行，則可用A機(jī)器中的C語言書寫一個(gè)編譯程序，它的源程序是C語言程序，而產(chǎn)生的目標(biāo)程序則是基于B機(jī)器的，即能夠在B機(jī)器上執(zhí)行的低級(jí)語言程序。以上兩種方法都假定已經(jīng)有了一個(gè)系統(tǒng)程序設(shè)計(jì)語言可以使用，若沒有可使用的系統(tǒng)程序設(shè)計(jì)語言，則可采用自展或移植的辦法來開發(fā)編譯程序。

3．自展自展的方法是：首先確定一個(gè)非常簡單的核心語言L0，然后用機(jī)器語言或匯編語言書寫出它的編譯程序T0；再把語言L0擴(kuò)充到L1，此時(shí)有L0

L1，并用L0編寫L1的編譯程序T1(即自編譯)；然后再把語言L1擴(kuò)充為L2，此時(shí)有L1

L2，并用L1編寫L2的編譯程序T2……?這樣不斷擴(kuò)展下去，直到完成所要求的編譯程序?yàn)橹埂?/p>

4．移植移植是指A機(jī)器上的某種高級(jí)語言的編譯程序稍加改動(dòng)后能夠在B機(jī)器上運(yùn)行。一個(gè)程序若能較容易地從A機(jī)器上搬到B機(jī)器上運(yùn)行，則稱該程序是可移植的。移植具有一定的局限性。用系統(tǒng)程序設(shè)計(jì)語言來書寫編譯程序雖然縮短了開發(fā)周期并提高了編譯程序的質(zhì)量，但實(shí)現(xiàn)的自動(dòng)化程度不高。實(shí)現(xiàn)編譯程序的最高境界是能夠有一個(gè)自動(dòng)生成編譯程序的軟件工具，只要把源程序的定義以及機(jī)器語言的描述輸入到該軟件中，就能自動(dòng)生成這個(gè)語言的編譯程序，如圖1–6所示。圖1–6編譯程序自動(dòng)生成示意1.5構(gòu)造編譯程序所應(yīng)掌握的內(nèi)容

(1)對(duì)被編譯的源語言(如C、PASCAL等)，要深刻理解其結(jié)構(gòu)(語法)和含義。例如，下面的for循環(huán)語句：

for(i=1;i<=10+i;i++)

x=x+1;就存在對(duì)循環(huán)終值的理解問題。一種理解是以第一次進(jìn)入for循環(huán)的i值計(jì)算出循環(huán)終值，此循環(huán)終值在循環(huán)中不再改變，也即循環(huán)終值為11；而另一種理解則是循環(huán)終值表達(dá)式10+i中的i值隨循環(huán)在不斷地改變，此時(shí)for語句將出現(xiàn)死循環(huán)。如TURBOPASCAL就是按第一種語義進(jìn)行翻譯的，而TURBOC則是按第二種語義翻譯的。此外，如果出了循環(huán)后還要引用i值，那么這個(gè)i值究竟是循環(huán)終值還是循環(huán)終值加1？因此，對(duì)語義的不同理解可以得到不同的編譯程序。

(2)必須對(duì)目標(biāo)機(jī)器的硬件和指令系統(tǒng)有深刻的了解。例如，產(chǎn)生兩個(gè)數(shù)相加的指令在8086/8088匯編中假定用下面兩種指令實(shí)現(xiàn)：

ADDAX，06或ADDBX，06粗略看來，這兩條加法指令除了寄存器不同外沒有本質(zhì)上的差別，其實(shí)不然。由于AX是累加器，因此，從機(jī)器指令的代碼長度來說(見附錄1)，第一條指令比第二條指令節(jié)省一個(gè)字節(jié)。此外，從PC機(jī)硬件結(jié)構(gòu)來看，AX本身就是累加器且相加的結(jié)果也在累加器中，這就節(jié)省了傳送的時(shí)間；而第二條指令則先要將BX中的值送到累加器中，相加后又要從累加器中取出結(jié)果再送回寄存器BX中。顯然，第二條指令要比第一條指令費(fèi)時(shí)，因此，在可能的情況下，應(yīng)盡量生成像第一條指令這樣的目標(biāo)代碼。

(3)必須熟練掌握編譯方法，編譯方法掌握的如何將直接影響到編譯程序的成敗，一個(gè)好的編譯方法可能得到事半功倍的效果。由于編譯程序是一個(gè)極其復(fù)雜的系統(tǒng)，故在討論中只好把它分解開來，一部分一部分地進(jìn)行研究。在學(xué)習(xí)編譯程序的過程中，應(yīng)注意前后聯(lián)系，切忌用靜止的、孤立的觀點(diǎn)看待問題；作為一門技術(shù)課程，學(xué)習(xí)時(shí)還必須注意理論聯(lián)系實(shí)際，多練習(xí)、多實(shí)踐。習(xí)題一

1.1完成下列選擇題：

(1)構(gòu)造編譯程序應(yīng)掌握

。

a.源程序 b.目標(biāo)語言

c.編譯方法 d.以上三項(xiàng)都是

(2)編譯程序絕大多數(shù)時(shí)間花在

上。

a.出錯(cuò)處理