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

1、編譯技術(shù)命題指導(dǎo)意見教學(xué)內(nèi)容知識點(diǎn)及題型第一章 編譯器概述A（1）編譯的階段劃分 選擇題 2分1 編譯程序絕大多數(shù)時間花在( )上。 A. 出錯處理 B. 詞法分析C. 目標(biāo)代碼生成 D. 符號表管理答案：D2 ( ) 和代碼優(yōu)化部分不是每個編譯程序都必需的。A. 語法分析B. 中間代碼生成C. 詞法分析D. 代碼生成答案：B3 編譯程序前三個階段完成的工作是( )。A. 詞法分析、語法分析和代碼優(yōu)化 B. 代碼生成、代碼優(yōu)化和詞法分析C. 詞法分析、語法分析和語義分析 D. 詞法分析、語法分析和代碼生成答案：C（2）遍的概念 填空題 2分1 編譯階段的活動常用一遍掃描來實(shí)現(xiàn)，一遍掃描包括 和

2、 。答案：讀一個輸入文件 寫一個輸出文件2 將編譯程序分成若干個“遍”是為了_。答案：使程序的結(jié)構(gòu)更加清晰3 編譯器從邏輯上可以分為7個階段，其中，可以作為一個后端遍的是_階段。答案：代碼生成（3）前端和后端的劃分 簡答題 5分1 什么是前端？ 5分答案：編譯器分成分析和綜合兩大部分。分析部分揭示源程序的基本元素和它們所形成的層次結(jié)構(gòu)，決定它們的含義，建立起源程序的中間表示，分析部分經(jīng)常被稱為前端。2 什么是后端？ 5分答案：編譯器分成分析和綜合兩大部分。綜合部分從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序，它經(jīng)常被稱為后端。3 什么是前端？什么是后端？ 5分答案：編譯器分成分析和綜合兩大部

3、分。分析部分揭示源程序的基本元素和它們所形成的層次結(jié)構(gòu)，決定它們的含義，建立起源程序的中間表示，分析部分經(jīng)常被稱為前端。綜合部分從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序，它經(jīng)常被稱為后端。第二章2.1 2.2 詞法記號的定義及描述B（1）詞法分析器的功能 選擇題 2分1 詞法分析程序的輸出結(jié)果是（ ）。A. 單詞的種別編碼B. 單詞在符號表中的位置 C. 單詞的種別編碼和單詞屬性值D. 單詞的單詞屬性值答案：C2 詞法分析器用于識別_。 A. 字符串 B語句C單詞D標(biāo)識符答案：C3 掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨(dú)立含義的最小語法單位即（ ）。A 字符 B單詞

4、 C句子 D句型答案：B（2）詞法記號概念及屬性 填空題2分1 詞法記號是由 和 構(gòu)成的二元組。答案：記號名 屬性值2 詞法單元是源程序中匹配一個 的字符序列。答案：記號模式3 影響語法分析的決策， 影響記號的翻譯。答案：記號名 屬性（3）正規(guī)式與語言的對應(yīng)關(guān)系 選擇題 2分1 下面文法（ ）和正規(guī)表達(dá)式a*b描述的語言相同。A. Sab | aSbB. Sb | aSC. Sa | aSbD. Sa | Sb答案：B2 最多包含兩個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*

5、答案：D3 與(a|b)*等價(jià)的正規(guī)式是（ ）。A. (a*|b*)*B. (a|b)+C. (ab)*D. a*|b*答案：A第二章2.3 NFA,DFAC（1）NFA與DFA的概念 選擇題 2分1 有如圖所示的有窮自動機(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)都不正確答案：C2 對于NFA和DFA模型說法錯誤的是（ ）。A. DFA是NFA的特殊形式B. DFA與NFA的狀態(tài)轉(zhuǎn)換完全相同C. 都有唯一的開始狀態(tài)D. 都可以有多個接受狀態(tài)答案：

6、B3 對于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è)有非確定的有自限動機(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。請畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。答案：狀態(tài)轉(zhuǎn)換距陣為：d01ACA，BBCCC11011狀態(tài)轉(zhuǎn)換圖為：2 構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101。答案： 3 為（|a）b*）* 構(gòu)造非確定的有限自動

7、機(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 設(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: 確定化：I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41

8、,2,3,4、2 構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的DFA。答案：先構(gòu)造NFA：確定化： 重新命名，令A(yù)B為B、AC為C、ABY為D得： 所以，可得DFA為： 3 對于下圖所示NFA，回答下列問題：（1）用正規(guī)式描述該有限自動機(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,z, M(x,1)=x, M(y,1)= ,M(z,1)=y, 構(gòu)造相應(yīng)的DFA并最小化。答

9、案：根據(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等價(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:由于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à)，

10、所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所以最小化的DFA如下：2 給定下列自動機(jī)：把此自動機(jī)轉(zhuǎn)換為確定自動機(jī)DFA。答案：有狀態(tài)矩陣如圖：從而可得DFA如圖：3 （1）將下圖中的NFA M確定化為DFA M。 （2）將DFA M化簡。答案：確定化: ab00,1110-0，10,11狀態(tài)編號 ab01220-11210 a -a a2 b b 未簡化的DFA最小化： 分為：終態(tài)集0,1 非終態(tài)集2 0,1a =1 0,1b = 2 所以：0,1 = 0 2 = 110 a - b a第二章2.4,2.5 詞法分析器的生成器; 第二章習(xí)題D（1）直接

11、從語言構(gòu)造DFA 簡答題5分1 寫出能產(chǎn)生字母表x,y上的不含兩個相鄰的x,且不含兩個相鄰的的全體符號串的有限狀態(tài)自動機(jī)。答案：2 處于/* 和 */之間的串構(gòu)成注解，注解中間沒有*/。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。答案：124start52othersothers/*/3 有語言 L=w|w (0,1)+，并且 w 中至少有兩個1 ，又在任何兩個1之間有偶數(shù)個 0 ，試構(gòu)造接受該語言的確定有限狀態(tài)自動機(jī)。答案：（2）Lex 的功能 填空題 2分1 Lex是從基于正規(guī)式的描述來構(gòu)造 。答案：詞法分析器2 Lex程序包含三部分： 、 和輔助函數(shù)。答案：聲明 翻譯規(guī)則3 由Lex建立的 分

12、析器通常作為 分析器的一個子程序。答案：詞法 語法第三章 3.1上下文無關(guān)文法E（1）上下文無關(guān)文法定義選擇題2分；1 一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組（ ）。 A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式答案：D2 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是（ ）。A. 短語文法 B. 正則文法 C. 上下文有關(guān)文法D. 上下文無關(guān)文法答案：D3 文法分為四種類型，即0型、1型、2型、3型。其中0型文法是_。A. 短語文法B. 正則文法C. 上下文有關(guān)文法D. 上下文無關(guān)文法答案：A（2）最左推導(dǎo)、最右

13、推導(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) =(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) =

14、(a,a),S,S),S) =(a,a),S),S) =(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S) =(a,a),(a),a)2 設(shè)文法GE: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+i3 考慮文法S-aSbS | bSaS |（a） 為句abab構(gòu)造兩個不同的最左推導(dǎo)，以此說明該文法是二義的。（b） 為abab構(gòu)造對應(yīng)的最右推導(dǎo)。答案：（3）分析樹簡答題

15、5分； 1 考慮文法S-aSbS | bSaS |（1） 為abab構(gòu)造對應(yīng)的分析樹。（2） 這個文法產(chǎn)生的語言是什么？答案：ETF(E)E+TFiTT*F（1）（2）該文法產(chǎn)生 a、b 個數(shù)相等的 ab 串（含空串）2 對于文法G(E): ET|E+TTF|T*FF(E)|i寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。答案：（1）ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i)（2）語法樹如右圖。3 令文法GS為： SABAaAb | abBb,（1）GS定義的語言L(G)是什么？（2）給出句子aabbb的最左推導(dǎo)，并給出其語法分析樹。答案：（1）SabBabb

16、 SaAbBaabbBaabbb SaAbBaaAbbBaaabbbBaaabbbb Sanbm(n=0,m=1)（2）s ABaAbBaabbBaabbbb/.（4）二義性概念選擇題2分1 如果文法G是無二義的，則它的任何句子（ ）。A. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 B. 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同 C. 最左推導(dǎo)和最右推導(dǎo)必定相同 D. 可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同答案：A2 如果一個文法G是無二義性文法，對于任何一個句子，該句子（ ）。A. 可能存在兩個不同的最左推導(dǎo)B. 可能存在兩個不同的最右推導(dǎo)C. 最左推導(dǎo)和最右推導(dǎo)不同D. 僅存在一個

17、最左推導(dǎo)和一個最右推導(dǎo)答案：D3 若文法 G 定義的語言是無限集，則文法必然是（ ）。 A. 遞歸的 B. 前后文無關(guān)的C. 二義性的 D. 無二義性的答案：A第三章 3.2 語言和文法F（1）消除左遞歸填空題2分；1 一個文法是左遞歸的，如果它有非終結(jié)符A，對某個串a(chǎn)，存在推導(dǎo) 。答案：A=+Aa2 的分析方法不能用于左遞歸文法，因此需要消除左遞歸。答案：自上而下3 由形式為A-Aa的產(chǎn)生式引起的左遞歸稱為 。答案：直接左遞歸（2）提取左因子填空題2分；1 提取左因子用于產(chǎn)生適合于 的文法。答案：自上而下2 A-aB|aC，經(jīng)過提取左因子，原來的產(chǎn)生式成為 和 。答案：A-aA A-B|C3

18、 對于懸空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. 1型C. 2型D. 3型答案：A2 文法分為四種類型，即0型、1型、2型、3型。其中1型文法是（ ）。A. 短語文法 B. 正則文法 C. 上下文有關(guān)文法D.

19、 上下文無關(guān)文法答案：C3 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是（ ）。A. 短語文法B. 正則文法C. 上下文有關(guān)文法D. 上下文無關(guān)文法答案：B第三章 3.3 自上而下分析G（1）LL(1)文法概念選擇題2分；1 3在下面的各種編譯方法中，屬于自頂向下的語法分析算法的是（ ）。A. LL(1)分析方法B. LR(K) 分析方法C. SLR分析方法D. LALR(1) 分析方法答案：A2 LL(1)分析法的名字中，第二個“L”的含義是（ ）。A. 自左向右進(jìn)行掃描B. 每次采用最左推導(dǎo) C. 采用最右推導(dǎo)的逆過程最左規(guī)約D. 向輸入串中查看一個輸入符號答案：B3 LL(

20、1)分析法的名字中，第一個“L”的含義是（ ）。A. 自左向右進(jìn)行掃描B. 每次采用最左推導(dǎo)C. 采用最右推導(dǎo)的逆過程最左規(guī)約D. 向輸入串中查看一個輸入符號答案：A （2）構(gòu)造預(yù)測分析表（包括求FIRST、FOLLOW集）簡答題10分；1 設(shè)文法 G(S)： SS 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（S） FIRST（S）+， FOLLOW（S） FIRST（F）* FOLLoW（F）（+， FIR

21、ST（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ù)測分析表中無多重入口，所以可判定文法是LL(1)的。3 請給對文法GS進(jìn)行改寫成LL（1）文法，并給出改寫后文法的預(yù)測分析表，要求計(jì)算出改寫后文法各非終極符的FIRST和FOLLOW集合。S S*aA | aA| *aA A +aA | +a答案：改寫文法如下： S*aAS | aAS S*aAS | e A+aA AA | eFIRSTFO

22、LLOWS*，a#S*,e#A+*,#A+,e*,#預(yù)測分析表：*a+#SS*aASS aASSS*ASSeAA+aAAAeAAAe（3）用預(yù)測分析表對輸入串進(jìn)行分析的過程簡答題5分；1 給定LL(1)分析表：有輸入符號串i+i*i，寫出按上述算法識別此符號串的過程。答案：2 已知文法分析表：i+*()#-/EE-TGE-TGGG-+TGG-G-G-TGTT-FST-FSSS-S-*FSS-S-S-S-/FSFF-iF-(E)有輸入符號串i-i/i#，寫出按上述算法識別此符號串的過程，遇到錯誤停止即可，不需要錯誤恢復(fù)。答案：步驟分析棧 剩余字符 所用產(chǎn)生式 0#E i-i/i# E-TG1#G

23、T i-i/i# T-FS2#GSF i-i/i# F-i3#GSi i-i/i# i匹配4#GS -i/i# S-5#G -i/i# G-TG6#GT- -i/i# -匹配7#GT i/i# T-FS8#GSF i/i# F-i9#GSi i/i# i匹配10#GS /i# S-/FS11#GSF/ /i# /匹配12#GSF /i# F出錯3 已知文法分析表：a$(),#Sa$(T)TSFSFSFF,SF有輸入符號串(a,(a)#，寫出按上述算法識別此符號串的過程。答案：步驟分析棧 剩余字符 所用產(chǎn)生式 0#S (a,(a)# S-(T) 1#)T( (a,(a)# (匹配2#)T a,(

24、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#)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- a為_項(xiàng)目。A. 歸約B. 移進(jìn)C. 接受D. 待約 答案：B2 移近-歸約分析為輸

25、入串構(gòu)造分析樹是從（ ）開始的。A. 根結(jié)點(diǎn)B. 葉結(jié)點(diǎn)C. 中間結(jié)點(diǎn)D. 任一結(jié)點(diǎn)答案：B3 在每一步歸約中，一個子串和某個產(chǎn)生式的（ ）匹配，然后用該產(chǎn)生式的（ ）符號代替這個子串。A. 右部 左部B. 右部 右部C. 左部 右部D. 左部 左部答案：A（2）句柄概念選擇題2分；1 在規(guī)范歸約中，用（ ）來刻畫可歸約串。A. 直接短語B. 句柄C. 產(chǎn)生式D. 記號答案：B2 下面說法正確的是（ ）。A. 句柄是該句型中和一個產(chǎn)生式左部匹配的子串B. 文法是二義的，句柄是唯一的C. 文法無二義時，句柄可能是唯一的D. 以上說法都不對答案：D3 面說法錯誤的是（ ）。A. 句柄是該句型中和一

26、個產(chǎn)生式右部匹配的子串B. 文法是二義的，句柄可能不唯一C. 文法無二義時，句柄是唯一的D. 句型中能和產(chǎn)生式A-右部匹配的最左子串就是句柄答案：D第三章 3.5 LR分析器I（1）活前綴概念選擇題2分；1一個句型中的活前綴為（）A. 短語 B.簡單短語 C.句柄 D.右句型的前綴，該前綴不超過最右句柄的右端答案：D2在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型( ) 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目答案：C3下列語句描述錯誤的是（）A.活前綴不包含句柄的任何符號，此時期待從輸入串中看到該句柄對應(yīng)的產(chǎn)生式的右部所推導(dǎo)出的符號串B.活前綴只包含句柄的一部

27、分符號，表明該句柄對應(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* E T F a T T F F b T F 2 考慮文法E EE +|EE*|a，構(gòu)造它的SLR分析表3設(shè)有文法 SrD DD,i|i(1)證明該文法不是LR(1)文法，是SLR文法(2)給出該文法的SLR分析表答案：(1)構(gòu)造活前綴的DFA因?yàn)樵跔顟B(tài)出出現(xiàn)（

28、移進(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給定文法 GS：請構(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)都是在面臨符號 $ 時才發(fā)生，和移進(jìn)符號不同。所以，該文法是LR文法。（2）它的LR分析表如下圖所示狀態(tài)ACTIONGOTOab$SA0S4S2R2131Acc2R4R4R43S7S5R263

29、4S4S285R46R17S7S598R3R3R39R33已知文法G(S) SBB BaB Bb構(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 ( E ) | a T ( E ) T a 2有如下文法G(S)： SS SL=R SR L*R Li RL(1)寫出此文法的LALR分析表(2)根據(jù)文法的LALR分析表分析輸入串“i=*i#”的過程答案：(1)LALR分析表(2) “i=*i#”的LALR分析過程3給定文法G(S)構(gòu)造其LALR分析表。狀態(tài)ACTI

30、ONGOTOabcd$SBA0S6S3S41231acc2S73R5S84S9105S6S12116R7R7R77R28R39R510S1411S12R412R6R6R613R1（5）SLR分析器對輸入串進(jìn)行分析的格局變化和相應(yīng)動作簡答題5分；1已知文法及其SLR分析表，給出輸入串“ab#”的SLR分析過程。SLR分析表答案：2若有定義二進(jìn)制數(shù)的文法如下：SLR分析表為給出輸入串101.110 的分析過程。答案： 3 考慮以下的文法G（E）：E(L) | aLL , E | E其SLR分析表為給出輸入串(a) , a , (a , a)的SLR分析程序的動作。答案：（6）LR分析器對輸入串進(jìn)行

31、分析的格局變化和相應(yīng)動作簡答題5分；1已知文法G(S) SBB BaB Bb其LR分析表為假定輸入串為abab，請給出LR分析過程（按步驟給出狀態(tài)棧，符號，輸入串的變化過程）答案：2 給定文法 GS：該文法的LR分析表為 請給出輸入符號串a(chǎn)bab 的分析過程。答案：3已知文法G：的LR分析表如下：給出()的LR分析過程。答案：第三章 3.7 語法分析器的生成器J（1）Yacc的相關(guān)概念選擇題2分;1Yacc程序不包含下面的哪一部分（）A.聲明B.翻譯規(guī)則C.支持例程D.定義答案：D2下列說法正確的是( )A.lex是一個詞法分析器B.Yacc是一個語法分析器的生成器C.lex是一個語法分析器的

32、生成器D.Yacc是一個語法生成器答案：B3用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.答案：B2下列說法正確的是A.綜合屬性值的計(jì)算依賴于分析樹中他的子節(jié)點(diǎn)的屬性值B.綜合屬性值的計(jì)算依賴于分析樹中他的兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的屬性值C.

33、繼承屬性值的計(jì)算依賴于分析樹中他的子節(jié)點(diǎn)的屬性值D.綜合屬性值的計(jì)算依賴于分析樹中他的父節(jié)點(diǎn)的屬性值答案：A3對于產(chǎn)生式的繼承屬性，可能正確的語義規(guī)則是 （）A. B. C. D. 答案：C（2）S屬性定義的概念 填空題 2分1S屬性是僅僅使用 的語法制導(dǎo)定義。答案：綜合屬性2對于S屬性定義，分析樹中各結(jié)點(diǎn)屬性的計(jì)算是 完成的。答案：自下而上3分析樹中各結(jié)點(diǎn)屬性的計(jì)算中采用自下而上方法計(jì)算的屬性定義為 。答案：S屬性定義（3）注釋分析樹 填空題 2分1注釋分析樹的概念為 。答案：每個結(jié)點(diǎn)的屬性值都標(biāo)識出來的分析樹2 每個結(jié)點(diǎn)的屬性值都標(biāo)識出來的分析樹稱為 。答案：注釋分析樹3 注釋分析樹中計(jì)算

34、各結(jié)點(diǎn)屬性值的過程稱為 。答案：注釋或修飾第四章 4.2 S屬性的計(jì)算L（1）S屬性定義的自下而上計(jì)算、棧操作 填空題 2分1在語法樹中，算符和關(guān)鍵字作為 結(jié)點(diǎn)。答案：內(nèi)部2S 屬性定義的計(jì)算中，拓展后分子棧的每個棧元素由 和 兩部分組成。答案：狀態(tài)域state 屬性域val3 S 屬性定義的計(jì)算中，若產(chǎn)生式的語義規(guī)則是，那么在XY規(guī)約成A之前，stacktop-1.Val中存放 的值。答案：x.val /X.x第四章 4.3 L屬性的計(jì)算M（1）L屬性定義的概念 選擇題 2分1下列關(guān)于L屬性定義的說法正確的是（）A.S屬性定義屬于L屬性定義B.變量類型聲明的語法制導(dǎo)定義不是一個L屬性定義C.

35、L屬性定義中只包含綜合屬性D.L屬性定義中只包含繼承屬性答案：A2在L屬性定義中，如果產(chǎn)生式的每條語義規(guī)則計(jì)算的是的繼承屬性，則他依賴于（）A的繼承屬性A的綜合屬性該產(chǎn)生式中左邊符號的屬性該產(chǎn)生式中右邊符號的屬性 A B C D答案：A3 在L屬性定義中，如果產(chǎn)生式的每條語義規(guī)則計(jì)算短的可以是（）A的綜合屬性A的繼承屬性的繼承屬性的綜合屬性A B C D 答案：A （2）給定文法，寫出翻譯方案 簡答題 10分1 為下列簡化的程序文法： P D， D D；D|id：T|proc id；D；S。 寫一個翻譯方案，打印該程序中每個標(biāo)識符id的嵌套深度答案：令屬性n表示嵌套深度，下面是一個打印標(biāo)識符i

36、d嵌套深度的翻譯模式 P D.n：=1 D D D1.n：=D.n D1；D2.n：=D.n D2 D id：T print（，D.n） D proc id；print（，D.n） D1.n：=D.n+1 D1:S2 假設(shè)有以下文法 D L id L , id L1 | : T T integer | real建立一個翻譯模式, 把每一個標(biāo)識符的類型加入到符號表中。答案： D L id addtype(id.entry, L.type L , id L1 L.type= L1.type addtype(id.entry, L.type L : T L.type= T

37、.type T integer T.type= 0 T real T.type= 1 用整數(shù)0表示整型, 1表示實(shí)型.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:=S.pos+1; ) Sa 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屬性定義的自上而下分析中各

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

39、是（）A. 引入標(biāo)記非終結(jié)符可以刪除翻譯方案中嵌入的動作B. 使L屬性定義的繼承屬性計(jì)算只出現(xiàn)在產(chǎn)生式左端C. 使L屬性定義的綜合屬性計(jì)算只出現(xiàn)在產(chǎn)生式右端D. 使L屬性定義的綜合屬性計(jì)算只出現(xiàn)在產(chǎn)生式左端答案：A2 L屬性定義的自下而上計(jì)算中引入標(biāo)記非終結(jié)符引入的目的錯誤的是（）A. 刪除翻譯方案中嵌入的動作B. 模擬綜合屬性的計(jì)算C. 模擬繼承屬性的計(jì)算D. 確定分析棧上屬性的位置答案：B3 L屬性定義的自下而上計(jì)算中處理繼承屬性時需要引入（）A. 標(biāo)記非終結(jié)符 B. 標(biāo)記終結(jié)符 C. 綜合屬性 D. L屬性答案：A第六章 6.1, 6.2局部、全局存儲分配O（1）襯墊區(qū)、對齊的概念 選擇

40、題 2分1下列說法正確的是（）A. 襯墊區(qū)是指由于考慮對齊問題而引起的無用空間B. 局部數(shù)據(jù)存儲安排不存在對齊問題C. 局部數(shù)據(jù)的數(shù)據(jù)存儲安排與目標(biāo)機(jī)器的尋址限制無關(guān)D. 襯墊區(qū)是一定會出現(xiàn)的答案：A2關(guān)于襯墊區(qū)的定義，下列說法正確的是（）A. 襯墊區(qū)是在考慮對齊問題時增加的額外空間B. 襯墊區(qū)是指由于考慮對齊問題而引起的無用空間C. 襯墊區(qū)是局部數(shù)據(jù)在存儲的所需要的最大空間D. 襯墊區(qū)是局部數(shù)據(jù)在存儲的所需要的最小空間答案：B3 局部數(shù)據(jù)在存儲安排時，襯墊區(qū)是因?yàn)椋ǎ﹩栴}而引起的無用空間A. 對齊 B. 數(shù)據(jù)的順序 C . 數(shù)據(jù)類型 D. 空間答案：A（2）活動記錄的內(nèi)容 簡答題 5分1活動

41、記錄包括哪些內(nèi)容/答案：返回值，參數(shù)，控制鏈，訪問鏈，保存的機(jī)器狀態(tài)，局部數(shù)據(jù)，臨時數(shù)據(jù)2簡述活動記錄中的各個域及其用途。答案：返回值：用于返回本過程中給調(diào)用過程的值 參數(shù)：調(diào)用過程傳遞給本過程的參數(shù) 控制鏈：指向調(diào)用過程的指針 訪問鏈：用于引用存于其他活動記錄的非局部數(shù)據(jù) 機(jī)器狀態(tài)：御用保存本過程調(diào)用前的機(jī)器狀態(tài) 局部數(shù)據(jù)：本過程內(nèi)部定義的局部變量 臨時數(shù)據(jù)：本過程計(jì)算中可能用到的臨時變量3簡述活動記錄的概念及其內(nèi)容答案：活動記錄是存儲過程執(zhí)行一次所需局部信息的連續(xù)的存儲區(qū)。其內(nèi)容包括返回值，參數(shù)，控制鏈，訪問鏈，保存的機(jī)器狀態(tài)，局部數(shù)據(jù)，臨時數(shù)據(jù)（3）活動樹的概念 簡答題 5分1活動樹有哪

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