1、編譯原理,計算機(jī)與信息工程學(xué)院 軟件工程教研室 何岸,第一章 引論 2,本課程的地位,是軟件技術(shù)基礎(chǔ) 是計算機(jī)專業(yè)的學(xué)生必修的一門主干專業(yè)課,第一章 引論 3,學(xué)習(xí)要求,成績考核方法 平時成績占30% 期末考試成績占70%。 平時成績?yōu)椋?課堂點(diǎn)名15% 作業(yè)15% 我的聯(lián)系方式： E-Mail：,第一章 引論 4,第一章 引論1.1程序設(shè)計語言,1)程序設(shè)計語言 高級語言 匯編語言 機(jī)器語言 在計算機(jī)上如何執(zhí)行一個高級語言程序？ 把高級語言程序翻譯成機(jī)器語言程序 運(yùn)行所得的機(jī)器語言程序求得計算結(jié)果,第一章 引論 5,程 序 設(shè) 計 語 言,機(jī)器語言,機(jī)器指令（0，1）,匯編語言,機(jī)器指令（符

2、號）,高級語言,Pascal、 c 、c+,002 0123 取出a 00E 1234 除以b 009 2103 減去c 004 0576 送c,CLA a 取出a DIV b 除以b SUB c 減去c STO c 送c,X=a/b-c,什么叫編譯程序,高級程序設(shè)計語言,機(jī)器語言,目標(biāo)程序,源程序,編譯程序,編譯程序：將高級語言程序根據(jù)其語法和語義翻譯成與之等價的機(jī)器能夠接受的機(jī)器語言程序的程序。 編譯技術(shù)：介紹如何設(shè)計和構(gòu)造編譯程序，也即討論編譯程序構(gòu)造的一般方法技術(shù)等。 編譯原理：是討論編譯程序設(shè)計的基本理論、基本概念、基本方法。,第一章 引論 6,翻譯程序 匯編程序：源語言為匯編語言，

3、目標(biāo)語言為 機(jī)器語言 編譯程序：源語言為高級語言，目標(biāo)語言為 sx 某臺計算機(jī)上的匯編語言或機(jī)器語言 解釋程序：能夠按源程序的動態(tài)順序逐句進(jìn)行分 d 析解釋，根據(jù)語句功能翻譯成與該語 d 句相應(yīng)的機(jī)器指令序列，并立即執(zhí) s 行，直至結(jié)束,1.2 編譯程序,翻 譯 程 序,第一章 引論 7,1.3 源程序執(zhí)行的途徑（編譯途徑、解釋途徑）,編譯的轉(zhuǎn)換過程 兩階段轉(zhuǎn)換：編譯運(yùn)行,編譯途徑即是將一份源程序從頭至尾翻譯成某臺計算機(jī)上的機(jī)器語言表示的目標(biāo)程序，然后執(zhí)行該目標(biāo)程序得到運(yùn)行結(jié)果，并允許重復(fù)執(zhí)行若干次。,第一章 引論 8,編譯的轉(zhuǎn)換過程 三個階段的轉(zhuǎn)換：編譯匯編運(yùn)行,1.3 源程序執(zhí)行的途徑（編

4、譯途徑、解釋途徑）,第一章 引論 9,1.3 源程序執(zhí)行的途徑（編譯途徑、解釋途徑）,解釋途徑即是對于源程序的一個語句，把它翻譯成相應(yīng)的機(jī)器語言，并讓計算機(jī)立即執(zhí)行。如果需要數(shù)據(jù)時，則提示用戶輸入初始數(shù)據(jù)，并立即進(jìn)行處理。解釋途徑就是邊解釋邊執(zhí)行，直至源程序動態(tài)處理完畢為止。 當(dāng)用高級語言編寫的源程序輸入計算機(jī)后，鍵入運(yùn)行程序命令，則解釋程序就對源程序逐條翻譯，翻譯一條立即執(zhí)行一條。該途徑不產(chǎn)生目標(biāo)代碼程序，故占用內(nèi)存較少，但執(zhí)行速度要慢些。,第一章 引論 10,1.4 編譯程序的結(jié)構(gòu),編譯程序的工作 先看自然語言的翻譯 1.識別出句子中的一個個單詞 2.分析句子的語法結(jié)構(gòu) 3.根據(jù)句子的含義

5、進(jìn)行初步翻譯 4.對譯文進(jìn)行修飾 5.寫出最后譯文,第一章 引論 11,編譯程序的工作,詞法分析器,語法分析器,語義分析器,中間代碼生成,優(yōu)化,目標(biāo)代碼生成,源程序,目標(biāo)代碼,表格管理,出錯處理,第一章 引論 12,1.詞法分析,任務(wù) 輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的單詞極其有關(guān)屬性，并轉(zhuǎn)換成屬性字。 單詞 是高級語言中有實(shí)在意義的最小語法單位，它由字符構(gòu)成。 屬性字 指單詞的一種機(jī)內(nèi)表示,第一章 引論 13,識別右邊程序中的單詞,基本字： 標(biāo)識符 常數(shù) : 運(yùn)算符 : 界限符:,Void jisuan() float r, s,c; s=3.14*r*r; c=

6、2*3.14*r; ,Void , float,r, s, c, jisuan,3.14 ， 2,*,=, ; , ( ),第一章 引論 14,2.語法分析,任務(wù)： 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，逐一分析詞法分析時得到的屬性字，檢查語法錯誤，若沒有錯誤，則給出正確的語法結(jié)構(gòu)（如短語、子句、句子、程序段、程序等）。 語法規(guī)則： 語言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語、語句、過程和程序。,c=2*3.14*r,賦值語句,第一章 引論 15,3.語義分析,任務(wù) 對語法分析識別出的各類語法范疇，分析其含義，進(jìn)行和初步翻譯，產(chǎn)生介于源代碼和目標(biāo)代碼之間的一種代碼。 分為兩階段工作 對每種

7、語法范疇進(jìn)行靜態(tài)語義檢查 若語義正確，就進(jìn)行中間代碼的翻譯 中間代碼形式 四元式、三元式、逆波蘭式,第一章 引論 16,“翻譯”工作僅僅在這里才開始涉及到。,“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號 系統(tǒng)。這種記號系統(tǒng)或者與現(xiàn)代計算機(jī)的指令形式 有某種程度的接近，或者能夠比較容易地把它變換 成現(xiàn)代計算機(jī)的機(jī)器指令。,常用的中間代碼如：三元式、四元式、逆波蘭式,第一章 引論 17,例如,x = 2 * a + b,三元式 (*,2,a) (2) (+,(1),b) (3) (=,(2),x),四元式 (*,2,a,t1) (2) (+,t1,b,t2) (3) (=,t2,/,x),依循規(guī)則：

8、語義規(guī)則,第一章 引論 18,如上述源程序經(jīng)語義分析得到下列中間代碼程序,Void jisuan() float r, s,c; s=3.14*r*r; c=2*3.14*r; ,（1） （*，3.14，r） （2） （*，（1），r） （3） （：=，（2），s） （4） （*，2，3.14） （5） （*，（4），r） （6） （：=，（5），c）,第一章 引論 19,如上述源程序經(jīng)代碼優(yōu)化得到下列中間代碼程序,Void jisuan() float r, s,c; s=3.14*r*r; c=2*3.14*r; ,（1） （*，3.14，r） （2） （*，（1），r） （3） （：=，

9、（2），s） （4） （*，2，（1） （5） （ ：=， （4），c）,（1） （*，3.14，r） （2） （*，（1），r） （3） （：=，（2），s） （4） （*，2，3.14） （5） （*，（4），r） （6） （：=，（5），c）,第一章 引論 20,4.優(yōu)化,任務(wù) 對前面產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生更為高效的目標(biāo)代碼。 原則：等價變換 主要方面 公共子表達(dá)式的提取、合并已知量、刪除無用語句、循環(huán)優(yōu)化等。,第一章 引論 21,5.目標(biāo)代碼生成,任務(wù) 把經(jīng)過優(yōu)化的中間代碼轉(zhuǎn)化成特定機(jī)器上的低級語言代碼 目標(biāo)代碼的形式 絕對指令代碼:可立即執(zhí)行的目標(biāo)代碼。 匯

10、編指令代碼：匯編語言程序，需要通過匯編程序匯編后才能運(yùn)行。 可重定位指令代碼：先將各目標(biāo)模塊連接起來，確定變量、常數(shù)在主存中的位置，裝入主存后才能成為可以運(yùn)行的絕對指令代碼。,第一章 引論 22,編譯程序的工作,詞法分析器,語法分析器,語義分析器,中間代碼生成,優(yōu)化,目標(biāo)代碼生成,源程序,目標(biāo)代碼,表格管理,出錯處理,第一章 引論 23,6.表格與表格管理,表格作用： 用來記錄源程序的各種信息以及編譯過程中的各種狀況。 與編譯前三階段有關(guān)的表格有： 符號表、常數(shù)表、標(biāo)號表、分程序入口表、中間代碼表等。,第一章 引論 24,1）符號表,符號表：用來登記源程序中的常量名、變量名、數(shù)組名、過程名等，

11、記錄它們的性質(zhì)、定義和引用情況。,第一章 引論 25,2）常數(shù)表與標(biāo)號表,常數(shù)表,（登記各類常量值） （登記標(biāo)號的定義與應(yīng)用）,標(biāo)號表,第一章 引論 26,3）入口名表,作用：登記過程的層號，分程序符號表入口等,第一章 引論 27,4）中間代碼表,第一章 引論 28,7.出錯處理,任務(wù) 如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，并報告給用戶。 完成：由專門的出錯處理程序來完成 錯誤類型: 語法錯誤:在詞法分析和語法分析階段檢測出來。 語義錯誤：一般在語義分析階段檢測。,第一章 引論 29,8、編譯程序的趟 趟 指一個編譯程序在編譯時把源程序或與之等價的中間程序從頭到尾掃描一遍，并轉(zhuǎn)換成為緊密相

12、鄰的等價的程序的全過程。 單趟掃描：五個階段結(jié)合在一起對源程序從頭到尾 掃描一遍生成目標(biāo)程序。 優(yōu)點(diǎn)：速度快、效率高 缺點(diǎn)：編譯程序復(fù)雜、占用存儲空間大 多趟掃描：五個階段單獨(dú)成趟掃描。 優(yōu)點(diǎn)：編譯程序簡單且易于分工。 缺點(diǎn)：各趟的工作有些要重復(fù)進(jìn)行、效率較低,第一章 引論 30,語法分析,掃描器,語義子程序,源程序,目標(biāo)代碼,編譯程序,取單詞,類號內(nèi)碼,一遍掃描（以語法分析為中心）,歸約,返回,第一章 引論 31,1.5 編譯程序構(gòu)造,要在某機(jī)器上為某種語言構(gòu)造一個編譯程序，必須掌握下面的內(nèi)容： ： 1、源語言：語法、語義。 2、目標(biāo)語言：對于機(jī)器指令，搞清硬件的系統(tǒng)結(jié)構(gòu)和OS的功能。 3、編譯方法：必須掌握一二種。 4、語言選擇：編制程序。,第一章 引論 32,編譯程序的設(shè)計與實(shí)現(xiàn)還要根據(jù)環(huán)境的不同可能有各種不同目標(biāo)，例如： 目標(biāo)程序效率高 目標(biāo)程序短 編譯的時間短