編譯原理和技術(shù)

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

,2ndedition,Addison-Wesley,2007

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

ActuallyIthinkthequalityofthecompilercourseinUSTCisreallyverygoodandcanbecomparedwithanyuniversitieshere.

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

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

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

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

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

=

id,2

+

id,3

60position=initial+rate

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

e1+e2e1

*

e2(e1)也都是表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識符表達(dá)式表達(dá)式(initial)標(biāo)識符(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ū)別詞法分析器語法分析器語義分析器源程序中間代碼生成器獨(dú)立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼解釋器不生成目標(biāo)代碼，而是直接執(zhí)行源程序所指定的運(yùn)算

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

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

高級語言的實(shí)現(xiàn) 每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究支持用戶定義的聚合數(shù)據(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)1.2編譯器技術(shù)的應(yīng)用

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

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

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

編譯器優(yōu)化歷來集中在優(yōu)化處理器的執(zhí)行上，但是現(xiàn)在更強(qiáng)調(diào)要使內(nèi)存分層更有效1.2編譯器技術(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)行，以評價(jià)擬采用體系結(jié)構(gòu)的特征編譯器技術(shù)影響計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)的一個(gè)著名例子是精簡指令集計(jì)算機(jī)（RISC）的發(fā)明1.2編譯器技術(shù)的應(yīng)用

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

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