編譯原理(引論)

1、編譯原理陳曉明 電 話-mail：minny-先修課程高級程序設(shè)計語言計算機組成原理操作系統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法介紹的理論知識：形式語言和自動機理論、語法制導(dǎo)的定義和屬性文法、類型論、程序分析原理等強調(diào)形式描述技術(shù)和自動生成技術(shù)強調(diào)對編譯原理和技術(shù)的宏觀理解，不把注意力分散到枝節(jié)算法，不偏向于任何源語言或目標(biāo)機器課程特點編譯原理是理論性較強的課程 。概念多、內(nèi)容抽象。尤其是文法、形式語言及自動機的概念是計算機專業(yè)理論學(xué)習(xí)和研究的基礎(chǔ) 。教學(xué)目的編譯原理是一門非常好的課程Alfred V.Aho：編寫編譯器的原理和技術(shù)具有十分普遍的意義

2、，以至于在每個計算機科學(xué)家的研究生涯中，本課程中的原理和技術(shù)都會反復(fù)用到本課程將兼顧語言的描述方法、設(shè)計與應(yīng)用(形式化)能形式化就能自動化（抽象符號化機械化）可以使學(xué)生對程序設(shè)計語言具有更加深刻的理解體驗實現(xiàn)自動計算的樂趣涉及的是一個比較適當(dāng)?shù)某橄髮用嫔系臄?shù)據(jù)變換（既抽象又實際，既有理論又有實踐）一個相當(dāng)規(guī)模的系統(tǒng)的設(shè)計總體結(jié)構(gòu)若干具體的表示和變換算法9/22/20225教學(xué)目的(續(xù))在系統(tǒng)級上認(rèn)識算法、系統(tǒng)的設(shè)計具有把握系統(tǒng)的能力局部最優(yōu)vs.全局最優(yōu)(木桶效用)“自頂向下”和“自底向上”的系統(tǒng)設(shè)計方法對其思想、方法、實現(xiàn)的全方位討論進(jìn)一步培養(yǎng)“計算思維能力”深入理解軟件系統(tǒng)的非物理性質(zhì)培養(yǎng)

3、抽象思維能力和邏輯思維能力訓(xùn)練對復(fù)雜數(shù)據(jù)結(jié)構(gòu)的設(shè)計和操縱能力9/22/20226教學(xué)目的(續(xù))計算機專業(yè)最為恰當(dāng)、有效的知識載體之一綜合運用下列課程所學(xué)知識高級程序設(shè)計語言匯編語言集合論與圖論數(shù)據(jù)結(jié)構(gòu)與算法計算機組成原理算法設(shè)計與分析形式語言與自動機9/22/202279/22/20228教學(xué)要求課程要求知識要求掌握編譯程序的總體結(jié)構(gòu)、編譯程序各個組成部分的任務(wù)、編譯過程各個階段的工作原理 、編譯過程各個階段所要解決的問題及其采用的方法和技術(shù) 能力要求掌握程序變換基本概念、問題描述和處理方法 增強理論結(jié)合實際能力探索“問題、形式化描述、計算機化” 的問題求解過程 使學(xué)生在系統(tǒng)級上認(rèn)識算法和系統(tǒng)

4、的設(shè)計，培養(yǎng)系統(tǒng)能力教學(xué)要求實驗要求實驗形式分析、設(shè)計、編寫、調(diào)試、測試程序撰寫實驗報告答辯實驗內(nèi)容詞法分析器的設(shè)計與實現(xiàn)語法分析器的設(shè)計與實現(xiàn)語義分析與中間代碼生成9/22/20229教學(xué)要求實驗?zāi)康膶嶒炟灤┯诶碚摗⒊橄蠛驮O(shè)計過程；實驗對軟件的設(shè)計和實現(xiàn)、測試原理和方法起示范作用；實驗不僅僅是對理論的驗證，重要的是技術(shù)訓(xùn)練和能力培養(yǎng)，包括動手能力、分析問題解決問題能力、表達(dá)能力、寫作能力等的培養(yǎng)；實驗可以彌補課堂教學(xué)的不足，加深對理論過程的理解，啟發(fā)學(xué)生深入思考，敢于創(chuàng)新，達(dá)到良好的理論聯(lián)系實際的教學(xué)效果。9/22/202210教學(xué)要求考試要求題型選擇、填空、計算、綜合等重點和難點會在各章的

5、開始點明考試權(quán)重出勤占5%作業(yè)占15%期末考試占80%考前答疑9/22/202211教學(xué)方法圍繞一條主線展開編譯過程的各個階段面向系統(tǒng)從系統(tǒng)的角度，引導(dǎo)大家逐步建立系統(tǒng)觀和工程觀，并學(xué)會折衷啟發(fā)式問題驅(qū)動，引導(dǎo)大家理解問題和方法的直觀背景以學(xué)生為中心，注重課堂交互，鼓勵大家多發(fā)問面向應(yīng)用引導(dǎo)大家了解技術(shù)、方法的應(yīng)用背景注重實踐以編寫一個小型語言編譯器為目標(biāo)9/22/2022129/22/202213教材及主要參考書目蔣宗禮，姜守旭. 編譯原理. 北京：高等教育出版社，2010年2月 Alfred Aho ect.，Compilers: Principles, Techniques, and T

6、ools，北京：人民郵電出版社，Pearson Education出版集團，2002.2. Alfred Aho ect.，Compilers: Principles, Techniques, and Tools(Second Edition)，北京：人民郵電出版社，Pearson Education出版集團，2008.2. 9/22/202214Alfred V. Aho Alfred V. Aho博士是哥倫比亞大學(xué)的勞倫斯科斯曼計算機科學(xué)教授，于普林斯頓大學(xué)獲得博士學(xué)位，IEEE、ACM Fellow，美國科學(xué)與藝術(shù)學(xué)院及國家工程學(xué)院院士，曾獲得IEEE的馮諾伊曼獎?！褒垥钡牡谝蛔髡?，A

7、WK的發(fā)明者之一。他目前的研究方向為量子計算、程序設(shè)計語言、編譯器和算法等。他還贏得了2003年大學(xué)畢業(yè)生社群的最佳教師獎 參考網(wǎng)站濟南大學(xué)信息學(xué)院精品課程：/byyl/國防科技大學(xué)精品課程：http:/cp/index.php西安電子科技大學(xué)計算機學(xué)院精品課程：/jp/index.asp主要內(nèi)容第1章 引論第2章 高級語言及其文法第3章 詞法分析第4章 自頂向下語法分析第5章 自底向上語法分析第6章 語法制導(dǎo)翻譯與屬性文法第7章 語義分析與中間代碼生成第9章 運行時的存儲組織第11章 代碼生成第一章 引論要點：本章通過簡要介紹編譯程序的各個邏輯階段，對全書的內(nèi)容進(jìn)行簡要概述。本章出現(xiàn)的大部分

8、概念在以后各章會詳細(xì)介紹，因此不要求在學(xué)習(xí)本章時就都能理解這些概念。主要掌握以下兩點： 1、基本概念：源語言、目標(biāo)語言、翻譯程序、編譯程序、解釋程序。 2、編譯程序的各個邏輯階段及各階段的主要功能。9/22/202218第1章 引論1.1 程序設(shè)計語言1.2 程序設(shè)計語言的翻譯1.3 編譯程序的總體結(jié)構(gòu)1.4 編譯程序的組織1.5 編譯程序的生成第一章 引論概念功能設(shè)計結(jié)構(gòu)設(shè)計建檔詳細(xì)設(shè)計編輯輸入輸出執(zhí)行鏈接編譯調(diào)試需求分析修改一般編程過程編輯輸入1.2 程序設(shè)計語言的翻譯1.2 程序設(shè)計語言的翻譯翻譯程序(Translator)將某種語言描述的程序(源程序Source Program)翻譯成

9、等價的另一種語言描述的程序(目標(biāo)程序Object Program)的程序。翻譯程序源程序目標(biāo)程序(*.C / *.PAS)(*.OBJ / *.EXE)9/22/202221編譯程序與解釋程序編譯器（編譯程序）：如果源語言是某種高級語言，而目標(biāo)語言是某種低級語言（匯編語言或機器語言），這樣的一個翻譯程序就稱為編譯程序。解釋器（解釋程序）：這是另外一種類型的翻譯程序，在翻譯過程中它按照高級語言源程序在計算機上執(zhí)行的動態(tài)順序?qū)υ闯绦虻恼Z句逐條翻譯（解釋），邊解釋邊執(zhí)行直至結(jié)束，它不產(chǎn)生目標(biāo)程序，它的工作結(jié)果就是源程序的執(zhí)行結(jié)果，這樣的一個翻譯程序就稱為解釋程序。（口譯與筆譯）（單句提交與整篇提交）

10、編譯程序與解釋程序例5 假設(shè)有源程序：read(x); write(x=, x);編譯程序與解釋程序特點：1編譯器：工作效率高，即時間快、空間??；交互性與動態(tài)特性差、可移植性差。大多數(shù)PL采用此種方法翻譯；2解釋器：工作效率低，即時間慢、空間費；交互性與動態(tài)特性好、可移植性好。早期的Basic和現(xiàn)在的Java等?；竟δ埽憾呦嗤凰捎玫募夹g(shù)：從翻譯的角度來講，兩種方式所涉及的原理、方法、技術(shù)相似。9/22/2022251.2 程序設(shè)計語言的翻譯SPCompilerS-SourceO-ObjectOPP-ProgramInputRS RS-Run Sys. Output編譯系統(tǒng)(Compil

11、ing System)編譯系統(tǒng)=編譯程序+運行系統(tǒng)支撐環(huán)境、運行庫等9/22/2022261.2 程序設(shè)計語言的翻譯其它翻譯程序：匯編程序(Assembler)交叉匯編程序(Cross Assembler)反匯編程序（Disassembler)交叉編譯程序（Cross Compiler)反編譯程序（Decompiler）可變目標(biāo)編譯程序（Retargetable Compiler)并行編譯程序（Parallelizing Compiler）診斷編譯程序（Diagnostic Compiler)優(yōu)化編譯程序（Optimizing Compiler)9/22/2022271.2 程序設(shè)計語言的翻譯

12、匯總解釋程序數(shù)據(jù)結(jié)果編譯系統(tǒng)機器語言程序機器語言程序機器語言程序匯編語言程序高級語言程序匯編語言程序匯編語言程序高級語言程序高級語言程序匯編程序反匯編程序編譯程序反編譯程序匯編程序反匯編程序編譯程序反編譯程序匯編程序編譯程序交叉匯編程序交叉編譯程序可變目標(biāo)編譯程序圖1.5 主要翻譯程序匯總運行系統(tǒng)編譯程序的發(fā)展 20世紀(jì)50年代早期出現(xiàn)編譯技術(shù)。 50年代中期隨著高級語言的出現(xiàn)，相應(yīng)的編譯系統(tǒng)開發(fā)成功。 50年代末期出現(xiàn)編譯程序自動生成工具。 60年代起利用自展技術(shù)構(gòu)造編譯程序。 70年代開始并行編譯技術(shù)得到深入研究，同時面向?qū)ο笳Z言、函數(shù)式語言的編譯技術(shù)得到研究。9/22/2022291.3

13、 編譯程序總體結(jié)構(gòu)目標(biāo)代碼生成器代碼優(yōu)化器語義分析與中間代碼生成器語法分析器表 格 管 理出 錯 處 理中間代碼中間代碼目標(biāo)代碼語法單位單詞符號詞法分析器源程序編譯的階段把英文翻譯為中文 識別出句子中的一個個單詞；分析句子的語法結(jié)構(gòu)；根據(jù)句子的含義進(jìn)行初步翻譯；對譯文進(jìn)行修飾；寫出最后的譯文。 詞法分析語法分析中間代碼產(chǎn)生優(yōu)化目標(biāo)代碼產(chǎn)生1、詞法分析任務(wù): 輸入源程序，對構(gòu)成源程序的字符串進(jìn)行從左到右的掃描和分解，識別出一個個單詞符號（記號token）。依循的原則：構(gòu)詞規(guī)則描述工具：正規(guī)式和有限自動機輸出：(種別碼，屬性值)序?qū)傩灾祎oken的機內(nèi)表示對不符合詞法規(guī)則的非法字符串作相應(yīng)的詞法

14、出錯處理。同時還要進(jìn)行標(biāo)識符登記符號表管理。9/22/2022321、詞法分析例：sum=(10+20)*(num+square); 結(jié)果(標(biāo)識符，sum)(賦值號，=)(左括號， ( )(整常數(shù)，10)(加號，+ )(整常數(shù)，20)(右括號， ) )(乘號，* )(左括號， ( )(標(biāo)識符，num)(加號，+ )(標(biāo)識符，square)(右括號， ) )(分號，; )2、語法分析任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位。如程序、語句、表達(dá)式等。（組詞成句）依循的原則：語法規(guī)則描述工具：上下文無關(guān)文法通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序，對不

15、符合語法規(guī)則的單詞序列作相應(yīng)的語法出錯處理。詞法分析是一種線性分析，而語法分析是一種層次結(jié)構(gòu)分析。 9/22/2022342、語法分析sum=(10+20)*(num+square);3、語義分析任務(wù)：審查源程序有無語義錯誤，為代碼生成收集類型信息（類型檢查）。一般和語法分析同時進(jìn)行，稱為語法制導(dǎo)翻譯(syntax-directed translation)依循的原則：語義規(guī)則語義分析的一個重要部分是類型檢查，編譯器檢查每個算符的運算對象，看它們的類型是否適當(dāng)。如：實數(shù)作為數(shù)組下標(biāo)，報錯；整數(shù)和實數(shù)進(jìn)行運算時，將整數(shù)轉(zhuǎn)變?yōu)閷崝?shù)。4、中間代碼生成任務(wù)：在語義分析的同時將源程序變換成一種內(nèi)部表示形

16、式（中間代碼）。 “翻譯”僅僅在這里才開始涉及到。中間代碼：一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)。原則： 簡單規(guī)范與機器無關(guān)易于優(yōu)化與轉(zhuǎn)換9/22/2022374、中間代碼生成例:sum=(10+20)*(num+square); 后綴表示(逆波蘭Anti- Polish Notation) sum 10 20 + num square +*=前綴表示(波蘭Polish Notation) = sum *+10 20+num square 四元式表示(三地址碼)(+，10，20，T1)(+，num，square，T2)(*， T1， T2， T3)(=， T3 ， ， sum) 三元式表示(+，1

17、0，20)(+，num，square)(*，)(=， sum，) 語法樹5、代碼優(yōu)化任務(wù)：對于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。依循的原則：程序的等價變換規(guī)則優(yōu)化的主要方面有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等等。6、代碼生成任務(wù): 把中間代碼變換成特定機器上的目標(biāo)代碼。特點：與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調(diào)度等。 目標(biāo)代碼三種形式:絕對指令代碼: 可直接運行 可重定位指令代碼: 需要連接裝配（多數(shù)）匯編指令代碼: 需要進(jìn)行匯編7、符號表管理符號表：

18、用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。例如，一個名字是常量名、變量名，還是過程名等等；若是變量名，它的類型、所占內(nèi)存、地址等等。通常，編譯程序在處理到名字的定義性出現(xiàn)時，要把名字的各種屬性填入到符號表中；當(dāng)處理到名字的使用性出現(xiàn)時，要對名字的屬性進(jìn)行查證。當(dāng)掃描器識別出一個名字（標(biāo)識符）后，它把該名字填入到符號表中。但這時不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填入。例如，名字的類型等要在語義分析時才能確定，而名字的地址可能要到目標(biāo)代碼生成才能確定?！皵?shù)據(jù)結(jié)構(gòu)與算法”課程的應(yīng)用8、錯誤處理出錯處理程序：發(fā)現(xiàn)源程序中的錯誤，把有關(guān)錯誤信息報告給用戶。語法錯誤語義錯誤好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源程序中的各種錯誤，準(zhǔn)確地指出錯誤的性質(zhì)和發(fā)生錯誤的地點，并且能將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以便進(jìn)一步發(fā)現(xiàn)其它可能的錯誤。9/22/202242語句sum=(10+20)*(num+square);的翻譯過程9/22/2022431.4 編譯程序的組織根據(jù)系統(tǒng)資源的狀況、運行目標(biāo)的要求等，可以