編譯程序引言-1

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

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

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

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

5、將它轉(zhuǎn)換成與之等價(jià)的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序（目標(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)簡(jiǎn)單， 易于實(shí)現(xiàn)人機(jī)對(duì)話。缺點(diǎn)：效率低。解釋程序的優(yōu)缺點(diǎn)17編譯程序的分類診斷型編譯程序: 用于幫助程序開發(fā)和調(diào)試的編譯程序。優(yōu)化型編譯程序： 著重于提高目標(biāo)代碼效率的編譯程序。交叉型編譯程序可變目標(biāo)型編譯程序18編譯技術(shù)的發(fā)展第一個(gè)編譯程序出現(xiàn)在20世紀(jì)50年代早期，主要是將算術(shù)公式翻譯

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

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

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

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

10、、分程序入口表、中間代碼表等。 注：在編譯過(guò)程中，隨著源程序的不斷被改造，編譯的各階段常常需要不同的表格，編譯過(guò)程的絕大多數(shù)時(shí)間是花在查表、造表和更新表格的事務(wù)上。在大多數(shù)的編譯程序中，表格專門由表格管理程序來(lái)處理。293）出錯(cuò)處理 出錯(cuò)處理程序的任務(wù)包括檢查錯(cuò)誤、報(bào)告出錯(cuò)信息、排錯(cuò)、恢復(fù)編譯工作。錯(cuò)誤類型: 語(yǔ)法錯(cuò)誤:在詞法分析和語(yǔ)法分析階段檢測(cè) 出來(lái)。 語(yǔ)義錯(cuò)誤：一般在語(yǔ)義分析階段檢測(cè)。 30編譯程序的前端： 與源語(yǔ)言有關(guān)，而與目標(biāo)機(jī)無(wú)關(guān)的編譯程序編譯程序的后端： 與目標(biāo)機(jī)有關(guān)，而與源語(yǔ)言無(wú)關(guān)的編譯程序遍（趟）：是對(duì)源程序或源程序的中間結(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)境 編譯程序無(wú)疑是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。 在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。32圖1.2 Ada程序設(shè)計(jì)環(huán)境 331.5 編譯程序的生成1 常用的方法（根據(jù)語(yǔ)言來(lái)分）1）直接用機(jī)器語(yǔ)言編寫編譯程序2）用匯編語(yǔ)言編寫編譯程序注：編譯程序核心部分常用匯編語(yǔ)言編寫3）用高級(jí)語(yǔ)言編寫編譯程序注：這是普遍采用的方法2 常用的方法（根據(jù)實(shí)現(xiàn)途徑來(lái)分）1）自編譯2）編譯工具:LEX(詞法分析)與YACC(用于自動(dòng)產(chǎn)生LALR分析表)3）移植（同種語(yǔ)言的編譯程序在不同類型的機(jī)器之間移植