編譯原理課外訓練體系

1、編譯原理課外訓練體系 一、課程編碼及適用專業(yè) 課程編碼 總學時： 56 授課學時： 40 適用專業(yè) ：計算機科學與技術專業(yè) 二、課程性質 編譯原理是為計算機科學與技術專業(yè)學生開設的重要專業(yè)課，是一門理論性、實 踐性和技術性很強的課程。 三、本課程的地位和作用 通過學習， 學生可基本掌握計算機系統(tǒng)軟件之一編譯程序的構造原理及相關技術， 同時， 還可提高學生計算機專業(yè)素質，培養(yǎng)學生的抽象思維能力。 四、學習目的與要求 對編譯的基本概念、 原理和方法有完整和清楚的理解，并能正確地、熟練地運用， 設計 出高級程序語言子集的編譯程序。 為了能確切地學好本課程，要求學生具備 : 高級語言程序設計、數(shù)據(jù)結構

2、、匯編語言、 離散數(shù)學、操作系統(tǒng)等課程的知識。 五、本課程的學習方法 認真閱讀教材，及時做習題 ; 做好階段總結，正確理解課程各單元之間的關系。 （一）學習目的明確，學習態(tài)度認真； （二）了解課程的性質和要求，以便在課程的學習中能緊緊圍繞本課程的基本要求； （三）對課程內容的學習，要重在理解，積極思考，不斷提出問題，解決問題； （四）通過認真完成習題鞏固和加深對所學理論的理解； （五）如有條件，可通過實驗按各單元編寫程序驗證和鞏固所學理論，取得事半功倍 的成效。 六、課外訓練與指導內容 第一章編譯程序的概述 （一）內容 本章介紹編譯程序在計算機科學中的地位和作用，介紹編譯技術的發(fā)展歷史，講解編

3、譯 程序、 解釋程序的基本概念， 概述編譯過程， 介紹編譯程序的邏輯結構和編譯程序的組織形 式等。 （二）本章重點 編譯（程序） ，解釋（程序） ，編譯程序的邏輯結構。 （三）本章難點 編譯程序的生成。 （四）本章考點 全部基本概念。 編譯程序的邏輯結構。 （五）學習指導 引論部分主要是解釋什么是編譯程序以及編譯的總體過程。 因此學習時要對以下幾個點 進行重點學習：翻譯、編譯、目標語言和源語言這幾個概念的理解；編譯的總體過程：詞法 分析，語法分析、語義分析與中間代碼的生成、代碼優(yōu)化、目標代碼的生成，以及伴隨著整 個過程的表格管理與出錯處理。 第三章文法和語言課外訓練 一）內容 本章是編譯原理課

4、程的理論基礎，主要介紹與課程相關的形式語言的基本概念，包括符 號串的基本概念和術語、 文法和語言的形式定義、 推導與歸約、句子和句型、語法分析樹和 二義性文法等定義、文法和語言的Chomsky分類。 （二）本章重點 上下文無關文法，推導，句子和句型，文法生成的語言，語法分析樹和二義性文法。 （三）本章難點 上下文無關文法，語法分析樹，文法的分類。 （四）本章考點 上下文無關文法的定義。 符號串的推導。 語法分析樹的構造。 （五）學習指導 要構造編譯程序，就要把源語言用某種方式進行定義和描述。學習高級語言的語法描述 是學習編譯原理的基礎。上下文無關文法及語法樹是本章學習的重點。語法與語義的概念；

5、 程序的在邏輯上的層次結構； 文法的定義， 文法是一個四元組： 終結符號集， 非終結符號集， 開始符號、產(chǎn)生式集；與文法相關的概念，字符，正則閉包，積（連接），或，空集，產(chǎn)生 式，推導，直接推導，句子，句型，語言，最左推導，最右推導（規(guī)范推導）；學會用文法 來描述語言及通過文法能分析該文法所描述的語言； 語法樹及二義性的概念、 能通過畫語法 樹來分析一個文法描述的語言是否具有二義性；上下文無關文法的定義和正規(guī)文法的定義， 能判斷一個語言的文法是哪一類文法。 附訓練試題： 1： 試構造生成語言 L=a nbnci |n 1, i 0的文法解： 2： 已知語言L=a nbbn| n 1,寫出產(chǎn)生L

6、的文法。 3： 已知文法 G=（A,B,C,a,b,c,A,P） 其中產(chǎn)生式 P 由以下組成： A t abc A taBbc Bb tbB Bc tCbcc bC tCb aC taaB aC taa 問：此文法表式的語言是什么？ 4 請給出描述語言=a2m+1b m+1| m=0 U a 2mb m+2 m=0的文法 5 已知文法 GS 為： S t dAB A t aA|a B t Bb | P|P 求：出每個非終結符的 FIRSTVT集和LASTVT集，并構造算符優(yōu)先關系矩陣。 3 考慮下面文法 G2: St a| A | (T) TT T, S | S (1) 給出(a,(a, a)

7、 和(a,a),A ,(a),a) 的最左和最右推導。 (2) 給出串( a, (a, a) )的算符優(yōu)先分析過程。 第七章 LR 分析法課外訓練 (一) 內容 本章介紹編譯程序的第二個階段語法分析的第二種設計方法和實現(xiàn)原理即自下而上分 析的原理，包括一些基本概念、LR分析法。 (二) 本章重點 自下而上分析的思想，LR分析器邏輯結構和功能，LR(0)文法及其分析、SLR(1)文法及 其分析、 LR(1)、 LALR(1) 文法及其分析。 (三) 本章難點 句柄的定義，LR項目及活前綴識別自動機，四種LR文法的差別。 (四) 本章考點 基本概念的定義(短語、直接短語、句柄、規(guī)范歸約等) 。 L

8、R( 0)、 SLR( 1 )分析。 (五) 學習指導 理解有效項目的基本概念；掌握 LR(0) 、 SLR( 1)文法的判斷及 LR(0) 、 SLR( 1 )分析 表的構造與分析方法。自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到 文法的開始符號， 從輸入串的語法樹上直觀地看就是沿著語法樹的底部向上分析歸約，最終 能到達根結點的就認為當前的輸入串能被接受。大部分現(xiàn)代的編譯器都采用LR分析作為語 法分析的方式。因此本章的學習重點是學習如何構造LR分析表。OPG分析可以作為自下而 上分析算法的切入點要求重點掌握。 附訓練試題： 1 、對于文法 GS ST ( L) | aS |a

9、 Lt L, S | S (1) 畫出句型 ( S ,(a) 的語法樹 (2) 寫出上述句型的所有短語，直接短語， 句柄 . 2、設有文法 GS: S t L=R S tR L t *R L ti R tL 為構造拓廣文法，增加新的非終結符 S,得到規(guī)則S t S,則： closure ( S t .S, # )= 3、設文法 G(S ) St A A t aA | b 構造識別文法 G(S ) 的所有活前綴的 DFA. 4、 求文法( 1) St A ( 2) A t aA ( 3) A t b LR(0) 分析表： 5、設文法G,試構造G的LR(O)分析表 G: 1) S t CC 2)

10、Ct cC 3) Ct d 6、對于文法 At aA|a構造SLR分析表 7、設有文法 G(S )為 1)St S 2) S t L=R 3) S t R 4) L t *R 5) L ti 6) R tL 構造文法 G(S )的 LR(1) 分析表： 8、設有文法 G(A) 1) A t A 2) A t BB 3) B t aB 4) B t b 構造LALR(1)分析表 第八章語法制導翻譯和中間代碼的生成課外訓練 抽 包括語法制 (一) 自學內容 本章內容圍繞語義分析展開，主要介紹屬性文法，語法制導翻譯與翻譯模式的計算， 象語法樹、 帶注釋的語法樹。 語義分析及中間代碼生成的設計原理和實

11、現(xiàn)方法， 導翻譯的具體實現(xiàn)、中間代碼的形式，可執(zhí)行語句和說明語句的語法制導翻譯方法。 (二) 本章重點 屬性文法、后綴式和四元式中間代碼表示，簡單算術表達式和賦值語句的翻譯，布爾表 達式及控制語句的翻譯，數(shù)組元素的處理，過程語句的翻譯。 （三）本章難點 抽象語法樹， 屬性的作用及計算， 語法制導翻譯。 布爾表達式的翻譯， 數(shù)組元素的處理。 （四）本章考點 語法制導翻譯定義。中間語言表示（后綴式和三地址代碼） 。賦值語句的翻譯。布爾表 達式及控制語句的翻譯。 （五）學習指導 要求理解屬性的引入、兩種屬性的計算原則，掌握S屬性的計算方法，掌握L屬性翻譯 模式的計算 （遞歸下降分析）， 繼承屬性計算

12、的四種方法。本章介紹屬性文法的基本概念和 基于屬性文法的處理方法， 討論如何在自上而下分析和自下而上分析中實現(xiàn)屬性的計算。 本 章的學習重點以掌握屬性文法及語法制導翻譯的概念為主，分析中屬性的計算作為了解。 理解語法制導翻譯、語義動作的基本概念；掌握算術表達式和賦值語句到中間代碼的翻 譯、布爾表達式和幾種控制語句的目標代碼結構分析和到四元式的語法制導翻譯；說明語句 的語法制導翻譯。 本章是將上一章介紹的屬性文法和語法制導翻譯的方法和技術應用于語義 分析和中間代碼的產(chǎn)生。 本章的學習重點為： 掌握各種中間代碼的形式，包括后綴式、 三元 式、四元式等；了解常用語法結構單元的語義表達形式，包括說明語

13、句，賦值語句，布爾表 達式，控制語句，過程調用。 附訓練試題： 1 、在一個移入歸約的分析中采用以下的語法制導的翻譯模式，在某產(chǎn)生式歸約時， 立即執(zhí)行括號中的動作。 Z aB print“0” Z c pri nt“ 1” B Ab print “2” 當分析器輸入為 aacbb時，打印的字符串是 什么? 2、下列文法由開始符 S 產(chǎn)生一個二進制數(shù)，令綜合屬性 val 給出該數(shù)的值： SL .L| L LLB | B B0 | 1 試設計求 S.val 的屬性文法，其中，已知 B 的綜合屬性，給出由 B 產(chǎn)生的二進位的結果 值。如輸入 101。101 時，輸出 S.val=5.625 。 3、

14、設有文法 GS ： S（L） | a LL , S | S 給此文法配上語義動作子程序（或者說為此文法寫出一個語法制導定義），使其輸出配對括 號的個數(shù)，如對于句子 （a, （a, a）, 輸出是 2。 4、 給出文法 GS：SSaA | A AAbB | B B cSd | e 1） 請證實 AacAbcBaAdbed 是文法的一個句型。 2 ）寫出該句型的短語、直接短語、以及句柄。 3 ）為文法 GS每個產(chǎn)生式寫出相應的翻譯語義動作，使句型AacAbcBaAdbed經(jīng)該翻譯 方案后，輸出 131042521430。 5、寫出下列各式的逆波蘭表示 ( 1) -a-(b*c/(c-d) + (-

15、b)*a) (2) -A+B*Cf (D/E)/F 6、寫出表達式 A+B*(C-D)-E/Ff G 逆波蘭表示， 三元組表示， 四元組表示。 7、寫出當型語句 WHILE x+y 3 DO a:= a+3*b; b:= a + e- f*e 該語句的四元式形式為： 8、寫出條件語句 IF a0 THEN x:=x+1 ELSE x:=4*( x- 1) 四元式序列 9、 把語句：if A V BD then S1 else S2 翻譯成四元式序列。 第十章 目標程序運行時存儲空間組織課外訓練 (一) 內容 本章介紹目標程序運行時的存儲組織方式，包括靜態(tài)存儲分配和動態(tài)存儲分配。 (二) 本章重

16、點 靜態(tài)存儲分配，棧式存儲分配，嵌套過程的存儲實現(xiàn)。 (三) 本章難點 嵌套過程的存儲實現(xiàn)。 (四) 本章考點 目標程序運行時存儲空間的劃分。 活動記錄的內容。 嵌套過程的存儲實現(xiàn)(DISPLA丫表的使用)。 (五) 學習指導 要求掌握各種存儲組織形式的基本方法。在編譯過程生成目標代碼之前，需要把程序靜 態(tài)的正文和實現(xiàn)這個程序的動行的活動聯(lián)系起來， 弄清楚將來在代碼運行時刻， 源代碼中的 各種變量、 常量等用戶定義的量是如何存放的， 如何去訪問它們。 本章就目標程序運行時的 活動和運行環(huán)境進行討論， 主要討論存儲組織與管理， 包括活動記錄的建立與管理、 存儲器 的組織與存儲分配策略、非局部名稱

17、的訪問。 附訓練試題： 1 在編譯過程中， 嵌套調用的過程之間尋址問題如何解決？下面是一個示意性源程序，請給 出編譯期間棧式符號表的變化情況。 PROGRAM main a=10; b,c: integer; d,e: real; PROCEDURE p ( x:real ); f:real; PROCEDURE q (y:real); g=5; n:boolean; ?BEGIN IF e0 DO ; p （d）; ? END. main 2 對于下面程序： Procedure p （x,y,z） ; begin y:=y+1; z:=z+x; end; p begin a:=2; b:=3

18、; p （a+b , a , a） print a end. 若參數(shù)傳遞的方法分別為（1）傳名（2）傳地址（3）傳值。執(zhí)行時所輸出的a分別是 什么？ 第十一章 代碼優(yōu)化課外訓練 （一）內容 本章介紹優(yōu)化概述， 局部優(yōu)化，基本塊的劃分，基本塊的DAG表示及其應用，循環(huán)優(yōu)化。 （二）本章重點 基本塊的劃分，基本塊的 DAG表示及其應用。 （三）本章難點 循環(huán)優(yōu)化。 （四）本章考點 優(yōu)化的分類。 基本塊的DAG表示及其應用。 （五）學習指導 要求了解局部優(yōu)化的常用技術， 基本塊的DAG表示及其應用。編譯程序為了最終生成更有效 的目標代碼， 常常在中間代碼生成之后對中間代碼序列進行優(yōu)化。 本章就目標代碼生成之前 進行中間代碼優(yōu)化的技術進行討論，主要討論基于基本塊的局部優(yōu)化。 附訓練試題： 1試對以下基本塊