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

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

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

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

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

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

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

6、3）正規(guī)式與語言的對(duì)應(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] 最多包含兩個(gè)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)*等價(jià)的正規(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] 有如圖所示的有窮自動(dòng)機(jī)，與之等價(jià)的正規(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選項(xiàng)都不正確 答案：C [2] 對(duì)于NFA和DFA模型說法錯(cuò)誤的是（ ）。 A. DFA是NFA的特殊形式 B. DFA與NFA的狀態(tài)轉(zhuǎn)換完全相同 C. 都有唯一的開始狀態(tài) D. 都可以有多個(gè)接受狀態(tài) 答案：B [3]

8、對(duì)于DFA模型，說法錯(cuò)誤的是（ ）。 A. DFA從任何狀態(tài)出發(fā)，對(duì)于任何輸入符號(hào)，可有多個(gè)轉(zhuǎn)換 B. 任何狀態(tài)都沒有ε轉(zhuǎn)換 C. DFA有唯一的開始狀態(tài) D. DFA可以有多個(gè)接受狀態(tài) 答案：A （2）NFA 的構(gòu)造 [簡答題 10分] [1] 設(shè)有非確定的有自限動(dòng)機(jī)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}。請(qǐng)畫出狀態(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)造非確定的有限自動(dòng)機(jī)，給出它們處理輸入串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ù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(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] 對(duì)于下圖所示NFA，回答下列問題： （1）用正規(guī)式描述該有限自動(dòng)機(jī)所表示的語言。 （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)集分成兩個(gè)子集：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等價(jià)。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價(jià)（見下步），從而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)不等價(jià)，所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P={{A}，{B}，{D}，{E}，{C，F(xiàn)}}。所以最小化的DFA如下： [2] 給定下列自動(dòng)機(jī)： 把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)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)編號(hào) 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}上的不含兩個(gè)相鄰的x,且不含兩個(gè)相鄰的ｙ的全體符號(hào)串的有限狀態(tài)自動(dòng)機(jī)。 答案： [2] 處于/* 和 */之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。 答案： 1 2 4 start 5 2 others others /

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

17、 E （1）上下文無關(guān)文法定義[選擇題2分]； [1] 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組（ ）。 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 對(duì) (a,(a,a) 和 (((a,a),^,(a)),a) 的最左推導(dǎo)。 答案： 對(duì)(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)) 對(duì)(((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* 對(duì)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)造兩個(gè)不同的最左推導(dǎo)，以此說明該文法是二義的。 （b） 為abab構(gòu)造對(duì)應(yīng)的最右推導(dǎo)。 答案： （3）分析樹[簡答題5分]； [1] 考慮文法S->aSbS | bSaS |ε （1） 為abab構(gòu)造對(duì)應(yīng)的分析樹。 （2） 這個(gè)文法產(chǎn)生的語言是什么？ 答案： E T F ( E ) E + T F i T T * F （1） （2）該文法產(chǎn)生 a、b 個(gè)數(shù)相等的 ab 串（含空串） [2] 對(duì)于文法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)對(duì)應(yīng)的語法樹必定相同 　　 B. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 　　 C. 最左推導(dǎo)和最右推導(dǎo)必定相同 &

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

25、題2分]； [1] 一個(gè)文法是左遞歸的，如果它有非終結(jié)符A，對(duì)某個(gè)串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] 對(duì)于懸空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種類型，其中描述能力最強(qiáng)的是（ ）。 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)分析法的名字中，第二個(gè)“L”的含義是（ ）。 A. 自左向右進(jìn)行掃描 B. 每次采用最左推導(dǎo) C. 采用最右推導(dǎo)的逆過程——最左規(guī)約 D. 向輸入串中查看一個(gè)輸入符號(hào) 答案：B [3] LL(1)分析法的名字中，第一個(gè)“L”的含義是（ ）。 A. 自左向右進(jìn)行掃描 B. 每次采用最左推導(dǎo) C. 采用最右推導(dǎo)的逆過程——最左規(guī)約 D. 向輸入串中查看一個(gè)輸入符

29、號(hào) 答案：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) 分析表。 答案： 各符號(hào)的FIRST集和FOLLOW集為： 預(yù)測分析表為： 由于預(yù)測分析表中無多

31、重入口，所以可判定文法是LL(1)的。 [3] 請(qǐng)給對(duì)文法G[S]進(jìn)行改寫成LL（1）文法，并給出改寫后文法的預(yù)測分析表，要求計(jì)算出改寫后文法各非終極符的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ù)測分析表對(duì)輸入串進(jìn)行分析的過程[簡答題5分]； [1] 給定LL(1)分析表： 有輸入符號(hào)串i+i*i，寫出按上述算法識(shí)別此符號(hào)串的過程。 答案： [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) 有輸入符號(hào)串i-i//i#，寫出按上述算法識(shí)別此符號(hào)串的過程，遇到錯(cuò)誤停止即可，不需要錯(cuò)誤恢復(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出錯(cuò) [3] 已知文法分析表： a $ ( ) , # S →a →$ →(T) T →SF →SF →SF F →ε →,SF 有輸入符號(hào)串(a,(a))#，寫出按上述算法識(shí)別此符號(hào)串的過程。 答案： 步驟 分析棧 剩余字符 所用產(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β為_____項(xiàng)目。 A. 歸約 B. 移進(jìn) C. 接受 D. 待約 答案：B [2] 移近-歸約分析為輸入串構(gòu)造分析樹是從（ ）開始的。 A. 根結(jié)點(diǎn) B. 葉結(jié)點(diǎn) C. 中間結(jié)點(diǎn) D. 任一結(jié)點(diǎn) 答案：B [3] 在每一步歸約中，一個(gè)子串和某個(gè)產(chǎn)生式的（ ）匹配，然后用該產(chǎn)生式的（ ）符號(hào)代替這個(gè)子串。 A. 右部 左部 B. 右部 右部 C. 左部 右部 D. 左部 左部 答案：A （2）句柄概念[選擇題2分]； [1] 在規(guī)范歸約中，用（ ）來刻畫可歸約串。 A. 直接短語 B. 句柄 C. 產(chǎn)生式

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

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

41、柄的任何符號(hào)，此時(shí)期待從輸入串中看到該句柄對(duì)應(yīng)的產(chǎn)生式的右部所推導(dǎo)出的符號(hào)串 B.活前綴只包含句柄的一部分符號(hào)，表明該句柄對(duì)應(yīng)的的產(chǎn)生式的右部子串已出現(xiàn)在棧頂，期待從輸入串中看到推導(dǎo)出的符號(hào)串 C.活前綴已含有句柄的全部符號(hào)，表明該句柄對(duì)應(yīng)的產(chǎn)生式的右部已出現(xiàn)在棧頂 D.活前綴只包含句柄的一部分符號(hào)，表明該句柄對(duì)應(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 因?yàn)樵跔顟B(tài)③出出現(xiàn)（移進(jìn)，歸約）沖突，所以不是LR(0)文法。 因?yàn)閒ollow(S)={#}，可以解決沖突，即若當(dāng)前單詞為‘，’，則移進(jìn)，④；若當(dāng)前單詞為‘#’，則歸約r(1)。所以是SLR 文法。 (2)SLR分析表 （3）構(gòu)造LR分析表[簡答題20分]； [1]給定文法 G[S]： 請(qǐng)構(gòu)造該文法的LR分析表 [2] 給定文法 （1）證明它是LR文法 （2）構(gòu)造其LR分析表 答案：（1）該文法LR的項(xiàng)集規(guī)范集如下： 觀察上面的項(xiàng)目規(guī)范集可以發(fā)現(xiàn)，在項(xiàng)集0和3中，歸約項(xiàng)都是在

44、面臨符號(hào)' $ '時(shí)才發(fā)生，和移進(jìn)符號(hào)不同。所以，該文法是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分析器對(duì)輸入串進(jìn)行分析的格局變化和相應(yīng)動(dòng)作[簡答題5分]； [1]已知文法及其SLR分析表，給出輸入串“ab#”的SLR分析過程。 SLR分析表 答案： [2]若有定義二進(jìn)制數(shù)的文法如下： SLR分析表為 給出輸入串101.110 的分析過程。 答案： [3] 考慮以下

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

50、[2] 給定文法 G[S]： 該文法的LR分析表為 請(qǐng)給出輸入符號(hào)串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是一個(gè)詞法分析器 B.Yacc是一個(gè)語法分析器的生成器 C.lex是一個(gè)語法分析器的生成器

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

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

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

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

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

56、 （2）給定文法，寫出翻譯方案 [簡答題 10分] [1] 為下列簡化的程序文法： P ® D， D® D；D|id：T|proc id；D；S。 寫一個(gè)翻譯方案，打印該程序中每個(gè)標(biāo)識(shí)符id的嵌套深度 答案：令屬性n表示嵌套深度，下面是一個(gè)打印標(biāo)識(shí)符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 建立一個(gè)翻譯模式, 把每一個(gè)標(biāo)識(shí)符的類型加入到符號(hà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表示實(shí)型. [3] 考慮文法： S ®( L)|a L ® L，S|S 寫一個(gè)翻譯模式，它打印出每個(gè)a在句子中的位置。例如，對(duì)于輸入串（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屬性的計(jì)算 N （1）L屬性定義的自上而下分析中各種屬性與參數(shù)、返回值的映射關(guān)系[填空題 2分] [1] 設(shè)計(jì)翻譯方案時(shí)，必須保證動(dòng)作在引用屬性時(shí)

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

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

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

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

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

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

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

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

69、 靜態(tài)作用域有兩種不同的嵌套方式，分別為無過程嵌套的靜態(tài)作用域和有過程嵌套的靜態(tài)作用域 C. 變量的嵌套深度定義為它的聲明所在過程的嵌套深度 D. 程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可以完成，則使用的是動(dòng)態(tài)存儲(chǔ)管理方法 答案：D [2] 過程的display表記錄了（） A. 過程的鏈接數(shù)據(jù) B. 過程的嵌套層次 C.過程的返回地址 D.過程的入口地址 答案：B [3] 如果活動(dòng)記錄中沒有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)用過程的活動(dòng)記錄的訪問鏈 np ³ nx的情況 · p和x的嵌套深度分別為1，2，…，nx- 1的外圍過程肯定相同 · 追蹤訪問鏈np - （nx – 1）次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過程的最新活動(dòng)記錄 · 所到達(dá)的訪問鏈就是x的活動(dòng)記錄中的訪問鏈應(yīng)該指向的那個(gè)訪問鏈 [2] 簡述活動(dòng)記錄和訪問鏈的主要作用，以及訪問鏈的指向。 答：活動(dòng)記錄用于提供活動(dòng)所需的環(huán)境，訪問鏈用于訪問非本地?cái)?shù)據(jù)。訪問鏈的指向有兩種：非顯示表指向直接外層的最新活動(dòng)記錄，顯示表指向同層次新活動(dòng)記錄。 [3