編譯原理第一章課件

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

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

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

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

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

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

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

8、（器）的組織編譯程序（器）的組織4 編譯程序的生成編譯程序的生成上一頁下一頁111.1 為什么要用編譯器為什么要用編譯器機器語言：C7 06 0000 0002 匯編語言：匯編語言：MOV X, 2 高級語言：高級語言：x = 2 上一頁下一頁12階乘的C語言實現算法描述，求某整數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). 高級程序設計語言描述，（如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í)行程序庫函數或其它object文件編譯和執(zhí)行過程a.out/可執(zhí)行程序loader/裝入程序計算機輸入數據計算結果上一頁下一頁141.2 翻譯程序翻譯程序翻譯程序（器）翻譯程序（器）：接受某種語言的源語言程序后，將它改造成另一種邏輯上等價邏輯上等價的目標語言程序。 匯編程序：匯編程序：源語言為匯編語言，目標語言為機器語言的翻譯程序。 編譯程序（器）：編譯程序（器）：源語言為高級語言，目標語

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

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

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

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

14、符號、括號、分號等）?；咀钟址Q為保留字，界符又稱為分隔符。 詞法分析階段遵循詞法規(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） 語法分析的任務：在詞法分析的基礎上，根據語言的語法規(guī)則，把單詞符號串分解成各類語法單位（語法范疇），如“短語”、“子句”、“句子”和“程序”等。通過語法分析，確定整個輸入串是否構成語法上正確的“程序”。語法分析遵循語法規(guī)則，常

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

16、進行初步翻譯，產生中間代碼。包括兩方面的工作： 靜態(tài)語義檢查。 中間代碼的翻譯。這一階段所依循的是語言的語義規(guī)則語義規(guī)則。 第三階段第三階段 語義分析和中間代碼的產生語義分析和中間代碼的產生 semantic analysis and intermediate code generation上一頁下一頁25 中間代碼：是一種含義明確、便于處理的記號系統(tǒng)，它通常獨立于具體硬件。常見的記號系統(tǒng)有：四元式、三元式、間接三元式、逆波蘭式、樹形表示等。四元式：算符算符左操作數左操作數右操作數右操作數結果結果例子：A = B + C*60 四元式表示 NO算符左操作數右操作數結果（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)化階段的任務：對前一階段產生的中間代碼進行加工交換，以期在最后階段能夠產生出運行效率更高的（省時間和空間）的目標代碼。優(yōu)化的主要方法有：公共子表達式的提取、強度削弱、刪除無用代碼等。 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第五階段第五階段 目標代碼的生成目標代碼的生成 code generation 這一階段的任務：把中間代碼（或經過優(yōu)化處理之后）變換成特定機器上的低級語言代碼。目標代碼的形式： 絕對指令代碼 可重定位的指令代碼 匯編代碼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 表格和表格管理表格和表格管理 符號表：用來登記源程序中出現的每個名字以及名字的各種屬性。一般符號表包括：名字欄和信息欄。 當掃描器識別出一個名字（標志符）后，它把該名字填入到符號表中。名字的各種屬性需要在后續(xù)的各個階段填入。上一頁下一頁312.4 出錯處理出錯處理 編譯程序在各個階段應診斷和報告源程序中的錯誤，包括詞法錯誤，語法錯誤，語義錯誤等。編譯程序應報告出錯地點，并給出簡明準確的提示信息。 比如詞法分析階段能夠檢測出“非法字符”之類的錯誤；語法分析階段能夠檢測出諸如“括號不匹配”、“缺少；”之類的錯誤。語義錯誤包括：說明錯誤、作用域錯誤、類型不一致等

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

23、僅依賴于源程序僅僅依賴于目標計算機源程序1源程序2源程序3源程序n前端后端目標代碼1目標代碼2目標代碼3目標代碼n中間代碼上一頁下一頁343.2 遍（遍（PASS）（趟）（趟） 對輸入文件（源程序或其等價的中間形式）從頭到尾掃描，完成預定的處理，生成新的中間結果或目標程序。 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 分析與綜合分析與綜合 將分析源程序以計算其特性的編譯器操作歸為編譯器的分析部分，而將生成翻譯代碼時所涉及到的操作歸為編譯器的綜合部分。分析：詞法分析、語法分析、語義分析綜合：中間代碼的產生、優(yōu)化、目標代碼的產生 目前：分析正趨向于易懂和更具數學性，而綜合則要求 更深的專業(yè)技術。詞法分析語法分析語義分析中間代碼產生代碼優(yōu)化代碼生成源程序源程序目標程序目標程序符號表管理出錯管理上一頁下一頁36本章教學線索本章教學線索1 編譯程序的概念及功能編譯程序的概念及功能2 編譯程序的邏輯結構及過程概述編譯程序的邏輯結構及過程概述3 編譯程序（器）的組織編譯程序（器）的組織4 編譯程序的生成編譯程序的

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

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