1、編譯原理II電子教案第一章第一章 緒論緒論謝強(qiáng)謝強(qiáng)計算機(jī)科學(xué)與技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院QQ:7878414上一頁下一頁2課程簡介課程簡介 編譯原理II是一門理論與實踐緊密結(jié)合的計算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課，是我們信息安全專業(yè)的專業(yè)選修課。編譯器的編寫涉及到程序設(shè)計語言、計算機(jī)體系結(jié)構(gòu)、語言理論、算法和軟件工程等學(xué)科，是計算機(jī)科學(xué)技術(shù)的重要基礎(chǔ)。另外，編譯原理課程中蘊(yùn)涵著許多計算機(jī)學(xué)科中解決問題的思路、抽象問題和解決問題的方法，這對計算機(jī)科學(xué)技術(shù)專業(yè)的學(xué)生今后學(xué)習(xí)其它專業(yè)課程和從事科研工作非常重要。課程主要介紹程序設(shè)計語言編譯程序構(gòu)造的一般原理、基本設(shè)計方法和主要實現(xiàn)技術(shù)。課程內(nèi)容主要包括：編

2、譯過程和編譯程序的結(jié)構(gòu)，文法的構(gòu)造，有限自動機(jī)、正規(guī)表達(dá)式和正規(guī)文法的等價性，消除文法的左遞歸和回溯，預(yù)測分析表的構(gòu)造，LR分析表的構(gòu)造，屬性的計算，翻譯模式的構(gòu)造、主要語句的的翻譯，運(yùn)行時存儲空間的分配，基于DAG的局部優(yōu)化，循環(huán)優(yōu)化等。上一頁下一頁3前修課程、能力和知識結(jié)構(gòu)要求前修課程、能力和知識結(jié)構(gòu)要求 本課程的先修課程包括：離散數(shù)學(xué)(1)，離散數(shù)學(xué)(2),計算機(jī)科學(xué)導(dǎo)論，程序設(shè)計語言(1)，程序設(shè)計語言(2)，數(shù)據(jù)結(jié)構(gòu)等，學(xué)生通過上述課程的學(xué)習(xí)需要熟悉計算機(jī)的基本結(jié)構(gòu)，具有分析問題和進(jìn)行形式化思維的能力，掌握高級程序設(shè)計語言和數(shù)據(jù)結(jié)構(gòu)。上一頁下一頁4課程結(jié)構(gòu)說明課程結(jié)構(gòu)說明 課程內(nèi)容分

3、為四大部分：詞法分析、語法分析、語義分析及中間代碼的產(chǎn)生、優(yōu)化。主要內(nèi)容包括為：文法、有限自動機(jī)、詞法分析、LL(1)分析、算符優(yōu)先分析、LR分析、屬性文法及語法制導(dǎo)的翻譯、中間語言及高級語言主要語句的翻譯、運(yùn)行時存儲空間的組織、中間代碼的優(yōu)化等。課程主要以課堂教學(xué)為主，動手實踐為輔，其中詞法分析和語法分析分別安排上機(jī)實驗。上一頁下一頁5課程考核形式與要求課程考核形式與要求 課程考核采用閉卷考試方法，考核成績由平時成績+上機(jī)+考試組成，其中平時成績包括考勤、上課情況和作業(yè)情況，分?jǐn)?shù)可以以平時成績（20%）+上機(jī)（10%）+考試（70%），可以根據(jù)實際情況略做調(diào)整。重點在于考查學(xué)生對主要知識的理

4、解和靈活應(yīng)用，試題中一般不會出現(xiàn)識記題?？荚嚨闹攸c在于詞法分析、語法分析（自上而下、自下而上），知識單元分?jǐn)?shù)分配大致為：緒論5%，文法15%，詞法分析20%，語法分析30%，語義分析15%，存儲空間的組織5%，優(yōu)化10%。上一頁下一頁6學(xué)習(xí)編譯原理的重要作用學(xué)習(xí)編譯原理的重要作用 通過本課程的學(xué)習(xí)，使學(xué)生掌握和理解編譯系統(tǒng)的結(jié)構(gòu)、工作流程以及編譯程序各組成部分的設(shè)計原理和實現(xiàn)技術(shù)，獲得分析、設(shè)計、實現(xiàn)和維護(hù)編譯系統(tǒng)的初步能力； 通過學(xué)習(xí)編譯的理論和方法，提高學(xué)生對程序設(shè)計語言、操作系統(tǒng)、計算機(jī)原理和體系結(jié)構(gòu)等課程知識的綜合理解。對于將來從事編譯系統(tǒng)設(shè)計工作的學(xué)生來說，編譯原理課程將為其打下堅實

5、的能力和知識基礎(chǔ)； 編譯原理蘊(yùn)涵著抽象問題、解決問題的思路、方法和技術(shù)，對學(xué)生今后的學(xué)習(xí)和研究有很重要的作用。 編譯程序是計算機(jī)系統(tǒng)中的系統(tǒng)軟件，包含許多軟件設(shè)計和開發(fā)技術(shù)，為學(xué)生提供了一個大型軟件設(shè)計的參考。 課程介紹的經(jīng)典的語言分析方法和工具，對于設(shè)計一些實用的工具和軟件，如自然語言理解、網(wǎng)絡(luò)信息處理、網(wǎng)絡(luò)協(xié)議的分析與實現(xiàn)等，都是必備的基礎(chǔ)。此外，學(xué)習(xí)這門課程有利于對程序設(shè)計語言的理解，有利于迅速掌握新的語言工具。上一頁下一頁7參考書參考書1 Alfred V.Aho，Monica S.Lam，Ravi Sethi，等著， 趙建華，鄭滔，等 譯，編譯原理（第二版），機(jī)械工業(yè)出版社，2009

6、.1 （龍書）（龍書）2 （美）安佩爾，（美）金斯伯格 著，趙克佳，黃春，沈志宇 譯，現(xiàn)代編譯原理-C語言描述，人民郵電出版社，2006.4 （虎書）（虎書）3 （美）Steven S.Muchnick著，趙克佳，沈志宇譯，高級編譯器設(shè)計與實現(xiàn)，機(jī)械工業(yè)出版社，2005.7 （鯨書）（鯨書）4 Kenneth C. Louden 著，馮博琴 馮嵐 等譯，編譯原理及實踐（Compiler Construction Principles and Practice），機(jī)械工業(yè)出版社，2000.3上一頁下一頁8本章的主要內(nèi)容本章的主要內(nèi)容 什么是編譯程序 編譯程序的邏輯結(jié)構(gòu) 編譯程序各階段的工作 編譯

7、程序的組織上一頁下一頁9本章要求本章要求 清楚編譯程序的總框架，了解編譯程序工作的大致過程，能分辨清楚編譯前端與后端的區(qū)別及其相互配合的方法，要清楚編譯程序是如何生成的。請大家記憶并理解以下概念： 編譯程序，解釋程序，翻譯程序，目標(biāo)機(jī)、源語言、目標(biāo)語言、編譯程序?qū)崿F(xiàn)語言、掃描器，分析器，編譯前端與后端，符號表，“遍”的概念等。上一頁下一頁10本章教學(xué)線索本章教學(xué)線索1 編譯程序的概念及功能編譯程序的概念及功能 1.1 為什么要用編譯器 1.2 翻譯程序 1.3 編譯程序 1.4 編譯程序與解釋程序 1.5 編譯器的發(fā)展階段2 編譯程序的邏輯結(jié)構(gòu)及過程概述編譯程序的邏輯結(jié)構(gòu)及過程概述3 編譯程序

8、（器）的組織編譯程序（器）的組織4 編譯程序的生成編譯程序的生成上一頁下一頁111.1 為什么要用編譯器為什么要用編譯器機(jī)器語言：C7 06 0000 0002 匯編語言：匯編語言：MOV X, 2 高級語言：高級語言：x = 2 上一頁下一頁12階乘的C語言實現(xiàn)算法描述，求某整數(shù)n的階乘fact(n), n0 1 / n = 0 fact(n) = n * fact( n-1 ) / n! = n * (n-1)!. 偽語言描述fact(n) = if n 0 then 1 else n*fact(n-1). 高級程序設(shè)計語言描述，（如C語言）int fact( int n )if (n=

9、0) return 1;else return ( n*fact(n-1);上一頁下一頁13c 程序 foo.cAnsi C compiler ccObject fileLinker/連接程序a.out/可執(zhí)行程序庫函數(shù)或其它object文件編譯和執(zhí)行過程a.out/可執(zhí)行程序loader/裝入程序計算機(jī)輸入數(shù)據(jù)計算結(jié)果上一頁下一頁141.2 翻譯程序翻譯程序翻譯程序（器）翻譯程序（器）：接受某種語言的源語言程序后，將它改造成另一種邏輯上等價邏輯上等價的目標(biāo)語言程序。 匯編程序：匯編程序：源語言為匯編語言，目標(biāo)語言為機(jī)器語言的翻譯程序。 編譯程序（器）：編譯程序（器）：源語言為高級語言，目標(biāo)語

10、言是低級語言（匯編或機(jī)器語言）的翻譯程序。 上一頁下一頁151.3 編譯程序編譯程序把高級語言程序翻譯成等價的低級語言程序編譯程序目標(biāo)程序編譯系統(tǒng)：編譯程序和運(yùn)行程序源語言程序編譯程序編譯程序：就是能夠把某種語言程序（稱為：源語言程序）轉(zhuǎn)換成另一種語言程序（稱為：目標(biāo)語言程序）的程序，而后者與前者在邏輯上是等價的。源語言：源語言：一般指某種高級語言，易于理解和掌握。目標(biāo)語言：目標(biāo)語言：匯編語言、機(jī)器語言等宿主機(jī)：宿主機(jī)：運(yùn)行編譯程序的計算機(jī)目標(biāo)機(jī)：目標(biāo)機(jī)：運(yùn)行編譯程序產(chǎn)生目標(biāo)代碼的計算機(jī) 。編譯程序?qū)崿F(xiàn)語言：編譯程序?qū)崿F(xiàn)語言：用于生成編譯程序的語言。C、Java、C#、Fortran、Ada、

11、Pascal上一頁下一頁161.4 編譯程序與解釋程序編譯程序與解釋程序 高級語言程序高級語言程序也可通過解釋程序來執(zhí)行 解釋程序：以源程序為輸入，在執(zhí)行過程中不再產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行。 解釋程序運(yùn)行效率不高，空間開銷大。 目前，純粹的解釋程序已不多見，通常是將編譯和解釋作某種程度的結(jié)合。 編譯程序是現(xiàn)今任何計算機(jī)系統(tǒng)的最重要的系統(tǒng)程序。 本課程的目的，在于向大家介紹設(shè)計和構(gòu)造編譯程序的基本原理和基本方法，其中許多方法也適用于構(gòu)造解釋程序或匯編程序。上一頁下一頁171.5 編譯器的發(fā)展階段編譯器的發(fā)展階段Fortran編譯器的開發(fā)Chomsky文法19541957 IBM 的 Joh

12、n BackusNoam Chomsky分析問題（詞法分析、語法分析、語義分析）6070年代代碼優(yōu)化編譯器的自動構(gòu)造70年代后期80年代早期編譯器本身算法的發(fā)展IDE80年代以后1975 Yacc:Steve Johnson Lex：Mike Lesk并行編譯技術(shù)上一頁下一頁18本章教學(xué)線索本章教學(xué)線索1 編譯程序的概念及功能編譯程序的概念及功能2 編譯程序的邏輯結(jié)構(gòu)及過程概述編譯程序的邏輯結(jié)構(gòu)及過程概述 2.1編譯程序的結(jié)構(gòu) 2.2編譯程序的主要過程 2.3表格和表格管理 2.4出錯處理3 編譯程序（器）的組織編譯程序（器）的組織4 編譯程序的生成編譯程序的生成上一頁下一頁192.1 編譯程

13、序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)詞法分析器詞法分析器語法分析器語法分析器語義分析與中間代碼產(chǎn)生器語義分析與中間代碼產(chǎn)生器優(yōu)化器優(yōu)化器目標(biāo)代碼生成器目標(biāo)代碼生成器源程序源程序目標(biāo)代碼目標(biāo)代碼表表格格處處理理出出錯錯處處理理單詞符號單詞符號語法單位語法單位中間代碼中間代碼中間代碼中間代碼編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu) 上一頁下一頁202.2 編譯程序的主要過程編譯程序的主要過程第一階段：詞法分析（第一階段：詞法分析（lexical analysis or scanning） 詞法分析的任務(wù)：輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個一個的單詞。如：基本字、標(biāo)識符、常數(shù)、算符和界符（標(biāo)點

14、符號、括號、分號等）。基本字又稱為保留字，界符又稱為分隔符。 詞法分析階段遵循詞法規(guī)則。上一頁下一頁21例1-1：PROGRAM m; VAR a,b,c:real; BEGIN a:=b+c*60; END. 例2-2 for I:= 1 to 100 do 上一頁下一頁22第二階段：語法分析（第二階段：語法分析（syntax analysis or parsing） 語法分析的任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位（語法范疇），如“短語”、“子句”、“句子”和“程序”等。通過語法分析，確定整個輸入串是否構(gòu)成語法上正確的“程序”。語法分析遵循語法規(guī)則，常

15、用的語法規(guī)則用上下文無關(guān)文法描述。 注意：1.詞法分析是一種線性分析，而語法分析是一種層次結(jié)構(gòu)的分析。 2.有的編譯程序在識別出各類語法單位后，構(gòu)造并輸出一棵表示語法結(jié)構(gòu)的語法樹。上一頁下一頁23比如：A = B+C*60其中 B+C*60代表一個“算術(shù)表達(dá)式”，因此，語法分析就是要識別B+C *60為算術(shù)表達(dá)式，并且識別上述整個符號串為賦值語句這個范疇。賦值語句賦值語句變量變量A=表達(dá)式表達(dá)式表達(dá)式表達(dá)式項項因子因子B+項項項項*因子因子C因子因子60賦值語句賦值語句 A = B+C*60的語法分析樹的語法分析樹上一頁下一頁24 這一階段的任務(wù)：對語法分析所識別出的各類語法范疇分析其含義，并

16、進(jìn)行初步翻譯，產(chǎn)生中間代碼。包括兩方面的工作： 靜態(tài)語義檢查。 中間代碼的翻譯。這一階段所依循的是語言的語義規(guī)則語義規(guī)則。 第三階段第三階段 語義分析和中間代碼的產(chǎn)生語義分析和中間代碼的產(chǎn)生 semantic analysis and intermediate code generation上一頁下一頁25 中間代碼：是一種含義明確、便于處理的記號系統(tǒng)，它通常獨立于具體硬件。常見的記號系統(tǒng)有：四元式、三元式、間接三元式、逆波蘭式、樹形表示等。四元式：算符算符左操作數(shù)左操作數(shù)右操作數(shù)右操作數(shù)結(jié)果結(jié)果例子：A = B + C*60 四元式表示 NO算符左操作數(shù)右操作數(shù)結(jié)果（1）*C60T1（2）+

17、BT1T2（3）=T2A 例子：A = B + C*60 四元式表示上一頁下一頁26樹形表示（抽象語法樹）： 樹形表示（抽象語法樹）： =AB*C 60+生成中間代碼：temp1 =C * 60temp2 =B +temp1A =temp2上一頁下一頁27第四階段第四階段 優(yōu)化（優(yōu)化（code optimization） 優(yōu)化階段的任務(wù)：對前一階段產(chǎn)生的中間代碼進(jìn)行加工交換，以期在最后階段能夠產(chǎn)生出運(yùn)行效率更高的（省時間和空間）的目標(biāo)代碼。優(yōu)化的主要方法有：公共子表達(dá)式的提取、強(qiáng)度削弱、刪除無用代碼等。 for K:= 1 to 100 do begin M := I + 10*K ; N :

18、= J + 10*K ;endM := IN := Jfor K:= 1 to 100 do begin M :=M + 10 ;N := N + 10;end優(yōu)化上一頁下一頁28第五階段第五階段 目標(biāo)代碼的生成目標(biāo)代碼的生成 code generation 這一階段的任務(wù)：把中間代碼（或經(jīng)過優(yōu)化處理之后）變換成特定機(jī)器上的低級語言代碼。目標(biāo)代碼的形式： 絕對指令代碼 可重定位的指令代碼 匯編代碼A := B + C * 60.0的匯編指令： LD R0,60.0 MUL R0,C ADD R0,B ST R0,A上一頁下一頁29using System;namespace ConsoleAp

19、plication1 class Program static void Main(string args) int i = 0; int j = 1; i = i + j; Console.WriteLine(i is: 0,i); .method private hidebysig static void Main(string args) cil managed .entrypoint / 代碼大小 27 (0 x1b) .maxstack 2 .locals init (int32 V_0, int32 V_1) IL_0000: nop IL_0001: ldc.i4.0 IL_00

20、02: stloc.0 IL_0003: ldc.i4.1 IL_0004: stloc.1 IL_0005: ldloc.0 IL_0006: ldloc.1 IL_0007: add IL_0008: stloc.0 IL_0009: ldstr i is: 0 IL_000e: ldloc.0 IL_000f: box mscorlibSystem.Int32 IL_0014: call void mscorlibSystem.Console:WriteLine(string, object) IL_0019: nop IL_001a: ret / end of method Progr

21、am:Main上一頁下一頁302.3 表格和表格管理表格和表格管理 符號表：用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。一般符號表包括：名字欄和信息欄。 當(dāng)掃描器識別出一個名字（標(biāo)志符）后，它把該名字填入到符號表中。名字的各種屬性需要在后續(xù)的各個階段填入。上一頁下一頁312.4 出錯處理出錯處理 編譯程序在各個階段應(yīng)診斷和報告源程序中的錯誤，包括詞法錯誤，語法錯誤，語義錯誤等。編譯程序應(yīng)報告出錯地點，并給出簡明準(zhǔn)確的提示信息。 比如詞法分析階段能夠檢測出“非法字符”之類的錯誤；語法分析階段能夠檢測出諸如“括號不匹配”、“缺少；”之類的錯誤。語義錯誤包括：說明錯誤、作用域錯誤、類型不一致等

22、。上一頁下一頁32本章教學(xué)線索本章教學(xué)線索1 編譯程序的概念及功能編譯程序的概念及功能2 編譯程序的邏輯結(jié)構(gòu)及過程概述編譯程序的邏輯結(jié)構(gòu)及過程概述3 編譯程序（器）的組織編譯程序（器）的組織 3.1 前端與后端 3.2 遍（PASS)（趟） 3.3 分析與綜合4 編譯程序的生成編譯程序的生成上一頁下一頁333.1 前端與后端前端與后端前端：主要與源語言有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分，一般包括：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生等；后端：包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。后端不依賴于源程序而僅僅依賴于中間語言。 源程序前端后端目標(biāo)代碼中間代碼僅

23、僅依賴于源程序僅僅依賴于目標(biāo)計算機(jī)源程序1源程序2源程序3源程序n前端后端目標(biāo)代碼1目標(biāo)代碼2目標(biāo)代碼3目標(biāo)代碼n中間代碼上一頁下一頁343.2 遍（遍（PASS）（趟）（趟） 對輸入文件（源程序或其等價的中間形式）從頭到尾掃描，完成預(yù)定的處理，生成新的中間結(jié)果或目標(biāo)程序。 using System;namespace ConsoleApplication1 class Program static void Main(string args) int i = 0; int j = 1; i = i + j; Console.WriteLine(i is: 0,i); 一遍一遍上一頁下一頁35

24、3.3 分析與綜合分析與綜合 將分析源程序以計算其特性的編譯器操作歸為編譯器的分析部分，而將生成翻譯代碼時所涉及到的操作歸為編譯器的綜合部分。分析：詞法分析、語法分析、語義分析綜合：中間代碼的產(chǎn)生、優(yōu)化、目標(biāo)代碼的產(chǎn)生 目前：分析正趨向于易懂和更具數(shù)學(xué)性，而綜合則要求 更深的專業(yè)技術(shù)。詞法分析語法分析語義分析中間代碼產(chǎn)生代碼優(yōu)化代碼生成源程序源程序目標(biāo)程序目標(biāo)程序符號表管理出錯管理上一頁下一頁36本章教學(xué)線索本章教學(xué)線索1 編譯程序的概念及功能編譯程序的概念及功能2 編譯程序的邏輯結(jié)構(gòu)及過程概述編譯程序的邏輯結(jié)構(gòu)及過程概述3 編譯程序（器）的組織編譯程序（器）的組織4 編譯程序的生成編譯程序的

25、生成 4.1 T形圖 4.2 編譯程序的自展 4.3 已知一種語言的編譯器，構(gòu)造另一種語言的編譯器 4.4 編譯程序的移植 4.5 具有代表意義的自動化編譯工具 4.6 .NET的公共語言運(yùn)行環(huán)境上一頁下一頁374.1 T形圖形圖 T形圖 L1語言要在A機(jī)器上運(yùn)行，需要生成的目標(biāo)代碼為A的機(jī)器代碼，如果我們用A的機(jī)器代碼來實現(xiàn)L1語言的編譯系統(tǒng)，可以表示為： L1 AA原始編譯器S T I源語言目標(biāo)機(jī)機(jī)器語言編譯程序?qū)崿F(xiàn)語言T形圖上一頁下一頁384.2 編譯程序的自展編譯程序的自展目標(biāo)：在機(jī)器A（目標(biāo)機(jī)）上，用語言A（實現(xiàn)語言）構(gòu)造高級語言L（源語言）的編譯程序。L A AStep1:可以考慮

26、源語言L的子集語言S, S L。在機(jī)器A（目標(biāo)語言）上，用語言A（實現(xiàn)語言）構(gòu)造語言S的編譯程序。Step2: 在機(jī)器A上，用語言S（實現(xiàn)語言）構(gòu)造語言L的編譯程序。L A SL A SS A AL A AS A AStep3:上一頁下一頁394.3 已知一種語言的編譯器，構(gòu)造另已知一種語言的編譯器，構(gòu)造另一種語言的編譯器一種語言的編譯器有另一種語言L2語言，我們可以用L1語言編寫L2語言的編譯程序，這樣L2語言經(jīng)編譯后可以生成在A機(jī)器上運(yùn)行目標(biāo)程序?？梢员硎緸椋?L2 A L1L1 AAL2 AA上一頁下一頁404.4 編譯程序的移植編譯程序的移植 利用A機(jī)器上已有的高級語言L編寫一個在B機(jī)器上運(yùn)行的高級語言L的編譯程序。 分析：B機(jī)器上運(yùn)行的L的編譯程序P，就是將L語言編寫的源程序經(jīng)過P編譯后，產(chǎn)生為B機(jī)器代碼的目標(biāo)代碼。P的作用就是產(chǎn)生L語言的B機(jī)器代碼。P是B機(jī)器代碼構(gòu)成。 做法：先用L語言編寫能夠在A