《編譯的基本概念》PPT課件.ppt

1、1,編譯原理,2,第一章 編譯的基本概念,3,基本概念,術(shù)語(yǔ)： 語(yǔ)言和程序 翻譯程序和翻譯方式 宿主機(jī)與目標(biāo)機(jī) 編譯過程概述 編譯程序的邏輯結(jié)構(gòu) 編譯程序的前端、后端、遍 編譯技術(shù)的應(yīng)用與發(fā)展,4,語(yǔ)言：符合一定規(guī)則（文法）的程序的集合 低級(jí)語(yǔ)言 字位碼、機(jī)器語(yǔ)言、匯編語(yǔ)言 特點(diǎn)：與特定的機(jī)器有關(guān)，功效高，但使用復(fù)雜、繁 瑣、費(fèi)時(shí)、易出錯(cuò) 高級(jí)語(yǔ)言 Fortran、Pascal、C、JAVA等 特點(diǎn)：不依賴具體機(jī)器，移植性好、對(duì)用戶要求低、易 使用、易維護(hù)等,1.1 術(shù)語(yǔ),5,1.1 術(shù)語(yǔ),程序：一組指令組成的序列，稱為程序 源程序：用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序稱為源程序 目標(biāo)程序：用目標(biāo)語(yǔ)

2、言所表示的程序，可以是介于源語(yǔ)言和 機(jī)器語(yǔ)言之間的“中間語(yǔ)言”，可以是某種機(jī)器 的機(jī)器語(yǔ)言,也可以是某機(jī)器的匯編語(yǔ)言。 翻譯程序：將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。 它是指各種語(yǔ)言的翻譯器，包括匯編程序和編譯 程序，是匯編程序、編譯程序以及各種變換程序 的總稱,6,源程序、翻譯程序、目標(biāo)程序三者關(guān)系,源程序,翻譯程序,目標(biāo)程序,SOURCE PROGRAM,TRANSLATER,OBJECT PROGRAM,即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出,1.1 術(shù)語(yǔ),7,匯編程序 若源程序用匯編語(yǔ)言書寫，經(jīng)過翻譯程序得到用機(jī)器語(yǔ)言表示的程序，這時(shí)的翻譯程序就稱之為匯編程序，這種翻

3、譯過程稱為“匯編”。 編譯程序 若源程序是用高級(jí)語(yǔ)言書寫，經(jīng)加工后得到目標(biāo)程序，上述翻譯過程稱“編譯,匯編程序與編譯程序都是翻譯程序，主要區(qū)別是加工對(duì)象的 不同。由于匯編語(yǔ)言格式簡(jiǎn)單，常與機(jī)器語(yǔ)言之間有一一對(duì) 應(yīng)的關(guān)系。匯編程序所要做的翻譯工作比編譯程序簡(jiǎn)單的多,1.1 術(shù)語(yǔ),8,源程序的編譯和運(yùn)行,編譯或匯編階段 運(yùn)行階段,1.1 術(shù)語(yǔ),9,工作過程,解釋程序：對(duì)源程序邊解釋，邊執(zhí)行的程序。類似于口譯， 不生成目標(biāo)代碼,特點(diǎn)：邊解釋，邊執(zhí)行； 不生成目標(biāo)代碼； 比較簡(jiǎn)單，但速度慢,1.1 術(shù)語(yǔ),10,1.1 術(shù)語(yǔ),工作過程,編譯程序：把源程序翻譯成等價(jià)的目標(biāo)程序（匯編語(yǔ)言，機(jī)器語(yǔ)言）。 類似

4、于筆譯,源程序,編譯程序,目標(biāo)程序,輸出數(shù)據(jù),目標(biāo)程序+運(yùn)行程序,輸入數(shù)據(jù),11,編譯程序的特點(diǎn)： 1、翻譯過程是一種功能上等價(jià)的翻譯； 2、輸出結(jié)果是低級(jí)語(yǔ)言； 3、編譯程序與具體的語(yǔ)言和機(jī)器有關(guān)； 4、被編譯的源程序是被加工的對(duì)象， 目標(biāo)程序是加工的結(jié)果； 5、比較復(fù)雜，效率高,1.1 術(shù)語(yǔ),12,1.1 術(shù)語(yǔ),宿主機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)。 目標(biāo)機(jī): 運(yùn)行編譯程序所產(chǎn)生目 標(biāo)代碼的計(jì)算機(jī),13,編譯程序的分類 1、診斷編譯程序 用于幫助程序開發(fā)和調(diào)試的編譯程序。 2、優(yōu)化編譯程序 著重于提高目標(biāo)代碼效率的編譯程序。 3、交叉編譯程序 如果一個(gè)編譯程序產(chǎn)生不同于其宿主機(jī)的 機(jī)器代碼。 4、

5、可變目標(biāo)編譯程序 如果不需重寫編譯程序中與機(jī)器無關(guān)的部 分就能改變目標(biāo)機(jī),1.1 術(shù)語(yǔ),14,編譯過程是將高級(jí)語(yǔ)言程序翻譯為等價(jià)的目標(biāo)程序的過程,翻譯外文資料： 1、能識(shí)別出句子中的每個(gè)單詞； 2、分析句子的語(yǔ)法結(jié)構(gòu)； 3、根據(jù)句子的含義進(jìn)行初步翻譯； 4、對(duì)譯文進(jìn)行修飾； 5、寫出最后的譯文,1.2 編譯過程,15,1.2 編譯過程,文獻(xiàn)翻譯與編譯過程的比較,16,詞法分析,語(yǔ)法分析,語(yǔ)義分析及中間代碼生成,代碼優(yōu)化,目標(biāo)代碼生成,習(xí)慣上是將編譯過程劃分為5個(gè)基本階段,1.2 編譯過程,17,1.2 編譯過程,單詞：是語(yǔ)言的基本語(yǔ)法單位 保留字（或稱基本字，如:if、else、while）

6、標(biāo)識(shí)符（如:max、min、str） 常數(shù) （如:12、6.8、a） 運(yùn)算符（如:+、-、*、/） 界符 （;、（,任務(wù)：對(duì)源程序的字符串流進(jìn)行掃描和分解，識(shí)別并輸出 一個(gè)個(gè)單詞符號(hào)，及其與此相關(guān)的屬性（保留字， 標(biāo)識(shí)符，常數(shù)，運(yùn)算符，界符,一、詞法分析,例：if B1 = 13 then X := Y + 1 （20個(gè)字符） | | | | | | | | | | 基 標(biāo) 運(yùn) 常 基 標(biāo) 運(yùn) 標(biāo) 運(yùn)常 本 識(shí) 算 數(shù) 本 識(shí) 算 識(shí) 算數(shù) 字 符 符 符 號(hào) 符 符 符,18,1.2 編譯過程,單詞符號(hào)內(nèi)部的表示: 二元式,詞法分析依循的規(guī)則： 描述詞法規(guī)則的有效工具是正規(guī)文法和正規(guī)式,19

7、,任務(wù)：根據(jù)語(yǔ)法規(guī)則（即語(yǔ)言的文法），把單詞符號(hào)串分解成各類 語(yǔ)法成分（如表達(dá)式、語(yǔ)句、函數(shù)等），分析其源程序的結(jié) 構(gòu)，判別是否為相應(yīng)程序語(yǔ)言中的合法程序,二、語(yǔ)法分析（編譯程序的核心,1.2 編譯過程,語(yǔ)法分析依循的規(guī)則： 描述語(yǔ)法規(guī)則的有效工具是上下文無關(guān)文法,20,1.2 編譯過程,上下文無關(guān)文法： :=“=” :=“+” | “*” :=“(”“)” | | ,21,語(yǔ)法分析的結(jié)果-語(yǔ)法樹,1.2 編譯過程,賦值語(yǔ)句,標(biāo)識(shí)符,表達(dá)式,表達(dá)式,標(biāo)識(shí)符,實(shí)數(shù),表達(dá)式,Z,X,Y,0.618,表達(dá)式,表達(dá)式,Z X + 0.618 *Y,標(biāo)識(shí)符,22,1.2 編譯過程,任務(wù)：規(guī)定各語(yǔ)法成分的

8、含義和功能，即規(guī)定它們的屬性或 在執(zhí)行時(shí)應(yīng)進(jìn)行的運(yùn)算和操作，進(jìn)行相應(yīng)的語(yǔ)義檢 查；產(chǎn)生中間代碼,三、語(yǔ)義分析及中間代碼生成,靜態(tài)： 分析語(yǔ)法成份的含義，進(jìn)行語(yǔ)義上的正確性檢查。 動(dòng)態(tài)： 根據(jù)相應(yīng)語(yǔ)義，生成中間代碼（介于源語(yǔ)言和目標(biāo)語(yǔ)言之間的中間語(yǔ)言形式,23,生成中間代碼的目的： 1、利于代碼優(yōu)化 2、利于目標(biāo)代碼的移植,中間代碼的形式： 三元式、四元式、逆波蘭表示,1.2 編譯過程,語(yǔ)義分析依循的規(guī)則： 為文法的每一個(gè)產(chǎn)生式配備計(jì)算屬性的計(jì)算規(guī)則,24,1.2 編譯過程,其中t1、t2、t3為編譯程序引入的臨時(shí)工作單元,例：y=x+r*6,25,1.2 編譯過程,任務(wù)：對(duì)中間代碼進(jìn)行加工變換

9、，以期在最后階段產(chǎn)生 出更為高效（省時(shí)間、空間）目標(biāo)程序。 優(yōu)化包括：局部?jī)?yōu)化、全局優(yōu)化、循環(huán)優(yōu)化,四、優(yōu)化,26,1.2 編譯過程,例：y=x+r*6,27,1.2 編譯過程,五、目標(biāo)代碼生成,任務(wù)：把優(yōu)化后的中間代碼變換成目標(biāo)機(jī)的低級(jí)語(yǔ)言代碼,movr, R1 mul#6.0, R1 movx, R2 addR1, R2 movR2, y,28,編譯過程小結(jié),1.2 編譯過程,29,按邏輯功能不同，可將編譯過程劃分為五個(gè)基本階段，與此相對(duì)應(yīng)，我們將實(shí)現(xiàn)整個(gè)編譯過程的編譯程序劃分為五個(gè)邏輯階段（即五個(gè)邏輯子過程,每個(gè)階段中都要有： 符號(hào)表管理和錯(cuò)誤處理,1.3 編譯程序的邏輯結(jié)構(gòu),30,診察

10、錯(cuò)誤，并能報(bào)告用戶錯(cuò)誤性質(zhì)和位置。 出錯(cuò)處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個(gè)重要指標(biāo),填表：把源程序中的信息和編譯過程中所產(chǎn)生的信 息登記在表格中。 查表：在隨后的編譯過程中同時(shí)又要不斷的查找這 些表格中的信息,符號(hào)表管理,錯(cuò)誤處理,1.3 編譯程序的邏輯結(jié)構(gòu),31,典型的編譯程序具有7個(gè)邏輯部分,S.P,O.P,1.3 編譯程序的邏輯結(jié)構(gòu),32,根據(jù)編譯程序各部分功能，將編譯程序分成前端和后端,前端：通常將與源程序有關(guān)的編譯部分稱為前端分析部分。 包括：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成 特點(diǎn)：與源語(yǔ)言有關(guān) 后端：與目標(biāo)機(jī)有關(guān)的部分稱為后端綜合部分。 包括：代碼優(yōu)化、代碼生成

11、特點(diǎn)：與目標(biāo)機(jī)有關(guān),編譯程序的前端和后端,1.4 編譯程序的前端、后端、遍,33,第一遍 第二遍,S.P 中間形式1,S.P 中間形式2,C2,C1,S.P,O.P,上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序,對(duì)源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一遍,1.4 編譯程序的前端、后端、遍,34,一遍掃描即可完成整個(gè)編譯工作的稱為一遍掃描編譯程序,遍的劃分視具體情況而定（內(nèi)存的大小、源語(yǔ)言的繁簡(jiǎn)、目標(biāo)程序質(zhì)量的高低,優(yōu)點(diǎn)： 1、減少對(duì)內(nèi)存容量的要求 2、編譯程序結(jié)構(gòu)清晰、各遍功能獨(dú)立、相互聯(lián)系簡(jiǎn)單,缺點(diǎn)： 增加讀寫中間

12、文件的次數(shù)，降低效率,1.4 編譯程序的前端、后端、遍,35,應(yīng)用：大部分軟件工具的開發(fā)，都要使用編譯技術(shù)和方法,高級(jí)語(yǔ)言的翻譯工具，自然語(yǔ)言理解 編輯器，信息檢索，模式識(shí)別 軟件測(cè)試工具 靜態(tài)分析器：不可能執(zhí)行的代碼、定義后未引用的變量 動(dòng)態(tài)測(cè)試工具：運(yùn)行后與期望結(jié)果比較 程序理解工具：確定調(diào)用關(guān)系，畫出流程圖 排版、繪圖系統(tǒng),1.5 編譯技術(shù)的應(yīng)用與發(fā)展,36,并行編譯技術(shù) 目的：提高并行計(jì)算機(jī)體系結(jié)構(gòu)的性能，超大規(guī)模計(jì)算 的日益增長(zhǎng)的需求。兩種實(shí)現(xiàn)方法： 利用重構(gòu)技術(shù)將串行程序并行化 直接編寫并行程序 交叉編譯技術(shù) 由于目標(biāo)機(jī)指令系統(tǒng)與宿主機(jī)的指令系統(tǒng)不同，編譯時(shí) 將應(yīng)用程序的源程序在宿主機(jī)上生成目標(biāo)機(jī)代碼，稱為 交叉編譯,發(fā)展,1.5 編譯技術(shù)的應(yīng)用與發(fā)展,37,1.判斷下面的陳述是否正確。 （1）高級(jí)語(yǔ)言程序到低級(jí)語(yǔ)言程序的轉(zhuǎn)換是基于功能的 等價(jià)變換； （2）含有優(yōu)化部分的編譯程序的執(zhí)行效率高； （3）因?yàn)榫幾g程序和解釋程序具有不同的功能，所以它 們的實(shí)現(xiàn)技術(shù)也完全不同； （4）編譯程序