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

1、編譯原理主講：XX1重要性計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)必修課之一軟件技術(shù)基礎(chǔ) 計(jì)算機(jī)專業(yè)的學(xué)生必修的一門主干課 2作用 編譯原理介紹了如何將高級程序設(shè)計(jì)語言變換成計(jì)算機(jī)硬件所能識(shí)別的機(jī)器語言，以便計(jì)算機(jī)進(jìn)行處理。 它的理論基礎(chǔ)堅(jiān)實(shí)，其形式化系統(tǒng)不僅應(yīng)用于編譯技術(shù)，還大量應(yīng)用于人工智能、多媒體技術(shù)及數(shù)據(jù)庫等領(lǐng)域。 3主要應(yīng)用領(lǐng)域編譯器的設(shè)計(jì)一般的軟件設(shè)計(jì)例如：文本編輯器、信息檢索系統(tǒng)、模式識(shí)別器排版、繪圖系統(tǒng)程序驗(yàn)證器4基本要求對編譯程序的整體結(jié)構(gòu)有非常清晰的了解 熟練掌握詞法分析和語法分析的基本原理及其理論基礎(chǔ) 熟練掌握詞法和語法分析的常用方法并初步了解其自動(dòng)生成技術(shù) 熟悉編譯中各種符號(hào)表的構(gòu)造和應(yīng)用

2、 具有初步的分析和設(shè)計(jì)編譯程序的能力 5學(xué)習(xí)方法認(rèn)真聽課，認(rèn)真理解書中的基本概念、基本原理和基本算法弄懂書中的例題和習(xí)題在看書時(shí)或理解例題時(shí)，一定要畫出相應(yīng)的細(xì)節(jié)變化過程，通過畫圖來加深理解在理解的基礎(chǔ)上記憶理論結(jié)合實(shí)踐6先修課程要求先學(xué)習(xí)以下課程1.程序設(shè)計(jì)C語言 高級語言是編譯程序的源語言，高級語言的數(shù)據(jù)類型、結(jié)構(gòu)、表達(dá)式、語句、程序結(jié)構(gòu)、參數(shù)傳遞方式和存儲(chǔ)管理方法直接影響編譯程序的實(shí)現(xiàn)。2.匯編程序設(shè)計(jì) 匯編語言是編譯程序的目的語言，匯編語言的指令形式、寄存器、變址器以及尋址方式與編譯程序代碼生成直接有關(guān)。 3.算法與數(shù)據(jù)結(jié)構(gòu) 編譯程序?qū)Ω呒壵Z言描述的數(shù)據(jù)類型進(jìn)行組織和管理，編譯過程中

3、編譯程序?qū)Ψ?hào)表進(jìn)行組織、管理和查找，大量使用到數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和算法。74.操作系統(tǒng) 編譯程序?qū)χ虚g代碼和目標(biāo)代碼進(jìn)行存儲(chǔ)空間的分配和管理，使用到了操作系統(tǒng)的基本知識(shí)和管理算法。 5.離散數(shù)學(xué) 編譯原理建立在形式語言與自動(dòng)機(jī)的理論基礎(chǔ)上，在編譯程序的實(shí)現(xiàn)上大量應(yīng)用了離散數(shù)學(xué)的知識(shí)，如集合，關(guān)系，邏輯，圖論等。最好學(xué)習(xí)過或同時(shí)學(xué)習(xí)以下課程1.軟件工程 掌握大型程序設(shè)計(jì)以及工程化的軟件生產(chǎn)方法。2.形式語言與自動(dòng)機(jī) 相當(dāng)于本課程中詞法分析與語法分析的理論基礎(chǔ)。 8計(jì)算機(jī)編譯原理編譯程序構(gòu)造實(shí)踐張幸兒科學(xué)出版社 編譯程序設(shè)計(jì)原理杜淑敏等北京大學(xué)出版社編譯原理李贛生等清華大學(xué)出版社編譯程序構(gòu)造

4、原理和實(shí)現(xiàn)技術(shù)金成植高等教育出版社程序設(shè)計(jì)語言編譯程序陳火旺等國防工業(yè)出版社Compiler Construction Principle and Pratice編譯原理及實(shí)踐Kenneth C.Louden機(jī)械工業(yè)出版社參考書籍參考書籍9知識(shí)結(jié)構(gòu) 第一章 引論 第二章 PL/O編譯程序的實(shí)現(xiàn) 第三章 文法和語言 第四章 詞法分析 第五章 自頂向下語法分析方法 第六章 自底向上優(yōu)先分析 第七章 LR分析10 第八章 語法制導(dǎo)翻譯和中間代碼生成 第九章 符號(hào)表 第十章 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織 第十一章 代碼優(yōu)化 第十二章 代碼生成 第十三章 編譯程序的構(gòu)造 第十四章 面向?qū)ο笳Z言的編譯 第十五

5、章 編譯程序的面向?qū)ο髽?gòu)造11課程成績評定平時(shí)成績(30%) （考勤20、 書面作業(yè)30、平時(shí)測驗(yàn)30、態(tài)度與提問20） 期末考試(70%)12第一章 引論學(xué)習(xí)目標(biāo)：掌握：編譯的各個(gè)階段理解：編譯程序的概念了解：編譯程序的結(jié)構(gòu)和組合131.1 什么是編譯程序1.計(jì)算機(jī)語言的層次低級語言（Low level Language)字位碼、機(jī)器語言、匯編語言特點(diǎn)：與特定的機(jī)器有關(guān)，功效高，但使用復(fù)雜、繁瑣、費(fèi)時(shí)、易出錯(cuò)高級語言 - Fortran、Pascal、C語言等特點(diǎn)：不依賴具體機(jī)器，移植性好、對用戶要求低、易使用、易維護(hù)等。14程序設(shè)計(jì)語言機(jī)器語言機(jī)器指令（0，1）匯編語言機(jī)器指令（符號(hào)）可以

6、直接執(zhí)行、依賴具體機(jī)器、煩瑣容易出錯(cuò)高級語言Pascal、 c 、c+與機(jī)器無關(guān)、不可直接執(zhí)行002 0123 取出a00E 1234 除以b009 2103 減去c004 0576 送xX=a/b-c CLA a 取出a DIV b 除以b SUB c 減去c STO x 送xX=a/b-c例如，在國產(chǎn)DJS21計(jì)算機(jī)中，取、除、減、送的指令代碼分別為：002，00E，009，004。假定a、b、c、x四個(gè)單元的地址碼分別為：0123，1234，2103，0576，那么要計(jì)算 x：= a / b c如對應(yīng)于取、除、減、送采用下列符號(hào)：CLA，DIV，SUB，STO152.編譯程序（compi

7、ler） 將用高級語言（如FORTRAN,PASCAL或C）書寫的程序翻譯成等價(jià)的低級語言程序（如匯編語言或機(jī)器語言），這種翻譯程序稱為編譯程序(compiler)。編譯程序的輸入對象稱為源程序(Source program)輸出對象稱為目標(biāo)程序 （Targer or Object program）16源程序 用匯編語言或高級語言編寫的程序稱為源程序目標(biāo)程序 用目標(biāo)語言所表示的程序 目標(biāo)語言：可以是介于源語言和機(jī)器語言之間的“中間語言”，可以是某種機(jī)器的機(jī)器語言,也可以是某機(jī)器的匯編語言。翻譯程序 將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語言的翻譯器，包括匯編程序和編譯程序，是匯編

8、程序、編譯程序以及各種變換程序的總稱。17在計(jì)算機(jī)上如何執(zhí)行一個(gè)高級語言程序？ 把高級語言程序翻譯成機(jī)器語言程序 運(yùn)行所得的機(jī)器語言程序求得計(jì)算結(jié)果高級語言程序編譯程序低級語言程序18源程序、翻譯程序、目標(biāo)程序 三者關(guān)系：源程序翻譯程序目標(biāo)程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出19需預(yù)處理的源程序預(yù)處理程序源程序編譯程序目標(biāo)匯編程序匯編程序可再裝配的機(jī)器代碼裝配/連接-編輯程序絕對機(jī)器代碼可再裝配目標(biāo)文件3.高級語言程序的處理過程204.編譯程序的發(fā)展第一個(gè)編譯程序的出現(xiàn)：20世紀(jì)50年代早期，主要將

9、算術(shù)公式翻譯成機(jī)器代碼20世紀(jì)50年代中期，一批編譯系統(tǒng)程序開發(fā)成功20世紀(jì)50年代末，開始研究編譯程序的自動(dòng)生成工具20世紀(jì)60年代，研究使用自展技術(shù)并行編譯技術(shù)21 所謂編譯過程是指將高級語言程序翻譯為等價(jià)的目標(biāo)程序的過程。翻譯外文資料：1、能識(shí)別出句子中的一個(gè)個(gè)單詞；2、分析句子的語法結(jié)構(gòu)；3、根據(jù)句子的含義進(jìn)行初步翻譯；4、對譯文進(jìn)行修飾；5、寫出最后的譯文。1.2編譯過程和編譯程序的結(jié)構(gòu)1.2.1 編譯過程概述1.編譯過程2.自然語言的翻譯 22翻譯和編譯工作的比較翻譯外文編譯程序分析識(shí)別單詞分析句子根據(jù)語義進(jìn)行初步翻譯詞法分析語法分析語義分析、生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)

10、化目標(biāo)代碼生成233.編譯程序的工作 詞法分析語法分析語義分析和中間代碼生成代碼優(yōu)化目標(biāo)代碼生成24Void jisuan( ) int y,c,d; float x,a,b; x=a+b*50; y=c+)d*(x+b; 例子25單詞：高級語言中有實(shí)在意義的最小語法單位，它由字符構(gòu)成。 任務(wù)：輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞。 （1）詞法分析26識(shí)別右邊程序中的單詞 Void jisuan( ) int y,c,d; float x,a,b; x=a+b*50; y=c+)d*(x+b; 保留字（如:void,int,float） 標(biāo)識(shí)符（如:a, b, c

11、, d, x, y, jisuan） 常數(shù) （如:50） 運(yùn)算符（如:*,+,= ） 界限符（如 ；，（ ） ） ）27任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號(hào)組成各類語法單位：短語、子句、語句、過程、程序。 （2）語法分析（編譯程序的核心）語法規(guī)則： 語言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語、語句、過程和程序。 28a:=b+c*60 經(jīng)語法分析得到的語法樹表達(dá)式3賦值語句標(biāo)識(shí)符=表達(dá)式1表達(dá)式2+表達(dá)式5ab標(biāo)識(shí)符表達(dá)式4*60整數(shù)c標(biāo)識(shí)符29（3）語義分析及中間代碼的生成任務(wù)：對語法分析識(shí)別出的各類語法范疇，分析其含義，進(jìn)行初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼之間的一種

12、代碼。 分為兩階段工作 對每種語法范疇進(jìn)行靜態(tài)語義檢查 若語義正確，就進(jìn)行中間代碼的翻譯中間代碼的形式： 四元式、三元式、逆波蘭式30四元式其中t1、t2、t3為編譯程序引入的臨時(shí)工作單元例：y = x + r * 6運(yùn)算符運(yùn)算對象1運(yùn)算對象2結(jié)果(1)inttoreal6-t1(2)*rt1t2(3)+t2xt3(4)=t3y31任務(wù)：對中間代碼進(jìn)行加工變換，以得到高質(zhì)量的目標(biāo)代碼（4）代碼優(yōu)化運(yùn)算符左運(yùn)算對象右運(yùn)算對象結(jié)果(1)Inttoreal6-t1(2)*rt1t2(3)+t2xt3(4)=t3y運(yùn)算符左運(yùn)算對象右運(yùn)算對象結(jié)果(1)*r6.0t1(2)+t1xy(1)inttorea

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

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

15、ava源程序文件.class 二進(jìn)制字節(jié)碼文件Java虛擬機(jī)（JVM)本地計(jì)算機(jī)系統(tǒng)編譯同一前端+不同后端 不同機(jī)器構(gòu)成同一語言的編譯程序例如Java語言38 同一前端+不同后端 不同機(jī)器構(gòu)成同一語言的編譯程序例如.NET框架 39 不同前端+同一后端 同一機(jī)器生成幾個(gè)語言的編譯程序例如GCC 40 第一遍 第二遍 S.P中間形式1S.P中間形式2C2C1S.PO.P 上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。 對源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一遍。 遍41一遍掃描即可完成整個(gè)編譯工作的稱為一遍掃描編譯程序遍的劃分視具體情況而定（內(nèi)存的大小、源語言的繁簡、目標(biāo)程序質(zhì)量的高低） 優(yōu)點(diǎn)：1、減少對內(nèi)存容量的要求2、編譯程序結(jié)構(gòu)清晰、各遍功能獨(dú)立、相互聯(lián)系簡單缺點(diǎn)：增加讀寫中間文件的次數(shù)，降低效率421.3 編譯程序和一些軟件工具1.3.1解釋程序接受某個(gè)語言的程序并立即運(yùn)行這個(gè)源程序.它的工作模式是一個(gè)個(gè)地獲取,分析并執(zhí)行源程序語句,一旦第一個(gè)語句分析結(jié)束,源程序便開始運(yùn)行并且生成結(jié)果, 它特別適合程