大連理工大學(xué)編譯原理復(fù)習(xí)Word版

《大連理工大學(xué)編譯原理復(fù)習(xí)Word版》由會員分享，可在線閱讀，更多相關(guān)《大連理工大學(xué)編譯原理復(fù)習(xí)Word版（68頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！ 編譯技術(shù)命題指導(dǎo)意見 教學(xué)內(nèi)容 知識點及題型 第一章 編譯器概述 A （1）編譯的階段劃分 [選擇題 2分] [1] 編譯程序絕大多數(shù)時間花在( )上。 A. 出錯處理 B. 詞法分析 C. 目標(biāo)代碼生成 D. 符號表管理 答案：D [2] ( ) 和代碼優(yōu)化部分不是每個編譯程序都必需的。 A. 語法分析 B. 中間代碼生成 C. 詞法分析 D. 代碼生成 答案：B [3] 編譯程序前三個階段完成的工作是( )。 A. 詞法分析、語法分析和代碼優(yōu)化 B. 代碼

2、生成、代碼優(yōu)化和詞法分析 C. 詞法分析、語法分析和語義分析 D. 詞法分析、語法分析和代碼生成 答案：C （2）遍的概念 [填空題 2分] [1] 編譯階段的活動常用一遍掃描來實現(xiàn)，一遍掃描包括 和 。 答案：讀一個輸入文件 寫一個輸出文件 [2] 將編譯程序分成若干個“遍”是為了________。 答案：使程序的結(jié)構(gòu)更加清晰 [3] 編譯器從邏輯上可以分為7個階段，其中，可以作為一個后端遍的是___________階段。 答案：代碼生成 （3）前端和后端的劃分 [簡答題 5分] [1] 什

3、么是前端？ [5分] 答案：編譯器分成分析和綜合兩大部分。分析部分揭示源程序的基本元素和它們所形成的層次結(jié)構(gòu)，決定它們的含義，建立起源程序的中間表示，分析部分經(jīng)常被稱為前端。 [2] 什么是后端？ [5分] 答案：編譯器分成分析和綜合兩大部分。綜合部分從源程序的中間表示建立起和源程序等價的目標(biāo)程序，它經(jīng)常被稱為后端。 [3] 什么是前端？什么是后端？ [5分] 答案

4、：編譯器分成分析和綜合兩大部分。分析部分揭示源程序的基本元素和它們所形成的層次結(jié)構(gòu)，決定它們的含義，建立起源程序的中間表示，分析部分經(jīng)常被稱為前端。綜合部分從源程序的中間表示建立起和源程序等價的目標(biāo)程序，它經(jīng)常被稱為后端。 第二章2.1 2.2 詞法記號的定義及描述 B （1）詞法分析器的功能 [選擇題 2分] [1] 詞法分析程序的輸出結(jié)果是（ ）。 A. 單詞的種別編碼 B. 單詞在符號表中的位置 C. 單詞的種別編碼和單詞屬性值 D. 單詞的單詞屬性值 答案：C [2] 詞法分析器用于識別_____。 A. 字符串 B．語句 C．單

5、詞 D．標(biāo)識符 答案：C [3] 掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即（ ）。 A． 字符 B．單詞 C．句子 D．句型 答案：B （2）詞法記號概念及屬性 [填空題2分] [1] 詞法記號是由 和 構(gòu)成的二元組。 答案：記號名 屬性值 [2] 詞法單元是源程序中匹配一個 的字符序列。 答案：記號模式 [3] 影響語法分析的決策， 影響記號的翻譯。 答案：記號名 屬性 （

6、3）正規(guī)式與語言的對應(yīng)關(guān)系 [選擇題 2分] [1] 下面文法（ ）和正規(guī)表達(dá)式a*b描述的語言相同。 A. S→ab | aSb B. S→b | aS C. S→a | aSb D. S→a | Sb 答案：B [2] 最多包含兩個a的{a,b}上的語言（ ）。 A. (a|ε)b*(a|ε) B. b*ab*ab*|b*ab* C. b*(a|b*)(a|b*)b* D. b*(a|ε)b*(a|b*)b* 答案：D [3] 與(a|b)*等價的正規(guī)式是（ ）。 A. (a*|b*)* B. (a|b)+ C. (ab)* D. a*

7、|b* 答案：A 第二章2.3.1,2.3.2 NFA,DFA C （1）NFA與DFA的概念 [選擇題 2分] [1] 有如圖所示的有窮自動機，與之等價的正規(guī)式為（ ）。 A. (0|1)*(000|111)(0|1) B. (0|1) (000|111)(0|1) C. (0|1)*(000|111)(0|1) * D. Ａ，B ，C選項都不正確 答案：C [2] 對于NFA和DFA模型說法錯誤的是（ ）。 A. DFA是NFA的特殊形式 B. DFA與NFA的狀態(tài)轉(zhuǎn)換完全相同 C. 都有唯一的開始狀態(tài) D. 都可以有多個接受狀態(tài) 答案：B [3]

8、對于DFA模型，說法錯誤的是（ ）。 A. DFA從任何狀態(tài)出發(fā)，對于任何輸入符號，可有多個轉(zhuǎn)換 B. 任何狀態(tài)都沒有ε轉(zhuǎn)換 C. DFA有唯一的開始狀態(tài) D. DFA可以有多個接受狀態(tài) 答案：A （2）NFA 的構(gòu)造 [簡答題 10分] [1] 設(shè)有非確定的有自限動機NFA M=({A，B，C}，{0，1}，d，{A}，{C})，其中： d (A，0)={C} d (A，1)={A，B} d (B，1)={C} d (C，1)={C}。請畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。 答案： 狀態(tài)轉(zhuǎn)換距陣為： d 0 1 A C A，B B

9、Æ C C Æ C 1 1 0 1 1 狀態(tài)轉(zhuǎn)換圖為： [2] 構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101。 答案： [3] 為（（ε|a）b*）* 構(gòu)造非確定的有限自動機，給出它們處理輸入串a(chǎn)babbab的轉(zhuǎn)換序列。 答案： 輸入串a(chǎn)babbab的轉(zhuǎn)換序列： 0 1456789 145678 789 1456789 10 或者 0 1456789 1456789 1236789 1456789 10 （3）NFA轉(zhuǎn)化為 DFA [簡答題 10分] [1]

10、設(shè)S={0，1}上的正規(guī)集S由倒數(shù)第二個字符為1的所有字符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(guī)集的DFA。 答案：構(gòu)造相應(yīng)的正規(guī)式：(0|1)*1(0|1) NFA: 確定化： I {0,1,2} {1,2} {1,2,3} {1,2} {1,2} {1,2,3} {1,2,3} {1,2,4} {1,2,3,4} {1,2,4} {1,2} {1,2,3} {1,2,3,4} {1,2,4} {1,2,3,4} 、 [2] 構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的DFA。 答案：先構(gòu)造N

11、FA： 確定化： 重新命名，令A(yù)B為B、AC為C、ABY為D得： 所以，可得DFA為： [3] 對于下圖所示NFA，回答下列問題： （1）用正規(guī)式描述該有限自動機所表示的語言。 （2）由NFA轉(zhuǎn)為DFA。 （3）構(gòu)造最簡DFA。 答案： （1）(a|b)*a(a|b)* （2） （3） （4）DFA的化簡 [簡答題 10分] [1] 已知 NFA= （ {x,y,z},{0,1},M,{x},{z} ），其中： M(x,0)={z}, M(y,0)={x,y}, M(z,0)={x

12、,z}, M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 構(gòu)造相應(yīng)的DFA并最小化。 答案：根據(jù)題意有NFA圖: 下表由子集法將NFA轉(zhuǎn)換為DFA： 面將該DFA最小化： (1) 首先將它的狀態(tài)集分成兩個子集：P1={A,D,E},P2={B,C,F} (2) 區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21={C,F},P22={B}。 (3) 區(qū)分P1:由于

13、A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價，所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P={{A}，{B}，{D}，{E}，{C，F(xiàn)}}。所以最小化的DFA如下： [2] 給定下列自動機： 把此自動機轉(zhuǎn)換為確定自動機DFA。 答案： 有狀態(tài)矩陣如圖： 從而可得DFA如圖： [3] （1）將下圖中的NFA M確定化為DFA M’。 （2）將DFA M’化簡。 答案： 確定化: a

14、 b {0} {0,1} {1} {1} {0} --- {0，1} {0,1} {1} 狀態(tài)編號 a b 0 1 2 2 0 --- 1 1 2 1 0 a --> a a 2 b b 未簡化的DFA 最小化： 分為：終態(tài)集{0,1} 非終態(tài)集{2} {0,1}a ={1} {0,1}b = {2} 所以

15、：{0,1} = ｛0｝ ｛2｝ = ｛1｝ 1 0 a --> b a 第二章2.4,2.5 詞法分析器的生成器; 第二章習(xí)題 D （1）直接從語言構(gòu)造DFA [簡答題5分] [1] 寫出能產(chǎn)生字母表{x,y}上的不含兩個相鄰的x,且不含兩個相鄰的ｙ的全體符號串的有限狀態(tài)自動機。 答案： [2] 處于/* 和 */之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。 答案： 1 2 4 start 5 2 others others /

16、* * * / [3] 有語言 L={w|w ∈ (0,1)+，并且 w 中至少有兩個1 ，又在任何兩個1之間有偶數(shù)個 0 }，試構(gòu)造接受該語言的確定有限狀態(tài)自動機。 答案： （2）Lex 的功能 [填空題 2分] [1] Lex是從基于正規(guī)式的描述來構(gòu)造 。 答案：詞法分析器 [2] Lex程序包含三部分： 、 和輔助函數(shù)。 答案：聲明 翻譯規(guī)則 [3] 由Lex建立的 分析器通常作為 分析器的一個子程序。 答案：詞法 語法 第三章 3.1上下文無關(guān)文法

17、 E （1）上下文無關(guān)文法定義[選擇題2分]； [1] 一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組（ ）。 A. 句子 　 　　 B. 句型 　 C. 單詞 　　　 D. 產(chǎn)生式 答案：D [2] 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是（ ）。 A. 短語文法    　　　 B. 正則文法     C . 上下文有關(guān)文法　　　 D. 上下文無關(guān)文法 答案：D [3] 文法分為四種類型，即0型、1型

18、、2型、3型。其中0型文法是_____。 A. 短語文法 B. 正則文法 C. 上下文有關(guān)文法 D. 上下文無關(guān)文法 答案：A （2）最左推導(dǎo)、最右推導(dǎo)[簡答題5分]； [1] 文法 S->a|^|(T) T->T,S|S 對 (a,(a,a) 和 (((a,a),^,(a)),a) 的最左推導(dǎo)。 答案： 對(a,(a,a)的最左推導(dǎo)為： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)

19、) =>(a,(a,a)) 對(((a,a),^,(a)),a) 的最左推導(dǎo)為： S=>(T) =>(T,S) =>(S,S) =>((T),S) =>((T,S),S) =>((T,S,S),S) =>((S,S,S),S) =>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =&g

20、t;(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) [2] 設(shè)文法G[E]: E → RP|P P → (E)|i R → RP+| RP* |P+|P* 對i+i*(i+i)的最右推導(dǎo)。 答案： EÞ RP Þ R(E) Þ R(RP) Þ R(Ri) Þ R(P+i) Þ R(i+i) Þ RP*(i+i) Þ Ri*(i+i) Þ P+i*(i+i) Þ i+i*(i

21、+i [3] 考慮文法S->aSbS | bSaS |ε （a） 為句abab構(gòu)造兩個不同的最左推導(dǎo)，以此說明該文法是二義的。 （b） 為abab構(gòu)造對應(yīng)的最右推導(dǎo)。 答案： （3）分析樹[簡答題5分]； [1] 考慮文法S->aSbS | bSaS |ε （1） 為abab構(gòu)造對應(yīng)的分析樹。 （2） 這個文法產(chǎn)生的語言是什么？ 答案： E T F ( E ) E + T F i T T * F （1） （2）該文法產(chǎn)生 a、b 個數(shù)相等的 ab 串（含空串） [2] 對于文法G(E): E

22、4;T|E+T T®F|T*F F®(E)|i 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。 答案： （1）EÞTÞFÞ(E) Þ(E+T) Þ(E+F) Þ(E+i) Þ(T+i) Þ(T*F+i) （2）語法樹如右圖。 [3] 令文法G[S]為： S→AB A→aAb | ab B→b, （1）G[S]定義的語言L(G)是什么？ （2）給出句子aabbb的最左推導(dǎo)，并給出其語法分析樹。 答案： （1）SàabBàabb

23、SàaAbBàaabbBàaabbb SàaAbBàaaAbbBàaaabbbBàaaabbbb …… Sàanbm(n>=0,m>=1) （2）s àABàaAbBàaabbBàaabbbb /. （4）二義性概念[選擇題2分] [1] 如果文法G是無二義的，則它的任何句子α（ ）。 A. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 　　 B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同 　　 C. 最左推導(dǎo)和最右推導(dǎo)必定相同 &

24、#160; 　　 D. 可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同 答案：A [2] 如果一個文法G是無二義性文法，對于任何一個句子，該句子（ ）。 A. 可能存在兩個不同的最左推導(dǎo) B. 可能存在兩個不同的最右推導(dǎo) C. 最左推導(dǎo)和最右推導(dǎo)不同 D. 僅存在一個最左推導(dǎo)和一個最右推導(dǎo) 答案：D [3] 若文法 G 定義的語言是無限集，則文法必然是（ ）。  A. 遞歸的   　 　 B. 前后文無關(guān)的　 C. 二義性的 　　 D. 無二義性的 答案：A 第三章 3.2 語言和文法 F （1）消除左遞歸[填空

25、題2分]； [1] 一個文法是左遞歸的，如果它有非終結(jié)符A，對某個串a(chǎn)，存在推導(dǎo) 。 答案：A=>+Aa [2] 的分析方法不能用于左遞歸文法，因此需要消除左遞歸。 答案：自上而下 [3] 由形式為A->Aa的產(chǎn)生式引起的左遞歸稱為 。 答案：直接左遞歸 （2）提取左因子[填空題2分]； [1] 提取左因子用于產(chǎn)生適合于 的文法。 答案：自上而下 [2] A->aB|aC，經(jīng)過提取左因子，原來的產(chǎn)生式成為 和 。 答案：A->aA’ A’-&

26、gt;B|C [3] 對于懸空else的文法 stmt->if expr then stmt else stmt | if expr then stmt | other 提取左因子后的文法成為 和 。 答案：stmt->if expr then stmt optional_else_part | other optional_else_part->else |ε （3）形式語言鳥瞰[選擇題2分]； [1] Chomsky把文法分為4種類型，其中描述能力最強的是（ ）。 A. 0型 B.

27、 1型 C. 2型 D. 3型 答案：A [2] 文法分為四種類型，即0型、1型、2型、3型。其中1型文法是（ ）。 A. 短語文法    　　　 B. 正則文法     C. 上下文有關(guān)文法　　　 D. 上下文無關(guān)文法 答案：C [3] 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是（ ）。 A. 短語文法 B. 正則文法 C. 上下文有關(guān)文法 D. 上下文無關(guān)文法 答案：B 第三章 3.3 自上而下分析 G （1）LL(1)文法概念[選擇題2分]； [1] 3在下面

28、的各種編譯方法中，屬于自頂向下的語法分析算法的是（ ）。 A. LL(1)分析方法 B. LR(K) 分析方法 C. SLR分析方法 D. LALR(1) 分析方法 答案：A [2] LL(1)分析法的名字中，第二個“L”的含義是（ ）。 A. 自左向右進行掃描 B. 每次采用最左推導(dǎo) C. 采用最右推導(dǎo)的逆過程——最左規(guī)約 D. 向輸入串中查看一個輸入符號 答案：B [3] LL(1)分析法的名字中，第一個“L”的含義是（ ）。 A. 自左向右進行掃描 B. 每次采用最左推導(dǎo) C. 采用最右推導(dǎo)的逆過程——最左規(guī)約 D. 向輸入串中查看一個輸入符

29、號 答案：A （2）構(gòu)造預(yù)測分析表（包括求FIRST、FOLLOW集）[簡答題10分]； [1] 設(shè)文法 G(S)： S→S ＋ aF|aF| ＋ aF F→*aF|*a （1）消除左遞歸和回溯； （2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合。 答案： （1） 　　 S->aFS'|＋aFS' 　　 　　 S'->＋aFS'|ε 　　 　　 F->*aF' 　　 　　 F'->F|ε （2） FIRST（S）＝｛a，+｝ 　 FOLLOW（

30、S）＝｛＃｝ 　 FIRST（S'）＝｛+，ε ｝ FOLLOW（S'）＝｛＃｝ 　 FIRST（F）＝｛*｝ 　　 FOLLoW（F）＝（+，＃｝ 　 FIRST（F'）＝｛*，ε｝ FOLLOW（+，＃｝ [2] 文法： S->MH|a H->LSo| ε K->dML| ε L->eHf M->K|bLM 判斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1) 分析表。 答案： 各符號的FIRST集和FOLLOW集為： 預(yù)測分析表為： 由于預(yù)測分析表中無多

31、重入口，所以可判定文法是LL(1)的。 [3] 請給對文法G[S]進行改寫成LL（1）文法，并給出改寫后文法的預(yù)測分析表，要求計算出改寫后文法各非終極符的FIRST和FOLLOW集合。 S → S*aA | aA| *aA A→ +aA | +a 答案： 改寫文法如下： Sà*aAS’ | aAS’ S’à*aAS’ | e Aà+aA’ A’àA | e FIRST FOLLOW S {*，a} {#} S’ {*,e} {#} A {+

32、} {*,#} A’ {+,e} {*,#} 預(yù)測分析表： * a + # S Sà*aAS’ Sà aAS S’ S’à*AS’ S’àe A Aà+aA’ A’ A’àe A’àA A’àe （3）用預(yù)測分析表對輸入串進行分析的過程[簡答題5分]； [1] 給定LL(1)分析表： 有輸入符號串i+i*i，寫出按上述算法識別此符號串的過程。 答案： [2] 已知文法分析表： i + * (

33、 ) # - / E E->TG E->TG G G->+TG G->ε G->ε G->-TG T T->FS T->FS S S->ε S->*FS S->ε S->ε S->ε S->/FS F F->i F->(E) 有輸入符號串i-i//i#，寫出按上述算法識別此符號串的過程，遇到錯誤停止即可，不需要錯誤恢復(fù)。 答案： 步驟

34、分析棧 剩余字符 所用產(chǎn)生式 0 #E i-i//i# E->TG 1 #GT i-i//i# T->FS 2 #GSF i-i//i# F->i 3 #GSi i-i//i# i匹配 4 #GS -i//i# S->^ 5 #G -i//i# G->-TG 6 #GT- -i//i# -匹配 7 #GT i//i# T->FS 8 #GSF i//i# F->i 9 #

35、GSi i//i# i匹配 10 #GS //i# S->/FS 11 #GSF/ //i# /匹配 12 #GSF /i# F出錯 [3] 已知文法分析表： a $ ( ) , # S →a →$ →(T) T →SF →SF →SF F →ε →,SF 有輸入符號串(a,(a))#，寫出按上述算法識別此符號串的過程。 答案： 步驟 分析棧 剩余字符 所用產(chǎn)生式 0 #S

36、 (a,(a))# S->(T) 1 #)T( (a,(a))# (匹配 2 #)T a,(a))# T->SF 3 #)FS a ,(a))# S->a 4 #)Fa a,(a))# a匹配 5 #)F ,(a))# F->,SF 6 #)FS, ,(a))# ,匹配 7 #)FS (a))# S->(T) 8 #)F)T( (a))# (匹配 9

37、#)F)T a))# T->SF 10 #)F)FS a))# S->a 11 #)F)Fa a))# a匹配 12 #)F)F ))# F->^ 13 #)F) ))# )匹配 14 #)F )# F->^ 15 #) )# )匹配 16 # # acc! 第三章 3.4自下而上分析 H （1）歸約概念[選擇題2分]； [1] 若a為終結(jié)符，則A->α &#

38、183; aβ為_____項目。 A. 歸約 B. 移進 C. 接受 D. 待約 答案：B [2] 移近-歸約分析為輸入串構(gòu)造分析樹是從（ ）開始的。 A. 根結(jié)點 B. 葉結(jié)點 C. 中間結(jié)點 D. 任一結(jié)點 答案：B [3] 在每一步歸約中，一個子串和某個產(chǎn)生式的（ ）匹配，然后用該產(chǎn)生式的（ ）符號代替這個子串。 A. 右部 左部 B. 右部 右部 C. 左部 右部 D. 左部 左部 答案：A （2）句柄概念[選擇題2分]； [1] 在規(guī)范歸約中，用（ ）來刻畫可歸約串。 A. 直接短語 B. 句柄 C. 產(chǎn)生式

39、 D. 記號 答案：B [2] 下面說法正確的是（ ）。 A. 句柄是該句型中和一個產(chǎn)生式左部匹配的子串 B. 文法是二義的，句柄是唯一的 C. 文法無二義時，句柄可能是唯一的 D. 以上說法都不對 答案：D [3] 面說法錯誤的是（ ）。 A. 句柄是該句型中和一個產(chǎn)生式右部匹配的子串 B. 文法是二義的，句柄可能不唯一 C. 文法無二義時，句柄是唯一的 D. 句型中能和產(chǎn)生式A->β右部匹配的最左子串β就是句柄 答案：D 第三章 3.5 LR分析器 I （1）活前綴概念[選擇題2分]； [1]一個句型中的活前綴為（） A. 短語

40、 B.簡單短語 C.句柄 D.右句型的前綴，該前綴不超過最右句柄的右端 答案：D [2]在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型 ( ) 的DFA狀態(tài)。 A.句柄             B. 前綴           C. 活前綴          D. LR(0)項目 答案：C [3]下列語句描述錯誤的是（） A.活前綴不包含句

41、柄的任何符號，此時期待從輸入串中看到該句柄對應(yīng)的產(chǎn)生式的右部所推導(dǎo)出的符號串 B.活前綴只包含句柄的一部分符號，表明該句柄對應(yīng)的的產(chǎn)生式的右部子串已出現(xiàn)在棧頂，期待從輸入串中看到推導(dǎo)出的符號串 C.活前綴已含有句柄的全部符號，表明該句柄對應(yīng)的產(chǎn)生式的右部已出現(xiàn)在棧頂 D.活前綴只包含句柄的一部分符號，表明該句柄對應(yīng)的產(chǎn)生式的右部已出現(xiàn)在棧頂 答案：D （2）構(gòu)造SLR分析表[簡答題20分]； [1] 給定下列文法構(gòu)造其SLR分析表 E ® E + T F ® F*

42、E ® T F ® a T ® T F F ® b T ® F [2] 考慮文法E ® EE +|EE*|a，構(gòu)造它的SLR分析表 [3]設(shè)有文法 S®rD D®D,i|i (1)證明該文法不是LR(1)文法，是SLR文法 (2)給出該文法的SLR分析表 答案：(1)構(gòu)造活前綴的

43、DFA 因為在狀態(tài)③出出現(xiàn)（移進，歸約）沖突，所以不是LR(0)文法。 因為follow(S)={#}，可以解決沖突，即若當(dāng)前單詞為‘，’，則移進，④；若當(dāng)前單詞為‘#’，則歸約r(1)。所以是SLR 文法。 (2)SLR分析表 （3）構(gòu)造LR分析表[簡答題20分]； [1]給定文法 G[S]： 請構(gòu)造該文法的LR分析表 [2] 給定文法 （1）證明它是LR文法 （2）構(gòu)造其LR分析表 答案：（1）該文法LR的項集規(guī)范集如下： 觀察上面的項目規(guī)范集可以發(fā)現(xiàn)，在項集0和3中，歸約項都是在

44、面臨符號' $ '時才發(fā)生，和移進符號不同。所以，該文法是LR文法。 （2）它的LR分析表如下圖所示 狀態(tài) ACTION GOTO a b $ S A 0 S4 S2 R2 1 3 1 Acc 2 R4 R4 R4 3 S7 S5 R2 6 3 4 S4 S2 8 5 R4 6 R1 7 S7 S5 9 8 R3 R3 R3 9 R3 [3]已知文法G(S) S®B

45、B B®aB B®b 構(gòu)造其LR分析表 答案： LR分析表 （4）構(gòu)造LALR分析表[簡答題20分]； [1]給定下列文法，構(gòu)造其LALR分析表 S ® E S’ ® S S ® E E ® E + T | T E ® E + T E ® T T ® (

46、 E ) | a T ® ( E ) T ® a [2]有如下文法G(S')： S'®S S®L=R S®R L®*R L®i R®L (1)寫出此文法的LALR分析表 (2)根據(jù)文法的LALR分析表分析輸入串“i=*i#”的過程 答案：(1)LALR分析表 (2) “i=

47、*i#”的LALR分析過程 [3]給定文法G(S) 構(gòu)造其LALR分析表。 狀態(tài) ACTION GOTO a b c d $ S B A 0 S6 S3 S4 1 2 3 1 acc 2 S7 3 R5 S8 4 S9 10 5 S6 S12 11 6 R7 R7 R7 7 R2 8 R3

48、 9 R5 10 S14 11 S12 R4 12 R6 R6 R6 13 R1 （5）SLR分析器對輸入串進行分析的格局變化和相應(yīng)動作[簡答題5分]； [1]已知文法及其SLR分析表，給出輸入串“ab#”的SLR分析過程。 SLR分析表 答案： [2]若有定義二進制數(shù)的文法如下： SLR分析表為 給出輸入串101.110 的分析過程。 答案： [3] 考慮以下

49、的文法G（E）：  E→(L) | a  L→L , E | E  其SLR分析表為 給出輸入串((a) , a , (a , a))的SLR分析程序的動作。 答案： （6）LR分析器對輸入串進行分析的格局變化和相應(yīng)動作[簡答題5分]； [1]已知文法G(S) S®BB B®aB B®b 其LR分析表為 假定輸入串為abab，請給出LR分析過程（按步驟給出狀態(tài)棧，符號，輸入串的變化過程） 答案：

50、[2] 給定文法 G[S]： 該文法的LR分析表為 請給出輸入符號串a(chǎn)bab 的分析過程。 答案： [3]已知文法G： 的LR分析表如下： 給出(())的LR分析過程。 答案： 第三章 3.7 語法分析器的生成器 J （1）Yacc的相關(guān)概念[選擇題2分]; [1]Yacc程序不包含下面的哪一部分（） A.聲明B.翻譯規(guī)則C.支持例程D.定義 答案：D [2]下列說法正確的是( ) A.lex是一個詞法分析器 B.Yacc是一個語法分析器的生成器 C.lex是一個語法分析器的生成器

51、 D.Yacc是一個語法生成器 答案：B [3]用Yacc處理二義文法的兩大默認(rèn)規(guī)則為（） ①對于歸約-歸約沖突，選擇在Yacc程序中最先出現(xiàn)的那個產(chǎn)生式歸約 ②對于歸約-歸約沖突，選擇在Yacc程序中后出現(xiàn)的那個產(chǎn)生式歸約 ③對于移近-歸約沖突，優(yōu)先移近 ④對于移近-歸約沖突，優(yōu)先歸約 A ①③ B ①④ C ②③ D②④ 答案：A 第四章 4.1 語法制導(dǎo)定義 K （1）繼承屬性、綜合屬性的概念 [選擇題 2分] [1]描述文法符號的屬性有哪兩種（） ①L-屬性 ②R-屬性 ③綜合屬性 ④繼承屬性 A.①② B. ③④ C.①③ D.②④ 答案：B

52、[2]下列說法正確的是 A.綜合屬性值的計算依賴于分析樹中他的子節(jié)點的屬性值 B.綜合屬性值的計算依賴于分析樹中他的兄弟節(jié)點和父節(jié)點的屬性值 C.繼承屬性值的計算依賴于分析樹中他的子節(jié)點的屬性值 D.綜合屬性值的計算依賴于分析樹中他的父節(jié)點的屬性值 答案：A [3]對于產(chǎn)生式的繼承屬性，可能正確的語義規(guī)則是 （） A. B. C. D. 答案：C （2）S屬性定義的概念 [填空題 2分] [1]S屬性是僅僅使用 的語法制導(dǎo)定義。 答案：綜合屬性 [2]對于S屬性定義，分析樹中各結(jié)點屬性的計算是

53、 完成的。 答案：自下而上 [3]分析樹中各結(jié)點屬性的計算中采用自下而上方法計算的屬性定義為 。 答案：S屬性定義 （3）注釋分析樹 [填空題 2分] [1]注釋分析樹的概念為 。 答案：每個結(jié)點的屬性值都標(biāo)識出來的分析樹 [2] 每個結(jié)點的屬性值都標(biāo)識出來的分析樹稱為 。 答案：注釋分析樹 [3] 注釋分析樹中計算各結(jié)點屬性值的過程稱為 。 答案：注釋或修飾 第四章 4.2 S屬性的計算 L （1

54、）S屬性定義的自下而上計算、棧操作 [填空題 2分] [1]在語法樹中，算符和關(guān)鍵字作為 結(jié)點。 答案：內(nèi)部 [2]S 屬性定義的計算中，拓展后分子棧的每個棧元素由 和 兩部分組成。 答案：狀態(tài)域state 屬性域val [3] S 屬性定義的計算中，若產(chǎn)生式的語義規(guī)則是，那么在XY規(guī)約成A之前，stack[top-1].Val中存放 的值。 答案：x.val ///X.x 第四章 4.3 L屬性的計算 M （1）L屬性定義的概念 [選擇題 2分] [1]下列關(guān)于L屬性定義的說法正確的是（） A.

55、S屬性定義屬于L屬性定義 B.變量類型聲明的語法制導(dǎo)定義不是一個L屬性定義 C.L屬性定義中只包含綜合屬性 D.L屬性定義中只包含繼承屬性 答案：A [2]在L屬性定義中，如果產(chǎn)生式的每條語義規(guī)則計算的是的繼承屬性，則他依賴于（） ①A的繼承屬性 ②A的綜合屬性 ③該產(chǎn)生式中左邊符號的屬性 ④該產(chǎn)生式中右邊符號的屬性 A ①③ B ②④ C ①④ D②③ 答案：A [3] 在L屬性定義中，如果產(chǎn)生式的每條語義規(guī)則計算短的可以是（） ①A的綜合屬性 ②A的繼承屬性 ③的繼承屬性 ④的綜合屬性 A ①③ B ②④ C ①③ D ①④ 答案：A

56、 （2）給定文法，寫出翻譯方案 [簡答題 10分] [1] 為下列簡化的程序文法： P ® D， D® D；D|id：T|proc id；D；S。 寫一個翻譯方案，打印該程序中每個標(biāo)識符id的嵌套深度 答案：令屬性n表示嵌套深度，下面是一個打印標(biāo)識符id嵌套深度的翻譯模式 P ® {D.n：=1} D D ® {D1.n：=D.n} D1；{D2.n：=D.n} D2 D® id：T {print（id

57、.name，D.n）} D® proc id；{print（id.name，D.n）} {D1.n：=D.n+1} D1:S [2] 假設(shè)有以下文法 D ® L id L ® , id L1 | : T T ® integer | real 建立一個翻譯模式, 把每一個標(biāo)識符的類型加入到符號表中。 答案： D ® L id {addt

58、ype(id.entry, L.type} L ® , id L1 {L.type= L1.type} {addtype(id.entry, L.type} L ® : T {L.type= T.type} T ® integer {T.type= 0} T ®

59、; real {T.type= 1} 用整數(shù)0表示整型, 1表示實型. [3] 考慮文法： S ®( L)|a L ® L，S|S 寫一個翻譯模式，它打印出每個a在句子中的位置。例如，對于輸入串（a，（a，a））的結(jié)果是2,5,7. 答案：引入屬性pos，得到的翻譯模式如下： S' ® {S.pos：=1；} S S ® ' ( ' L {L.pos:=

60、S.pos+1;} ' ) ' S®a {print(S.pos);} L ® {L1.pos:=L.pos;} L1 ' , ' {S.pos:=L.pos+2;} S L ® {S.pos:=L.pos;} S 第四章 4.4 L屬性的計算 N （1）L屬性定義的自上而下分析中各種屬性與參數(shù)、返回值的映射關(guān)系[填空題 2分] [1] 設(shè)計翻譯方案時，必須保證動作在引用屬性時

61、其值已經(jīng)可用，在只有 屬性時，為每條語義規(guī)則建立一個賦值動作，把該動作放在對應(yīng)產(chǎn)生式的右部的末端，由此可以得到翻譯方案。 答案：綜合 [2] L屬性定義的自上而下分析中設(shè)計翻譯方案時，若包含繼承屬性則產(chǎn)生式右部符號的 必須在先于這個符號的動作中計算。 答案：繼承屬性 [3] L屬性定義的自上而下分析中設(shè)計翻譯方案時，若包含繼承屬性則左部非終結(jié)符的 只能在他所引用的所有屬性都計算完后才能計算。 答案：綜合屬性 （2）L屬性定義的自下而上計算中輔助非終結(jié)符引入的目的 [選擇題 2分] [1] L屬性定義的自下而

62、上計算中的標(biāo)記非終結(jié)符說法正確的是（） A. 引入標(biāo)記非終結(jié)符可以刪除翻譯方案中嵌入的動作 B. 使L屬性定義的繼承屬性計算只出現(xiàn)在產(chǎn)生式左端 C. 使L屬性定義的綜合屬性計算只出現(xiàn)在產(chǎn)生式右端 D. 使L屬性定義的綜合屬性計算只出現(xiàn)在產(chǎn)生式左端 答案：A [2] L屬性定義的自下而上計算中引入標(biāo)記非終結(jié)符引入的目的錯誤的是（） A. 刪除翻譯方案中嵌入的動作 B. 模擬綜合屬性的計算 C. 模擬繼承屬性的計算 D. 確定分析棧上屬性的位置 答案：B [3] L屬性定義的自下而上計算中處理繼承屬性時需要引入（） A. 標(biāo)記非終結(jié)符 B. 標(biāo)記終結(jié)符 C. 綜合屬性

63、 D. L屬性 答案：A 第六章 6.1, 6.2局部、全局存儲分配 O （1）襯墊區(qū)、對齊的概念 [選擇題 2分] [1]下列說法正確的是（） A. 襯墊區(qū)是指由于考慮對齊問題而引起的無用空間 B. 局部數(shù)據(jù)存儲安排不存在對齊問題 C. 局部數(shù)據(jù)的數(shù)據(jù)存儲安排與目標(biāo)機器的尋址限制無關(guān) D. 襯墊區(qū)是一定會出現(xiàn)的 答案：A [2]關(guān)于襯墊區(qū)的定義，下列說法正確的是（） A. 襯墊區(qū)是在考慮對齊問題時增加的額外空間 B. 襯墊區(qū)是指由于考慮對齊問題而引起的無用空間 C. 襯墊區(qū)是局部數(shù)據(jù)在存儲的所需要的最大空間 D. 襯墊區(qū)是局部數(shù)據(jù)在存儲的所需要的最

64、小空間 答案：B [3] 局部數(shù)據(jù)在存儲安排時，襯墊區(qū)是因為（）問題而引起的無用空間 A. 對齊 B. 數(shù)據(jù)的順序 C . 數(shù)據(jù)類型 D. 空間 答案：A （2）活動記錄的內(nèi)容 [簡答題 5分] [1]活動記錄包括哪些內(nèi)容/ 答案：返回值，參數(shù)，控制鏈，訪問鏈，保存的機器狀態(tài)，局部數(shù)據(jù)，臨時數(shù)據(jù) [2]簡述活動記錄中的各個域及其用途。 答案：返回值：用于返回本過程中給調(diào)用過程的值 參數(shù)：調(diào)用過程傳遞給本過程的參數(shù) 控制鏈：指向調(diào)用過程的指針 訪問鏈：用于引用存于其他活動記錄的非局部數(shù)據(jù) 機器狀態(tài)：御用保存本過程調(diào)用前

65、的機器狀態(tài) 局部數(shù)據(jù)：本過程內(nèi)部定義的局部變量 臨時數(shù)據(jù)：本過程計算中可能用到的臨時變量 [3]簡述活動記錄的概念及其內(nèi)容 答案：活動記錄是存儲過程執(zhí)行一次所需局部信息的連續(xù)的存儲區(qū)。其內(nèi)容包括返回值，參數(shù)，控制鏈，訪問鏈，保存的機器狀態(tài)，局部數(shù)據(jù)，臨時數(shù)據(jù) （3）活動樹的概念 [簡答題 5分] [1]活動樹有哪些特點？ 答案：每個結(jié)點代表某過程的一個活動； 根結(jié)點代表主程序的活動； 結(jié)點a是結(jié)點b的父結(jié)點，當(dāng)且僅當(dāng)控制流從a的活動進入b的活動； 結(jié)點a 處于結(jié)點b 的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期。

66、 [2]什么是活動樹？ 答案：用來描繪控制進入和離開活動的方式的樹 [3]簡介活動樹的概念及其特點。 答案：活動樹是用來描繪控制進入和離開活動的方式的樹。 其特點為：每個結(jié)點代表某過程的一個活動；根結(jié)點代表主程序的活動；結(jié)點a是結(jié)點b的父結(jié)點，當(dāng)且僅當(dāng)控制流從a的活動進入b的活動；結(jié)點a 處于結(jié)點b 的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期。 （4）控制棧、運行棧的概念 [填空題 2分] [1] 把控制棧中的信息拓廣到包括過程活動所需的所有局部信息，這種類型的棧稱為 。 答案：運行棧 [2] 當(dāng)活動開始時，講這個活動的結(jié)點壓入棧中；當(dāng)活動結(jié)束時，將把它的結(jié)點從

67、棧中取出。這樣的棧稱為 。 答案：控制棧 [3] 把控制棧中的信息增加到包括過程活動的活動記錄，控制棧就成為了 。 答案：運行棧 （5）過程調(diào)用序列、過程返回序列的概念 [填空題 2分] [1] 在過程調(diào)用時執(zhí)行的分配活動記錄，以及把信息填入其域中的代碼被稱為 。 答案：過程調(diào)用序列 [2] 過程返回時執(zhí)行的恢復(fù)機器狀態(tài)，釋放活動記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼被稱為 。 答案：過程返回序列 [3] 過程調(diào)用序列和過程返回序列常常都分成兩部分，分別處于

68、 中。 答案：調(diào)用過程和被調(diào)用過程 （6）懸空引用的概念 [填空題 2分] [1] 棧式分配的動態(tài)釋放空間會引起 問題。 答案：懸空引用 [2] 是指引用某個已被釋放的存儲單元。 答案：懸空引用 [3] 只要存儲空間可以回收，就有可能出現(xiàn) 問題，這是一種邏輯錯誤。 答案：懸空引用 第六章 6.3 非局部名字的訪問 P （1）靜態(tài)作用域、嵌套深度的概念 [選擇題 2分] [1] 下列說法錯誤的是（） A. 語言的作用域規(guī)則規(guī)定了如何處理非局部名字的訪問，一種常用的規(guī)則叫做靜態(tài)作用域 規(guī)則 B.

69、 靜態(tài)作用域有兩種不同的嵌套方式，分別為無過程嵌套的靜態(tài)作用域和有過程嵌套的靜態(tài)作用域 C. 變量的嵌套深度定義為它的聲明所在過程的嵌套深度 D. 程序所需的數(shù)據(jù)空間在程序運行前就可以完成，則使用的是動態(tài)存儲管理方法 答案：D [2] 過程的display表記錄了（） A. 過程的鏈接數(shù)據(jù) B. 過程的嵌套層次 C.過程的返回地址 D.過程的入口地址 答案：B [3] 如果活動記錄中沒有display表，則說明（） A. 無遞歸調(diào)用過程 B. 無嵌套定義變量 C.無遞歸、無嵌套 D.有遞歸、無嵌套 答案：D （2）靜態(tài)鏈的建立 [簡答題 5分] [1]

70、假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x ，則建立被調(diào)用過程靜態(tài)鏈的過程是什么？ 答： np < nx的情況 · x肯定就聲明在p中 · 被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記錄的訪問鏈 np ³ nx的情況 · p和x的嵌套深度分別為1，2，…，nx- 1的外圍過程肯定相同 · 追蹤訪問鏈np - （nx – 1）次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個過程的最新活動記錄 · 所到達(dá)的訪問鏈就是x的活動記錄中的訪問鏈應(yīng)該指向的那個訪問鏈 [2] 簡述活動記錄和訪問鏈的主要作用，以及訪問鏈的指向。 答：活動記錄用于提供活動所需的環(huán)境，訪問鏈用于訪問非本地數(shù)據(jù)。訪問鏈的指向有兩種：非顯示表指向直接外層的最新活動記錄，顯示表指向同層次新活動記錄。 [3