compiler_ch1

1、Compiler ?第 1 頁第一章 編譯引論1.1 程序設(shè)計(jì)語言與編譯程序第 2 頁Compiler ?定義1.1 :將某一種程序設(shè)計(jì)語言寫的程序翻譯成等價(jià)的另一種語言的程序的程序, 稱之為編譯程序(compiler) 。編譯程序是語言處理系統(tǒng) ；編譯程序是將高級語言翻譯成機(jī)器語言的程序；人、機(jī)交互的工具;第一章 編譯引論1.1 程序設(shè)計(jì)語言與編譯程序源語言： (source language)源語言是用來編寫源程序的語言, 一般是匯編語言或高級程序設(shè)計(jì)語言。源程序： (source program)用源語言寫的程序稱為源程序。目標(biāo)語言：(target language)目標(biāo)程序的描述語言稱

2、為目標(biāo)語言。第 3 頁第一章 編譯引論1.1 程序設(shè)計(jì)語言與編譯程序目標(biāo)程序：(target program)源程序經(jīng)過編譯后生成的程序稱之為目標(biāo)程序。宿主語言：編譯程序的實(shí)現(xiàn)語言。宿主機(jī)（目標(biāo)機(jī)）：編譯程序的運(yùn)行環(huán)境。第 4 頁第一章 編譯引論1.1 程序設(shè)計(jì)語言與編譯程序第 5 頁一.編譯程序編譯程序的分類與執(zhí)行解釋程序編譯程序匯編程序解釋程序： 接受某語言的源程序?qū)⑵渲苯臃g成目標(biāo)代碼且執(zhí)行。編譯程序： 接受某語言的源程序?qū)⑵渲苯臃g成等價(jià)的目標(biāo)代碼，然后執(zhí)行且允許重復(fù)執(zhí)行。匯編程序： 接受匯編源程序?qū)⑵浞g成等價(jià)的機(jī)器語言的目標(biāo)程序，然后執(zhí)行且允許重復(fù)執(zhí)行。第一章編譯引論1.2 編譯程

3、序的表示與分類解釋執(zhí)行：編譯執(zhí)行：結(jié)果第 6 頁Compiler源程序目標(biāo)程序運(yùn)行程序數(shù)據(jù)解釋程序源程序computer結(jié)果computerStep 1computerStep 2第一章編譯引論1.2 編譯程序的表示與分類編譯執(zhí)行和解釋執(zhí)行的區(qū)別：編譯執(zhí)行是由編譯程序生成一個(gè)與源程序等價(jià)的目標(biāo)程序，它可以完全取代源程序，該目標(biāo)程序可以運(yùn)行任意次。解釋執(zhí)行不生成目標(biāo)程序，僅是對源程序逐句解釋逐句執(zhí)行。編譯執(zhí)行類似于自然語言的筆譯；解釋執(zhí)行類似自然語言的口譯。第 7 頁第一章編譯引論1.2 編譯程序的表示與分類第 8 頁二. 編譯程序的表示1） 函 數(shù) 表 示 ：T = C（S）T: 目標(biāo)程序C:

4、 編譯程序S: 源程序2） T型圖表示 (體現(xiàn)編譯程序的三個(gè)要素)源語言目標(biāo)語言宿主語言第一章編譯引論1.2 編譯程序的表示與分類C源 目宿3）符 號 表 示第 9 頁表格管理源程序詞法分析語法分析語 中義 間生處 代成理 碼代碼優(yōu)化代碼生成目標(biāo)程序處出 錯(cuò)front end理back end( 分析 )（綜合）編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分)第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第 10 頁1. 詞法分析 (lexical analysis)詞法分析階段的任務(wù)是對輸入的符號串形式的源程序進(jìn)行最初的加工處理。 它依次掃描讀入的源程序中的每個(gè)字符,識別出源程序中有獨(dú)立意義的源語言單詞,用某種

5、特定的數(shù)據(jù)結(jié)構(gòu)對它的屬性予以表示和標(biāo)注。詞法分析實(shí)際上是一種線性分析。屬性字的數(shù)據(jù)結(jié)構(gòu)可據(jù)不同語言及編譯程序?qū)崿F(xiàn)方案來設(shè)計(jì), 但一般設(shè)計(jì)成單詞屬性標(biāo)識及單詞內(nèi)碼兩個(gè)數(shù)據(jù)項(xiàng)。Scanner源程序L屬性字流L1第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第 11 頁例1.1:有如下C代碼行 ：aindex = 12 * 3 ；經(jīng)詞法分析后將產(chǎn)生對9個(gè)識別的單詞, 如下屬性標(biāo)注:(1) a(2) ( 3 ) index標(biāo)識符左方括號標(biāo)識符(4)(5)(6)=12右方括號賦值整常數(shù)(7)(8)(9)*3;乘號整常數(shù)分號屬性字流第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織源程序2. 語法分析 (Syntax

6、 analysis)語法分析的任務(wù)是依據(jù)語言文本所規(guī)定的語法規(guī)則,對詞法分析的結(jié)果進(jìn)行語法檢查, 并識別出單詞序列所對應(yīng)的語法范疇 。通常將語法分析的結(jié)果表示為分析樹(parse tree)或語法樹(syntax tree)，它是一種層次結(jié)構(gòu)的形式。例1.2中的C語言的賦值表達(dá)式語句經(jīng)過語法分析，確認(rèn)合乎C語言的語法規(guī)則且語法范疇為表達(dá)式語句, 產(chǎn)生的語法樹形式的語法分析結(jié)果如下圖所示。第 12 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第 13 頁aindex*標(biāo)識符表達(dá)式表達(dá)式常數(shù) 12表達(dá)式常數(shù) 3C語句 aindex = 12 * 3 ；的語法樹表達(dá)式語法范疇賦值表達(dá)式第一章編譯引論

7、1.3 編譯程序的結(jié)構(gòu)與組織3. 語義分析 (semantic analysis)與中間代碼生成語義分析階段的任務(wù)是依據(jù)語言文本限定的語義規(guī)則對語法分析所識別的語法范疇進(jìn)行語義檢查和處理, 直至最后翻譯成與其等價(jià)的某種中間代碼或目標(biāo)代碼。語義分析是整個(gè)編譯程序完成的最實(shí)質(zhì)性的翻譯任務(wù)。第 14 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第 15 頁例1.2:設(shè)有賦值語句x=(a+b)*c+*=aT1T2bcT1T2x產(chǎn)生的四元式形式的中間代碼：第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織4. 代碼優(yōu)化 (optimization)代碼優(yōu)化是為了改進(jìn)目標(biāo)代碼的質(zhì)量而在編譯過程中進(jìn)行的工作。代碼優(yōu)

8、化可以在中間代碼或目標(biāo)代碼級上進(jìn)行 ,其實(shí)質(zhì)是在不改變源程序語義的基礎(chǔ)上對其進(jìn)行加工變換, 以期獲得更高效的目標(biāo)代碼。而高效一般是對所產(chǎn)生的目標(biāo)程序在運(yùn)行時(shí)間的縮短和存貯空間的節(jié)省而言。第 16 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第 17 頁例1.3:設(shè)有語句for (i=1; i=200; i+) y=y*i+y;x=x1/cos(x2)x=x1/cos(x2)for (i=1; i=200; i+)y=y*i+y;優(yōu)化后第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織5. 目標(biāo)代碼生成 (code generator)根據(jù)中間代碼及編譯過程中產(chǎn)生的各種表格的有關(guān)信息,最終生成所期望的目

9、標(biāo)代碼程序。一般為特定機(jī)器的機(jī)器語言代碼或匯編語言代碼, 需要充分考慮計(jì)算機(jī)硬件和軟件所提供的資源, 以生成較高質(zhì)量的目標(biāo)程序。第 18 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第 19 頁對例1.1的語句生成代碼。要考慮怎樣存儲整型數(shù)來為數(shù)組元素的引用生成目標(biāo)代碼，以假設(shè)的匯編語言描述如下：MOVMULR0, indexR0, 2; 索引值賦給寄存器R0; 存儲按字節(jié)編址，整型數(shù); 占2個(gè)字節(jié)MOV R1, &a; &a表示數(shù)組a的基地址ADDR1, R0; 計(jì)算aindex的地址MOV *R1, 36; aindex = 36第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織標(biāo)

10、識符id1運(yùn)算符標(biāo)識符id2運(yùn)算符標(biāo)識符id3運(yùn)算符*正常數(shù)；分號30第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織例1.4:設(shè)有語句(P7)c=a+b*30;詞法分析器第 20 頁第 21 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織30id2id1*語法分析器MOVFMULFMOVFADDFMOVFid3,#30.0,id2,R2,R1,R2R2R1R1id1id3代碼生成 編譯階段與自然語言的對比編譯程序詞法分析語法分析產(chǎn)生中間代碼代碼優(yōu)化目標(biāo)代碼生成自然語言翻譯查字典、識別單詞分析識別句子翻譯初稿對初稿潤色修飾譯文定稿第 22 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織表格管理編譯程序的

11、公共輔助程序。對源程序中的各種量進(jìn)行管理，登記相應(yīng)的表格。編譯程序處理時(shí)通過查表得到所需的信息。出錯(cuò)處理編譯程序的公共輔助程序。對源程序中的各種錯(cuò)誤檢查、定位、定性、報(bào)告，并盡可能將錯(cuò)誤限制在盡可能小的范圍內(nèi)，保障編譯繼續(xù)。第 23 頁第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織第一章編譯引論1.3 編譯程序的結(jié)構(gòu)與組織定義1.2 : ( 遍 Pass )對源程序或源程序的中間形式從頭到尾掃描一遍，并做有關(guān)的分析加工，生成新的源程序的中間形式或生成目標(biāo)程序。遍設(shè)置的考慮因素(1) 宿主機(jī)存儲容量；(2) 編譯程序功能的強(qiáng)弱；(3) 源語言的繁簡及約束；(4) 優(yōu)化因素；(5) 設(shè)計(jì)、實(shí)現(xiàn)的環(huán)境、

12、工具及人員因素等。第 24 頁源程序目標(biāo)程序第 25 頁詞法分析語義處理代碼生成一遍掃描的編譯程序結(jié)構(gòu)模型語法分析程序第一章編譯引論1.4 編譯程序結(jié)構(gòu)的實(shí)例模型AHPL模擬器（兩遍掃描的編譯程序結(jié)構(gòu)模型）第一遍第二遍AHPL源程序詞法分析語法分析語義處理操作表（目標(biāo)程序）AHPL模擬器模擬結(jié)果第 26 頁代碼生成第一章編譯引論1.4 編譯程序結(jié)構(gòu)的實(shí)例模型第 27 頁目標(biāo)代碼 （匯編）PDP 11 C編譯器結(jié)構(gòu)模型C 源程序詞法分析語法分析語義處理（中間代碼生成）中間代碼代 碼 生 成匯編代碼代 碼 優(yōu) 化第一章編譯引論1.4 編譯程序結(jié)構(gòu)的實(shí)例模型第 28 頁Gcc compiler st

13、ructureC source fileC ParserSyntax treeRTL representationOptimizationAssembleAssembly codeC+source fileC+ Parser目標(biāo)機(jī)描述宏文件 tm.hRTL generater機(jī)器描述文件machine.mdF source fileFortran Parser寄存器轉(zhuǎn)換語言第 29 頁Csource fileCFEIR fileOptimizerOptimizedcodeASSEMBLERLINKERCsource fileCFEIR fileOptimizerOptimizedcodeASS

14、EMBLERCsource fileCFEIR fileOptimizerOptimizedcodeASSEMBLERCsource fileCFEIR fileOptimizerOptimizedcodeASSEMBLER.StarCore Non Global Optimization第 30 頁Csource fileCFEIR fileCsource fileCFEIR fileCsource fileCFEIR fileCsource fileCFEIR fileOptimizedcodeASSEMBLERLINKEROptimizedcodeASSEMBLEROptimizedco

15、deASSEMBLEROptimizedcodeASSEMBLER.OptimizerStarCore Global OptimizationC Front EndASSEMBLERLINKERExecutableProgram第 31 頁SCC_structureC source filesC Front EndIntermediateRepresentationHigh-Level OptimizationsHigh-Level OptimizationsLow-Level OptimizationsLow-Level OptimizationsOptimizedAssembly Code

16、ASSEMBLERLINKERExecutableProgramLibrary IR fileLibraryObject ModulesSHELLApplication/machineconfig.filesExternalAssembly filesPreprocessorC Front End( CFE )OPTIMIZERASSEMBLERSCC_structureC source filesASSEMBLERApplication/machineconfig.filesLibraryObject ModulesLibrary IR file.libPreprocessor.i.elnL

17、INKER.eldExecutableProgram第 32 頁.asmC Front End( CFE.objOPTIMIZER.slSHELLExternalAssembly files編譯程序構(gòu)造要素源語言目標(biāo)語言編譯方法、技術(shù)與工具第 33 頁第一章編譯引論1.5 編譯程序的構(gòu)造與實(shí)現(xiàn)第 34 頁編譯程序的生成1） 使用編程語言；2） 移植方式；3） 自編譯 （用源語言作為宿主語言）；4） 自動(dòng)生成。TWS （Translater Writting System）LEXFLEX YACC Bison第一章編譯引論1.5 編譯程序的構(gòu)造與實(shí)現(xiàn)核心語句編譯xx.asm用xx.asm編譯PASCALcomp