編譯原理第1章(劉磊 機械工業(yè)出版社)

1、課程說明課程性質(zhì)：專業(yè)方向課 必修 考試形式： 考查學(xué)時：48學(xué)時，理論：32學(xué)時，實驗 16學(xué)時成績評定方法： 上機：30分 出勤：20分 作業(yè)：20分 考試：30分第第1章章 編譯引論編譯引論 11 程序設(shè)計語言和編譯程序程序設(shè)計語言和編譯程序 12 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 13 編譯程序和程序設(shè)計環(huán)境編譯程序和程序設(shè)計環(huán)境 14 編譯程序的實現(xiàn)編譯程序的實現(xiàn) 11 程序設(shè)計語言和編譯程序程序設(shè)計語言和編譯程序程序設(shè)計語言的演變：程序設(shè)計語言的演變：（1）機器語言）機器語言（2）匯編語言）匯編語言（3）高級語言）高級語言13DE:0000 0E PUSH CS13DE:0001 1F

2、 POP DS13DE:0002 BA0E00 MOV DX,000E13DE:0005 B409 MOV AH,0913DE:0007 CD21 INT 2113DE:0009 B8014C MOV AX,4C0113DE:000C CD21 INT 21int main(int argc, char *argv) int a=100,b=200; a=a+b; couta bTOKEN 形式（單詞的內(nèi)部表示）。例子：源程序片段： main() float i1,i2,i3;i3=i1+i2*10;詞法分析的結(jié)果： 類型 值類型 值 類型 值 保留字 main 界符 （ 界符 ） 界符 保留

3、字 float 標(biāo)識符 i1 界符 ， 標(biāo)識符 i2 界符 ， 標(biāo)識符 i3 界符 ； 標(biāo)識符 i3 運算符 = 標(biāo)識符 i1 運算符 + 標(biāo)識符 i2 運算符 * 常數(shù) 10 界符 ； 界符 單詞的類別：保留字、界符、運算符、常數(shù)和標(biāo)識符。單詞的類別：保留字、界符、運算符、常數(shù)和標(biāo)識符。語法分析語法分析：是編譯過程的第二個階段。任務(wù)任務(wù)：是在詞法分析的基礎(chǔ)上將單詞分解成各類語法短語（語法單位，TOKEN序列），同時檢查程序中是否有錯。依據(jù)依據(jù)：語言的語法規(guī)則。通過語法分析確定整個輸入串是否構(gòu)成一個語法上的程序。 如 i3=i1+i2*10 為賦值表達式，語法構(gòu)成方式為（即語法樹）：賦值表達式

4、 標(biāo)識符=表達式 i3 表達式+ 表達式 標(biāo)識符 i1 標(biāo)識符* 常數(shù) i210語義分析階段語義分析階段：對語法分析所識別出的各類與反范疇，分析其含義，并檢查靜態(tài)語義錯誤，為代碼生成階段收集類型信息。如語義分析的一個工作是進行類型檢查，審查每個算符是否具有語言規(guī)范允許的運算對象，當(dāng)不符合語言規(guī)范時，編譯程序應(yīng)報告錯誤。如 i3=i1+i2*10 插入語義結(jié)點的樹為：=id3id1inttofloat+id2 10*中間代碼生成中間代碼生成：編譯程序?qū)⒃绦蜃兂梢环N內(nèi)部碼（稱為中間代碼）。優(yōu)點：優(yōu)點：便于移植、修改、優(yōu)化。設(shè)計原則設(shè)計原則：1.容易生成； 2.容易將它翻譯成目標(biāo)代碼常用的中間代碼

5、：常用的中間代碼：后綴式、三地址（三元、四元）、圖結(jié)構(gòu)（樹、DAG）一般形式為四元式一般形式為四元式： （運算符，運算對象1，運算對象2，結(jié)果）如 i3=i1+i2*10可生成的四元式序列：（1） （inttofloat 10 - t1) (2) (* id2 t1 t2) ( 3) ( + id1 t2 t3 ) (4) ( = t3 - id3) （* id2 10.0 t1) ( + id1 t1 id3)一般的優(yōu)化方法有一般的優(yōu)化方法有：1常量表達式優(yōu)化 2. 公共子表達式優(yōu)化 3削減運算強度 4不變表達式的循環(huán)外提等代碼優(yōu)化代碼優(yōu)化：對前一階段生成的中間代碼進行變換或進行改造。目的目

6、的：使生成的代碼更為高效，即省時間和空間。如上述的中間代碼優(yōu)化為：目標(biāo)代碼生成目標(biāo)代碼生成：把目標(biāo)代碼變換成特定機器上的指令代碼或可重定位的指令代碼或匯編指令。如上述語句的匯編代碼為： mov al,id2 mov bl ,10 mul bl add ax, id1 mov id3,ax7表格管理表格管理 編譯過程中的建表、查表和填表。編譯過程中的建表、查表和填表。 8錯誤處理錯誤處理 如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，并把相如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，并把相關(guān)錯誤信息報告給用戶。關(guān)錯誤信息報告給用戶。 錯誤：詞法錯誤、語法錯誤、靜態(tài)語義錯誤、動態(tài)語義錯誤：詞法錯誤、語法

7、錯誤、靜態(tài)語義錯誤、動態(tài)語義錯誤。錯誤。22 遍遍 “遍遍(Pass)”：對源程序或源程序的中間表示形式從頭：對源程序或源程序的中間表示形式從頭到尾掃描一次，并做加工處理，生成新的中間結(jié)果或目標(biāo)到尾掃描一次，并做加工處理，生成新的中間結(jié)果或目標(biāo)程序。程序。源程序前端中間代碼后端目標(biāo)代碼與具體的語言有關(guān)與具體的機器有關(guān)1編譯程序的前端和后端編譯程序的前端和后端3 編譯程序和程序設(shè)計環(huán)境編譯程序和程序設(shè)計環(huán)境編澤程序同如下程序一起構(gòu)成程序設(shè)計環(huán)境。編澤程序同如下程序一起構(gòu)成程序設(shè)計環(huán)境。1編輯器編輯器(Editer)2預(yù)處理器預(yù)處理器Preprocessor)3連接程序連接程序(Linker)4裝

8、入程序裝入程序(Loader)5調(diào)試程序調(diào)試程序(Debugger)4 編譯程序的實現(xiàn)編譯程序的實現(xiàn) 要實現(xiàn)一個編譯程序，通常需要做到：要實現(xiàn)一個編譯程序，通常需要做到： （1）對源語言的語法和語義要有準確無誤的理解。）對源語言的語法和語義要有準確無誤的理解。 （2）對目標(biāo)語言和編譯技術(shù)也要有很好的了解。）對目標(biāo)語言和編譯技術(shù)也要有很好的了解。 （3）確定對編譯程序的要求。）確定對編譯程序的要求。 （4）根據(jù)編譯程序的規(guī)模，確定編譯程序的掃描次數(shù)、每）根據(jù)編譯程序的規(guī)模，確定編譯程序的掃描次數(shù)、每次掃描的具體任務(wù)和所要采用的技術(shù)。次掃描的具體任務(wù)和所要采用的技術(shù)。 （5）設(shè)計各遍掃描程序的算法

9、并加以實現(xiàn)。）設(shè)計各遍掃描程序的算法并加以實現(xiàn)。 一般開發(fā)編譯程序有如下幾種可能途徑：一般開發(fā)編譯程序有如下幾種可能途徑： 1轉(zhuǎn)換法轉(zhuǎn)換法(預(yù)處理法預(yù)處理法) 2移植法移植法3自展法：自展法： 1971年：PASCAL語言編譯程序用自展技術(shù)生成，影響重大。 4工具法工具法如如Bell實驗室推出的實驗室推出的LEX、 YACC至今還在廣泛使用。至今還在廣泛使用。自動生成法如自動生成法如YACC編譯程序的發(fā)展：編譯程序的發(fā)展：（）（） 20世紀世紀50年代早期：多數(shù)是將算術(shù)公式翻譯成機器代碼。年代早期：多數(shù)是將算術(shù)公式翻譯成機器代碼。（）（） 20世紀世紀50年代中期：高級語言出現(xiàn)，編譯技術(shù)的發(fā)展。年代中期：高級語言出現(xiàn)，編譯技術(shù)的發(fā)展。（）（）20世紀世紀50年代末期：研究編譯程序的自動生成工具。年代末期：研究編譯程序的自動生成工具。 如詞法分析程序的生成系統(tǒng)如詞法分析程序的生成系統(tǒng)LEX。（）（） 20