編譯程序引言-1

1、編 譯 原 理2011.11課程簡介先行課程： (PASCAL)、離散數(shù)學(xué)、 匯編語言、數(shù)據(jù)結(jié)構(gòu)編譯原理課程應(yīng)用領(lǐng)域編譯器的設(shè)計(jì)一般的軟件設(shè)計(jì)例如：文本編輯器、信息檢索系統(tǒng)、模式識別器排版、繪圖系統(tǒng)程序驗(yàn)證器21、程序設(shè)計(jì)語言編譯程序 陳火旺等 國防工業(yè)出版社（第三版）2、編譯原理 呂映芝 清華大學(xué)出版社 3、編譯原理及實(shí)踐，Kenneth C. Louden， 馮博琴譯，機(jī)械工業(yè)出版社主要參考資料3系統(tǒng)地了解程序設(shè)計(jì)語言編譯程序的構(gòu)造原理及其具體實(shí)現(xiàn)的方法；培養(yǎng)利用計(jì)算機(jī)語言處理技術(shù)進(jìn)行系統(tǒng)分析和軟件設(shè)計(jì)的能力。 為什么要學(xué)習(xí)編譯原理，學(xué)習(xí)的目的是什么？4課程考核方法主要采用閉卷考試的形式；

2、同時，作業(yè)完成情況和上機(jī)實(shí)踐的結(jié)果占一定的比例。 考試成績 = 閉卷考試+ 考勤和作業(yè)完成 情況 + 上機(jī)5聯(lián)系方式E-mail: Tel: 作業(yè)可通過班長（或課程代表）提交。如有什么建議和問題，課后可E-mail或電話聯(lián)系。6編譯原理第一章 引論第二章 高級語言及其語法描述第三章 詞法分析第四章 語法分析自上向下分析第五章 語法分析自下向上分析第六章 屬性文法與語法制導(dǎo)翻譯第七章 語義分析和中間代碼生成第八章 符號表第九章 運(yùn)行時存儲空間組織第十章 優(yōu)化第十一章 目標(biāo)代碼生成第十二章 并行編譯基礎(chǔ)7第一章 引論1.1 什么叫編譯程序1.2 編譯過程概述1.3 編譯程序的結(jié)構(gòu)1.4 編譯程序與

3、程序設(shè)計(jì)環(huán)境1.5 編譯程序的生成8知 識 結(jié) 構(gòu)9過程式語言 Fortran,Pascal,C函數(shù)式語言 Lisp邏輯式語言 Prolog對象式語言 C+匯編語言機(jī)器語言第一章 引論1.1 什么叫編譯程序. 程序設(shè)計(jì)語言程序設(shè)計(jì)語言 高級語言低級語言：面向機(jī)器的語言10編譯程序:是指這樣的程序，它能夠把某種語言的程序轉(zhuǎn)換成另一種語言的程序，而后者與前者在邏輯上是等價的。如果源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級語言”，而目標(biāo)語言如匯編語言之類的“低級語言”這樣的翻譯程序則稱之為編譯程序。112.在計(jì)算機(jī)上如何執(zhí)行一個高級語言程序？1）把

4、高級語言程序翻譯成機(jī)器語言程序；2）運(yùn)行所得的機(jī)器語言程序求得計(jì)算結(jié)果。高級語言源程序的執(zhí)行通常分兩個階段:計(jì)算機(jī)只能識別由0和1組成的二進(jìn)制指令。12源程序(高級語言)編譯程序計(jì)算機(jī)目標(biāo)程序(機(jī)器語言)編譯階段初始數(shù)據(jù)目標(biāo)程序計(jì)算機(jī)運(yùn)行系統(tǒng)計(jì)算結(jié)果運(yùn)行階段13. 翻譯和解釋程序(1)翻譯和編譯程序編譯：如果一個翻譯程序的源語言是某種高級語言，其目標(biāo)語言是相對于某一計(jì)算機(jī)的匯編語言或機(jī)器語言，則稱這種翻譯程序?yàn)榫幾g程序（或稱為編譯器）。翻譯：是指在計(jì)算機(jī)中放置一個能由計(jì)算機(jī)直接執(zhí)行的翻譯程序，它以某一種程序設(shè)計(jì)語言（源語言）所編寫的程序（源程序）作為翻譯或轉(zhuǎn)換的對象，當(dāng)計(jì)算機(jī)執(zhí)行翻譯程序時，就

5、將它轉(zhuǎn)換成與之等價的另一種語言（目標(biāo)語言）的程序（目標(biāo)程序）。輸入輸出14(2) 編譯和解釋程序目標(biāo)程序源程序編譯程序初始數(shù)據(jù)計(jì)算結(jié)果源程序解釋程序初始數(shù)據(jù)計(jì)算結(jié)果15解釋程序和編譯程序的區(qū)別解釋程序和編譯程序的根本區(qū)別：是否生成目標(biāo)代碼16口譯解釋程序筆譯編譯程序解釋程序和編譯程序的區(qū)別優(yōu)點(diǎn)：直觀易懂，結(jié)構(gòu)簡單， 易于實(shí)現(xiàn)人機(jī)對話。缺點(diǎn)：效率低。解釋程序的優(yōu)缺點(diǎn)17編譯程序的分類診斷型編譯程序: 用于幫助程序開發(fā)和調(diào)試的編譯程序。優(yōu)化型編譯程序： 著重于提高目標(biāo)代碼效率的編譯程序。交叉型編譯程序可變目標(biāo)型編譯程序18編譯技術(shù)的發(fā)展第一個編譯程序出現(xiàn)在20世紀(jì)50年代早期，主要是將算術(shù)公式翻譯

6、成機(jī)器代碼。20世紀(jì)60年代起，出現(xiàn)自編譯技術(shù)。還在不斷發(fā)展之中，目前已經(jīng)形成一套比較成熟的系統(tǒng)化的理論和方法。191. 編譯過程概述翻譯外文資料與編譯源程序進(jìn)行類比20 編譯程序的工作過程指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€過程。一般可劃分為五個階段：詞法分析、語法分析、語義分析和中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。 1)詞法分析 詞法分析的任務(wù)是輸入源程序, 對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個單詞符號, 并將識別出的單詞用統(tǒng)一長度的標(biāo)準(zhǔn)形式表示。詞法分析過程就是將源程序中的字符串變換成單詞串的過程。21 在詞法分析階段工作所依循的是語言的詞法規(guī)則。描述詞法規(guī)則的有效工

7、具是正規(guī)式和有限自動機(jī)。int fun() int i,sum; sum=0; for(i=0;i=100;i+) sum+=i; return sum;關(guān)鍵字：int for return 標(biāo)識符：i sum 常量：0 100 運(yùn)算符：= = + += 界限符：; ( ) , 222)語法分析 語法分析的任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號分解成各類語法單位（語法范疇），如“短語”、“句子”、 “子句”、“程序段”等。 語法規(guī)則通常用上下文無關(guān)文法描述。23int fun() -函數(shù)定義語句 int i,sum; -變量定義語句 sum=0; -賦值語句 for(i=0;

8、i=100;i+) - for語句 sum+=i; -賦值語句 return sum; -返回語句243)語義分析與中間代碼的產(chǎn)生 這一階段通常包括兩方面的工作：首先對各種語法范疇進(jìn)行靜態(tài)語義檢查，如果正確則進(jìn)行另一方面的工作，即進(jìn)行中間代碼的翻譯。 該階段遵循的是語言的語義規(guī)則。 通常使用屬性文法描述語義規(guī)則。 所謂“中間代碼”是一種含義明確，便于處理的記號系統(tǒng)，它通常獨(dú)立于具體的硬件。 中間代碼除四元式外，還有三元式、間接三元式、逆波蘭記號、樹形表示等。254）優(yōu)化 優(yōu)化的任務(wù)在于對前段產(chǎn)生的中間代碼進(jìn)行加工，以期在最后階段產(chǎn)生更為高效（省時間和空間）的代碼 優(yōu)化所依循的原則是程序的等價變

9、換規(guī)則。其方法有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等。265）目標(biāo)代碼生成 這一階段的任務(wù)：把中間代碼（或經(jīng)優(yōu)化處理后）變換成特定機(jī)器上的低級語言代碼。它有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。 如何充分利用寄存器、合理選擇指令以生成盡可能短且有效的目標(biāo)代碼等都與目標(biāo)機(jī)器硬件結(jié)構(gòu)有關(guān)。271）編譯程序的功能和組織結(jié)構(gòu)表 處 理詞法分析器源程序目標(biāo)程序錯 誤 處 理語法分析器語義分析目標(biāo)代碼生成前 端后 端代碼優(yōu)化器中間代碼生成1.3 編譯程序的結(jié)構(gòu)282）表格與表格管理 用于記錄源程序的各種信息以及編譯過程中的各種狀況，以便后續(xù)階段使用。 與編譯前三階段有關(guān)的表格有：符號表、常數(shù)表、標(biāo)號表

10、、分程序入口表、中間代碼表等。 注：在編譯過程中，隨著源程序的不斷被改造，編譯的各階段常常需要不同的表格，編譯過程的絕大多數(shù)時間是花在查表、造表和更新表格的事務(wù)上。在大多數(shù)的編譯程序中，表格專門由表格管理程序來處理。293）出錯處理 出錯處理程序的任務(wù)包括檢查錯誤、報(bào)告出錯信息、排錯、恢復(fù)編譯工作。錯誤類型: 語法錯誤:在詞法分析和語法分析階段檢測 出來。 語義錯誤：一般在語義分析階段檢測。 30編譯程序的前端： 與源語言有關(guān)，而與目標(biāo)機(jī)無關(guān)的編譯程序編譯程序的后端： 與目標(biāo)機(jī)有關(guān)，而與源語言無關(guān)的編譯程序遍（趟）：是對源程序或源程序的中間結(jié)果從頭到尾掃描一遍，并作有關(guān)加工處理，生成新的中間結(jié)

11、果或目標(biāo)程序。宿主機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)稱為宿主機(jī)。目標(biāo)機(jī)：運(yùn)行編譯程序所產(chǎn)生的目標(biāo)代碼的計(jì)算機(jī)成為目標(biāo)機(jī)。4）相關(guān)概念311.4 編譯程序與程序設(shè)計(jì)環(huán)境 編譯程序無疑是實(shí)現(xiàn)高級語言的一個最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。 在一個程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。32圖1.2 Ada程序設(shè)計(jì)環(huán)境 331.5 編譯程序的生成1 常用的方法（根據(jù)語言來分）1）直接用機(jī)器語言編寫編譯程序2）用匯編語言編寫編譯程序注：編譯程序核心部分常用匯編語言編寫3）用高級語言編寫編譯程序注：這是普遍采用的方法2 常用的方法（根據(jù)實(shí)現(xiàn)途徑來分）1）自編譯2）編譯工具:LEX(詞法分析)與YACC(用于自動產(chǎn)生LALR分析表)3）移植（同種語言的編譯程序在不同類型的機(jī)器之間移植