編譯原理課外訓(xùn)練體系

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

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

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

4、程的理論基礎(chǔ)，主要介紹與課程相關(guān)的形式語(yǔ)言的基本概念，包括符 號(hào)串的基本概念和術(shù)語(yǔ)、 文法和語(yǔ)言的形式定義、 推導(dǎo)與歸約、句子和句型、語(yǔ)法分析樹和 二義性文法等定義、文法和語(yǔ)言的Chomsky分類。 （二）本章重點(diǎn) 上下文無關(guān)文法，推導(dǎo)，句子和句型，文法生成的語(yǔ)言，語(yǔ)法分析樹和二義性文法。 （三）本章難點(diǎn) 上下文無關(guān)文法，語(yǔ)法分析樹，文法的分類。 （四）本章考點(diǎn) 上下文無關(guān)文法的定義。 符號(hào)串的推導(dǎo)。 語(yǔ)法分析樹的構(gòu)造。 （五）學(xué)習(xí)指導(dǎo) 要構(gòu)造編譯程序，就要把源語(yǔ)言用某種方式進(jìn)行定義和描述。學(xué)習(xí)高級(jí)語(yǔ)言的語(yǔ)法描述 是學(xué)習(xí)編譯原理的基礎(chǔ)。上下文無關(guān)文法及語(yǔ)法樹是本章學(xué)習(xí)的重點(diǎn)。語(yǔ)法與語(yǔ)義的概念；

5、 程序的在邏輯上的層次結(jié)構(gòu)； 文法的定義， 文法是一個(gè)四元組： 終結(jié)符號(hào)集， 非終結(jié)符號(hào)集， 開始符號(hào)、產(chǎn)生式集；與文法相關(guān)的概念，字符，正則閉包，積（連接），或，空集，產(chǎn)生 式，推導(dǎo)，直接推導(dǎo)，句子，句型，語(yǔ)言，最左推導(dǎo)，最右推導(dǎo)（規(guī)范推導(dǎo)）；學(xué)會(huì)用文法 來描述語(yǔ)言及通過文法能分析該文法所描述的語(yǔ)言； 語(yǔ)法樹及二義性的概念、 能通過畫語(yǔ)法 樹來分析一個(gè)文法描述的語(yǔ)言是否具有二義性；上下文無關(guān)文法的定義和正規(guī)文法的定義， 能判斷一個(gè)語(yǔ)言的文法是哪一類文法。 附訓(xùn)練試題： 1： 試構(gòu)造生成語(yǔ)言 L=a nbnci |n 1, i 0的文法解： 2： 已知語(yǔ)言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 問：此文法表式的語(yǔ)言是什么？ 4 請(qǐng)給出描述語(yǔ)言=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 求：出每個(gè)非終結(jié)符的 FIRSTVT集和LASTVT集，并構(gòu)造算符優(yōu)先關(guān)系矩陣。 3 考慮下面文法 G2: St a| A | (T) TT T, S | S (1) 給出(a,(a, a)

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

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

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

10、Ct cC 3) Ct d 6、對(duì)于文法 At aA|a構(gòu)造SLR分析表 7、設(shè)有文法 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òu)造文法 G(S )的 LR(1) 分析表： 8、設(shè)有文法 G(A) 1) A t A 2) A t BB 3) B t aB 4) B t b 構(gòu)造LALR(1)分析表 第八章語(yǔ)法制導(dǎo)翻譯和中間代碼的生成課外訓(xùn)練 抽 包括語(yǔ)法制 (一) 自學(xué)內(nèi)容 本章內(nèi)容圍繞語(yǔ)義分析展開，主要介紹屬性文法，語(yǔ)法制導(dǎo)翻譯與翻譯模式的計(jì)算， 象語(yǔ)法樹、 帶注釋的語(yǔ)法樹。 語(yǔ)義分析及中間代碼生成的設(shè)計(jì)原理和實(shí)

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

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

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

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

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

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

17、的訪問。 附訓(xùn)練試題： 1 在編譯過程中， 嵌套調(diào)用的過程之間尋址問題如何解決？下面是一個(gè)示意性源程序，請(qǐng)給 出編譯期間棧式符號(hào)表的變化情況。 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 對(duì)于下面程序： 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í)行時(shí)所輸出的a分別是 什么？ 第十一章 代碼優(yōu)化課外訓(xùn)練 （一）內(nèi)容 本章介紹優(yōu)化概述， 局部?jī)?yōu)化，基本塊的劃分，基本塊的DAG表示及其應(yīng)用，循環(huán)優(yōu)化。 （二）本章重點(diǎn) 基本塊的劃分，基本塊的 DAG表示及其應(yīng)用。 （三）本章難點(diǎn) 循環(huán)優(yōu)化。 （四）本章考點(diǎn) 優(yōu)化的分類。 基本塊的DAG表示及其應(yīng)用。 （五）學(xué)習(xí)指導(dǎo) 要求了解局部?jī)?yōu)化的常用技術(shù)， 基本塊的DAG表示及其應(yīng)用。編譯程序?yàn)榱俗罱K生成更有效 的目標(biāo)代碼， 常常在中間代碼生成之后對(duì)中間代碼序列進(jìn)行優(yōu)化。 本章就目標(biāo)代碼生成之前 進(jìn)行中間代碼優(yōu)化的技術(shù)進(jìn)行討論，主要討論基于基本塊的局部?jī)?yōu)化。 附訓(xùn)練試題： 1試對(duì)以下基本塊