安徽大學(xué)編譯原理課件第一章

1、1主講：主講：XX23456789計(jì)算機(jī)編譯原理編譯程計(jì)算機(jī)編譯原理編譯程序構(gòu)造實(shí)踐序構(gòu)造實(shí)踐張幸兒張幸兒10v 第一章第一章 引論引論v 第二章第二章 PL/OPL/O編譯程序的實(shí)現(xiàn)編譯程序的實(shí)現(xiàn)v 第三章第三章 文法和語言文法和語言v 第四章第四章 詞法分析詞法分析v 第五章第五章 自頂向下語法分析方法自頂向下語法分析方法v 第六章第六章 自底向上優(yōu)先分析自底向上優(yōu)先分析v 第七章第七章 LRLR分析分析11v 第八章第八章 語法制導(dǎo)翻譯和中間代碼生成語法制導(dǎo)翻譯和中間代碼生成v 第九章第九章 符號(hào)表符號(hào)表 v 第十章第十章 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織v 第十一章第十

2、一章 代碼優(yōu)化代碼優(yōu)化v 第十二章第十二章 代碼生成代碼生成v 第十三章第十三章 編譯程序的構(gòu)造編譯程序的構(gòu)造v 第十四章第十四章 面向?qū)ο笳Z言的編譯面向?qū)ο笳Z言的編譯v 第十五章第十五章 編譯程序的面向?qū)ο髽?gòu)造編譯程序的面向?qū)ο髽?gòu)造12131415程程序序設(shè)設(shè)計(jì)計(jì)語語言言 機(jī)器語言機(jī)器語言 機(jī)器指令（機(jī)器指令（0 0，1 1）匯編語言匯編語言機(jī)器指令（符號(hào)）機(jī)器指令（符號(hào)）可以直接執(zhí)可以直接執(zhí)行、依賴具行、依賴具體機(jī)器、煩體機(jī)器、煩瑣容易出錯(cuò)瑣容易出錯(cuò)高級(jí)語言高級(jí)語言PascalPascal、 c c 、c+c+與機(jī)器無關(guān)、與機(jī)器無關(guān)、不可直接執(zhí)行不可直接執(zhí)行002 0123 002 012

3、3 取出取出a a00E 1234 00E 1234 除以除以b b009 2103 009 2103 減去減去c c004 0576 004 0576 送送x xX=a/b-cX=a/b-c CLA a CLA a 取出取出a a DIV b DIV b 除以除以b b SUB c SUB c 減去減去c c STO x STO x 送送x xX=a/b-cX=a/b-cv例如，在國產(chǎn)例如，在國產(chǎn)DJSDJS2121計(jì)算機(jī)中，取、除、減、送的計(jì)算機(jī)中，取、除、減、送的指令代碼分別為：指令代碼分別為：002002，00E00E，009009，004004。假定假定a a、b b、c c、x x

4、四個(gè)單元的地址碼分別為：四個(gè)單元的地址碼分別為：01230123，12341234，21032103，05760576，那么要計(jì)算那么要計(jì)算 x x：= a / b = a / b c cv如對(duì)應(yīng)于取、除、減、送采用下列符號(hào)：如對(duì)應(yīng)于取、除、減、送采用下列符號(hào)：CLACLA，DIVDIV，SUBSUB，STOSTO1617源程序源程序 用匯編語言或高級(jí)語言編寫的程序稱為源程序目標(biāo)程序目標(biāo)程序 用目標(biāo)語言目標(biāo)語言所表示的程序 目標(biāo)語言：可以是介于源語言和機(jī)器語言之間的“中間語言”，可以是某種機(jī)器的機(jī)器語言,也可以是某機(jī)器的匯編語言。翻譯程序翻譯程序 將源程序源程序轉(zhuǎn)換為目標(biāo)程序目標(biāo)程序的程序稱為

5、翻譯程序。它是指各種語言的翻譯器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱。18高級(jí)語高級(jí)語言程序言程序編譯程序編譯程序低級(jí)語低級(jí)語言程序言程序19源程序、翻譯程序、目標(biāo)程序源程序、翻譯程序、目標(biāo)程序 三者關(guān)系：三者關(guān)系：源程序源程序翻譯程序翻譯程序目標(biāo)程序目標(biāo)程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出20需預(yù)處理的源程序需預(yù)處理的源程序預(yù)處理程序預(yù)處理程序源程序源程序編譯程序編譯程序目標(biāo)匯編程序目標(biāo)匯編程序匯編程序匯編程序可再裝

6、配的機(jī)器代碼可再裝配的機(jī)器代碼裝配裝配/ /連接連接-編輯程序編輯程序絕對(duì)機(jī)器代碼絕對(duì)機(jī)器代碼可再裝配目標(biāo)文件可再裝配目標(biāo)文件3.3.高級(jí)語言程序的處理過程高級(jí)語言程序的處理過程2122翻譯外文資料：翻譯外文資料：1 1、能識(shí)別出句子中的一個(gè)個(gè)單詞；、能識(shí)別出句子中的一個(gè)個(gè)單詞；2 2、分析句子的語法結(jié)構(gòu)；、分析句子的語法結(jié)構(gòu)；3 3、根據(jù)句子的含義進(jìn)行初步翻譯；、根據(jù)句子的含義進(jìn)行初步翻譯；4 4、對(duì)譯文進(jìn)行修飾；、對(duì)譯文進(jìn)行修飾；5 5、寫出最后的譯文。、寫出最后的譯文。1.21.2編譯過程和編譯程序的結(jié)構(gòu)編譯過程和編譯程序的結(jié)構(gòu)1.2.1 1.2.1 編譯過程概述編譯過程概述1.1.編譯

7、過程編譯過程2.2.自然語言的翻譯自然語言的翻譯 23242526單詞單詞：高級(jí)語言中有實(shí)在意義的最小語法單位，它由字符構(gòu)成。 任務(wù)：任務(wù)：輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞。和分解，識(shí)別出一個(gè)個(gè)的單詞。 （1 1）詞法分析）詞法分析27 保留字保留字（如（如: :void,int,floatvoid,int,float） 標(biāo)識(shí)符標(biāo)識(shí)符（如（如: :a, b, c, d, x, y, a, b, c, d, x, y, jisuan jisuan） 常數(shù)常數(shù) （如（如:50:50） 運(yùn)算符運(yùn)算符（如（如: :* *,+,=

8、 ,+,= ） 界限符界限符（如（如 ；，（；，（ ） ） ）28任務(wù)：任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號(hào)組成各類語法單位：短語、子句、則，把單詞符號(hào)組成各類語法單位：短語、子句、語句、過程、程序。語句、過程、程序。 （2 2）語法分析（編譯程序的核心）語法分析（編譯程序的核心）語法規(guī)則：語法規(guī)則： 語言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成語言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語、語句、過程和程序。短語、語句、過程和程序。 2930（3 3）語義分析及中間代碼的生成）語義分析及中間代碼的生成任務(wù)：任務(wù)：對(duì)語法分析識(shí)別出的各類語法范疇

9、，分析其含對(duì)語法分析識(shí)別出的各類語法范疇，分析其含義，進(jìn)行初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼之間義，進(jìn)行初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼之間的一種代碼。的一種代碼。 分為兩階段工作分為兩階段工作 對(duì)每種語法范疇進(jìn)行靜態(tài)語義檢查對(duì)每種語法范疇進(jìn)行靜態(tài)語義檢查 若語義正確，就進(jìn)行中間代碼的翻譯若語義正確，就進(jìn)行中間代碼的翻譯中間代碼的形式：中間代碼的形式： 四元式、三元式、逆波蘭式四元式、三元式、逆波蘭式31四元式四元式其中t1、t2、t3為編譯程序引入的臨時(shí)工作單元例：y = x + r * 632任務(wù)：任務(wù)：對(duì)中間代碼進(jìn)行加工變換加工變換，以得到高質(zhì)量的目標(biāo)代碼（4 4）代碼優(yōu)化）代碼優(yōu)化例

10、：y = x + r * 6等價(jià)變換33（5 5）目標(biāo)代碼生成）目標(biāo)代碼生成任務(wù)：任務(wù)：把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼低級(jí)語言代碼movr, R1mul#6.0, R1movx, R2addR1, R2movR2, y34 按邏輯功能不同，可將編譯過程劃分為五個(gè)基本階 段，與此相對(duì)應(yīng)，我們將實(shí)現(xiàn)整個(gè)編譯過程的編譯程序劃 分為五個(gè)邏輯階段（即五個(gè)邏輯子過程）。每個(gè)階段中都要有：符號(hào)表管理符號(hào)表管理和錯(cuò)誤處理錯(cuò)誤處理35診察錯(cuò)誤，并能報(bào)告用戶錯(cuò)誤性質(zhì)和位置出錯(cuò)處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個(gè)重要指標(biāo)。填表填表：把源程序中的信息和編譯過程中所產(chǎn)生的信息登記在表格中查表查表：在隨后

11、的編譯過程中同時(shí)又要不斷地查找這些表格中的信息符號(hào)表管理符號(hào)表管理錯(cuò)誤處理錯(cuò)誤處理編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu)36典型的編譯程序具有典型的編譯程序具有7 7個(gè)邏輯部分個(gè)邏輯部分S.PO.P語義分析及語義分析及生成中間代碼生成中間代碼程序程序代碼生成程序代碼生成程序代碼優(yōu)化代碼優(yōu)化程序程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號(hào)號(hào)表表管管理理1.2.2 1.2.2 編譯過程的結(jié)構(gòu)編譯過程的結(jié)構(gòu)37根據(jù)編譯程序各部分功能，將編譯程序分成根據(jù)編譯程序各部分功能，將編譯程序分成前端前端和和后端后端 前端前端：通常將與：通常將與源程序源程序有關(guān)的編譯部分稱為前端。有

12、關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成詞法分析、語法分析、語義分析、中間代碼生成 -分析部分分析部分 特點(diǎn)：與特點(diǎn)：與源語言源語言有關(guān)有關(guān) 后端后端：與：與目標(biāo)機(jī)目標(biāo)機(jī)有關(guān)的部分稱為后端。有關(guān)的部分稱為后端。 代碼優(yōu)化、代碼生成代碼優(yōu)化、代碼生成-綜合部分綜合部分 特點(diǎn)：與特點(diǎn)：與目標(biāo)機(jī)目標(biāo)機(jī)有關(guān)有關(guān)編譯程序的前端和后端編譯程序的前端和后端1.2.3 1.2.3 編譯階段的組合編譯階段的組合38.java java源程序文件.class 二進(jìn)制字節(jié)碼文件Java虛擬機(jī)（JVM)本地計(jì)算機(jī)系統(tǒng)編譯同一前端同一前端+ +不同后端不同后端 不同機(jī)器構(gòu)成同一語言的編譯程序不

13、同機(jī)器構(gòu)成同一語言的編譯程序例如例如JavaJava語言語言39 同一前端同一前端+ +不同后端不同后端 不同機(jī)器構(gòu)成同一語言的編譯程序不同機(jī)器構(gòu)成同一語言的編譯程序例如例如.NET.NET框架框架 40 不同前端不同前端+ +同一后端同一后端 同一機(jī)器生成幾個(gè)語言的編譯程序同一機(jī)器生成幾個(gè)語言的編譯程序例如例如GCCGCC 41 第一遍 第二遍 S.P中間形式1S.P中間形式2C2C1S.PO.P 上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。 對(duì)源程序（包括源程序中間形式）從頭到尾對(duì)源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一序中間形式或目標(biāo)程序，通常稱之為一遍遍。 遍遍42一遍掃描即可完成整個(gè)編譯工作的稱為一遍掃描即可完成整個(gè)編譯工作的稱為一遍掃描編譯程序一遍掃描編譯程序遍的劃分視具體情況而定（內(nèi)存的大小、源語言的繁簡(jiǎn)、遍的劃分視具體情況而定（內(nèi)存的大小、源語言的繁簡(jiǎn)、目標(biāo)程序質(zhì)量的高低）目標(biāo)程序質(zhì)量的高低） 優(yōu)點(diǎn)優(yōu)點(diǎn)：1