編譯原理ppt62219

1、 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系編譯原理編譯原理 主講教師:孫 斌 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系 課程安排課程安排: 總學(xué)時(shí)總學(xué)時(shí): 64學(xué)時(shí)學(xué)時(shí) 其中,理論基礎(chǔ): 48學(xué)時(shí) 實(shí)踐部分: 16學(xué)時(shí) 目的目的: 掌握編譯的基本理論、常用的編譯技術(shù)和方法，了解編譯過(guò)程及編譯系統(tǒng)的構(gòu)造（結(jié)構(gòu)和機(jī)理）。具備一定的實(shí)際動(dòng)手能力。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系 成績(jī): 總評(píng)成績(jī)=期末考試60%+平時(shí)成績(jī)40% 參考資料: 1.陳火旺、劉春林等編譯原理(第3版)國(guó)防工業(yè)出版社 2.呂映芝、張素琴、蔣唯杜編譯原

2、理清華大學(xué)出版社 3.伍春香編譯原理習(xí)題與解析清華大學(xué)出版社 4.劉春林、王挺典型題解析與實(shí)戰(zhàn)模擬:編譯原理 國(guó)防科技大學(xué)出版社 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系第1章 引論(主要介紹編譯程序的功能、體系結(jié)構(gòu)、工作過(guò)程、組織方式等內(nèi)容) 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.1 翻譯程序1.2 編譯程序的工作過(guò)程1.3 編譯程序的結(jié)構(gòu)1.4 編譯程序的組織方式1.5 編譯程序的自展、移植與自動(dòng)化1.6 翻譯程序編寫系統(tǒng)1.7 并行編譯程序1.8 小結(jié) 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.1 翻譯程序 程序設(shè)

3、計(jì)語(yǔ)言是人與計(jì)算機(jī)聯(lián)系的工具，人們通過(guò)程序設(shè)計(jì)語(yǔ)言指揮計(jì)算機(jī)按照人們的意志進(jìn)行運(yùn)算和操作、顯示信息和輸出運(yùn)算結(jié)果。 高級(jí)語(yǔ)言高級(jí)語(yǔ)言 fortran、pascal、c 語(yǔ)言等 特點(diǎn)：不依賴具體機(jī)器，移植性好、對(duì)用戶要求低、易使用、易維護(hù)等。低級(jí)語(yǔ)言低級(jí)語(yǔ)言機(jī)器語(yǔ)言、符號(hào)語(yǔ)言、匯編語(yǔ)言特點(diǎn)：與特定的機(jī)器有關(guān)，功效高，但使用復(fù)雜、繁瑣、費(fèi)時(shí)、易出錯(cuò) 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系源程序源程序 用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序稱為源程序目標(biāo)程序目標(biāo)程序 用目標(biāo)語(yǔ)言所表示的程序 目標(biāo)語(yǔ)言：可以是介于源語(yǔ)言和機(jī)器語(yǔ)言之間的“中間語(yǔ)言”，可以是某種機(jī)器的機(jī)器語(yǔ)言,也可以是某機(jī)

4、器的匯編語(yǔ)言。翻譯程序翻譯程序 將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語(yǔ)言的翻譯器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系源程序、翻譯程序、目標(biāo)程序 三者關(guān)系即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出源程序翻譯程序目標(biāo)程序 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系 匯編程序匯編程序 若源程序用匯編語(yǔ)言書寫，經(jīng)過(guò)翻譯程序得到用機(jī)器語(yǔ)言表示的程序，這時(shí)的翻譯程序就稱之為匯編程序，這種翻譯過(guò)程稱為“匯編”(assemble） 編譯程序編譯程序 若源程序是用高級(jí)語(yǔ)言

5、書寫，經(jīng)加工后得到目標(biāo)程序，上述翻譯過(guò)程稱“編譯”（compile) 匯編程序與編譯程序都是翻譯程序，主要區(qū)別是加工對(duì)象的不同。由于匯編語(yǔ)言格式簡(jiǎn)單，常與機(jī)器語(yǔ)言之間有一一對(duì)應(yīng)的關(guān)系。匯編程序所要做的翻譯工作比編譯程序簡(jiǎn)單的多。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系 解釋程序（解釋程序（interpreter） 對(duì)源程序進(jìn)行解釋執(zhí)行的程序 解釋方式并不先產(chǎn)生目標(biāo)程序然后再執(zhí)行之,而是對(duì)源程序邊翻譯邊執(zhí)行。 注注: 特點(diǎn)、與編譯程序比較特點(diǎn)、與編譯程序比較 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.2編譯程序的工作過(guò)程 編譯程序的主要功能是將源程

6、序翻譯成等價(jià)的目標(biāo)程序,這個(gè)翻譯過(guò)程一般可分為詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等階段來(lái)實(shí)現(xiàn)。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.詞法分析 詞法分析是編譯過(guò)程的基礎(chǔ),其任務(wù)是掃描源程序,根據(jù)語(yǔ)言的詞法規(guī)則,分解和識(shí)別出每個(gè)單詞,并把單詞翻譯成相應(yīng)的機(jī)內(nèi)表示。 單詞:是語(yǔ)言的基本語(yǔ)法單位。一般語(yǔ)言有五大類單詞:關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符和分界符。 對(duì)于如下的字符串,詞法分析程序?qū)⒎治龊妥R(shí)別出9個(gè)單詞： x1 := ( 2.0 + 0.8 ) * c1 1 2 3 4 5 6 7 8 9 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北

7、大學(xué)數(shù)計(jì)學(xué)院計(jì)科系2.語(yǔ)法分析 語(yǔ)法分析的任務(wù)是根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位，如表達(dá)式、語(yǔ)句等，并進(jìn)行語(yǔ)法正確性檢查。例如，對(duì)于前面提到的例子x1:= (2.0+ 0.8 ) * c1 我們可以根據(jù)語(yǔ)言賦值語(yǔ)句的文法來(lái)分析和識(shí)別該語(yǔ)句（單詞串）。首先給定文法： := 語(yǔ)法分析根據(jù)文法，將、識(shí)別出來(lái)，進(jìn)而將賦值語(yǔ)句識(shí)別出來(lái)，在識(shí)別過(guò)程中進(jìn)行語(yǔ)法檢查，若有錯(cuò)誤，則應(yīng)輸出出錯(cuò)信息。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系3.語(yǔ)義分析 語(yǔ)義分析的任務(wù)是對(duì)源程序進(jìn)行語(yǔ)義檢查,其目的是保證標(biāo)識(shí)符和常數(shù)的正常使用,把必要的信息收集保存到符號(hào)表或中間代碼程序中,并

8、進(jìn)行相應(yīng)的處理。例如,對(duì)賦值語(yǔ)句 x:= e 需要檢查表達(dá)式e與變量x的類型是否一致;如果不一致,編譯程序?qū)?bào)告出錯(cuò)。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系4.中間代碼生成 中間代碼生成階段的任務(wù)是在語(yǔ)法、語(yǔ)義分析的基礎(chǔ)上,根據(jù)語(yǔ)法成分的語(yǔ)義對(duì)其進(jìn)行翻譯,這種翻譯的結(jié)果即某種中間代碼形式。 生成中間代碼的目的： 便于做優(yōu)化處理； 便于編譯程序的移植（中間代碼不依賴與目標(biāo)計(jì)算機(jī)）。 中間代碼的形式: 三元式、四元式和逆波蘭式等。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系例： x1:= (2.0+ 0.8 ) * c1 由語(yǔ)法分析識(shí)別出為賦值語(yǔ)句，語(yǔ)

9、義分析首先要分析語(yǔ)義上的正確性，例如要檢查表達(dá)式中和賦值號(hào)兩邊的類型是否一致。根據(jù)賦值語(yǔ)句的語(yǔ)義，生成中間代碼。 四元式四元式（三地址指令三地址指令） 運(yùn)算符 左運(yùn)算對(duì)象 右運(yùn)算對(duì)象 結(jié)果(1) + 2.0 0.8 t1(2) * t1 c1 t2(3) := x1 t2 其中t1和t2為編譯程序引入的工作單元 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系5.中間代碼優(yōu)化 任務(wù):調(diào)整和改變中間代碼中某些操作的次序,以最終產(chǎn)生更加高效的目標(biāo)代碼。例如：上面的四元式中第一個(gè)四元式是計(jì)算常量表達(dá)式值，該值在編譯時(shí)就可以算出并存放在工作單元中，不必生成目標(biāo)指令來(lái)計(jì)算，這樣四元式可優(yōu)化

10、為： 編譯時(shí)：2.0 + 0.8 t1* t1 c1 t2:=x1 t2 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系6.目標(biāo)代碼生成 任務(wù):將中間代碼或優(yōu)化之后的中間代碼轉(zhuǎn)換為等價(jià)的目標(biāo)代碼,即機(jī)器指令或匯編語(yǔ)言。 由中間代碼很容易生成目標(biāo)程序（地址指令序列）。這部分工作與機(jī)器關(guān)系密切 ，所以要根據(jù)機(jī)器進(jìn)行。在做這部分工作時(shí)（要注意充分利用累加器），也可以進(jìn)行優(yōu)化處理。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.3 編譯程序的結(jié)構(gòu) 一個(gè)典型的編譯過(guò)程包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、中間代碼優(yōu)化和目標(biāo)代碼生成六個(gè)階段。相應(yīng)的,編譯程序也

11、包括六個(gè)程序模塊,即詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序和目標(biāo)代碼生成程序。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系在上述六個(gè)階段中都要做兩件事：（1）建表和查表；（2）出錯(cuò)處理；所以編譯程序中都要包括表格管理和出錯(cuò)處理兩部分 出錯(cuò)處理 規(guī)模較大的源程序難免有多種錯(cuò)誤，編譯程序必須要有出錯(cuò)處理的功能。即能診察出錯(cuò)誤，并能報(bào)告用戶錯(cuò)誤性質(zhì)和位置，以便用戶修改源程序。出錯(cuò)處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個(gè)重要指標(biāo)。 表格管理（符號(hào)表組織） 在整個(gè)編譯過(guò)程中始終都要貫穿著建表（填表）和查表的工作。即要及時(shí)的把源程序中的信息和編譯

12、過(guò)程中所產(chǎn)生的信息登記在表格中，而在隨后的編譯過(guò)程中同時(shí)又要不斷的查找這些表格中的信息。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.4編譯程序的組織方式根據(jù)編譯程序各部分功能，將編譯程序分成前端和后端。前端前端：通常將與源程序有關(guān)的編譯部分稱為前端。 詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、 代碼優(yōu)化 -分析部分 特點(diǎn)：與源語(yǔ)言有關(guān)后端后端：與目標(biāo)機(jī)有關(guān)的部分稱為后端。 目標(biāo)程序生成（與目標(biāo)機(jī)有關(guān)的優(yōu)化）-綜合部分 特點(diǎn)：與目標(biāo)機(jī)有關(guān) 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系 遍遍（pass） 遍：對(duì)源程序（包括源程序中間形式）從頭到尾掃描一次

13、，并做有關(guān)的加工處理 ，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一遍。 第一遍 第二遍 s.p中間形式1s.p中間形式2c2c1s.po.p 上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。六個(gè)基本階段：是將源程序翻譯為目標(biāo)程序在邏輯上要完成的 工作。 遍：是指完成上述6個(gè)基本階段的工作，要經(jīng)過(guò)幾次掃描處理。要注意遍與基本階段的區(qū)別要注意遍與基本階段的區(qū)別 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系一遍掃描即可完成整個(gè)編譯工作的稱為一遍掃描即可完成整個(gè)編譯工作的稱為一遍掃描編譯程序一遍掃描編譯程序 取單詞取單詞 返回單詞返回單詞其結(jié)構(gòu)為其結(jié)構(gòu)為：s.p.詞法分析語(yǔ)法分

14、析整理目標(biāo)程序 停機(jī)語(yǔ)義分析生成目標(biāo)程序o.p.語(yǔ)法成分語(yǔ)法成分返回分析結(jié)果返回分析結(jié)果 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系1.5編譯程序的自展、移植與自動(dòng)化 高級(jí)語(yǔ)言的自編譯性是指可以用這個(gè)語(yǔ)言來(lái)編寫自己的編譯程序。 對(duì)于具有自編譯性的高級(jí)語(yǔ)言，可運(yùn)用自展技術(shù)構(gòu)造其編譯程序。即先對(duì)語(yǔ)言的核心部分構(gòu)造一個(gè)小小的編譯程序(可用低級(jí)語(yǔ)言實(shí)現(xiàn))，再以它為工具構(gòu)造一個(gè)能夠編譯更多語(yǔ)言成分的較大編譯程序，如此擴(kuò)展下去，最后形成整個(gè)編譯程序。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系l0l1ln=l 分解源程序之后，先用匯編語(yǔ)言或機(jī)器語(yǔ)言編寫l0的編譯程序

15、，然后再用l0編寫l1的編譯程序，用li編寫li+1的編譯程序（i=1,2,n-1），最后得到源語(yǔ)言l的編譯程序。在這個(gè)自展過(guò)程中，除了l0的編譯程序是用低級(jí)語(yǔ)言編寫的之外，l1,l2,ln=l的編譯程序都是用高級(jí)語(yǔ)言編寫的。 2008年年9月月湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系湖北大學(xué)數(shù)計(jì)學(xué)院計(jì)科系 編譯程序可以通過(guò)移植得到，即可以將一個(gè)機(jī)器（宿主機(jī)）上的一個(gè)具有自編譯性的高級(jí)語(yǔ)言編譯程序移植到另一個(gè)機(jī)器（目標(biāo)機(jī)）上。cla：在宿主機(jī)a上用高級(jí)語(yǔ)言l編寫的源語(yǔ)言為l的編譯程序。coa：在宿主機(jī)a上用機(jī)器語(yǔ)言編寫的源語(yǔ)言為l的編譯程序。 cla=cfla+cala c1la=cfla+calb c1la c1oac1oa：能在宿主機(jī)a上運(yùn)行，能生成目標(biāo)