編譯原理教案(終稿)

1、PAGE 教 案2006-2007學年第 1 學期 課 程 名 稱： 編譯原理 課 程 編 號： 學院、專業(yè)、年級： 計算機科學與技術學院 任 課 教 師： 教 師 所 在 單 位： 計算機科學與技術學院 泰山學院編譯原理教案課程簡介編譯原理是計算機科學與技術專業(yè)的一門重要專業(yè)課程。該課程的目的是讓學生掌握程序設計語言編譯程序構造的一般原理、基本設計方法、主要實現(xiàn)技術和一些自動構造工具，從而讓學生了解將高級程序設計語言源程序翻譯成計算機能處理的目標代碼語言的整個過程。該課程是理論性很強的課程，對于計算機專業(yè)學生的進一步深造有較大的促進作用。同時，該課程還可以提高學生計算機的專業(yè)素質，培養(yǎng)他們的

2、軟件開發(fā)能力和抽象思維能力，為進一步深造打下基礎。課程主要內容有：詞法分析、自頂向下語法分析、自底向上語法分析、屬性文法和語法制導翻譯、存儲器管理、符號表的組織與管理、中間代碼優(yōu)化、代碼生成等內容。課程要求：了解編譯程序的構造技術；理解編譯原理的理論基礎即文法與形式語言概念；掌握各種詞法分析、語法分析、語法制導翻譯、代碼優(yōu)化、存儲管理的方法和技巧；具備一定的設計相關語法分析器的能力。該課程是計算機專業(yè)中較難得一門專業(yè)課，有如下四個重點，也是難點：（1）自動機理論 （2）語法分析（3）語法制導的翻譯（4）代碼優(yōu)化。編譯原理教案教學大綱編譯原理教學大綱課程名稱：編譯原理英文名稱：The Princ

3、iple of Compiler Design課程編號：課程類別：專業(yè)課學時數(shù)：80學時學分數(shù)：4先修課程：高級程序設計語言、數(shù)據(jù)結構、離散數(shù)學等適用年級：四年級適用專業(yè)：計算機科學與技術一、內容簡介該課程的研究對象是編譯程序構造的一般原理、基本設計方法、主要實現(xiàn)技術和一些自動構造工具，從而讓學生掌握將高級程序設計語言翻譯成計算機能處理的目標代碼語言的整個過程。該課程的主要內容為：詞法分析、自頂向下語法分析、自底向上語法分析、屬性文法和語法制導翻譯、存儲器管理、符號表的組織與管理、中間代碼優(yōu)化、代碼生成等內容。二、本課程的性質、目的和任務編譯原理是計算機科學與技術專業(yè)的一門重要專業(yè)課程，其研究

4、對象是編譯程序構造的一般原理、基本設計方法、主要實現(xiàn)技術和一些自動構造工具，從而讓學生掌握將高級程序設計語言翻譯成計算機能處理的目標代碼語言的整個過程。通過該課程的學習，使學生掌握編譯原理的基本理論和編譯程序的構造技術，為進一步學習和深造打下基礎。該課程的主要內容有：詞法分析、自頂向下語法分析、自底向上語法分析、屬性文法和語法制導翻譯、存儲器管理、符號表的組織與管理、中間代碼優(yōu)化、代碼生成等內容。通過各個教學環(huán)節(jié)，逐步培養(yǎng)學生的抽象思維能力、程序設計能力和自學能力，培養(yǎng)學生運用所學知識、獨立解決較復雜問題的能力。三、本課程與其它課程的關系 本課程是計算機科學與技術專業(yè)的重要專業(yè)課。其先行課有高

5、級程序設計語言、數(shù)據(jù)結構、離散數(shù)學、計算機系統(tǒng)結構、操作系統(tǒng)等。課程基礎性、理論性強，與相關課程的學習聯(lián)系密切，是計算機科學與技術專業(yè)學生進一步提高的基本課程。四、本課程的基本要求了解編譯程序的構造技術；理解編譯原理的理論基礎即文法與形式語言概念；掌握各種詞法分析、語法分析、語法制導翻譯、代碼優(yōu)化、存儲管理的方法和技巧；具備一定的設計相關語法分析器的能力。五、課程內容與學時分配（一）編譯原理概論 2學時1、教學內容：什么是編譯原理編譯過程概述編譯程序的結構編譯階段的組合編譯技術和軟件工具2、教學要求：了解：編譯技術和軟件工具。掌握：什么是編譯原理, 編譯程序的結構，編譯過程和六個階段的任務和組

6、合。 （二）PL/0編譯程序的實現(xiàn) 4學時1、教學內容：PL/0語言描述：PL/0語言的語法描述圖；PL/0語言文法的EBNF表示PL/0編譯程序的結構PL/0編譯程序的詞法分析PL/0編譯程序的語法分析PL/0編譯程序的目標代碼結構和代碼生成PL/0編譯程序的語法錯誤處理PL/0編譯程序的目標代碼解釋執(zhí)行時的存儲分配2、教學要求：了解：PL/0編譯程序的詞法分析、語法分析、目標代碼結構和代碼生成、語法錯誤處理及目標代碼解釋執(zhí)行時的存儲分配。掌握：PL/0語言的語法描述圖及文法的EBNF表示，PL/0編譯程序的結構。（三）文法和語言 4學時1、教學內容：文法的直觀概念符號和符號串文法和語言的形

7、式定義文法的類型上下文無關文法及其語法樹句型的分析：自上而下的分析方法；自下而上的分析方法；句型分析的有關問題有關文法實用中的一些說明：有關文法的實用限制；上下文無關文法中的規(guī)則2、教學要求：了解：文法的直觀概念，符號和符號串，上下文無關文法中的規(guī)則。掌握：文法和語言的形式定義。熟練掌握：文法的類型，上下文無關文法及其語法樹，句型的分析。（四）詞法分析 8學時1、教學內容：詞法分析程序的設計：詞法分析程序與語法分析程序的接口方式；詞法分析程序的輸出；將詞法分析工作分離的考慮單詞的描述工具：正規(guī)文法；正規(guī)式；正規(guī)文法到正規(guī)式有窮自動機：確定的有窮自動機（DFA）；不確定的有窮自動機（NFA）；D

8、FA NFA的轉換；確定有窮自動機的化簡正規(guī)式和有窮自動機的等價性正規(guī)式和有窮自動機間的轉換詞法分析程序的自動構造工具：LEX語言（選講內容）2、教學要求：了解：詞法分析程序與語法分析程序的接口方式和輸出；詞法分析工作分離的考慮，LEX語言。掌握：正規(guī)文法；正規(guī)式；正規(guī)文法到正規(guī)式。熟練掌握：確定的有窮自動機（DFA）；不確定的有窮自動機（NFA）；DFA NFA的轉換；確定有窮自動機的化簡，正規(guī)式和有窮自動機的等價性，正規(guī)式和有窮自動機間的轉換。（五）自頂向下語法分析方法 6學時1、教學內容：確定的自頂向下分析思想LL(1)文法的判別某些非LL(1)文法到LL(1)文法的等價變換不確定的自頂

9、向下分析思想確定的自頂向下分析方法：遞歸子程序法；預測分析法2、教學要求：了解：不確定的自頂向下分析思想。掌握：確定的自頂向下分析思想，LL(1)文法的判別，遞歸子程序法，預測分析法。熟練掌握：某些非LL(1)文法到LL(1)文法的等價變換。（六）自底向上優(yōu)先分析法 6學時1、教學內容：自底向上優(yōu)先分析法概述簡單優(yōu)先分析法：優(yōu)先關系；簡單優(yōu)先文法的定義；簡單優(yōu)先分析法算符優(yōu)先分析法：直觀算符優(yōu)先分析法；算符優(yōu)先分析法的定義；算符優(yōu)先關系表的構造；算符優(yōu)先分析法；優(yōu)先函數(shù)；算符優(yōu)先分析法的局限性2、教學要求：掌握：簡單優(yōu)先分析法。熟練掌握：算符優(yōu)先分析法。（七）LR分析法 10學時1、教學內容：

10、LR分析概述LR(0)分析：可歸前綴和子前綴；識別活前綴的有限自動機；活前綴及其可歸前綴的一般計算方法；LR(0)項目集規(guī)范族的構造SLR(1)分析LR(1)分析：LR(1)項目集族的構造；LR(1)分析表的構造LALR(1)分析二義性文法在LR分析中的應用2、教學要求：掌握：SLR(1)分析，LALR(1)分析。熟練掌握：LR(0)分析，LR(1)分析。（八）語法制導翻譯和中間代碼生成 10學時1、教學內容：屬性文法語法制導翻譯概論中間代碼的形式：逆波蘭記號；三元式和樹形表示；四元式簡單賦值語句的翻譯布爾表達式的翻譯：布爾表達式的翻譯方法；控制語句中布爾表達式的翻譯控制結構的翻譯：條件轉移；

11、開關語句；for循環(huán)語句；出口語句；goto 語句；過程調用語句的四元式產生。說明語句的翻譯：簡單說明句的翻譯；過程中的說明數(shù)組和結構的翻譯：數(shù)組說明和數(shù)組元素的引用；結構（記錄）說明和引用的翻譯2、教學要求：掌握：中間代碼的形式逆波蘭記號、三元式和樹形表示、四元式。熟練掌握：簡單賦值語句、布爾表達式、控制結構、說明語句、數(shù)組和結構的翻譯。（九）符號表 4學時1、教學內容：符號表的作用和地位符號的主要屬性機作用符號表的組織：符號表的總體組織；符號表項的排列；關鍵字域的組織；其它域的組織；下推鏈域的組織符號表的管理：符號表的初始化；符號的登錄；符號的查找；符號表中分程序結構層次的管理2、教學要求

12、：掌握：符號的主要屬性機作用。熟練掌握：符號表的組織。（十）目標程序運行時的存儲組織 6學時1、教學內容： 數(shù)據(jù)空間的三種不同使用方法和管理方法：靜態(tài)存儲分配；動態(tài)存儲分配；棧式動態(tài)存儲分配；堆式動態(tài)存儲分配棧式存儲分配的實現(xiàn)：簡單的棧式存儲分配的實現(xiàn)；嵌套過程語言的棧式實現(xiàn)；分程序結構的存儲管理參數(shù)傳遞：傳值；傳地址；過程參數(shù)2、教學要求：了解：堆式動態(tài)存儲分配、過程調用、過程進入和過程返回掌握：靜態(tài)存儲分配，參數(shù)的傳值、傳地址和過程參數(shù)熟練掌握：簡單的棧式存儲分配的實現(xiàn)；嵌套過程語言的棧式實現(xiàn)；分程序結構的存儲管理（十一）代碼優(yōu)化 8學時1、教學內容：優(yōu)化技術簡介局部優(yōu)化：基本塊的劃分；基

13、本塊的變換；基本塊的DAG表示；DAG的應用；DAG構造算法討論控制流分析和循環(huán)優(yōu)化：出現(xiàn)域循環(huán)；循環(huán)；循環(huán)的查找；可規(guī)約流圖；循環(huán)優(yōu)化數(shù)據(jù)流的分析與全局優(yōu)化：一些主要的概念；數(shù)據(jù)流方程的一般形式；到達一定值數(shù)據(jù)流方程；可用表達式及其數(shù)據(jù)流方程；活躍變量數(shù)據(jù)流方法；復寫傳播2、教學要求：了解：數(shù)據(jù)流的分析與全局優(yōu)化。掌握：局部優(yōu)化、控制流分析和循環(huán)優(yōu)化。 十二、代碼生成 6學時1、教學內容：代碼生成概述一個計算機模型一個簡單的代碼生成器：寄存器分配的原則；待用信息鏈表法；代碼生成算法代碼生成研究現(xiàn)狀：中間語言的選擇；代碼生成的自動化研究2、教學要求：了解：代碼生成研究現(xiàn)狀。掌握：寄存器分配的原

14、則；待用信息鏈表法；代碼生成算法。五、主要參考書目考試教材：編譯原理,呂映芝、張素琴等編著 清華大學出版社。主要參考書目有；Compilers: Principles, Techniques, and Tools/編譯原理技術與工具（英文版） ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN.程序設計語言編譯原理 陳火旺，國防工業(yè)出版社， 2000編譯原理及編譯程序構造高仲儀、金茂忠，北京航空學院出版社，1990.12 編譯原理胡倫駿、徐蘭芳、劉建農編，電子工業(yè)出版社.2002年編譯程序原理與技術李贛生、王華民編著，清華大學出版社編譯原理技術陳意云，中國科

15、技大學出版社編譯原理習題精選陳意云、張昱著，中國科技大學出版社編譯原理教案 授課時間 第一周 第 1 次課 授課章節(jié)課程的性質與任務引論1.1 什么是編譯程序1.2 編譯過程、 編譯程序的結構1.3 編譯程序和軟件工具1.4 程序設計語言范型任課教師及職稱馮玲 講師教學方法與手段多媒體課堂教學課時安排2節(jié)課使用教材和主要參考書編譯原理（第2版）張素琴，呂映芝等著，清華大學出版社Compilers: Principles, Techniques, and Tools/編譯原理技術與工具（英文版） ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN.程序設計語言

16、編譯原理 陳火旺，國防工業(yè)出版社， 2000編譯原理及編譯程序構造高仲儀、金茂忠，北京航空學院出版社，1990.12 編譯原理胡倫駿、徐蘭芳、劉建農編，電子工業(yè)出版社.2002年編譯程序原理與技術李贛生、王華民編著，清華大學出版社編譯原理技術陳意云，中國科技大學出版社編譯原理習題精選陳意云、張昱著，中國科技大學出版社教學目的與要求：本章重點對編譯程序的功能和結構做了綜合概述,要求學生了解編譯程序各個成分在編譯階段的邏輯關系以及它們怎樣作為一個整體完成編譯任務的。1 了解課程的性質與任務2 理解什么是編譯程序3了解編譯過程和編譯程序的結構4為什么要學習編譯程序教學重點，難點：理解理解什么是編譯程

17、序了解編譯過程和編譯程序的結構教學內容：課程的性質與任務本課程地位屬于計算機科學與技術專業(yè)的一門重要的專業(yè)必修課。本課程的學習有助于對語言的執(zhí)行系統(tǒng)、程序語言的理解。通過本課程的學習，要掌握編譯程序的一般構造原理，包括語言基礎知識、詞法分析程序設計原理和構造方法。各種語法分析技術和中間代碼生成符號表的構造、代碼優(yōu)化、并行編譯技術常識及運行時存儲空間的組織等基本方法和主要實現(xiàn)技術。語言的發(fā)展機器語言匯編語言 高級語言查詢語言、標注語言第1章 編譯程序概論1.1 什么是編譯程序1.1.1 語言處理程序語言處理程序：把較高級語言編寫的程序語義等價地變換成較低級語言程序的程序。 匯編程序語言處理程序

18、解釋程序 編譯程序源程序目標程序語言處理程序（0）語言的執(zhí)行方式解釋方式（Basic) 口譯編譯方式(C,pascal) 筆譯(1)匯編程序匯編程序：把用匯編語言編寫的程序翻譯成機器語言的程序。匯編語言是為特定的計算機或計算機系統(tǒng)設計的面向機器的語言。如8086/8088 PC、Z-80、VAX匯編語言。匯編的過程就是對匯編指令逐行進行處理，最終得到機器代碼的過程。匯編語言程序可重定位的機器語言程序匯編程序(2)解釋程序解釋程序：對用高級語言編寫的程序進行逐句分析并立即得到結果。解釋程序按源程序中語句的動態(tài)順序逐句進行分析翻譯，并立即予以執(zhí)行，它不產生目標代碼。BASIC APL LISP J

19、ava等語言就是采用解釋方法實現(xiàn)的。計算結果解釋程序源程序初始數(shù)據(jù) SHAPE * MERGEFORMAT 高級語言解釋系統(tǒng)(interpreter)功能：讓計算機執(zhí)行高級語言（basic,lisp,prolog)與編譯程序的不同：1）不生成目標代碼 2）能支持交互環(huán)境（同增量式編譯系統(tǒng)） 解釋程序計算結果源 程 序 初始數(shù)據(jù) 解釋系統(tǒng)直接對源程序中的語句進行分析，執(zhí)行其隱含的操作。 編譯原理教案 如： Int 2St bLd badd 2St a編譯程序 b := 2 ; a := b+2 ; write a ; 解釋程序直接將4的值輸出（顯示）(3)編譯程序編譯程序：把用高級語言編寫的源程

20、序翻譯成等價的低級語言(稱作目標語言)程序。編譯系統(tǒng)是編譯程序和運行系統(tǒng)的合稱。高級語言源程序低級語言目標程序編譯程序一個編譯程序把一個高級語言源程序翻譯成目標程序的工作可分為前后銜接的六個階段：詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化及目標代碼生成。大多數(shù)高級語言是采用編譯的方法實現(xiàn)的。如：PASCAL、FORTRAN、ADA、C、C+、PL/1、 ALGOL 60、 ALGOL 68,等等。1.1.2 什么是編譯程序(compiler)編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分.從功能上看，一個編譯程序就是一個語言翻譯程序,它把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作

21、目標語言)的等價的程序. 編譯程序的功能術語：編譯程序的源語言(源程序);編譯程序的目標語言(目標程序);編譯程序的實現(xiàn)語言;軟件：計算機系統(tǒng)中的程序及其文檔;系統(tǒng)軟件：居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。他和具體的應用領域無關，如編譯系統(tǒng)和操作系統(tǒng)等。處理系統(tǒng)：把軟件語言書寫的各種程序處理成可在計算機上執(zhí)行的程序。軟件語言：用于書寫軟件的語言。它主要包括需求定義語言，功能性語言，設計性語言，程序設計語言以及文檔語言編譯程序(compiler);編譯程序的源語言(源程序) (source language)(source program);編譯程序的目標語言(

22、目標程序) (object or target language)(object or target program) ;編譯程序的實現(xiàn)語言(implementation language);語言處理程序(language processor);語言轉（變）換(language transformation) 預處理器 編譯器 匯編器 裝配連接編輯 源程序源程序 目標匯編程序 可重定位機器代碼 絕對機器碼 可重定位目標文件庫高級語言程序的處理過程 SHAPE * MERGEFORMAT 編譯原理教案 1.2 編譯過程和結構1.2.1編譯邏輯過程(1) 詞法分析這個階段的任務是從左至右、從上到下

23、一個字符一個字符地讀入源程序，對構成源程序的字符流進行掃描和分解，從而識別出一個個單詞。詞法分析后可能返回:單詞類型單詞值 保留字 int標識符(變量名) a界符 ;標識符(變量名) a算符(賦值) =標識符(變量名) a 算符(加) +整數(shù) 2界符 ；有關術語詞法分析從左到右讀字符流的源程序、識別（拼）單詞。單詞具有獨立意義的基本語法單位。保留字具有特殊規(guī)定的意義，不允許用戶將它們作為別用，是用戶定義標識符的禁區(qū)。標識符 用來表示程序、過程、函數(shù)、類型、常量和變量等名稱的符號。(2)語法分析在詞法分析的基礎上，根據(jù)語言的語法規(guī)則（文法規(guī)則），把單詞符號串分解成各類語法單位，如“短語”、“句子

24、”、“程序段”和“程序”。通過語法分解，確定整個輸入串是否構成一個語法上正確的程序。 例: 符號串 X+0.168*Y, 經(jīng)語法分析就可識別出這個字符串屬于算術表達式。 Y:= X+0.168*Y; 語法分析所依循的是語言的語法規(guī)則，用產生式描述。語法分析器讀入單詞，將它們組合成按產生式規(guī)定的各類語法單位。sum :=first + count * 10規(guī)則 :=“:=” :=“+” :=“*” :=“(”“)” := := := 編譯原理教案 賦值語句 表達式 表達式 + 表達式 標識符 整數(shù) 標識符 = 表達式 * 表達式 SHAPE * MERGEFORMAT 標識符 術語語法：定義語言

25、各語法成分的形式或結構。語法分析：依據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹) 。語法樹(推導樹)：表示句型推導（或歸約）的樹型結構。語法樹有助于理解一個句子語法結構的層次。(3 )語義分析語義審查(靜態(tài)語義)類型匹配類型轉換例:Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */;語義分析的一個重要內容是類型檢查,對表達式及語句中的各語法成分作類型檢查和分析.如: Var count:real

26、; Var first :real; Var sum :real ; sum := first + count* 10術語語法：用來定義語言中各語法成份的形式或結構。語義：用來規(guī)格各語法成份的含義和功能，即規(guī)定它們的屬性或在執(zhí)行時應進行的運算或操作。語義分析：檢查源程序是否包含語義錯誤，并搜集類型，供后面的代碼生成階段使用，只有語法和語義正確的源程序才可被翻譯成目標代碼。 語義分析程序需要進行頻繁的造表和查表工作。(4 )中間代碼生成語義分析之后生成一種介于源語言和目標語言之間的中間語言代碼。中間代碼有多種形式：三元式、四元式、逆波蘭表示、樹型結構 編譯原理教案 例： a:=b*c 三元式：

27、逆波蘭表示式：abc* := (1) (*, b, c) 樹： :=(2) (:=,a,(1) a * 四元式： b c（*, b, c, a)id1:= id2 + id3 * 10 因運算需要，需設置臨時變量t1,t2,t3來存放中間運算結果。四元式 ( 算符 第一運算量 第二運算量 運算結果 )(1) (inttoreal, 10, -, t1 )(2) (*, id3, t1, t2 )(3) (+, id2, t2, t3 )(4) (:=, t3, -, id1 )中間代碼的幾種形式逆波蘭表示：運算符在其運算量之后的表達式。三元式：（OP，ARG1，ARG2）四元式：（OP，ARG

28、1，ARG2，RESULT）樹：根結點OP，左子樹ARG1，右子樹ARG2 (5 )代碼優(yōu)化對前階段產生的中間代碼進行加工變換，以期在最后階段能產生出更為高效（省時間和省空間）的目標代碼t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1t3 = b* c a = t2t4 = t2 + t3a = t4在本例中，b、c的值沒有改變，故t1=t3，由第二個表達式知道t2=t1。(6 )目標代碼生成將前階段產生的中間代碼翻譯為機器語言或匯編語言形式的目標程序。目標程序總是按某一具體計算機的機器語言或匯編語言來產生的。目標代碼生成movfid3,R2mulf#10

29、.0,R2movfid2,R1addfR2,R1movfR1,id1(*,id310.0t1)(+,id2t1id1) 編譯原理教案 (7) 符號表管理符號表管理：記錄源程序中使用的名字,收集每個名字的各種屬性信息:類型、作用域、分配存儲信息在編譯過程中，源程序中的標識符及其各種屬性都要記錄在符號表中，這些屬性可以提供標識符的存儲分配信息、類型信息、作用域信息等等。對于過程標識符，還要有參數(shù)信息，包括參數(shù)的個數(shù)和類型、實參和形參的結合方式等等。符號表結構符號表是一種含記錄的數(shù)據(jù)結構，通常一個標識符在符號表中占一個記錄，記錄中除了標識符的名字域之外，還有記錄該標識符屬性的域。(8) 出錯處理編譯

30、的每一個階段都會發(fā)現(xiàn)源程序的錯誤，在發(fā)現(xiàn)錯誤之后，一般要對其有一定的處理措施，因而編譯還可繼續(xù)執(zhí)行，不會一有錯誤就停止編譯工作。出錯處理(error handling)(error reporting and error recovery)在詞法分析中，能發(fā)現(xiàn)單詞拼寫錯誤。在語法分析中，檢查單詞串是否符合語法的結構規(guī)則。在語義分析中，編譯程序進一步查出語法上雖正確但含有無意義的操作部分，如兩個標識符相加，一個是數(shù)組名，一個是過程名，雖然語法上允許，但語義上不允許，各種錯誤，都應在相應的階段進行處理。檢查錯誤報告出錯信息（錯誤種類及位置）校錯及排錯恢復編譯工作1.2.2 編譯程序的結構(comp

31、onents) 出錯處理 語法分析程序 語義分析程序 目標代碼生成程序 詞法分析程序 中間代碼生成程序 代碼優(yōu)化程序 表格管理 1.2.3 編譯階段的組合分析，綜合(synthesis)源程序的分析線性分析層次分析語義分析目標程序的綜合編譯的前端（front end）:這些階段以來于源語言、與目標機無關。編譯的后端（back end）：依賴于目標機器的階段。遍（趟）從頭到尾掃描源程序（各種形式）一遍(pass) 編譯階段和運行階段存儲結構 編譯原理教案 1.3 編譯技術和軟件工具編譯程序實現(xiàn)方式:手工,機器語言,匯編,系統(tǒng)程序設計語言,自動構造工具lex yacc gcc1.3.1 編譯程序的

32、發(fā)展 Human-orientedlanguageComputer-orientedlanguage 計算模式，語言 范式 編譯程序 馮諾曼機體系結構 并行體系結構 嵌入系統(tǒng) 編譯程序的發(fā)展(1)語言范型（支持的計算模式）命令式(imperative language)應用式(applicative)，也成函數(shù)式基于規(guī)則的（rule-based）面向對象的（object-oriented）(2)編譯程序執(zhí)行環(huán)境批處理交互環(huán)境嵌入系統(tǒng)環(huán)境1.3.2 編譯技術和軟件工具結構化編輯器程序調試工具程序測試工具:1靜態(tài)分析 2 動態(tài)分析 3度量工具(結構度量) 4分析工具(source insight)

33、 高級語言轉換工具廣泛的語言領域 1.3.3 研究領域(1) 并行化編譯技術目的：提高并行計算機體系結構的性能(2)交叉編譯器由于目標機指令系統(tǒng)與宿主機的指令系統(tǒng)不同，編譯時將應用程序的源程序在宿主機上生成目標機代碼，稱為交叉編譯。簡單地說，就是在一個平臺上生成另一個平臺上的可執(zhí)行代碼。嵌入式(3) 自展編譯技術用被編譯的語言來書寫該語言自身的編譯程序。小結編譯原理教案復習思考題、作業(yè)題：1. 什么是編譯程序？2. 簡要介紹編譯過程的六個階段，并給出編譯程序的結構。下次課預習要點預習第二章PL/0編譯程序的結構與詞法分析等內容實施情況及教學效果分析授課時間分配合理；編譯過程、編譯基本概念重點突

34、出，學生能夠掌握基本內容；教學效果良好。學院審核意見 同意實施 學院負責人簽字 年 月 日 編譯原理教案 授課時間 第一周 第 2 次課 授課章節(jié)第2章 PL/0編譯程序的實現(xiàn)2.1 PL/0語言描述2.2 PL/0編譯程序的結構2.3 PL/0編譯程序的詞法分析任課教師及職稱馮玲 講師教學方法與手段多媒體課堂教學課時安排2節(jié)課使用教材和主要參考書編譯原理（第2版）張素琴，呂映芝等著，清華大學出版社Compilers: Principles, Techniques, and Tools/編譯原理技術與工具（英文版） ALFRED V. AHO, RAVISETHI, JEFFREY D. UL

35、LMAN.程序設計語言編譯原理 陳火旺，國防工業(yè)出版社， 2000編譯原理及編譯程序構造高仲儀、金茂忠，北京航空學院出版社，1990.12 編譯原理胡倫駿、徐蘭芳、劉建農編，電子工業(yè)出版社.2002年編譯程序原理與技術李贛生、王華民編著，清華大學出版社編譯原理技術陳意云，中國科技大學出版社編譯原理習題精選陳意云、張昱著，中國科技大學出版社教學目的與要求：以PL/0為實例,學習編譯程序實現(xiàn)的基本步驟和相關技術。 教學重點，難點：PL/0編譯程序的結構與詞法分析教學內容： 第2章 PL/0編譯程序的實現(xiàn)PL/0編譯程序類 pcode解釋程序類 pcode代碼PL/0源程序輸入輸出PL/0編譯系統(tǒng)的

36、結構框架2.1 PL/0語言(1) PL/0程序示例CONST A=10; （* 常量說明部分 *） VAR B,C; （* 變量說明部分 *） PROCEDURE P; （* 過程說明部分 *） VAR D; PROCEDURE Q; VAR X; BEGIN READ(X); D:=X; WHILE X#0 DO CALL P; END; BEGIN WRITE(D); CALL Q; END; BEGIN CALL P; END.(2) PL/0的語法描述圖分序程序.內的文字表示非終結符或內的文字或符號表示終結符條件語法描述圖表達式和項的語法描述圖因子的語法圖(3) PL/0語言文法的E

37、BNF表示EBNF 引入的符號(元符號)： 用左右尖括號括起來的語法成分為非終結符= () 定義為 =() 的左部由右部定義 | 或 表示花括號內的語法成分可重復任意次或限定次數(shù) 表示方括號內的語法成分為任選項( ) 表示圓括號內的成分優(yōu)先例：用EBNF描述的定義 ：=+|-=0|1|2|3|4|5|6|7|8|9 或更好的寫法 =+|-|0=1|2|3|4|5|6|7|8|9 =0| PL/0余言的文法表示見P15.(4) PL/0語言是PASCAL語言的子集同PASCAL作用域規(guī)則（內層可引用包圍它的外層定義的標識符），上下文約束，過程可嵌套定義，可遞歸調用子集數(shù)據(jù)類型,只有整型數(shù)據(jù)結構

38、,只有簡變和常數(shù)數(shù)字最多為14位標識符的有效長度是10語句種類過程最多可嵌套三層(5) 目標代碼類pcode目標代碼類pcode是一種假想棧式計算機的匯編語言。指令格式：fla f功能碼l層次差 （標識符引用層減去定義層）a根據(jù)不同的指令有所區(qū)別2.2 PL/0編譯程序的結構(1)PL/0編譯程序結構詞法分析程序語法語義分析程序代碼生成程序表格管理程序出錯處理程序PL/0源程序目標程序 編譯原理教案 （2）PL/0編譯程序的總體設計其編譯過程采用一趟掃描方式，以語法、語義分析程序為核心詞法分析程序和代碼生成程序都作為一個過程，當語法分析需要讀單詞時就調用詞法分析程序，而當語法、語義分析正確，需

39、要生成相應的目標代碼時，則調用代碼生成程序。表格管理程序實現(xiàn)變量，常量和過程標識符的信息的登錄與查找。出錯處理程序，對詞法和語法、語義分析遇到的錯誤給出在源程序中出錯的位置和與錯誤 性質有關的編號，并進行錯誤恢復。（3）編譯程序總體流程圖（4）PL/0編譯程序過程一覽表（P17)2.3 PL/0編譯程序的詞法分析（1）Pl/0詞法分析程序Getsym 識別的單詞： （類別，值）保留字：如：BEGIN、 END、 IF、 THEN等運算符： 如：+、-、*、/、：=、#、=、=等標識符： 用戶定義的變量名、常數(shù)名、過程名常數(shù)： 如：10、25、100等整數(shù)界符： 如：,、. 、; 、( 、)等G

40、etsym用到三個單元：SYM:存放單詞類別ID:存放標識符的值NUM:存放整數(shù)的值（2）詞法分析過程GETSYM流程圖(P19)所要完成的任務：濾空格識別保留字識別標識符拼數(shù)識別單字符單詞(等)拼雙字符單詞（=,等）輸出源程序讀字符子程序（getch）（p20）（3）進一步的說明如何識別標識符先查保留字表,建立保留字表 保留字 內部表示 begin beginsym call callsym . write writesym 查到時找到相應的內部表示若不是保留字，則是用戶定義的標識符，應建立標識符表。類似地可以建立運算符、常數(shù)、界符表詞法分析程序的實現(xiàn)見附錄 編譯原理教案 復習思考題、作業(yè)題

41、：P30,練習22.2若pl/0編譯程序運行時的存儲分配策略采用棧式動態(tài)分配，并用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調用和非局部變量的引用問題，試寫出下列程序執(zhí)行到賦值語句b:=10時運行棧的布局示意圖。Var x,y;Procedure p; Var a; Procedure q; Var b; Begin (q) B:=10;End(q);Procedure s; Var c,d; Procedure r; Var e,f; Begin(r) Call q; End(r); Begin (s) Call r; End(s); Begin(p); Call s; End(p); Begin(m

42、ain) Call p; End(main).下次課預習要點復習PL/0編譯程序的結構與詞法分析，預習2.42.7小節(jié)實施情況及教學效果分析授課時間分配合理；PL/0語言、編譯各階段的功能為教學重點，也是難點；學生能夠掌握基本內容；教學效果良好。學院審核意見 同意實施 學院負責人簽字 年 月 日 編譯原理教案 授課時間 第二周 第 3 次課 授課章節(jié)第2章 PL/0編譯程序的實現(xiàn)2.4 PL/0編譯程序的語法語義分析 2.5 PL/0編譯程序的目標代碼結構和代碼生成2.6 PL/0編譯程序的語法錯誤處理2.7 PL/0編譯程序的目標代碼解釋執(zhí)行時的存儲分配任課教師及職稱馮玲 講師教學方法與手段

43、多媒體課堂教學課時安排2節(jié)課使用教材和主要參考書編譯原理（第2版）張素琴，呂映芝等著，清華大學出版社Compilers: Principles, Techniques, and Tools/編譯原理技術與工具（英文版） ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN.程序設計語言編譯原理 陳火旺，國防工業(yè)出版社， 2000編譯原理及編譯程序構造高仲儀、金茂忠，北京航空學院出版社，1990.12 編譯原理胡倫駿、徐蘭芳、劉建農編，電子工業(yè)出版社.2002年編譯程序原理與技術李贛生、王華民編著，清華大學出版社編譯原理技術陳意云，中國科技大學出版社編譯原理習題

44、精選陳意云、張昱著，中國科技大學出版社教學目的與要求：以PL/0為實例,學習編譯程序實現(xiàn)的基本步驟和相關技術。教學重點，難點：1掌握PL/0編譯程序的語法語義分析與目標代碼結構和代碼生成2了解PL/0編譯程序的語法錯誤處理3理解PL/0編譯程序的目標代碼解釋執(zhí)行時的存儲分配 編譯原理教案 教學內容：2.4 PL/0編譯程序語法語義分析2.4.1 PL/0編譯程序語法分析的設計與實現(xiàn)自頂向下的語法分析遞歸子程序法：對于每個非終結符，編寫一個子程序，由該子程序負責識別該語法單位是否正確。先回憶PL/0的語法規(guī)定。遞歸子程序法：對應每個非終結符語法單元，編一個獨立的處理過程（或子程序）,識別該終結符

45、對應的句子。語法分析從讀入第一個單詞開始，由非終結符（即開始符）出發(fā)，沿語法描述圖箭頭所指出的方向進行分析。當遇到非終結符時，則調用相應的處理過程，從語法描述圖看，也就進入了一個語法單元，再沿當前所進入的語法單元所指箭頭方向繼續(xù)進行分析。當遇到描述圖中是終結符時，則判斷當前讀入的單詞是否與圖中的終結符相匹配，若匹配，再讀取下一個單詞繼續(xù)分析。遇到分支點時，將當前的單詞與分支點上多個終結符逐個相比較，若都不匹配時可能是進入下一個非終結符語法單位或是出錯。表達式的EBNF表達式=+|-項（+|-）項項=因子（*|/）因子因子=標識符|無符號整數(shù)|（表達式）表達式的遞歸子程序實現(xiàn)procedure

46、expr;begin if sym in plus, minus then begin getsym; term; end else term; while sym in plus, minus do begin getsym; term; endend;項的遞歸子程序實現(xiàn)項=因子（*|/）因子procedure term;begin factor; while sym in times, slash do begin getsym; factor; endend;因子的遞歸子程序實現(xiàn)procedure factor;begin if sym ident then 編譯原理教案 if sym

47、number then if sym = ( then begin getsym; expr; if sym = ) then getsym else error end else error else getsym else getsym end;=begin（*main*)(*initialize*) (*r/w file set*) getsym; block( ); if sym period then error.end.2.4.2 PL/0編譯程序語義分析的設計與實現(xiàn)PL/0編譯程序語法、語義分析的的核心程序是BLOCK過程 (1)說明部分的分析與處理對每個過程（含主程序）說明的對

48、象（變量，常量和過程）造符號表, 登錄標識符的屬性。標識符的屬性:種類，所在層次,值和分配的相對位置。登錄信息由ENTER過程完成。注意：所有標識符保存在Table中，TX表示索引表的指針 LEV表示層次 Dx表示局部變量分配的位置常量說明語句的處理語法：: := const ， ； : := = : := if sym = constsym then begin getsym; (* 獲取下一個token，正常應為用作常量名的標識符 *) repeat (* 反復進行常量聲明 *) constdeclaration; (* 聲明以當前token為標識符的常量 *) while sym = c

49、omma do (* 如果遇到了逗號則反復聲明下一常量*) begin getsym; (* 獲取下一個token，這里正好應該是標識符 *) constdeclaration (* 聲明以當前token為標識符的常量 *) end; 編譯原理教案 if sym = semicolon then (* 如果常量聲明結束，應遇到分號 *) getsym (* 獲取下一個token，為下一輪循環(huán)做好準備 *) else error(5) (*提示5號錯誤 *) until sym ident (* 如果遇到非標識符，則常量聲明結束 *) end; 常量說明處理procedure constdecl

50、aration; begin if sym = ident then begin getsym; if sym in eql, becomes then (* 如果是等號或賦值號 *) if sym = becomes then (* 如果是賦值號(常量生明中應該是等號) *) error(1); (* 提示1號錯誤 *) getsym; (* 獲取下一個token，等號或賦值號后應接上數(shù)字 *) if sym = number then (* 如果的確是數(shù)字 *) begin enter(constant); (* 把這個常量登陸到符號表 *) getsym (* 獲取下一個token，為后

51、面作準備 *) end else error(2) (* 如果等號后接的不是數(shù)字，提示2號錯誤 *) else error(3)(* 如常量標識符后不是等號或賦值號，提示3號錯誤 *) end else error(4) end(* constdeclaration *);變量定義語句的處理語法：: := var ， ；程序： if sym=varsym then begin getsym; repeat vardeclaration;(*變量說明處理*) while sym=comma do begin getsym; vardeclaration end; if sym=semicolon

52、 then getsym else error(5) until symident; end; 編譯原理教案 變量說明處理procedure ardeclaration; begin if sym=ident then begin enter(variable); getsym end else error(4) end(*vardeclaration*);過程定義語句的處理程序：while sym = procsym do (* 循環(huán)聲明各子過程 *) begin getsym; (* 獲取下一個token，此處正常應為作為過程名的標識符 *) if sym = ident then (*

53、如果token確為標識符 *) begin enter(procedur); (* 把這個過程登錄到名字表中 *) getsym (* 獲取下一個token，正常情況應為分號 *) end else error(4); (* 否則提示4號錯誤 *) if sym = semicolon then (* 如果當前token為分號 *) getsym (* 獲取下一個token，準備進行語法分析的遞歸調用 *) else error(5); (* 否則提示5號錯誤 *)2.5 目標代碼結構和代碼生成(1)目標代碼結構 f 功能碼 l 層次差 a 根據(jù)不同的指令有所區(qū)別const a=10;var

54、b,c;procedure p; begin c:=b+a; end;begin read(b); while b#0 do begin call p; write(2*c); read(b); 編譯原理教案 endend.( 0) jmp 0 8 轉向主程序入口( 1) jmp 0 2 轉向過程p入口( 2) int 0 3 過程p入口,為過程p開辟空間( 3) lod 1 3 取變量b的值到棧頂( 4) lit 0 10 取常數(shù)10到棧頂( 5) opr 0 2 次棧頂與棧頂相加( 6) sto 1 4 棧頂值送變量c中( 7) opr 0 0 退棧并返回調用點(16)( 8) int 0

55、 5 主程序入口開辟5個?？臻g( 9) opr 0 16 從命令行讀入值置于棧頂(10) sto 0 3 將棧頂值存入變量b中(11) lod 0 3 將變量b的值取至棧頂(12) lit 0 0 將常數(shù)值0進棧(13) opr 0 9 次棧頂與棧頂是否不等(14) jpc 0 24 等時轉(24)（條件不滿足轉）(15) cal 0 2 調用過程p(16) lit 0 2 常數(shù)值2進棧(17) lod 0 4 將變量c的值取至棧頂(18) opr 0 4 次棧頂與棧頂相乘(2*c)(19) opr 0 14 棧頂值輸出至屏幕(20) opr 0 15 換行(21) opr 0 16 從命令行

56、讀取值到棧頂(22) sto 0 3 棧頂值送變量b中(23) jmp 0 11 無條件轉到循環(huán)入口(11)(24) opr 0 0 結束退棧(2) 代碼生成代碼生成是由過程GEN完成。GEN有3個參數(shù)，分別代表目標代碼的功能碼，層差和位移量。例如 gen(opr,0,16); gen(sto,lev-level,adr) lev：當前處理的過程層次 level：被引用變量或過程所在層次 CX：為保存目標代碼code數(shù)組的下標指針，初值為02.6 PL/0編譯程序的語法錯誤處理程序遇到的錯誤：語法錯、語義錯、運行錯。對語法錯誤的兩種處理方法：(1) 對于易于校正的錯誤，如丟了逗號，分號等，指出

57、出錯位置，加以校正，繼續(xù)進行分析。(2) 對于難于校正的錯誤，給出錯誤的位置與性質，跳過后面的一些單詞，直到讀到下一個可以進行正常語法分析的語法單位。方法 當語法分析進入或退出一個語法單位時，調用測試程序TEST,檢查當前單詞是否屬于該語法單元的開始或結束。 編譯原理教案 TEST測試過程流程圖 三個參數(shù)：S1:開始符號或后繼符號集 S2：補充單詞集合 N：出錯編號n見p27開始符號集合與后繼符號集合READ語句的語法語義分析處理read（A1，b2，c4）;if sym=readsym then begin getsym; if symlparen then error(34) else r

58、epeat getsym; if sym=ident then i:=position(id) else i:=0; if i=0 then error(32) else with tablei do if kind=variable then(* 如標識符為變量則生成目標代碼*）begin gen(opr,0,16); gen(sto,lev-level,adr)end; getsym until symcomma; if symrparen then begin error(33); while not(sym in fsys) 出錯處理 do getsym end else getsym

59、 正確出口 end2.7 PL/0編譯程序的目標代碼解釋執(zhí)行時的存儲分配(1)類pcode解釋器的結構:目標代碼CODE目標代碼解釋執(zhí)行時數(shù)據(jù)棧的布局（運行棧的存儲分配）四個寄存器 棧頂寄存器（指針）T: p28 基址寄存器（指針）B：過程數(shù)據(jù)區(qū)地址 程序地址寄存器 P：指向下一條要執(zhí)行的指令 指令寄存器 I：存放正在執(zhí)行的指令在每個過程調用時在棧頂分配3個聯(lián)系單元：SL： 靜態(tài)鏈，指向定義該過程的直接外過程 （或主程序）運行時最新數(shù)據(jù)段的基地址。DL： 動態(tài)鏈，指向調用該過程前正在運行過 程的數(shù)據(jù)段基地址。RA： 返回地址，記錄調用該過程時目標程序的斷點，即調用過程指令的下一條指令的地址。

60、編譯原理教案 （2）目標代碼的解釋執(zhí)行 運行棧S過程中變量的編址：0-SL,1-DL,2-RA,變量從3開始M調用過程Q實例P29 RA DL SLb. ttbQM（3）幾條特殊指令在code中的位置和功能INT 0 A在過程目標程序的入口處，開辟A個單元的數(shù)據(jù)段。A為局部變量的個數(shù)+3。OPR 0 0在過程目標程序的出口處，釋放數(shù)據(jù)段（退棧），恢復調用該過程前正在運行的過程的數(shù)據(jù)段基址寄存器B和棧頂寄存器T的值，并將返回地址送到指令地址寄存器P中，以使調用前的程序從斷點開始繼續(xù)執(zhí)行。CAL L A調用過程，完成填寫靜態(tài)鏈、動態(tài)鏈、返回地址，給出被調用過程的基地址值，送入基址寄存器B中，目標程