編譯原理和技術

編譯原理和技術中國科學技術大學計算機科學與技術學院陳意iyun@課程簡介課程內(nèi)容介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法包括的理論知識：形式語言和自動機理論、語法制導的定義和屬性文法、類型論與類型系統(tǒng)、程序分析原理等強調(diào)形式描述技術和自動生成技術強調(diào)對編譯原理和技術的宏觀理解，不把注意力分散到枝節(jié)算法，不偏向于任何源語言或目標機器課程簡介學習意義對編程語言的設計和實現(xiàn)有深刻的理解，對和編程語言有關的理論有所了解，對宏觀上把握編程語言來說，起一個奠基的作用從軟件工程看，編譯器是一個很好的實例，所介紹的概念和技術能應用到一般的軟件設計之中編譯技術的應用和編譯技術的發(fā)展高級語言設計、計算機體系結(jié)構(gòu)的優(yōu)化（并行、內(nèi)存分層）、新型計算機體系結(jié)構(gòu)設計、程序翻譯、提高軟件開發(fā)效率的工具、高可信軟件課程簡介教材和參考書陳意云、張昱，編譯原理，高等教育出版社，2008張昱、陳意云，編譯原理實驗教程，高等教育出版社，2009A.V.Aho,M.S.Lam,R.Sethi,andJ.D.Ullman,Compilers:Principles,Techniques,andTools

,2ndedition,Addison-Wesley,2007

陳意云、張昱，編譯原理習題精選與解析，高等教育出版社，2005教學資源網(wǎng)頁：/~yiyun /~yuzhang/compiler課程簡介課程要求質(zhì)量上的目標：師生共同努力，達國內(nèi)最好水平講課進展較快，平時不復習并加深理解，后面將聽不懂作業(yè)：少而精，周一課間交作業(yè)課程設計：自己動手，大有收獲考試：開卷，靈活運用知識學期總評=考試成績占60%，作業(yè)占10%，課程設計30%上課、設計、考試時間大體安排課程簡介課程設計要求內(nèi)容：獨立地研發(fā)擴展PL/0語言的編譯器和解釋器目標：鞏固對理論和技術的理解，提高程序設計能力技術準備：VC++的編程環(huán)境，C語言編程考查與評分：對截止時間前提交的程序，通過測試和答辯進行公開評分前四年課程設計的經(jīng)驗和教訓對該課程設計的綜合性認識不足對考查的“動真格”認識不足對課程的評論本校少年班1994級一個同學，Stanford大學博士（1999年）

ActuallyIthinkthequalityofthecompilercourseinUSTCisreallyverygoodandcanbecomparedwithanyuniversitieshere.

本系某考研同學（2006年） 感覺您出的題目很有創(chuàng)意，也很有深度

，沒有局限于固定的算法和題型，只看課本和復習往年的題目而不深入思考的人是做不出來的，能夠真正從本質(zhì)上考察一個考生的水平對課程的評論西南科技大學某考研學生（2004年）

看過你編的書后，感覺編譯的原理可以一下子和我平常學的很多學科和語言都聯(lián)系起來了，可以學到很多可以實際用到的東西，雖然是在講同樣的東西，但您的教學方式讓我很適應，學起來也很有興趣，大大減輕了我考研的疲勞感第一章引論

名詞解釋翻譯器(translator)、編譯器(compiler)解釋器(interpreter)編譯器從邏輯上可以分成若干個階段每個階段把源程序從一種表示變換成另一種表示本章通過描述編譯器的各個階段來介紹編譯這個課題1.1編譯器概述詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機器的代碼優(yōu)化器代碼生成器依賴于機器的代碼優(yōu)化器目標機器代碼符號表符號表

positioninitialrate.........123詞法分析器id,1

=

id,2

+

id,3

60position=initial+rate

601.1編譯器概述記號流字符流1.1編譯器概述表達式的語法特征任何一個標識符都是表達式任何一個數(shù)都是表達式如果e1和e2都是表達式，那么

e1+e2e1

*

e2(e1)也都是表達式表達式表達式表達式標識符表達式表達式(initial)標識符(rate)數(shù)(60)*+initial+rate*60的分析樹符號表

positioninitialrate.........123語法分析器id,1

=

id,2

+

id,3

60=+60id,1id,2id,3語法樹1.1編譯器概述記號流符號表

positioninitialrate.........1231.1編譯器概述語義分析器=+60id,1id,2id,3=+inttofloatid,1id,2id,360語法樹語法樹符號表

positioninitialrate.........123中間代碼生成器t1=inttofloat(60)t2=id3t1t3=id2+t2id1=t3=+inttofloatid,1id,2id,3601.1編譯器概述三地址中間代碼語法樹符號表

positioninitialrate.........123代碼優(yōu)化器t1=inttofloat(60)t2=id3t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t11.1編譯器概述三地址中間代碼三地址中間代碼符號表

positioninitialrate.........123代碼生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t11.1編譯器概述三地址中間代碼匯編代碼1.1編譯器概述解釋器和編譯器的區(qū)別詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機器的代碼優(yōu)化器代碼生成器依賴于機器的代碼優(yōu)化器目標機器代碼解釋器不生成目標代碼，而是直接執(zhí)行源程序所指定的運算

解釋器也需要對源程序進行詞法、語法和語義分析,中間代碼生成1.1編譯器概述BASIC年代的解釋器功能：它將高級語言的源程序翻譯成一種中間語言程序，然后對中間語言程序進行解釋執(zhí)行在那個年代，編譯和解釋兩個功能是合在一個程序中，該程序被稱為解釋器Java年代的解釋器上述兩個功能分在兩個程序中前一個叫做編譯器，它把源程序翻譯成一種叫做字節(jié)碼的中間語言程序后一個叫做解釋器，它對字節(jié)碼程序進行解釋執(zhí)行1.1編譯器概述階段分組前端后端詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機器的代碼優(yōu)化器代碼生成器依賴于機器的代碼優(yōu)化器目標機器代碼1.1編譯器概述詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機器的代碼優(yōu)化器代碼生成器依賴于機器的代碼優(yōu)化器目標機器代碼階段分組遍1.2編譯器技術的應用

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

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

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

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

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

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

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

程序翻譯二進制翻譯

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