研究生院第一章

1、1編譯程序高級(jí)教程編譯程序高級(jí)教程Compilers: An Advanced Course馮曉兵馮曉兵E-mail: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所中國(guó)科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室編譯與編程實(shí)驗(yàn)室編譯與編程實(shí)驗(yàn)室2 復(fù)雜的系統(tǒng)工程復(fù)雜的系統(tǒng)工程：現(xiàn)代高性能并行計(jì)算機(jī)在體系設(shè)計(jì)中采用了多層次并行、多級(jí)分布存儲(chǔ)等復(fù)雜結(jié)構(gòu)，加大了開發(fā)高質(zhì)量并行軟件的難度。影響先進(jìn)計(jì)算機(jī)性能的三個(gè)主要因素是：算法、編譯程序和硬件體系結(jié)構(gòu)，必須體系結(jié)構(gòu)、硬件、系統(tǒng)軟件/編程環(huán)境及算法、應(yīng)用等領(lǐng)域有機(jī)結(jié)合、合理分配復(fù)雜性,才能獲得高計(jì)算性能。 3 課程內(nèi)容課程內(nèi)容：本課程介紹了

2、編譯程序的基本構(gòu)造原理和基本實(shí)現(xiàn)技術(shù)，主要內(nèi)容包括形式語(yǔ)言基礎(chǔ)知識(shí)、詞法分析、語(yǔ)法分析及語(yǔ)法制導(dǎo)翻譯、流分析、程序優(yōu)化、代碼生成等編譯理論和技術(shù)。課程目標(biāo)課程目標(biāo)：現(xiàn)代芯片體系結(jié)構(gòu)的設(shè)計(jì)和適應(yīng)這種體系結(jié)構(gòu)的高性能編譯程序的設(shè)計(jì)，在過(guò)去20年里，都取得了巨大的進(jìn)展，但是還存在大量挑戰(zhàn)性問(wèn)題。本課程將介紹當(dāng)代編譯系統(tǒng)普遍使用的成熟技術(shù)，并簡(jiǎn)要介紹部分當(dāng)前的研究熱點(diǎn)問(wèn)題。促進(jìn)算法、編譯程序和體系結(jié)構(gòu)領(lǐng)域研究人員的溝通與合作，使大家具備從事研發(fā)工作的高級(jí)編譯專業(yè)基礎(chǔ)。 4參考書：主要參考書： Alfred V. Aho, Ravi Sethi, Jeffery D. Ullman, Compilers

3、 Principles, Techniques and Tools, Addison-Wesley, 1985參考書：陳火旺等：程序設(shè)計(jì)語(yǔ)言編譯原理（第三版），國(guó)防工業(yè)出版社，2000年呂映芝、張素琴、蔣維杜：編譯原理；清華大學(xué)出版社 1998杜淑敏、王永寧：編譯程序設(shè)計(jì)原理；北京大學(xué)出版社 1986陳意云編著：編譯原理和技術(shù)（第二版，中國(guó)科學(xué)技術(shù)大學(xué)出版社，1997）1.張幸兒：計(jì)算機(jī)編譯原理，科學(xué)出版社，1999年5考核方式：習(xí)題1.課堂開卷考試6第第1 1章章 編譯概論編譯概論編譯的概念編譯的概念編譯的階段編譯的階段編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)與編譯相關(guān)的程序與編譯相關(guān)的程序自舉和移植自

4、舉和移植7編譯的概念（編譯的概念（1 1）編譯：從面向人的編譯：從面向人的源語(yǔ)言源語(yǔ)言表示的算法到面向硬表示的算法到面向硬件的件的目標(biāo)語(yǔ)言目標(biāo)語(yǔ)言表示的算法的一個(gè)表示的算法的一個(gè)等價(jià)變換等價(jià)變換等價(jià)變換：是指功能的等價(jià)性等價(jià)變換：是指功能的等價(jià)性一般程序設(shè)計(jì)語(yǔ)言的定義包括以下三個(gè)方面：一般程序設(shè)計(jì)語(yǔ)言的定義包括以下三個(gè)方面：v語(yǔ)法：指程序的構(gòu)造規(guī)則，目前已較好地形式化語(yǔ)法：指程序的構(gòu)造規(guī)則，目前已較好地形式化v語(yǔ)義：指按語(yǔ)法規(guī)則構(gòu)成的各個(gè)語(yǔ)法成分的含義語(yǔ)義：指按語(yǔ)法規(guī)則構(gòu)成的各個(gè)語(yǔ)法成分的含義，作了一些形式化的探索，作了一些形式化的探索v語(yǔ)用：表示程序與使用者間的關(guān)系，語(yǔ)用：表示程序與使用者間

5、的關(guān)系，一般地，變換要求滿足程序的語(yǔ)義的等價(jià)性一般地，變換要求滿足程序的語(yǔ)義的等價(jià)性8編譯的概念（編譯的概念（2 2）通常通常源語(yǔ)言編寫的程序是編譯器的輸入，用戶用于編源語(yǔ)言編寫的程序是編譯器的輸入，用戶用于編程的通常是某種高級(jí)語(yǔ)言，如程的通常是某種高級(jí)語(yǔ)言，如C C、FortranFortran等等目標(biāo)語(yǔ)言是指目標(biāo)計(jì)算機(jī)的目標(biāo)代碼，有時(shí)也稱目標(biāo)語(yǔ)言是指目標(biāo)計(jì)算機(jī)的目標(biāo)代碼，有時(shí)也稱為機(jī)器代碼，編譯器的輸出是目標(biāo)語(yǔ)言的程序?yàn)闄C(jī)器代碼，編譯器的輸出是目標(biāo)語(yǔ)言的程序但隨著編譯應(yīng)用的發(fā)展，編譯器的輸出也可以但隨著編譯應(yīng)用的發(fā)展，編譯器的輸出也可以是高級(jí)語(yǔ)言的程序（如串行程序的并行編譯），是高級(jí)語(yǔ)言的

6、程序（如串行程序的并行編譯），而編譯器的輸入也可以是某種機(jī)器代碼（如二進(jìn)而編譯器的輸入也可以是某種機(jī)器代碼（如二進(jìn)制翻譯、動(dòng)態(tài)優(yōu)化器等）制翻譯、動(dòng)態(tài)優(yōu)化器等）編譯只是一個(gè)對(duì)程序進(jìn)行靜態(tài)優(yōu)化的過(guò)程嗎？編譯只是一個(gè)對(duì)程序進(jìn)行靜態(tài)優(yōu)化的過(guò)程嗎？編譯不僅可以在靜態(tài)時(shí)刻完成，也可以在動(dòng)態(tài)時(shí)編譯不僅可以在靜態(tài)時(shí)刻完成，也可以在動(dòng)態(tài)時(shí)刻進(jìn)行，甚至可以實(shí)行動(dòng)靜態(tài)信息的交互刻進(jìn)行，甚至可以實(shí)行動(dòng)靜態(tài)信息的交互編譯器處理的語(yǔ)言以及編譯器的實(shí)現(xiàn)語(yǔ)言對(duì)編編譯器處理的語(yǔ)言以及編譯器的實(shí)現(xiàn)語(yǔ)言對(duì)編譯器有重要的影響譯器有重要的影響9編譯的階段（編譯的階段（1 1）人進(jìn)行進(jìn)行漢英翻譯的過(guò)程：信、達(dá)、雅的翻人進(jìn)行進(jìn)行漢英翻譯的

7、過(guò)程：信、達(dá)、雅的翻譯目標(biāo)譯目標(biāo)識(shí)別句子中的一個(gè)個(gè)單詞識(shí)別句子中的一個(gè)個(gè)單詞分析句子的語(yǔ)法結(jié)構(gòu)分析句子的語(yǔ)法結(jié)構(gòu)根據(jù)語(yǔ)義進(jìn)行初步翻譯根據(jù)語(yǔ)義進(jìn)行初步翻譯對(duì)譯文進(jìn)行修飾對(duì)譯文進(jìn)行修飾寫出最后的譯文寫出最后的譯文10一個(gè)中英翻譯的例子一個(gè)中英翻譯的例子If you do not leave me, I will stand by your side until the life ends.你如果不離開我，我就和你同歸于盡。你如果不離開我，我就和你同歸于盡。 （四級(jí)水平）（四級(jí)水平） 你若不離不棄，我必生死相依。你若不離不棄，我必生死相依。 （六級(jí)水平）（六級(jí)水平） 問(wèn)世間情為何物？直教人生死相許。

8、問(wèn)世間情為何物？直教人生死相許。 （八級(jí)水平）（八級(jí)水平） 山無(wú)棱，天地合，乃敢與君絕。山無(wú)棱，天地合，乃敢與君絕。 （專家水平）（專家水平） 你在或不在，愛(ài)就在那里，不增不減。你在或不在，愛(ài)就在那里，不增不減。 （圣者水平）（圣者水平） 11編譯的階段（編譯的階段（2 2）編譯是一個(gè)類似的過(guò)程，一般一個(gè)編譯器不僅編譯是一個(gè)類似的過(guò)程，一般一個(gè)編譯器不僅要將源程序翻譯為等價(jià)的可以執(zhí)行的目標(biāo)程序要將源程序翻譯為等價(jià)的可以執(zhí)行的目標(biāo)程序，還要對(duì)程序進(jìn)行優(yōu)化。因此一個(gè)編譯器包括，還要對(duì)程序進(jìn)行優(yōu)化。因此一個(gè)編譯器包括以下幾個(gè)階段：以下幾個(gè)階段：詞法分析程序（詞法分析程序（scanner）：）：將源程

9、序的字符流將源程序的字符流組成記號(hào)流組成記號(hào)流記號(hào)表示邏輯上有內(nèi)聚力的字符序列記號(hào)表示邏輯上有內(nèi)聚力的字符序列形成記號(hào)的字符序列稱為該記號(hào)的單詞形成記號(hào)的字符序列稱為該記號(hào)的單詞賦值語(yǔ)句：賦值語(yǔ)句：a index = 4 + 2詞法分析后形成詞法分析后形成8個(gè)單詞：標(biāo)識(shí)符個(gè)單詞：標(biāo)識(shí)符a、左括號(hào)左括號(hào)、標(biāo)、標(biāo)識(shí)符識(shí)符index、右括號(hào)右括號(hào)、賦值號(hào)、賦值號(hào)=、數(shù)字、數(shù)字4、加號(hào)、加號(hào)+、數(shù)字?jǐn)?shù)字2詞法分析同時(shí)完成一些可行的操作，如填符號(hào)表詞法分析同時(shí)完成一些可行的操作，如填符號(hào)表12編譯的階段（編譯的階段（3 3）語(yǔ)法分析程序（語(yǔ)法分析程序（parser）：）：語(yǔ)法分析語(yǔ)法分析syntax a

10、nalysis將記號(hào)流按語(yǔ)言的語(yǔ)法結(jié)構(gòu)層次分組，得到語(yǔ)法將記號(hào)流按語(yǔ)言的語(yǔ)法結(jié)構(gòu)層次分組，得到語(yǔ)法短語(yǔ)短語(yǔ)語(yǔ)法分析得到分析樹或語(yǔ)法樹語(yǔ)法分析得到分析樹或語(yǔ)法樹分析樹：內(nèi)部節(jié)點(diǎn)由其表示的結(jié)構(gòu)名標(biāo)出，而葉分析樹：內(nèi)部節(jié)點(diǎn)由其表示的結(jié)構(gòu)名標(biāo)出，而葉子節(jié)點(diǎn)表示輸入的記號(hào)流子節(jié)點(diǎn)表示輸入的記號(hào)流13編譯的階段（編譯的階段（4 4）賦值語(yǔ)句表達(dá)式表達(dá)式=下標(biāo)表達(dá)式加法表達(dá)式表達(dá)式表達(dá)式表達(dá)式+表達(dá)式標(biāo)標(biāo)識(shí)識(shí)符符a標(biāo)標(biāo)識(shí)識(shí)符符index數(shù)數(shù)字字4數(shù)數(shù)字字214編譯的階段（編譯的階段（5 5）語(yǔ)法樹：是分析樹中所含信息的濃縮，也可以稱語(yǔ)法樹：是分析樹中所含信息的濃縮，也可以稱為抽象語(yǔ)法樹（為抽象語(yǔ)法樹（AST

11、），），算符作為內(nèi)部節(jié)點(diǎn)出現(xiàn)算符作為內(nèi)部節(jié)點(diǎn)出現(xiàn)賦值語(yǔ)句下標(biāo)表達(dá)式加法表達(dá)式標(biāo)標(biāo)識(shí)識(shí)符符a標(biāo)標(biāo)識(shí)識(shí)符符index數(shù)數(shù)字字4數(shù)數(shù)字字215編譯的階段（編譯的階段（6 6）語(yǔ)義分析程序（語(yǔ)義分析程序（semantic analyzer）：）：檢查程序檢查程序的語(yǔ)義正確性的語(yǔ)義正確性程序的語(yǔ)義決定了程序的運(yùn)行程序的語(yǔ)義決定了程序的運(yùn)行程序設(shè)計(jì)語(yǔ)言中存在在執(zhí)行前可以確定而不易被程序設(shè)計(jì)語(yǔ)言中存在在執(zhí)行前可以確定而不易被語(yǔ)法表示的特征，這些特征稱為靜態(tài)語(yǔ)義，這也語(yǔ)法表示的特征，這些特征稱為靜態(tài)語(yǔ)義，這也是語(yǔ)義分析的內(nèi)容是語(yǔ)義分析的內(nèi)容一般，典型的靜態(tài)語(yǔ)義包括聲明和類型檢查等一般，典型的靜態(tài)語(yǔ)義包括聲明和

12、類型檢查等由語(yǔ)義分析程序計(jì)算得到的額外信息（如數(shù)據(jù)類由語(yǔ)義分析程序計(jì)算得到的額外信息（如數(shù)據(jù)類型）等作為屬性（型）等作為屬性（attribute），），填加到填加到AST中中16編譯的階段（編譯的階段（7 7）賦值語(yǔ)句下標(biāo)表達(dá)式整形加法表達(dá)式整形標(biāo)標(biāo)識(shí)識(shí)符符a整形數(shù)組標(biāo)標(biāo)識(shí)識(shí)符符index整形數(shù)數(shù)字字4整形數(shù)數(shù)字字2整形17編譯的階段（編譯的階段（8 8）源程序優(yōu)化程序（源程序優(yōu)化程序（source code optimizer）：）：代代碼的改進(jìn)只依賴于源代碼碼的改進(jìn)只依賴于源代碼各個(gè)編譯器由于接受的源語(yǔ)言、目標(biāo)語(yǔ)言的不同各個(gè)編譯器由于接受的源語(yǔ)言、目標(biāo)語(yǔ)言的不同，優(yōu)化的目標(biāo)不同等，采用的優(yōu)

13、化手段也是不同，優(yōu)化的目標(biāo)不同等，采用的優(yōu)化手段也是不同的。的。在編譯時(shí)刻完成可以靜態(tài)完成的操作，是優(yōu)化的在編譯時(shí)刻完成可以靜態(tài)完成的操作，是優(yōu)化的一個(gè)典型手段一個(gè)典型手段賦值語(yǔ)句下標(biāo)表達(dá)式整形標(biāo)標(biāo)識(shí)識(shí)符符a整形數(shù)組標(biāo)標(biāo)識(shí)識(shí)符符index整形數(shù)數(shù)字字6整形18編譯的階段（編譯的階段（9 9）代碼生成器（代碼生成器（code generator）：）：生成目標(biāo)代碼生成目標(biāo)代碼目標(biāo)機(jī)器的特性成為主要影響因素目標(biāo)機(jī)器的特性成為主要影響因素指令選擇、寄存器分配、數(shù)據(jù)表示形式等指令選擇、寄存器分配、數(shù)據(jù)表示形式等MOVR0 , index/ index的值的值=R0MULR0 , 2MOVR1 , &a

14、/ a的首地址的首地址=R1ADDR1 , R0/ 計(jì)算計(jì)算aindex的地址的地址MOV*R1 , 6/ 賦值賦值19編譯的階段（編譯的階段（1010）目標(biāo)代碼優(yōu)化器（目標(biāo)代碼優(yōu)化器（target code optimizer）：）：改進(jìn)改進(jìn)目標(biāo)代碼目標(biāo)代碼選擇編址模式提高性能選擇編址模式提高性能將速度慢的指令換為速度快的指令將速度慢的指令換為速度快的指令刪除多余的代碼刪除多余的代碼寄存器優(yōu)化寄存器優(yōu)化軟流水等軟流水等MOVR0 , index/ index的值的值=R0SHLR0/ R0*2MOV&aR0 , 6/ 賦值賦值20編譯的階段（編譯的階段（1111）中間代碼的生成可以被認(rèn)為是一

15、個(gè)獨(dú)立的階段，中間代碼的生成可以被認(rèn)為是一個(gè)獨(dú)立的階段，但其工作可以在三個(gè)分析階段逐步完成，因此我但其工作可以在三個(gè)分析階段逐步完成，因此我們不把它單獨(dú)出來(lái)們不把它單獨(dú)出來(lái)編譯器與上述各階段：通常編譯器通常包含上述編譯器與上述各階段：通常編譯器通常包含上述幾個(gè)階段幾個(gè)階段但不同的編譯器由于要求的不同，因此上述各個(gè)但不同的編譯器由于要求的不同，因此上述各個(gè)階段不是一定要出現(xiàn)的階段不是一定要出現(xiàn)的在不同的編譯器中，上述各個(gè)階段的結(jié)構(gòu)細(xì)節(jié)差在不同的編譯器中，上述各個(gè)階段的結(jié)構(gòu)細(xì)節(jié)差異很大異很大各個(gè)階段間存在著先后的次序關(guān)系，但不是絕對(duì)各個(gè)階段間存在著先后的次序關(guān)系，但不是絕對(duì)的，如詞法分析程序通常作

16、為語(yǔ)法分析程序的一的，如詞法分析程序通常作為語(yǔ)法分析程序的一個(gè)過(guò)程調(diào)用，每次返回一個(gè)記號(hào)供語(yǔ)法分析使用個(gè)過(guò)程調(diào)用，每次返回一個(gè)記號(hào)供語(yǔ)法分析使用21編譯的主要數(shù)據(jù)結(jié)構(gòu)（編譯的主要數(shù)據(jù)結(jié)構(gòu)（1 1）編譯器與其使用的數(shù)據(jù)結(jié)構(gòu)間存在著密切的交編譯器與其使用的數(shù)據(jù)結(jié)構(gòu)間存在著密切的交互關(guān)系互關(guān)系主要數(shù)據(jù)結(jié)構(gòu)如下：主要數(shù)據(jù)結(jié)構(gòu)如下：記號(hào)記號(hào)(token)記號(hào)集可以用枚舉數(shù)據(jù)表示，有時(shí)還要記錄記號(hào)記號(hào)集可以用枚舉數(shù)據(jù)表示，有時(shí)還要記錄記號(hào)代表的字符串的相關(guān)信息，如名字、數(shù)值等代表的字符串的相關(guān)信息，如名字、數(shù)值等對(duì)于多數(shù)語(yǔ)言，一次生成一個(gè)記號(hào)即可推動(dòng)編譯對(duì)于多數(shù)語(yǔ)言，一次生成一個(gè)記號(hào)即可推動(dòng)編譯器的工作，

17、但對(duì)器的工作，但對(duì)FORTRAN等語(yǔ)言，可能要多個(gè)等語(yǔ)言，可能要多個(gè)記號(hào)：記號(hào)：DO 10 I = 5 ， 1022編譯的主要數(shù)據(jù)結(jié)構(gòu)（編譯的主要數(shù)據(jù)結(jié)構(gòu)（2 2）語(yǔ)法樹語(yǔ)法樹(syntax tree)：由分析程序生成，由于對(duì)象語(yǔ)言等的不同，各個(gè)由分析程序生成，由于對(duì)象語(yǔ)言等的不同，各個(gè)節(jié)點(diǎn)的內(nèi)容是不同的節(jié)點(diǎn)的內(nèi)容是不同的語(yǔ)法樹的各個(gè)節(jié)點(diǎn)由于表示的對(duì)象的不同，因此語(yǔ)法樹的各個(gè)節(jié)點(diǎn)由于表示的對(duì)象的不同，因此數(shù)據(jù)內(nèi)容也是不同的數(shù)據(jù)內(nèi)容也是不同的既可以是動(dòng)態(tài)分配，也可以是靜態(tài)數(shù)組實(shí)現(xiàn)，還既可以是動(dòng)態(tài)分配，也可以是靜態(tài)數(shù)組實(shí)現(xiàn)，還可以用存儲(chǔ)池實(shí)現(xiàn)可以用存儲(chǔ)池實(shí)現(xiàn)符號(hào)表符號(hào)表(symbol table)

18、：記錄標(biāo)識(shí)符相關(guān)的信息，如函數(shù)、變量、常量、記錄標(biāo)識(shí)符相關(guān)的信息，如函數(shù)、變量、常量、數(shù)據(jù)類型等數(shù)據(jù)類型等編譯器的全程都有應(yīng)用編譯器的全程都有應(yīng)用操作的效率必須重視，雜湊表是一種主要的構(gòu)造操作的效率必須重視，雜湊表是一種主要的構(gòu)造方式方式23編譯的主要數(shù)據(jù)結(jié)構(gòu)（編譯的主要數(shù)據(jù)結(jié)構(gòu)（3 3）常數(shù)表常數(shù)表(literal table)：存放程序中出現(xiàn)的常量和字符串存放程序中出現(xiàn)的常量和字符串允許重復(fù)使用，無(wú)須刪除允許重復(fù)使用，無(wú)須刪除目標(biāo)代碼也要使用目標(biāo)代碼也要使用中間代碼中間代碼(intermediate code)：三元式是一種簡(jiǎn)單的表示三元式是一種簡(jiǎn)單的表示編譯器出于各方面的考慮，中間代碼可

19、以很復(fù)雜編譯器出于各方面的考慮，中間代碼可以很復(fù)雜，也可以分成多層，一般稱為中間表示，也可以分成多層，一般稱為中間表示(intermediate representation)臨時(shí)文件臨時(shí)文件(temporary file)：存儲(chǔ)局限存儲(chǔ)局限分別編譯分別編譯24編譯的結(jié)構(gòu)（編譯的結(jié)構(gòu)（1 1）源代碼源代碼詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析源代碼優(yōu)源代碼優(yōu)化化代碼生成代碼生成目標(biāo)代碼目標(biāo)代碼優(yōu)化優(yōu)化目標(biāo)代碼目標(biāo)代碼記號(hào)記號(hào)語(yǔ)法樹語(yǔ)法樹帶注釋的語(yǔ)法樹帶注釋的語(yǔ)法樹中間代碼中間代碼目標(biāo)代碼目標(biāo)代碼符號(hào)表等符號(hào)表等錯(cuò)誤處理錯(cuò)誤處理25編譯的結(jié)構(gòu)（編譯的結(jié)構(gòu)（2 2）分析與綜合分析與綜合分

20、析源程序以計(jì)算其特性的操作稱為分析，如詞分析源程序以計(jì)算其特性的操作稱為分析，如詞法分析、語(yǔ)法分析和語(yǔ)義分析等法分析、語(yǔ)法分析和語(yǔ)義分析等生成翻譯代碼時(shí)所涉及到的操作稱為綜合，如代生成翻譯代碼時(shí)所涉及到的操作稱為綜合，如代碼生成碼生成優(yōu)化過(guò)程中，既有分析，也有綜合優(yōu)化過(guò)程中，既有分析，也有綜合前端與后端前端與后端前端依賴源語(yǔ)言，后端依賴目標(biāo)語(yǔ)言前端依賴源語(yǔ)言，后端依賴目標(biāo)語(yǔ)言編譯器移植的考慮編譯器移植的考慮26編譯的結(jié)構(gòu)（編譯的結(jié)構(gòu)（3 3）遍遍(pass)：對(duì)源程序或中間表示的一次掃描，同時(shí)作相應(yīng)的對(duì)源程序或中間表示的一次掃描，同時(shí)作相應(yīng)的處理，稱為一遍處理，稱為一遍只要語(yǔ)言沒(méi)有特殊限制，編

21、譯器可以在一只要語(yǔ)言沒(méi)有特殊限制，編譯器可以在一“遍遍”完成，但目標(biāo)代碼不是很好完成，但目標(biāo)代碼不是很好可以根據(jù)需要，將多個(gè)編譯的階段合成一遍完成可以根據(jù)需要，將多個(gè)編譯的階段合成一遍完成，如將詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代，如將詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼的生成組成一遍完成，各個(gè)階段穿插進(jìn)行碼的生成組成一遍完成，各個(gè)階段穿插進(jìn)行由于優(yōu)化階段的工作復(fù)雜，優(yōu)化技術(shù)繁多，所以由于優(yōu)化階段的工作復(fù)雜，優(yōu)化技術(shù)繁多，所以優(yōu)化階段可能分解成多遍完成優(yōu)化階段可能分解成多遍完成27編譯的結(jié)構(gòu)（編譯的結(jié)構(gòu)（4 4）出錯(cuò)處理：出錯(cuò)處理：編譯器的各個(gè)階段都可能發(fā)現(xiàn)錯(cuò)誤編譯器的各個(gè)階段都可能發(fā)現(xiàn)錯(cuò)誤

22、錯(cuò)誤處理包括錯(cuò)誤的報(bào)告和錯(cuò)誤的恢復(fù)錯(cuò)誤處理包括錯(cuò)誤的報(bào)告和錯(cuò)誤的恢復(fù)一次編譯應(yīng)盡可能找到完全的錯(cuò)誤，并準(zhǔn)確報(bào)告一次編譯應(yīng)盡可能找到完全的錯(cuò)誤，并準(zhǔn)確報(bào)告錯(cuò)誤的種類和位置，只報(bào)告一個(gè)錯(cuò)誤不是一種好錯(cuò)誤的種類和位置，只報(bào)告一個(gè)錯(cuò)誤不是一種好的方法的方法編譯器的前三個(gè)分析階段可以發(fā)現(xiàn)大部分錯(cuò)誤編譯器的前三個(gè)分析階段可以發(fā)現(xiàn)大部分錯(cuò)誤靜態(tài)可檢測(cè)的錯(cuò)誤由靜態(tài)編譯報(bào)告，但有些語(yǔ)言靜態(tài)可檢測(cè)的錯(cuò)誤由靜態(tài)編譯報(bào)告，但有些語(yǔ)言要求檢查動(dòng)態(tài)時(shí)刻的錯(cuò)誤，編譯器要生成代碼完要求檢查動(dòng)態(tài)時(shí)刻的錯(cuò)誤，編譯器要生成代碼完成上述功能，如異常處理的機(jī)制成上述功能，如異常處理的機(jī)制28編譯相關(guān)的程序（編譯相關(guān)的程序（1 1）伙伴

23、程序：與編譯器協(xié)作最終實(shí)現(xiàn)目標(biāo)程序的伙伴程序：與編譯器協(xié)作最終實(shí)現(xiàn)目標(biāo)程序的執(zhí)行執(zhí)行預(yù)處理器預(yù)處理器(preprocessor)：編譯器之前的處理程序編譯器之前的處理程序注釋的刪除注釋的刪除宏處理宏處理文件的包含文件的包含語(yǔ)言擴(kuò)充，如語(yǔ)言擴(kuò)充，如SQL的數(shù)據(jù)庫(kù)操作的數(shù)據(jù)庫(kù)操作29編譯相關(guān)的程序（編譯相關(guān)的程序（2 2）匯編器匯編器(assembler)：生成可重定位的機(jī)器碼生成可重定位的機(jī)器碼連接器連接器(linker)：將不同的目標(biāo)文件合成一個(gè)可將不同的目標(biāo)文件合成一個(gè)可執(zhí)行的文件執(zhí)行的文件外部量外部量/全局量的處理全局量的處理裝入程序裝入程序(loader)：將可重定位的代碼讀入內(nèi)存將可重

24、定位的代碼讀入內(nèi)存，形成可執(zhí)行的程序，形成可執(zhí)行的程序可重定位地址的確定化可重定位地址的確定化解釋程序：同編譯一樣對(duì)高級(jí)語(yǔ)言程序翻譯執(zhí)解釋程序：同編譯一樣對(duì)高級(jí)語(yǔ)言程序翻譯執(zhí)行行在源程序運(yùn)行的同時(shí)對(duì)程序進(jìn)行翻譯和優(yōu)化在源程序運(yùn)行的同時(shí)對(duì)程序進(jìn)行翻譯和優(yōu)化對(duì)源程序逐句進(jìn)行分析、執(zhí)行（模擬）對(duì)源程序逐句進(jìn)行分析、執(zhí)行（模擬）仍然可能生成某種簡(jiǎn)單的中間代碼仍然可能生成某種簡(jiǎn)單的中間代碼編譯是在靜態(tài)時(shí)刻完成源程序到目標(biāo)代碼的翻譯編譯是在靜態(tài)時(shí)刻完成源程序到目標(biāo)代碼的翻譯30編譯相關(guān)的程序（編譯相關(guān)的程序（3 3）結(jié)構(gòu)編輯器：結(jié)構(gòu)編輯器：可以對(duì)輸入進(jìn)行一些分析可以對(duì)輸入進(jìn)行一些分析調(diào)試程序：調(diào)試程序：源

25、程序信息的獲得源程序信息的獲得斷點(diǎn)的管理斷點(diǎn)的管理優(yōu)化代碼的調(diào)試優(yōu)化代碼的調(diào)試靜態(tài)檢查器：靜態(tài)檢查器：程序的分析程序的分析性能預(yù)測(cè)性能預(yù)測(cè)動(dòng)態(tài)監(jiān)測(cè)程序：程序動(dòng)態(tài)行為的監(jiān)測(cè)和分析動(dòng)態(tài)監(jiān)測(cè)程序：程序動(dòng)態(tài)行為的監(jiān)測(cè)和分析31編譯相關(guān)的程序（編譯相關(guān)的程序（4 4）程序開發(fā)環(huán)境：程序開發(fā)環(huán)境：便于程序的開發(fā)便于程序的開發(fā)幾類特殊的編譯程序：幾類特殊的編譯程序：高級(jí)語(yǔ)言間的轉(zhuǎn)換工具高級(jí)語(yǔ)言間的轉(zhuǎn)換工具并行編譯程序并行編譯程序二進(jìn)制翻譯程序二進(jìn)制翻譯程序動(dòng)態(tài)優(yōu)化工具動(dòng)態(tài)優(yōu)化工具32編譯程序的自舉與移植（編譯程序的自舉與移植（1 1）T形圖：形圖：描述源語(yǔ)言描述源語(yǔ)言S、目標(biāo)語(yǔ)言目標(biāo)語(yǔ)言T和編譯程序?qū)崿F(xiàn)語(yǔ)言

26、和編譯程序?qū)崿F(xiàn)語(yǔ)言I間間的關(guān)系的關(guān)系T形圖的組合方式：形圖的組合方式：將第一個(gè)將第一個(gè)T形圖的輸出作為第二個(gè)形圖的輸出作為第二個(gè)T形圖的輸入形圖的輸入已有將語(yǔ)言已有將語(yǔ)言A編譯為語(yǔ)言編譯為語(yǔ)言B的編譯器和將語(yǔ)言的編譯器和將語(yǔ)言B到語(yǔ)到語(yǔ)言言C的編譯器，用上述方法得到得到的編譯器，用上述方法得到得到A到到C的編譯器的編譯器 S T I A B I B C I A C I=33編譯程序的自舉與移植（編譯程序的自舉與移植（2 2）編譯器實(shí)現(xiàn)語(yǔ)言的變換編譯器實(shí)現(xiàn)語(yǔ)言的變換例如我們用例如我們用C語(yǔ)言開發(fā)了一個(gè)將語(yǔ)言開發(fā)了一個(gè)將FORTRAN語(yǔ)言語(yǔ)言程序編譯為程序編譯為JAVA程序的編譯器程序的編譯器FO

27、R2J，如果我們?nèi)绻覀円呀?jīng)有一個(gè)將已經(jīng)有一個(gè)將C語(yǔ)言編譯為語(yǔ)言編譯為X86代碼的編譯器，利代碼的編譯器，利用上述的方式可以得到一個(gè)在用上述的方式可以得到一個(gè)在X86機(jī)器上執(zhí)行的機(jī)器上執(zhí)行的FOR2J編譯器編譯器 A B I I K M A B K=34編譯程序的自舉與移植（編譯程序的自舉與移植（3 3）編譯器的自舉編譯器的自舉(bootstrapping)的開發(fā)方式的開發(fā)方式?jīng)]有高級(jí)語(yǔ)言可以用來(lái)寫編譯器，怎么辦？沒(méi)有高級(jí)語(yǔ)言可以用來(lái)寫編譯器，怎么辦？用匯編語(yǔ)言開發(fā)一個(gè)完整的編譯器？太繁瑣用匯編語(yǔ)言開發(fā)一個(gè)完整的編譯器？太繁瑣用自舉的方式：用自舉的方式：v首先用匯編語(yǔ)言開發(fā)一個(gè)實(shí)現(xiàn)源語(yǔ)言一個(gè)子

28、集的首先用匯編語(yǔ)言開發(fā)一個(gè)實(shí)現(xiàn)源語(yǔ)言一個(gè)子集的編譯器，這個(gè)編譯器只要正確即可編譯器，這個(gè)編譯器只要正確即可v用這個(gè)子集語(yǔ)言開發(fā)語(yǔ)言全集的編譯器用這個(gè)子集語(yǔ)言開發(fā)語(yǔ)言全集的編譯器v上述過(guò)程可以重復(fù)多次，直至得到性能良好的、上述過(guò)程可以重復(fù)多次，直至得到性能良好的、正確的對(duì)語(yǔ)言全集有效的編譯器正確的對(duì)語(yǔ)言全集有效的編譯器 A M A A M M A M M=35編譯程序的自舉與移植（編譯程序的自舉與移植（4 4）編譯器的移植的開發(fā)方式編譯器的移植的開發(fā)方式以以PC機(jī)為工具開發(fā)機(jī)為工具開發(fā)MIPS芯片的芯片的C語(yǔ)言編譯器語(yǔ)言編譯器PC機(jī)上已有機(jī)上已有C語(yǔ)言編譯器語(yǔ)言編譯器用用C語(yǔ)言在語(yǔ)言在PC機(jī)上開發(fā)一個(gè)產(chǎn)生機(jī)上開發(fā)一個(gè)產(chǎn)生MIPS代碼的代碼的C編編譯器譯器C1將將C1在在PC機(jī)上編譯，得到機(jī)上編譯，得到PC機(jī)上運(yùn)行的交叉編機(jī)上運(yùn)行的交叉編譯器譯器用交叉編譯器在用交叉編譯器在PC機(jī)上對(duì)機(jī)上對(duì)C1重新編譯，得到在重新編譯，得到在MIPS上運(yùn)行的上運(yùn)行的C語(yǔ)言編譯器語(yǔ)言編譯器36編譯程序的自舉與移植（編譯程序的自舉與移植（5 5） C M CC P P C M P=PC上的C語(yǔ)言編譯器交叉編譯器 C M CC M P C M M=交叉編譯器MIPS上的C語(yǔ)言編譯