編譯原理第一章編譯原理引論

編譯原理第一章編譯原理引論課程簡(jiǎn)介課程內(nèi)容介紹編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法理論知識(shí)：形式語言和自動(dòng)機(jī)理論、語法制導(dǎo)的定義和屬性文法、類型論等強(qiáng)調(diào)形式化描述技術(shù)強(qiáng)調(diào)對(duì)編譯原理和技術(shù)的宏觀理解，不把注意力分散到枝節(jié)算法，不偏向于某種源語言或目標(biāo)機(jī)器課程簡(jiǎn)介課程意義對(duì)編程語言的設(shè)計(jì)和實(shí)現(xiàn)有深刻的理解，對(duì)宏觀把握編程語言來說，起一個(gè)奠基的作用。從軟件工程看，編譯器是一個(gè)很好的實(shí)例，所介紹的概念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。大多數(shù)程序員同時(shí)是簡(jiǎn)單語言的設(shè)計(jì)者，有助于提高對(duì)這些語言的設(shè)計(jì)水平。在軟件逆向工程、程序理解和軟件安全等方面有著廣泛的應(yīng)用。課程簡(jiǎn)介教材：教材名稱：編譯原理主編：陳意云張昱出版社：高等教育出版社主要參考資料《程序設(shè)計(jì)語言編譯原理（第3版）》，國(guó)防工業(yè)出版社，陳火旺等編著《編譯原理》，清華大學(xué)出版社，呂映芝、張素琴、蔣維杜編著A.Aho,R.Sethi,andJ.D.Ullman,Compilers:Principles,Techniques,andTools,2ndedition,Addison-Wesley,1986陳意云、張昱，編譯原理習(xí)題精選，中國(guó)科大出版社，2002教學(xué)資源網(wǎng)頁：/~yiyun課程簡(jiǎn)介課程要求目標(biāo)：師生共同努力，掌握編譯器的基本原理和技術(shù)講課進(jìn)展較快，平時(shí)要及時(shí)復(fù)習(xí)加深理解，否則后面將聽不懂作業(yè)要求獨(dú)立完成上機(jī)實(shí)驗(yàn)，不要輕視考試閉卷，學(xué)期總評(píng)=考試成績(jī)占70%，作業(yè)占15%，上機(jī)實(shí)驗(yàn)15%課程教學(xué)內(nèi)容及時(shí)間安排編譯原理概論-------------------2課時(shí)詞法分析-----------------------6課時(shí)文法及其描述-------------------2課時(shí)自頂向下語法分析方法-----------4課時(shí)自底向上語法分析法-------------8課時(shí)語法制導(dǎo)翻譯-------------------6課時(shí)類型檢查-----------------------2課時(shí)運(yùn)行時(shí)空間組織----------------2課時(shí)中間代碼生成-------------------4課時(shí)代碼生成-----------------------4課時(shí)代碼優(yōu)化-----------------------4課時(shí)第一章編譯原理引論內(nèi)容提要編譯器構(gòu)造法的研究目的編譯器的結(jié)構(gòu)編譯的基本原則編譯器應(yīng)有的性質(zhì)編譯器技術(shù)的應(yīng)用關(guān)于學(xué)習(xí)編譯原理編譯器構(gòu)造法的研究目的什么是編譯程序編譯程序高級(jí)程序設(shè)計(jì)語言書寫的程序低級(jí)語言程序術(shù)語源語言(程序)目標(biāo)語言(程序)實(shí)現(xiàn)語言STI源語言程序目標(biāo)語言程序翻譯程序翻譯翻譯程序把某一種語言程序(稱為源語言程序)等價(jià)地轉(zhuǎn)換成另一種語言程序(稱為目標(biāo)語言程序)的程序編譯器構(gòu)造法的研究目的什么是編譯程序?高級(jí)語言程序機(jī)器語言程序結(jié)果編譯程序翻譯運(yùn)行什么是編譯程序?編譯程序(compiler)

把某一種高級(jí)語言程序等價(jià)地轉(zhuǎn)換成另一種低級(jí)語言程序(如匯編語言或機(jī)器語言程序)的程序診斷編譯程序 優(yōu)化編譯程序交叉編譯程序 可變目標(biāo)編譯程序什么是編譯程序?解釋程序把源語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身源程序結(jié)果解釋程序解釋執(zhí)行編譯程序vs.解釋程序編譯解釋什么叫編譯程序?編譯程序:是指這樣的程序，它能夠把某種語言的程序轉(zhuǎn)換成另一種語言的程序，而后者與前者在邏輯上是等價(jià)的。如果源語言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級(jí)語言”，而目標(biāo)語言如匯編語言之類的“低級(jí)語言”這樣的翻譯程序則稱之為編譯程序。內(nèi)容提要編譯器構(gòu)造法的研究目的編譯器的結(jié)構(gòu)編譯的基本原則編譯器應(yīng)有的性質(zhì)編譯器技術(shù)的應(yīng)用關(guān)于學(xué)習(xí)編譯原理編譯過程把英文翻譯為中文識(shí)別出句子中的一個(gè)個(gè)單詞；分析句子的語法結(jié)構(gòu)；根據(jù)句子的含義進(jìn)行初步翻譯；對(duì)譯文進(jìn)行修飾；寫出最后的譯文。編譯過程詞法分析器語法分析器語義分析器源程序中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理器符號(hào)表管理器1.詞法分析詞法分析也叫線性分析和掃描。從左到右讀構(gòu)成源程序的字符流，分組為多個(gè)記號(hào)。詞法分析器position=initial+rate*60id1=id2+id3*60符號(hào)表

positioninitialrate.........1232.語法分析任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號(hào)串分解成各類語法單位。依循的原則：語法規(guī)則描述工具：上下文無關(guān)文法語法分析（續(xù)）語法分析器id1=id2+id3*60id1id3id2=+*60在本例中，算符優(yōu)先級(jí)可以通過如下方法定義：1.定義程序語言的語法規(guī)則體現(xiàn)算符的優(yōu)先級(jí)2.通過某些規(guī)則庫，例如算符優(yōu)先級(jí)表格等來定義算符的優(yōu)先級(jí)符號(hào)表

positioninitialrate.........1233.語義分析語義分析這一階段通常包括兩方面的工作，首先對(duì)各種語法范疇進(jìn)行靜態(tài)語義檢查，如果正確則進(jìn)行另一方面的工作，即進(jìn)行中間代碼的翻譯。通常使用屬性文法描述語義規(guī)則。

語義分析（續(xù)）語義分析器id1id3id2=+*60id1id3id2=+*inttoreal60在本例中，幾個(gè)標(biāo)識(shí)符都是實(shí)數(shù)類型，而且源程序語言允許整數(shù)向?qū)崝?shù)類型的強(qiáng)制轉(zhuǎn)換編譯過程詞法分析器語法分析器語義分析器源程序中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理符號(hào)表管理前三個(gè)階段完成對(duì)源程序的分析4.中間代碼生成符號(hào)表

positioninitialrate.........123中間代碼生成器temp1=inttoreal(60)temp2=id3*temp1temp3=id2+temp2id1=temp3=+*60id1id2id3inttoreal5.代碼優(yōu)化符號(hào)表

positioninitialrate.........123代碼優(yōu)化器temp1=inttoreal(60)temp2=id3*temp1temp3=id2+temp2id1=temp3temp1=id3*60.0id1=id2+temp1任務(wù)：對(duì)于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。依循的原則：程序的等價(jià)變換規(guī)則6.目標(biāo)代碼產(chǎn)生任務(wù):把中間代碼變換成特定機(jī)器上的目標(biāo)代碼。依賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義目標(biāo)代碼三種形式:絕對(duì)指令代碼:可直接運(yùn)行可重新定位指令代碼:連接裝配，匯編指令代碼:需要進(jìn)行匯編符號(hào)表

positioninitialrate.........123temp1=id3*60.0id1=id2+temp1代碼生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1編譯過程詞法分析器語法分析器語義分析器源程序中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理器符號(hào)表管理器

后三個(gè)階段對(duì)源程序進(jìn)行綜合編譯過程詞法分析器語法分析器語義分析器源程序中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理符號(hào)表管理后三個(gè)階段對(duì)源程序進(jìn)行綜合編譯前端與后端前端(frontend)主要由與源語言有關(guān)，但與目標(biāo)機(jī)無關(guān)的那些部分組成。通常包括詞法分析、語法分析、語義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作，也可以包括在前端。后端(backend)包括編譯程序中與目標(biāo)代碼有關(guān)的部分，如與目標(biāo)機(jī)有關(guān)的有關(guān)的優(yōu)化，和目標(biāo)代碼的生成等。源語言中間語言目標(biāo)語言前端后端編譯器的應(yīng)用模型出錯(cuò)處理語法分析程序語義分析程序目標(biāo)代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理編譯的前端（FrontEnd）編譯的后端（BackEnd）編譯器的構(gòu)造工具編譯程序自動(dòng)產(chǎn)生編譯程序-編譯程序，編譯程序書寫系統(tǒng)LEX詞法分析程序產(chǎn)生器YACC語法分析程序產(chǎn)生器編譯程序自動(dòng)產(chǎn)生器L語言的語法描述語義描述目標(biāo)語言或機(jī)器描述L語言的編譯程序內(nèi)容提要編譯器構(gòu)造法的研究目的編譯器的結(jié)構(gòu)編譯器的基本原則編譯器應(yīng)有的性質(zhì)編譯器技術(shù)的應(yīng)用關(guān)于學(xué)習(xí)編譯原理編譯器技術(shù)的應(yīng)用

高級(jí)語言的實(shí)現(xiàn)高級(jí)編程語言易于編程，但程序運(yùn)行較慢低級(jí)語言編程時(shí)可實(shí)施更有效的控制方式，得到更有效的代碼，但難編寫、易出錯(cuò)、難維護(hù)流行編程語言的大多數(shù)演變都是朝著提高抽象級(jí)別的方向每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究編譯器技術(shù)的應(yīng)用

高級(jí)語言的實(shí)現(xiàn) 每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究支持用戶定義的聚合數(shù)據(jù)類型和高級(jí)控制流，如數(shù)組和記錄、循環(huán)和過程調(diào)用：C、Fortran面向?qū)ο蟮闹饕拍钍菙?shù)據(jù)抽象和性質(zhì)繼承，使得程序更加模塊化并易于維護(hù)：Smalltalk、C++、C#、Java類型安全的語言：Java沒有指針，也不允許指針?biāo)阈g(shù)。它用無用單元收集機(jī)制來自動(dòng)地釋放那些不再使用的變量占據(jù)的內(nèi)存Java設(shè)計(jì)來支持代碼移植和代碼移動(dòng)編譯器技術(shù)的應(yīng)用

針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化計(jì)算機(jī)體系結(jié)構(gòu)的迅速演化引起對(duì)新的編譯器技術(shù)一種不知足的需要并行化

編譯器重新整理指令，使得指令級(jí)并行更有效

編譯器從傳統(tǒng)的串行程序自動(dòng)生成并行代碼，使之運(yùn)行于多處理器上內(nèi)存分層

編譯器優(yōu)化歷來集中在優(yōu)化處理器的執(zhí)行上，但是現(xiàn)在更強(qiáng)調(diào)要使內(nèi)存分層更有效編譯器技術(shù)的應(yīng)用

新計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)現(xiàn)在計(jì)算機(jī)系統(tǒng)的性能不僅僅取決于它的原始速度，還取決于編譯器是否能生成充分利用其特征的代碼在現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的研究中，在處理器的設(shè)計(jì)階段就開發(fā)編譯器，并將編譯生成的代碼在模擬器上運(yùn)行，以評(píng)價(jià)擬采用體系結(jié)構(gòu)的特征編譯器技術(shù)影響計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)著名例子是精簡(jiǎn)指令集計(jì)算機(jī)（RISC）的發(fā)明編譯器技術(shù)的應(yīng)用

程序翻譯二進(jìn)制翻譯

編譯器技術(shù)可用于把一種機(jī)器的二進(jìn)制代碼翻譯成另一種機(jī)器的代碼，以運(yùn)行原先為別的指令集編譯的代碼數(shù)據(jù)庫查詢解釋器

數(shù)據(jù)庫查詢由一些謂詞組成，這些謂詞由包含關(guān)系運(yùn)算的布爾表達(dá)式組成，可以被解釋執(zhí)行,也可以被編譯成搜索數(shù)據(jù)庫的命令編譯器技術(shù)的應(yīng)用

提高軟件開發(fā)效率的工具 源于編譯器中代碼優(yōu)化技術(shù)的程序分析一直在改進(jìn)軟件開發(fā)效率類型檢查

類型檢查是一種捕捉程序中前后不一致的成熟并且有效的技術(shù)邊界檢查

數(shù)據(jù)流分析技術(shù)