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

1、課程說(shuō)明課程性質(zhì)：專業(yè)方向課 必修 考試形式： 考查學(xué)時(shí)：48學(xué)時(shí)，理論：32學(xué)時(shí)，實(shí)驗(yàn) 16學(xué)時(shí)成績(jī)?cè)u(píng)定方法： 上機(jī)：30分 出勤：20分 作業(yè)：20分 考試：30分第第1章章 編譯引論編譯引論 11 程序設(shè)計(jì)語(yǔ)言和編譯程序程序設(shè)計(jì)語(yǔ)言和編譯程序 12 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 13 編譯程序和程序設(shè)計(jì)環(huán)境編譯程序和程序設(shè)計(jì)環(huán)境 14 編譯程序的實(shí)現(xiàn)編譯程序的實(shí)現(xiàn) 11 程序設(shè)計(jì)語(yǔ)言和編譯程序程序設(shè)計(jì)語(yǔ)言和編譯程序程序設(shè)計(jì)語(yǔ)言的演變：程序設(shè)計(jì)語(yǔ)言的演變：（1）機(jī)器語(yǔ)言）機(jī)器語(yǔ)言（2）匯編語(yǔ)言）匯編語(yǔ)言（3）高級(jí)語(yǔ)言）高級(jí)語(yǔ)言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)識(shí)符 i1 界符 ， 標(biāo)識(shí)符 i2 界符 ， 標(biāo)識(shí)符 i3 界符 ； 標(biāo)識(shí)符 i3 運(yùn)算符 = 標(biāo)識(shí)符 i1 運(yùn)算符 + 標(biāo)識(shí)符 i2 運(yùn)算符 * 常數(shù) 10 界符 ； 界符 單詞的類別：保留字、界符、運(yùn)算符、常數(shù)和標(biāo)識(shí)符。單詞的類別：保留字、界符、運(yùn)算符、常數(shù)和標(biāo)識(shí)符。語(yǔ)法分析語(yǔ)法分析：是編譯過(guò)程的第二個(gè)階段。任務(wù)任務(wù)：是在詞法分析的基礎(chǔ)上將單詞分解成各類語(yǔ)法短語(yǔ)（語(yǔ)法單位，TOKEN序列），同時(shí)檢查程序中是否有錯(cuò)。依據(jù)依據(jù)：語(yǔ)言的語(yǔ)法規(guī)則。通過(guò)語(yǔ)法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語(yǔ)法上的程序。 如 i3=i1+i2*10 為賦值表達(dá)式，語(yǔ)法構(gòu)成方式為（即語(yǔ)法樹(shù)）：賦值表達(dá)式

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

5、：常用的中間代碼：后綴式、三地址（三元、四元）、圖結(jié)構(gòu)（樹(shù)、DAG）一般形式為四元式一般形式為四元式： （運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象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常量表達(dá)式優(yōu)化 2. 公共子表達(dá)式優(yōu)化 3削減運(yùn)算強(qiáng)度 4不變表達(dá)式的循環(huán)外提等代碼優(yōu)化代碼優(yōu)化：對(duì)前一階段生成的中間代碼進(jìn)行變換或進(jìn)行改造。目的目

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

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

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

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