編譯原理復習題2017含試卷共35頁

1、編譯原理復習題一簡答題：1) 什么是句子？ 什么是語言 ?解答：句子 設g是一個給定的文法， s是文法的開始符號，如果 s * x （其中 xvt *），則稱 x 是文法的一個句子。語言 語言是句子的集合?；?設gs 是給定 文 法 ，則由 文 法 g 所 定義的語言 l(g) 可 描 述為： l(g) x s x,x vt * 。2) dfa與 nfa有何區(qū)別?解答 :dfa 與 nfa的區(qū)別表現(xiàn)為兩個方面 : 一是 nfa可以有若干個開始狀態(tài)，而 dfa僅只有一個開始狀態(tài)。另一方面， dfa的映象 m是從 k×到 k，而 nfa的映象 m是從 k×到 k的子集，即映象

2、m將產生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。3) 自頂向下的語法分析方法的基本思想是什么 ?解答 : 從文法的開始符號開始 ，根據(jù)給定的輸入串并按照文法的產生式一步一步的向下進行直接推導，試圖推導出文法的句子，使之與給定的輸入串匹配。4) 自底向上的語法分析方法的基本思想是什么 ?解答 : 從給定的輸入串（終結符串）開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試圖歸約到文法的開始符號。5) 一個上下文無關文法 g包括哪四個組成部分？解答 : 一組非終結符號，一組終結符號，一個開始符號，以及一組產生式。6) 在自底向上的語法分析方法中，分析的關鍵是什么？解答: 關鍵是尋找句柄。7)

3、在自頂向下的語法分析方法中，分析的關鍵是什么？解答: 關鍵是選擇候選式。8）什么是屬性文法？答：是在上下文無關文法的基礎上，為每個文法符號 ( 含終結符和非終結符 ) 配備若干個屬性值 ，對文法的每個產生式都配備了一組屬性計算規(guī)則 ( 稱為語義規(guī)則 )。在語法分析過程中，完成語義規(guī)則所描述的動作，從而實現(xiàn)語義處理。一個屬性文法形式的定義為一個三元組 ag，ag=（g，v，e）。其中 g為一個上下文無關文法； v為屬性的有窮集； e為一組語義規(guī)則。9）語法制導翻譯語法制導翻譯：定義翻譯所必須的語義屬性和語義規(guī)則，一般不涉及計算順序。語法制導翻譯 (syntax-directed translat

4、ions) ： 一個句子的語義翻譯過程與語法分析過程同時進行。在文法中，文法符號有明確的意義，文法符號之間有確定的語義關系。屬性描述語義信息，語義規(guī)則描述屬性間的的關系，將語義規(guī)則與語法規(guī)則相結合，在語法分析的過程中計算語義屬性值。10）詞法分析的主要任務是什么？解答 : 詞法分析器的任務是對構成源程序的字符串從左到右逐個字符逐個字符地進行掃描，依次把它們識別為一個一個具有獨立意義的單詞，并確定其屬性，再轉換為長度統(tǒng)一的屬性字并輸出。 目標代碼11) 圖示運行時存儲空間的劃分（分為哪幾個區(qū)）。解答: 一般分為靜態(tài)區(qū)和動態(tài)區(qū)：靜態(tài)數(shù)據(jù)棧程序代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)堆12) 常用的中間語言種

5、類有哪幾種？解答: 常用的中間語言種類有逆波蘭表示、三元式、四元式和樹形表示。13）文法 g所描述的語言是什么的集合？解答: 是由文法的開始符號推出的所有終結符串的集合?；蛘f是句子的集合。14）喬姆斯基把文法分為四種類型，即 0 型、1 型、 2 型、 3 型。其中 2 型文法叫什么？解答: 2 型文法叫上下文無關文法。15）常見的動態(tài)存貯分配策略有哪兩種？解答: 常見的兩種動態(tài)存貯分配策略是棧式動態(tài)分配策略和堆式動態(tài)分配策略。16）語法分析的任務是什么？解答: 語法分析的任務是識別給定的終結符串是否為給定文法的句子。17）局部優(yōu)化是局限于一個什么范圍內的一種優(yōu)化？解答: 是局限于一個基本塊范

6、圍內的一種優(yōu)化。18）通常一個編譯程序中應包括哪七個部分？解答: 通常一個編譯程序中應包含詞法分析，語法分析，語義分析與中間代碼生成， 代碼優(yōu)化，目標代碼生成以及表格處理和出錯處理等七個部分。19）代碼優(yōu)化的主要目標是什么？解答: 代碼優(yōu)化的主要目標是如何提高目標程序的運行速度和如何減少目標程序運行時所需的空間。20）. 符號表的組織方式有哪幾種？答：一個編譯程序對符號表的總體組織可有三種選擇：第一種： 把屬性種類完全相同的那些符號組織在一起， 構造出表項是分別為等長的多個符號表。這樣組織的最大優(yōu)點是每個符號表的屬性個數(shù)和結構完全相同。則表項是等長的，并且表項中的每個屬性欄都是有效的，對于單個

7、符號表示來說，這樣使得管理方便一致，空間效率高。但這樣組織的主要缺點是一個編譯程序將同時管理若干個符號表，增加了總體管理的工作量和復雜度。而且對各類符號共同屬性的管理必須設置重復的運行機制。使得符號表的管理顯得臃腫。第二種： 把所有語言中的符號都組織在一張符號表中。 組成一張包括了所有屬性的龐大的符號表。這樣組織方式的最大優(yōu)點是總體管理非常集中單一，且不同種類符號的共同屬性可一致地管理和處理。這樣組織所帶來的缺點是，由于屬性的不同，為完整表達各類符號的全部屬性必將出現(xiàn)不等長的表項，以及表項中屬性位置的交錯重疊的復雜情況，這就極大地增加了符號表管理的復雜度。為使表項等長且實現(xiàn)屬性位置的唯一性，可

8、以把所有符號的可能屬性作為符號表項屬性。這種組織方法可能有助于降低符號表管理復雜性，但對某個具體符號，可能增加了無用的屬性空間，從而增加了空間開銷。第三種：折衷方式是根據(jù)符號屬性相似程度分類組織成若干張表，每張表中記錄的符號都有比較多的相同屬性。這種折衷的組織方式在管理復雜性及時空效率方面都取得折衷的效果，并且對復雜性和效率的取舍可由設計者根據(jù)自己的經(jīng)驗和要求及目標系統(tǒng)的客觀環(huán)境和需求進行選擇和調整。21）. 在整個編譯期間，對于符號表的操作有哪些？答：在整個編譯期間，對于符號表的操作大致可歸納為五類：· 對給定名字，查詢此名是否已在表中；· 往表中填入一個新的名字；

9、83; 對給定名字，訪問它的某些信息；· 對給定名字，往表中填寫或更新它的某些信息；· 刪除一個或一組無用的項。22）. 符號表的作用有哪些？答：在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關標識符的屬性信息，這些信息集中反映了標識符的語義特征屬性。起主要作用是： 收集符號屬性； 上下文語義的合法性檢查的依據(jù)； 作為目標代碼生成階段地址分配的依據(jù)。23）. 簡述優(yōu)化的原則是什么？答：編譯程序提供的對代碼優(yōu)化必須遵循的原則是：（1） 等價原則。經(jīng)過優(yōu)化后不應改變程序運行的結果。（2） 有效原則。使優(yōu)化后所產生的目標代碼運行時間較短，占用的存儲空間較小。（3） 合算原則。應盡可

10、能以較低的代價取得較好的優(yōu)化效果。24）簡述常用的優(yōu)化技術有哪些？答：編譯程序中常用的優(yōu)化技術有：刪除公共子表示式；復寫傳播；刪除無用代碼；代碼外提；強度削弱；刪除歸納變量；合并常量。25 ） . 何 謂 優(yōu) 化 ？ 按 所 涉 及 的 程 序 范 圍 可 分 為 哪 幾 級 優(yōu) 化 ？答：優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。26) 、編譯程序目標代碼運行時的存儲區(qū)通常被劃分為幾部分？答： 目標代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)、堆區(qū)。27) 、數(shù)組的內情向量包含哪些內容？在編譯程序對數(shù)組說明進行語義處理時， 須把數(shù)組的類

11、型 type 、維數(shù) n、各維的上、 下界 lk,uk等有關信息記錄下來。 此外 , 如果數(shù)組是常界的 , 還可將各維的界差 dk 以及計算數(shù)組元素地址的常量 c記錄下來。 為了便于引用， 通常是把上述信息存放于數(shù)組相應的“內情向量”之中 . 對數(shù)組內情向量的訪問 , 可通過數(shù)組在符號表中相應登記項的 addr域以間接尋址方式進行（即將其addr域作為指針用于存放內情向量的首地址）。28) 、文法分為幾種類型？其分類依據(jù)是什么？答：分為四類：短語文法（ 0 型文法）、前后文有關文法（ 1 型文法）、前后文無關文法（ 2 型文法）、正規(guī)文法（ 3 型文法）。分類依據(jù)：對產生式家約束。29) 、一

12、般來說編譯程序至少包含哪幾部分？各部分的作用是什么？答：詞法分析，語法分析，語義分析和目標代碼生成是必須的，代碼優(yōu)化是為了提高目標代碼的質量而引入的，不是必須的，沒有代碼優(yōu)化編譯程序同樣生成目標代碼。各部分的作用參見教材30）、分程序結構的棧式存儲管理中的活動記錄包括哪些內容？答：臨時工作單元、局部變量、保存機器狀態(tài)、存取鏈、控制鏈、實參，也稱形式單元、返回地址，保存該被調過程返回后的地址。31）、有人認為編譯程序的五個組成部分缺一不可，這種看法正確嗎？為什么？答：不正確詞法分析，語法分析，語義分析和目標代碼生成是必須的，代碼優(yōu)化是為了提高目標代碼的質量而引入的，不是必須的，沒有代碼優(yōu)化編譯程

13、序同樣生成目標代碼。二、應用題1） 寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以 0 開頭。解：文法 g(n)：nab|baac|db1|3|5|7|9db|2|4|6|8c0|d2）寫一個文法，使其語言是無符號二進制實數(shù)（不含指數(shù)）。解答 : 文法 g(n)：n l.l|ll lb|bb 0|13）給出上下文無關文法的定義。一個上下文無關文法 g是一個四元式 (vt， vn， s，p)，其中：v t是一個非空有限集，它的每個元素稱為終結符號；v n是一個非空有限集，它的每個元素稱為非終結符號， vtvn=；s 是一個非終結符號，稱為開始符號；p 是一個產生式集合 ( 有限 ) ，每個產生式的

14、形式是 p，其中， pvn， (vtvn)*。開始符號 s 至少必須在某個產生式的左部出現(xiàn)一次。4）給出正規(guī)式與正規(guī)集的遞歸定義。(1) 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為 和；(2) 任何 a， a 是上的一個正規(guī)式，它所表示的正規(guī)集為a ；(3) 假定 u和 v都是上的正規(guī)式， 它們所表示的正規(guī)集分別記為l(u) 和 l(v) ，那么，(u|v) 、(u· v)和(u)* 也都是正規(guī)式，它們所表示的正規(guī)集分別為 l(u) l(v) 、l(u)l(v)(連接積) 和(l(u)*(閉包 ) 。僅由有限次使用上述三步驟而得到的表達式才是上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是

15、上的正規(guī)集。5）設文法 g為：s aacb|bdsa bab|abc|ab asca|cab|b對于輸入串 aacabccb ，給出最左推導。答： s=>aacb=>aabccb=>aacabccb=>aacabccb=>aacabccb=>aacabccb6）設文法 g為：s baa bs|db aa|bs|c對于輸入串 adccd，給出最左推導。答： s=>ba=>aaa=>ada=>adbs=>adcs=>adcba=>adcca=>adccd7）給定正規(guī)文法 g:a bs as|ba|ba assbaa

16、請構造與之等價的有限自動機。f8）給定正規(guī)文法 g:s aaa ba|ab|bb aa請構造與之等價的有限自動機。bsaba f aa9）對下面給出的 nfa確定化。aa ba bs a faa 21bb3a4 a10）. 將文法 gs 改寫為等價的 gs ，使 gs 不含左遞歸和左公共因子。gs ： sbsae | baaab | d答： 文法 gs 改寫為等價的不含左遞歸和左公共因子的 g's 為：sbbbsae | aad a'a' ba' | 11） 消除下列文法 ga 的左遞歸。aaabbbbbccced dd(a) d解答：消除文法 ga 的左遞歸后

17、得到：a baa abab c bbbcbce ddd(a) d12） 正規(guī)式（ a|b ） * a(a|b) 構造一個等價的有限自動機。解答：aa,ba0 1 2b13）將下圖的 nfa確定化為 dfa。答： 用子集法確定化如下表i ia ib 狀態(tài)x,1,2 1,2. 1,2,3 x1,2. 1,2. 1,2,3 11,2,3 1,2,y 1,2,3 21,2,y 1,2. 1,2,3 3確定化后如下圖：14）. 已知文法 g(e)e t|e ttf|t *ff (e)|i(1) 給出句型 (t *f i) 的最右推導；(2) 給出句型 (t *f i) 的短語、簡單短語、句柄、素短語、最

18、左素短語。解：(1) 最右推導： e ->t->f->(e)->(e t)->(e f)->(e i)->(t i)->(t*f i)(2) 短語： (t*f i) ，t*fi ，t*f，i簡單短語： t*f,i句柄： t*f素短語： t*f,i最左素短語： t*f15）. 構造正規(guī)式 1(0|1)*101 相應的 dfa 。解：先構造 nfa ：確定化：重新命名，令 ab 為 b 、ac 為 c、aby 為 d 得：所以，可得 dfa 為：16）. 文法：s->mh|ah - >lso| k - >dml| l ->eh

19、fm->k|blm判斷 g 是否為 ll(1) 文法，如果是，構造 ll(1) 分析表。 解：各符號的 first 集和 follow集為：預測分析表由于預測分析表中無多重入口，所以可判定文法是 ll(1) 的17）. 對下面的文法 g ：e ->te'e'->+e| t ->ft't' ->t| f-> pf'f'-> *f'| p->(e)|a|b|(1) 計算這個文法的每個非終結符的 first 集和 follow集。 (4 分)(2) 證明這個方法是 ll(1) 的。(4 分)(3)

20、 構造它的預測分析表。 (2 分)解：（ 1）計算這個文法的每個非終結符的 first 集和 follow集。first 集合有：first(e)=first(t)=first(f)=first(p)=(,a,b,;first(e')=+, first(t)=first(f)=first(p)=(,a,b,;first(t')=first(t)u =(,a,b, ;first(f)=first(p)=(,a,b,;first(f')=first(p)=*, ;first(p)=(,a,b,;follow集合有：follow(e)=),#;follow(e')=f

21、ollow(e)=),#; follow(t)=first(e')ufollow(e)=+,),#;/ 不包含 follow(t')=follow(t)=first(e')ufollow(e)=+,),#;follow(f)=first(t')ufollow(t)=(,a,b,+,),#;/ 不包含 follow(f')=follow(f)=first(t')ufollow(t)=(,a,b,+,),#;follow(p)=first(f')ufollow(f)=*,(,a,b,+,),#;/ 不包含 (2) 證明這個方法是 ll(1)

22、的。各產生式的 select 集合有：e->te' ： first(t)=(,a,b,;e'->+e: first(+e ) =+;e'-> : follow(e')=),#t->ft': first(f)=(,a,b,;t'->t: first(t)=(,a,b,;t'- >: follow(t/)=+,),#;f->pf': first(p)=(,a,b,;f'->*f': first(*f)=*;f'-> : follow(f')=(,a,

23、b,+,),#;p->(e) first(e) =(p->a first(a )=ap->b first(b)=bp-> first()=可見，相同左部產生式 若不能推出為空，其產生式右部的交集均為空，相同左部產生式，若其中有一個能推出為空，其不能推出為空的產生式右部 first 集合和左部的 follow交集均為空，所以文法 ge 是 ll(1) 文法。(3) 構造它的預測分析表。 文法 ge 的預測分析表如下：18）設有文法 g:s s*f|ff fp|pp (s)|i 完成下列算符優(yōu)先關系表，并判斷是否為算符優(yōu)先文法（請說明理由）。* ( ) i #* ·

24、; · · · · · · · · · · · ( · · · ·) · · · · i · · · · # · · · · 由于該文法的任何產生的右部都不含兩個相繼的非終結符，故屬于算符文法。從上表可以看出，任何兩個終結符之間至少滿足、· 、· 三種關系之一，故 g為算符優(yōu)先文法。 給出句型 s*p(s)

25、對應的語法樹，指出該句型的短語、句柄ss * f短語： s*p(s) p (s) p (s) f p句柄: p ( s )p19） 已知文法 g(s)st | s-ttf | t / ff( s) | i（1）給出句型 t/ f-i 的最右推導；（2）畫出句型 t/f-i 規(guī)范規(guī)約的語法樹及算符優(yōu)先分析規(guī)約的語法樹框架；（3）給出句型 t / f-i 的短語、素短語。答：(1) 最右推導： etf(e) (et) (ef) (ei) (ti) (t*f i)(2) 略(3) 短語： (t*f i) ，t*fi ，t*f，i素短語： t*f, i20) 某語言的拓廣文法 g為：(0) s s(1

26、) s db|b(2) d d| (3) b ba| 證明 g不是 lr(0) 文法而是 slr(1) 文法，請給出 slr(1)分析表。答：拓廣文法 g'，增加產生式 s' s在項目集 i 0 中：有移進項目 d · d歸約項目 d · 和 b ·存在移進 -歸約和歸約 - 歸約沖突，所以 g不是 lr(0) 文法。若產生式排序為：(0) s' s(1) s db(2) s b(3) d d(4) d (5) b ba(6) b g的 lr(0) 項目集族及識別活前綴的 dfa如下圖：由產生式知follow(s)=#follow(d)=

27、bfollow(b)= a ,#在 i 0 中:follow(d) d= bd=follow(b) d= a ,#d=follow(d) follow(b)= b a ,#=在 i 3 中:follow(s)a=# a=所以在 i 0，i 3 中的移進 - 歸約和歸約 - 歸約沖突可以由 follow 集解決 , 所以 g是 slr(1) 文法,構造的 slr(1)分析表如下表：action goto 狀態(tài)b d a # s d b0 r4 s4 r6 r6 1 2 31 acc2 s53 s6 r24 r35 r16 r5 r521) 、下面文法 g 為:（0）e e（1）e r b（2）b

28、 b ; d（3）b d判斷 g 是 slr(1)還是 lr(1) ，說明理由，并構造相應的分析表i6:b b;d ?i3:e r b ?b b ?; di 1:e e ? i5:;db b; ?de bdi 0: r i2:e ? e e r?be ?r b b ?b;d b ?di4:b d ?狀態(tài) i3 中含項目：e rb· 為歸約項目b b· ; i 為移進項目所以 不是 lr(0) 文法follow(s)=# follow(s): 為空，所以該文法是 slr(1)文法。action goto 狀態(tài)r ; d # e b0 s2 11 acc2 s4 33 s5 r

29、 14 r 3 r 35 s66 r 2 r 222) 、設文法 g(s)：s(f) |d s |dff ; s | s(1) 消除左遞歸和回溯；(2) 列出第一小題完成后的文法，并計算每個非終結符的 first 和 follow；(3) 構造預測分析表。解：(1) s( f) sds ss s 2 分f sf f ， s f f 2 分評分細則：消除左遞歸2 分，提公共因子 2 分。(2) first(s) ( ，d follow(s) # , ，, ) first(s) d , follow(s) # , ，, ) first(l) ( ，d follow(l) )first(l) ，,

30、follow(l ) 3 分因為：first ( s(f) first ( sds)=first ( ss ) follow (s )= first (f ， s f ) first (f )= 所以，此文法是 ll(1) 文法(4)預測分析表d ， ( ) #s ds (f)s s s f sf sff ，s f 23）. 設有基本塊：(1) a:=b-c (6) c:=b-f(2) d:=a+4 (7) b:=b-c(3) e:=a-b (8) f:=b+f(4) f:=a+4 (9) a:=a-f(5) b:=b+c(1) 畫出 dag圖；(2) 假設基本塊出口時只有 a，b 還被引用，

31、請寫出優(yōu)化后的三地址代碼序列。解答：(1) 給出 dag如右：(2) 重寫三地址代碼如下：a:=b-cd:=a+4e:=a-bf:=db:=b+cc:=b-fb:=b-cf:=b+fa:=a-f24）. 設有基本塊t1： 2t2： 10/t 1t3： srt4： sra：t2 * t 4b：at5： srt6： t3 * t 5b： t6(1) 畫出 dag圖；(2) 假設基本塊出口時只有 a，b還被引用，請寫出優(yōu)化后的三地址代碼序列。解： (1)dag：見右圖(2)優(yōu)化后的四元式t3： srt4： sra： 5*t 4b： t3t425）將下面的條件語句表示成四元式序列：if a>b

32、then x:=a+b*c else x:=b-a;答：(1) ( j>, a, b, (3)(2) ( j, , , (7) )(3) ( *, b, c, t1)(4) ( +, a, t1, t2)(5) ( :=, t2, , x)(6) ( j, , , (9)(7) ( -, b, a, t3)(8) ( :=, t3, , x)(9) ( )26）翻譯成四元式序列。while a 0 b 0 dobeginx ： x 1；if a 0 then a ： a1else b ： b1end；答：(1) (j ， a，0，5)(2) (j ， 3)(5) ( ，×， 1

33、，t1)(6) ( ：， t1，× )(7) (j ， a，0，9)(8) (j ， 12)(9) ( ， a，1，t2)(10) ( ：， t2， a)(11) (j ， 1)(12) ( ， b，1， t3)(13) ( ：， t3， b)(14) (j ， 1)(15)27）設有基本塊：t1:=3*at2:=2*ct3:=t1+t2t4:=t3+5t5:=2*ct6:=3*at7:=t6+t5e:=t7-1f:=t4-ea) 畫出 dag圖；b) 假設基本塊出口時只有 e，f還被引用，請寫出優(yōu)化后的三地址代碼序列。解答：a) 構造 dag：見右圖。f n12en11n9 n10

34、 t4 1+ t3,t7n7b) 優(yōu)化后的三地址代碼序列為：t1:=3*at2:=2*ct3:=t1+t2t4:=t3+5e:=t3-1f:=t4-e五、填空題 :1. 編譯程序的工作過程一般可以劃分為 詞法分析 , 語法分析 , 語義分析，之間代碼生成 , 代碼優(yōu)化 等幾個基本階段 , 同時還會伴有 表格處理 和 出錯處理 .2. 若源程序是用高級語言編寫的 , 目標程序是 機器語言程序或匯編程序 , 則其翻譯程序稱為編譯程序 .3. 對編譯程序而言 , 輸入數(shù)據(jù)是 源程序 , 輸出結果是 目標程序 .4. 一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標代碼生

35、成等五個部分，還應包括表格處理和出錯處理。其中，詞法分析器用于識別 單詞 。5. 所謂最右推導是指： 任何一步 都是對中最右非終結符進行替換的 。6. 一個上下文無關文法所含四個組成部分是 一組終結符號、 一組非終結符號、 一個開始符號、一組產生式 。7. 產生式是用于定義 語法成分 的一種書寫規(guī)則。8. 設 gs 是 給 定 文 法 ， 則 由 文 法 g 所 定 義 的 語 言 l(g) 可 描 述 為 ： l(g) x s x,x vt * 。9.設g是一個給定的文法， s 是文法的開始符號，如果s x（其中 xv *），則稱 x 是文法的一個句型 。10.設g 是 一 個給定 的 文

36、法 ， s 是 文 法 的 開 始 符 號 ， 如 果s x( 其中 xvt * ),則稱 x 是文法的一個句子。11.語法分析最常用的兩類方法是 自上而下 和 自下而上 分析法。12.語法分析的任務是識別給定的終極符串是否為給定文法的句子。13. 自頂向下的語法分析方法的關鍵是 如何選擇候選式 的問題。14. 自頂向下的語法分析方法的基本思想是： 從文法的 開始符號 開始， 根據(jù)給定的輸入串并按照文法的產生式一步一步的向下進行直接推導，試圖推導出文法的 句子 ，使之與給定的輸入串匹配。15. 自底向上的語法分析方法的基本思想是： 從給定的終極符串開始， 根據(jù)文法的規(guī)則一步一步的向上進行直接歸

37、約，試圖歸約到文法的 開始符號 。16. 自底向上的語法分析方法的基本思想是： 從輸入串入手， 利用文法的產生式一步一步地向上進行 直接歸約 ，力求歸約到文法的 開始符號 。17. 在 l r（0）分析法的名稱中， l 的含義是 自左向右的掃描輸入串 ，r的含義是 最左歸約，0 的含義是 向貌似句柄的符號串后查看 0 個輸入符號 。18. 在 slr（1）分析法的名稱中， s 的含義是簡單的 。19. 所謂屬性文法是 一個屬性文法是一個三元組： a（ g，v，f），一個上下文無關文法 g；一個屬性的有窮集 v 和關于屬性的斷言或謂詞的有窮集 f。每個斷言與文法的某產生式相聯(lián)。19.綜合屬性是用

38、于 “自下而上”傳遞信息。20.繼承屬性是用于 “自上而下”傳遞信息。21. 符號表中的信息欄中登記了每個名字的 屬性和特征等有關信息 ，如類型、 種屬、所占單元大小、地址等等。22. 常用的兩種動態(tài)存貯分配辦法是棧式動態(tài)分配和 堆式動態(tài)分配。23. 局部優(yōu)化是局限于一個 基本塊 范圍內的一種優(yōu)化。24. 代碼優(yōu)化的主要目標是如何提高 目標程序的運行速度 和如何減少 目標程序運行時所需的空間 。編譯原理期末考試試卷（ a 卷）一、簡述編譯程序的工作過程。（ 10）編譯程序的工作過程，是指從輸入源程序開始到輸出目標程序為止的整個過程，是非常復雜的，就其過程而言，一般可以劃分為五個工作階段：詞法分

39、析，對構成源程序的字符串進行掃描和分解，識別出一個個的單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位；語義分析與中間代碼產生，即對各類語法單位，分析其漢一并進行初步翻譯；代碼優(yōu)化，以期產生更高效的代碼；目標代碼生成，把中間代碼變換成特定機器上的低級語言指令形式。二、給出下面的正規(guī)表達式（ 15）（1） 以 01 結尾的二進制數(shù)串；（2） 能被 5 整除的十進制整數(shù)；（3） 包含偶數(shù)個 1 或偶數(shù)個 0 的二進制數(shù)串。（1）（0|1）*01（2）digit=0|1|2|3|4|5|6|7|8|9digit* （0|5）（3）（ 0*10*1 ）*0* ）|（1*01*0 ）*

40、1* ）三、對下面的文法 g：sa | b | （t）tt，s | s(1) 消去文法的左遞歸，得到等價的文法 g2；(2) 判斷文法 g2 是否 ll （1）文法，如果是，給出其預測分析表。（ 15）g2：sa | b | （t）t stt ， s t | g2 是 ll（1）文法。a b （ ） ， #s sa sb s（t）t t st t st t stt t t ， st四、對下面的文法 g：sabaa00 | 0bb11 | 1(1) 消去文法的左遞歸，得到等價的文法 g2；(2) 判斷文法 g2 是否 ll （1）文法，如果是，給出其預測分析表。（ 15）g： saba 0aa

41、00a | b 1bb 11b | 文法 gs 是 ll(1) 文法。預測分析表：0 1 #s saba a0aa a00a ab b1bb b11b b五、設有文法 ga ：abcc | gdbbbcde | cdab | caddd |egaf | c(1) 計算該文法的每一個非終結符的 first 集和 follow 集；(2) 試判斷該文法是否為 ll （1）文法。（ 15）first followa a,b,c,d,gb b a,c,dc a,c,d c,d,gd d a,b,c,ge c,g（2） 是 ll（1）文法。編譯原理期末考試試卷（ b卷）三、應用題（ 1、4、5 每題 1

42、0 分，2、3 每題 15 分，共 60 分）1、為正規(guī)式 (a|b)*a(a|b) 構造等價且狀態(tài)最少的確定有限自動機。（要求給出主要步驟）2、有文法如下：s baa bs | db aa | bs | c(1). 計算文法的每個非終結符的 first 和 follow集合；(2). 判斷文法是否 ll（1）文法，如果是，給出其預測分析表，否則說明理由。4、有文法如下：t t*f | ff p f | pp (t) | i證明 t*i p是該文法的一個句型，但不是規(guī)范句型；指出 t*i p 的所有短語、直接短語、素短語、句柄。三、應用題（ 1、4、5 每題 10 分，2、3 每題 15 分，共 60 分）1、對于符號串 t*i p存在如下推導：（或畫一顆語法樹證明是句型）t t*f t*p f t*p p t*i