編譯原理習題集與答案解析整理后

1、精品第一章1、將編譯程序分成若干個“遍”是為了 。a.提高程序的執(zhí)行效率b .使程序的結(jié)構(gòu)更加清晰c.利用有限的機器內(nèi)存并提高機器的執(zhí)行效率d .利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率2、構(gòu)造編譯程序應(yīng)掌握 a.源程序c.編譯方法3、變量應(yīng)當。a.持有左值c.既持有左值又持有右值4、編譯程序絕大多數(shù)時間花在a.出錯處理c.目標代碼生成5、不可能是目標代碼。a.匯編指令代碼c.絕對指令代碼b .目標語百d.以上三項都是b.持有右值d.既不持有左值也不持有右值上。b.詞法分析d.管理表格b .可重定位指令代碼d.中間代碼6、使用 可以定義一個程序的意義。a.語義規(guī)則b.語法規(guī)則c.產(chǎn)生規(guī)則d.詞

2、法規(guī)則7、詞法分析器的輸入是 。a.單詞符號串b.源程序感謝下載載精品c.語法單位d.目標程序8、中間代碼生成時所遵循的是-。b.詞法規(guī)則d.b.詞法規(guī)則d.等價變換規(guī)則b.高級語言程序的解釋執(zhí)行d.高級語言的翻譯b.語法規(guī)則d.等價變換規(guī)則c.語義規(guī)則9、編譯程序是對。a.匯編程序的翻譯c.機器語言的執(zhí)行10、語法分析應(yīng)遵循a.語義規(guī)則c.構(gòu)詞規(guī)則、多項選擇題1、編譯程序各階段的工作都涉及到 。a.語法分析b .表格管理c.出錯處理d .語義分析e .詞法分析2、編譯程序工作時，通常有 階段。a.詞法分析b .語法分析c.中間代碼生成d .語義檢查e .目標代碼生成三、填空題1、解釋程序和編

3、譯程序的區(qū)別在于 。代碼優(yōu)化和目標代碼生程序。2、編譯過程通?？煞譃?5個階段，分別是 、語法分析 成。 3代碼優(yōu)化和目標代碼生程序。4、編譯程序是指將 程序翻譯成 程序的程序。單選解答感謝下載載精品1、將編譯程序分成若干個“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選 bo2、構(gòu)造編譯程序應(yīng)掌握源程序、目標語言及編譯方法等三方面的知識，故選d o3、對編譯而言，變量既持有左值又持有右值，故選 c。4、編譯程序打交道最多的就是各種表格，因此選 do5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選do6、詞法分析遵循的是構(gòu)詞規(guī)則， 語法分析遵循的是語法規(guī)則，

4、中間代碼生成遵循的是語義規(guī)則，并且語義規(guī)則可以定義一個程序的意義。因此選 a。7、b8、c 9、d 10、c多選解答. b、c 2. a、b、c、e填空解答是否生成目標程序2、詞法分析中間代碼生成 3、源程序 目標代碼生成4、源程序 目標語言第二章、單項選擇題1、文法G: SfxSx|y所識別的語言是 。xyxb. (xyx)* c. xnyxn(n 0)d. x*yx*2、文法G描述的語言L(G)是指。L(G)=a|S?a , a CVt* b. L(G)=a|S?*a,a CVt*c. L(G)=a|S?*a,a C(VtUVn*) d . L(G)=a|S?a,“JVtUVn*)3、有限

5、狀態(tài)自動機能識別 。a.上下文無關(guān)文法b.上下文有關(guān)文法c.正規(guī)文法d.短語文法4、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關(guān)系成立 a.若 f(a)g(b),則 ab b.若 f(a)g(b),則 a0a nbncmdm|n,m0ananbmcmdn|n,m 0a nbncmdm|n,m 0e. anbncndn|n 05、自下而上的語法分析中，應(yīng)從 開始分析。a.句型b.句子c.以單詞為單位的程序d.文法的開始符e.句柄6、對正規(guī)文法描述的語言，以下 有能力描述它。a.0型文法 b.1型文法c.上下文無關(guān)文法d.右線性文法e.左線性文法三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是

6、 。詞法分析器交給語法分析器的文法符號一定 是,它一定只出現(xiàn)在產(chǎn)生式的 部。2、最左推導(dǎo)是指每次都對句型中的 非終結(jié)符進行擴展。3、在語法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。4、采用 語法分析時，必須消除文法的左遞歸。5、樹代表推導(dǎo)過程， 樹代表歸約過程。6、自下而上分析法采用 、歸約、錯誤處理、 等四種操作。7、Chomsky 把文法分為 種類型，編譯器構(gòu)造中采用 和 文法，它們分別產(chǎn)生 和 語言，并分別用 和 自動機識別所產(chǎn)生的語言。四、判斷題1、文法,SfaS|bR| 描述的語言是(a|bc)*()感謝下載載精品R 一 cS()()()()()()()()()5、推導(dǎo)

7、3、二義文法不是上下文無關(guān)文法。4、語法分析時必須先消除文法中的左遞歸。5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。6、一個文法所有句型的集合形成該文法所能接受的語言。五、簡答題1、句柄 2、素短語3、語法樹 4、歸約六、問答題1、給出上下文無關(guān)文法的定義。2、文法 GS:SfaSPQ|abQQPfPQ bP f bb bQ 一 bc cQ fcc (1)它是Chomsky 哪一型文法？ (2)它生成的語言是什么？ 3、按指定類型，給出語言的文法。L=a ibj|jiR1的上下文無關(guān)文法。4、有文法 G: SfaAcB|BdA fAaB|cB一 bScA|b(1)試求句型 aAaBcbbdcc和(

8、1)試求句型 aAaBcbbdcc和aAcbBdcc 的句柄;(2)寫出句子 acabcbbdcc的最左推導(dǎo)過程。5、對于文法GS:Sf ( Sf ( L) |aS|aL一 L, S|S(1)畫出句型(S, (a)的語法樹。(2)寫出上述句型的所有短語、直接短語、句柄和素短語。6、考慮文法GT:T-T*F|FF-F1P|PP-(T) |i證明T*P T T*F)是該文法的一個句型，并指出直接短語和句柄。單選解答1、選 c。2、選 a。3、選 Co4、雖然a與b沒有優(yōu)先關(guān)系，但構(gòu)造優(yōu)先函數(shù)后，a與b就一定存在優(yōu)先關(guān)系了。所以，由f(a)g)(b) 或f(a) 13【解答】(1)由L=a ibj|

9、j i 1知，所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有S-aSb型產(chǎn)生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有S-Sb或S-bS型的產(chǎn)生式，用以保證b的個數(shù)多于a的個數(shù)；也即所求上下文無關(guān)文法GS為：GS : S-aSb|Sb|b4【解答】(1)分別畫出對應(yīng)兩句型的語法樹，如圖 2-8-2所示句柄：AaBBd(a)(b)句柄：AaBBd(a)(b)感謝下載載精品圖2-8-2 語法樹(2)句子acabcbbdcc的最左推導(dǎo)如下:acabcbScA acabcbBdcAS aAcB aAaBcB acaBcB acabcBacabcbScA acabcbBdcASacabcbbdcA acab

10、cbbdccS5【解答】(1)句型(S, (a)的語法樹如圖Ia圖2-8-3 句型(S, (a)的語法樹(2)由圖2-8-3 可知：短語：S、a、(a)、S,(a)、(S,(a);直接短語：a、S;句柄：S;素短語：素短語可由圖 2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即;# V(V,() ) #因此素短語為a。T * F圖2-8-4 句型T*P T (T*F T * F圖2-8-4 句型T*P T (T*F )的語法樹首先構(gòu)造T*P T T*F)的語法樹如圖 2-8-4所示。由圖2-8-4 可知，T*P T T*F)是文法GT的一個句型。直接短語有兩個，即 P和T*F ;句柄為P。感謝下載

11、載精品第三章、單項選擇題1、詞法分析所依據(jù)的是。a.語義規(guī)則 精品第三章、單項選擇題1、詞法分析所依據(jù)的是。a.語義規(guī)則 b.構(gòu)詞規(guī)則2、詞法分析器的輸出結(jié)果是 。a.單詞的種別編碼c.語法規(guī)則d.等價變換規(guī)則b.單詞在符號表中的位置c.單詞的種別編碼和自身值3、正規(guī)式 M 1和M2等價是指 M 1和M 2的狀態(tài)數(shù)相等d.單詞自身值M 1和M 2的有向弧條數(shù)相等M 1和M 2所識別的語言集相等M 1和M 2狀態(tài)數(shù)和有向弧條數(shù)相等4、狀態(tài)轉(zhuǎn)換圖(見圖 3-6-1 )接受的字集為a.以0開頭的二進制數(shù)組成的集合b.以0結(jié)尾的二進制數(shù)組成的集合c.含奇數(shù)個0的二進制數(shù)組成的集合d.含偶數(shù)個0的二進制

12、數(shù)組成的集合5、詞法分析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確，因此， a.詞法分析器應(yīng)作為獨立的一遍b.詞法分析器作為子程序較好c.詞法分析器分解為多個過程，由語法分析器選擇使用d.詞法分析器并不作為一個獨立的階段、多項選擇題1、在詞法分析中，能識別出 。a.基本字b.四元式c.運算符d.逆波蘭式e.常數(shù)ab的字的全體對應(yīng)的正規(guī)式為 c.(ba)*b2、令匯=a,b,則匯上所有以ab的字的全體對應(yīng)的正規(guī)式為 c.(ba)*ba. b(ab)*b. b(ab) +d. (ba) + be. b(a|b)三、填空題1、確定有限自動機 DFA是 的一個特例。2、若二個正規(guī)式所表示的 相同

13、，則認為二者是等價的。3、一個字集是正規(guī)的，當且僅當它可由 所。四、判斷題 TOC o 1-5 h z 1、一個有限狀態(tài)自動機中，有且僅有一個唯一終態(tài)。()2、設(shè)r和s分別是正規(guī)式，則有 L (r|s) =L(r)|L(s)。()3、自動機M和M 的狀態(tài)數(shù)不同，則二者必不等價。()4、確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。()5、對任意一個右線性文法G,都存在一個 NFA M ,滿足L(G)=L(M)。()6、對任意一個右線性文法G,都存在一個 DFA M ,滿足L(G)=L(M)。()7、對任何正規(guī)表達式 e,都存在一個 NFA M ,滿足L(G)=L(e)。()感謝下載載精品

14、8、對任何正規(guī)表達式e,都存在一個 DFA M ,滿足L(G)=L(e)。()五、基本題1、設(shè)M = (x,y, a,b, f,x,y)為一非確定的有限自動機，其中 f定義如下：f (x,a) = x,yf (x,b) = yf (y,a) = ef (y,b) = x,y試構(gòu)造相應(yīng)的確定有限自動機M。2、對給定正規(guī)式 b* (d|ad )(b|ab )單選解答多選解答填空解答判斷解答1、b1、 a、 c、1、NFA2、ce 2、22、對給定正規(guī)式 b* (d|ad )(b|ab )單選解答多選解答填空解答判斷解答1、b1、 a、 c、1、NFA2、ce 2、2、3、c a、b、 正規(guī)集4、d

15、5、 b1 、 2、 3、錯4、5、6、1解答：對照自動機的定義 是一非確定有限自動機，先畫出M=(S,3、DFA (NFA)所識別7、8、正確2f,S0,Z),由 f 的定義可知 f(x,a)、f(y,b)NFA M 相應(yīng)的狀態(tài)圖，如圖 3-6-2 所示。均為多值函數(shù),abXYbII a圖 3-6-2 NFA MIbxx,yyy一x,yx,yx,yx,y用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。ab0211一2222表3-6-4狀態(tài)轉(zhuǎn)換矩陣即得到 M = (0,1,2, a,b,f,0, 1,2),其狀態(tài)轉(zhuǎn)換圖如圖 3-6-

16、5所示。感謝下載載精品將圖3-6-5 考察1,2。由于 1,2:令狀態(tài)1 所示化簡DFA M的DFA M 最小化。首先，將M 的狀態(tài)分成終態(tài)組1 , 2與非終態(tài)組將圖3-6-5 考察1,2。由于 1,2:令狀態(tài)1 所示化簡DFA M圖3-6-6 化簡后的DFA M2解答：首先用A + =AA如圖3-6-7所示。改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)其次，構(gòu)造該正規(guī)式的b*(d|ad)(b|ab)(b|ab)*b|abd1234Ybdb12345Yba687.a d_X1adabXa圖3-6-6 化簡后的DFA M2解答：首先用A + =AA如圖3-6-7所示。改造正規(guī)式得：b*

17、(d|ad)(b|ab)(b|ab)其次，構(gòu)造該正規(guī)式的b*(d|ad)(b|ab)(b|ab)*b|abd1234Ybdb12345Yba687.a d_X1adabXab*3(b|ab)*J Y !)圖 3-6-7 的 NFA M感謝下載載精品第四章1、構(gòu)造下面文法的LL (1)分析表。Df TLTf int | realLf id RRf , id R | 下面文法GS是否為LL (1)文法？說明理由。SfAB | P Qx A-x y B-bcP- dP | Q f aQ | 設(shè)有以下文法：GS : SfaAbDe|dAfBSD|eBfSAc| cD| D fSe| e(1)求出該文法

18、的每一個非終結(jié)符U的FOLLOW 集(2)該文法是LL (1)文法嗎？(3)構(gòu)造CS的LL (1 )分析表。將文法GV改造成為LL(1)的。GV : VfN|NE感謝下載載精品E 一 V|V+E NT 5、已知文法：GA :A - aAa| (1)該文法是LL (1)文法嗎?為什么？(2)若采用LL (1)方法進行語法分析，如何得到該文法的LL (1)分析表？(3)若輸入符號串“ aaaa”，請給出語法分析過程。1解答：LL (1)分析表見表4-3-1分析 雖然這個文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。FIRST (D) =FIRST (T) =int, realFOLLOW

19、 (D) =FOLLOW (L) =#FIRST (L) =idFOLLOW (T) =idFIRST (R) = , , 4FOLLOW (R) =#有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部a的FIRST ( a)就不是件難事了。填表時唯一要小心的時，e是產(chǎn)生式R-e右部的一個開始符號，而 #在FOLLOW (R)中，所以R- e填在輸入符號#的欄目中。表4-3-1 LL (1)分析表非終結(jié)符輸入符號intrealid#DD f TLDfTLTT- intT 一 realLLfid R感謝下載載精品RRf,id RR 一 2解答：該文法不是LL (1)文法，見下面

20、分析中的說明。分析只有三個非終結(jié)符有兩個選擇。1、P的兩個右部d P和e的開始符號肯定不相交。2、Q的兩個右部a Q和的開始符號肯定不相交。3、對S來說，由于x C FIRST(A B),同時也有x FIRST(P Q x)(因為P和Q都可能為空)所以該文法不是LL (1 )文法。3解答： (1 )求文法的每一個非終結(jié)符U的FOLLOW 集的過程如下：因為：S是識別符號，且有 A- BSD、BfSAc、DfSe,所以FOLLOW (S)應(yīng)包含F(xiàn)IRST(D) U FIRST(Ac) U FIRST(e) U#=a,d U a,d,c,e U e U #=a,c,d,e#又因為A -BSD和D-

21、 s,所以FOLLOW 中還包含 FOLLOW(A)。因為S-aAbDe 和B-SAc,所以FOLLOW (A) =FIRST (bDe ) U FIRST (c) =b,c綜合、得 FOLLOW (S) =a,d,c,e,# U a,b,c,d,e,#因為 A- BSD,所以 FOLLOW (B) =FIRST (SD) =a,d因為 S-aAbDe | d 、A - BSD| e 和 B-SAc | cD ,所以FOLLOW (D) =FIRST (e) U FOLLOW (A) U FOLLOW (B)=e U b,c U a,d=a,b,c,d,e(2) GS不是 LL (1 )文法。

22、感謝下載載精品因為產(chǎn)生式B-SAc|cD|中FIRST (SAc) nFOLLOW (B) =a,d w?(3)構(gòu)造GS的LL (1)分析表。按照LL (1)分析表的構(gòu)造算法構(gòu)造方法GS的LL (1)分析表如表4-3-2所示。表4-3-2 GS的LL (1 )分析表abcde#SaAbDedABSDBSDBSDeBSac/ ecDSac/ eDSe/ Se/ 4解答：對文法GV提取公共左因子后得到文法:G V : V-NAAEE 一 VBBf s|+EN fi求出文法G V中每一個非終結(jié)符號的 FIRST集:FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B尸+,FI

23、RST(N)=i求出文法G V中每一個非終結(jié)符號的FOLLOW集：FOLLOW(V)=# U FIRST(B) U FOLLOW(E尸#,+,FOLLOW(A)= FOLLOW(V尸+,#感謝下載載精品FOLLOW(E)= FIRST() U FOLLOW(B)= FIRST() U FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) U FOLLOW(V)=,+,#可以看到，對文法 G V的產(chǎn)生式A-e|E,有FIRST(E) AFOLLOW(A)= 0+,#=?對產(chǎn)生式B- s|+E ,有FIRST(+E) AFOLLOW(B)=+ 0=

24、 ?而文法的其他產(chǎn)生式都只有一個不為的右部，所以文法G V是LL(1)文法。5解答：(1)因為產(chǎn)生式 A - aAa| e有空產(chǎn)生式右部，而FOLLOW(A)=# U FIRST(a)=a, #造成 FIRST(A) AFOLLOW(A)=A, Aa, # w?所以該文法不是LL (1 )文法。(2)若采用LL (1)方法進行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)(可以為0)個a,所以得到文法G A ： A-aaA| 此時對產(chǎn)生式 A - aaA| ,有 FOLLOW(A)=# U FOLLOW(A)=# ,因而FIRST(A) AFOLLOW(A)=a,*#= ?所以文法G A是LL (

25、 1 )文法，按LL (1 )分析表構(gòu)造算法本造該文法的LL (1 )分析表如表4-3-3所示。表4-3-3文法G A的LL(1)分析表A#AA 一 aaAA - 感謝下載載精品(3)若采用LL(1)方法進行語法分析，對符號串“ aaaa”的分析過程如表 4-3-4所示。表4-3-4對符號串“ aaaa ”的分析過程步驟分析棧輸入串產(chǎn)生式/動作1#Aa a a a #A 一 aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #A 一 aaA5#A a aa a #匹配6#A aa#匹配7#A#A - 8#接受第五章.設(shè)有文法GS為:Sfa|b|(A)AfSdA

26、|S完成下列算符優(yōu)先關(guān)系表，見表5-7-1，并判斷GS是否為算符優(yōu)先文法。表5-7-1算符優(yōu)先關(guān)系表ab()d#a?b?感謝下載載精品(?)?d#?(2)給出句型(SdSdS)的短語、簡單短語、句柄、素短語和最左素短語。(3)給出輸入串(adb ) #的分析過程。解答：(1)先求文法 GS的FIRSTVT 集和LASTVT 集：由 S-a|b|(A)得：FIRSTVT(S)=a,b,();由 A - Sd 得：FIRSTVT(A)=d; 又由 A - S得：FIRSTVT(S) ? FIRSTVT(A)，即 FIRSTVT(A)=d,a,b,(;由 S-a|b|(A)得；LASTVT(S)=a

27、,b,;由 A 一 dA 得：LASTVT(A)=d, 又由 A - S 得：LASTVT(S) ? LASTVT(A),即 LASTVT(A)=d,a,b,) 。構(gòu)造優(yōu)先關(guān)系表方法如下：對Pfab，或P faQb，有a? b;對 PfaR，而 b C FIRSTVT(R),有 a? b;對 PfRb ，而 a FIRSTVT(R),有 a? b。由此得到：由 S一(A)得：(?); 由 S一(A 得：(? FIRSTVT(A)，即：(? d,( ? a ,( ? b,( ?(;由 A一dA 得：d ? FIRSTVT(A), 即：d? d,d ? a,d ? b,d ?(; 由 S-A)得，

28、LASTVT(A) ?)，即：d? ),a ? ),b ? ),) ?);由 A-Sd 得：LASTVT(S) ?d，即：a ? d,b ? d,) ? d;此外，由#S#得:#? #;由#? FIRSTVT(S)得：#? a,#? b,# ?(;脂由 LASTVT(S) ? #得：d? #,a ? #,b ? #,) ? #。最后得到算符優(yōu)先關(guān)系表，見表 5-7-2 。表5-7-2算符優(yōu)先關(guān)系表ab()d#a?b?(?)?d?#?由表5-7-2可以看出，任何兩個終結(jié)符之間至少只滿足？、？、？三種優(yōu)先關(guān)系之一，故 GS為算符優(yōu)先文法。（2）為求出句型（SdSdS）的短語、簡單短語、句柄，我們先

29、畫出該句型對應(yīng)的語法樹，如感謝下載載圖5-7-3所示。由圖5-7-3得到：感謝下載載短語：S, SdS , SdSdS , （SdSdS ）簡單短語（即直接短語）：S句柄（即最左直接短語）：S素短語：SdS ,它同時也是該句型的最左素短語。精品（3）輸入串（adb ） #的分析過程見表 5-7-4表5-7-4輸入串（adb ） #的分析過程符號棧輸入串說明#(adb)#移進# (adb)#移進# (adb)#用S-a歸約# (Sdb)#移進# (Sdb)#移進# (Sdb)#用S-b歸約# (SdS)#用A - S歸約# (SdA)#用A - SdA歸約# (A)#移進# (A)#用S-（A）

30、歸約#S#分析成功感謝下載載精品第六章精品第六章、單項選擇題1、若a為終結(jié)符，則A 一 a a 3為 項目a.歸約b.移進c.接受d.待約2、若項目集Ik含有Af&則在狀態(tài)k時，僅當面臨的輸入符號 a FOLLOW(A)時，才采取“A 一動作的一定是。a.LALR 文法 b.LR (0)文法 c.LR (1)文法 d.SLR (1)文法3、就文法的描述能力來說，有 。a. SLR (1) ? LR (0) b. LR (1) ? LR (0) c. SLR (1) ? LR ( 1) d.無二義文法？ LR (1)4、在LR (0)的ACTION子表中，如果某一行中存在標記“ rj”的欄，則

31、。a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一部分。a.活前綴b.前綴c.項目d.項目集、多項選擇題1、一個LR分析器包括 。a.一個總控程序b.一個項目集c. 一個活前綴d. 一張分析表e. 一個分析棧2、LR分析器核心部分是一張分析表，該表包括 等子表。a.LL(1)分析b.優(yōu)先關(guān)系c.GOTOd.LRe.ACTION3、每一項ACTIONS , a3、每一項ACTIONS , a所規(guī)定的動作包括 。a.移進 b.比較 c.接受 d.歸約4、對LR分析表的構(gòu)造，有可能存在 動作沖突。c.移衽7d.移

32、進/移進a.移進 b.歸約5、就文法的描述能力來說，有SLR (1) ?LR d. LR (1) ?無二義文法6、對LR分析器來說，存在a.LALR b.LR (0)7、自上而下的語法分析方法有 a.算符優(yōu)先分析法d.LR (0)分析法LR (1) ? SLR (1)e. SLR (1) ?無二義文法 一等分析表的構(gòu)造方法。c.SLR (1) d.SLR (0)b.LL (1)分析法e.LALR (1)分析法e.報錯e.歸約/歸約LR (0) ? LR ( 1)e.LR (1)c.SLR (1)分析法三、填空題1、對于一個文法，如果能夠構(gòu)造 。使得它的 均是唯一確定的，則稱該文法為LR文法。2

33、、字的前綴是指該字的 。3、活前綴是指 的一個前綴，這種前綴不含 之后的任何符號。4、在LR分析過程中，只要 的已掃描部分保持可歸約成一個 ,則掃描過的部分正確。5、將識別 的NFA確定化，使其成為以 為狀態(tài)的DFA,這個DFA就是建立 的基礎(chǔ)。6、A-稱為項目；對文法開始符S 一 a 為 項目；若a為終結(jié)符，則稱A- a a 3為項目；若B為非終結(jié)行則稱 A aS為 項目。7、LR (0)分析法的名字中“ L”表示, “R”表示, “0表示。 四、綜合題1、對于文法 GS : S-AS|bA 一 SA|a(1)列出所有LR (0)項目(2)列出構(gòu)成文法 LR (0)項目集規(guī)范族。 單項解答：

34、1、A-稱為歸約項目，對文法開始符 S的歸約項目，如 S a 稱為接受項目，A- a ,a 3 (a為終結(jié)符)稱為移進項目。在此選 b.2、當用產(chǎn)生式Af“歸約時，LR (0)無論面臨什么輸入符號都進行歸約；SLR (1)則僅當面感謝下載載精品臨的輸入符號a FOLLOW(A)時進行歸約；LR (1)則當在把 “歸約為A的規(guī)范句型的前綴 由a 前提下，當“后跟終結(jié)符a時，才進行歸約；因此選 do3、由于 LR (0) ? SLR ( 1) ? LR (1) ?無二義文法，故選 c。4、選 a。5、選 c。多選解答：1、一個LR分析器包括一個總控程序和一張分析表，選a、d。2、c、e o3、選

35、a、c、d、e。4、在LR分析表的構(gòu)造中有可能存在“移進” / “歸約”和“歸約” / “歸約”沖突；故選 c、 e。5、選 a、b、c、d、e。6、選 a、b、c、e。7、選 a、c、d、e。填空解答：1、一張分析表每個入口2、任意首部3、規(guī)范句型句柄4、輸入串 活前綴5、活前綴 項目集合 LR分析算法6、歸約接受移進待約7、自左至右分析采用最右推導(dǎo)的逆過程即最左歸約向右查看0個字符綜合解答：首先將文法 G拓廣為GS:2、列出構(gòu)成文法LR (0)2、列出構(gòu)成文法LR (0)項目集規(guī)范族。用 CLOSURE(閉包)辦法構(gòu)造文法 G的LRI。： 1、S f SI3： 9、A -S A3、Sf A

36、S8、Af SA8、Af SA3、Sf AS11、Af a6、Sf b6、Sf b11、Af aI1 : 2、S f S -I4： 10、A fSA9、A f S A4、Sf A S8、Af SA3、Sf AS11、Af a6、Sf b3、Sf AS8、Af SA6、Sf b11、Af aI2： 4、S-A SI 5 ： 5、Sf AS ,3、Sf AS9、A fS A6、Sf b8、Af SA8、Af SA11、Af a11、Af a3、Sf AS6、Sf b(0)項目集規(guī)范族如下：I6： 12、Afa - 17: 7、S b ,S fS Sf AS|b A fSA|a文法GS 的LR(0)

37、項目是：1、S f S5、S-AS -9、AfS A2、S f S 6、Sf，b10、A f SA3、Sf AS7、S-b ,11、Af a4、Sf A S8、Af SA12、A fa -注意：Ii中的S -S 和Af-SA是由狀態(tài)I0中的1和3讀入一個S字符后得到的下一個項目；， 而I4中的A -SA和A fA S則是由I3中的9和3讀入一個A字符后得到的下一個項目；I5中的S fAS -和AfS A則是由I4中的4和8讀入一個S字符后得到的下一個項目。狀態(tài)全體構(gòu)成了文法 G的LR (0)規(guī)范族。感謝下載載精品第七章、單項選擇題1、中間代碼生成所依據(jù)的是。a.語法規(guī)則b.詞法現(xiàn)財c.語義規(guī)則

38、d.等價變換規(guī)則2、四元式之間的聯(lián)系是通過 實現(xiàn)的。a.指示器b.臨時變宣c.符號表d.程序變量3、后綴式ab+cd+/可用表達式 來表不a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d) d.a+b+c/d4、表達式(r AVB) A (OVD)的逆波蘭表示為。a. rABVACDVb. A n B VCD V AAB VrCDVAA r BV/CD VAB VrCDVAA r BV/CD V5、中間代碼的樹型表示A B C D5、中間代碼的樹型表示A B C D所對應(yīng)的表達式為a.A+B+C+Db.A+(B+C)+D6、四元式表示法的優(yōu)點為 a.A+B+C+Db.A+(B+

39、C)+D6、四元式表示法的優(yōu)點為 。a.不便于優(yōu)化處理，但便于表的更動c.便于優(yōu)化處理，也便于表的更動7、終結(jié)符具有屬性。a.傳遞b.繼承、多頂選擇題1、中間代碼主要有。a.四元式b .二元式c.(A+B)+C+Dd.(A+B)+(C+D)b.不便于優(yōu)化處理，但節(jié)省存儲空間d.便于表的更動，也節(jié)省存儲空間c.抽象d.綜合c.三元式d .后綴式e.間接三元式2、下面中間代碼形式中，能正確表示算術(shù)表達式a+b+c的有ab+c+abc+e. a+b+cab+c+abc+e. a+b+c3、在下面的 語法制導(dǎo)翻譯中，采用拉鏈 -回填技術(shù)。a.賦值語句b . goto語句 c.條件語句d .循環(huán)語句4、

40、下列 中間代碼形式有益于優(yōu)化處理。a.三元式 b.四元式c.間接三元式d.逆波蘭表示法e.樹形表示法5、在編譯程序中安排中間代碼生成的目的是a.便于進行存儲空間的組織c.a.便于進行存儲空間的組織c.利于編譯程序的移植e.利于提高目標代碼的質(zhì)量6、下面的中間代碼形式中， b.利于目標代碼的優(yōu)化d.利于目標代碼的移植能正確表示算術(shù)表達式a+b*c 。題)a. ab+c*b . abc*+a. ab+c*b . abc*+7、三地址代碼語句具體實現(xiàn)通常有 表示方法。d .樹形表示e .四元式a.逆波蘭表示 b.d .樹形表示e .四元式感謝下載載精品三、填空題 TOC o 1-5 h z 1、中間

41、代碼有 等形式，生成中間代碼主要是為了使 。2、語法制導(dǎo)翻譯既可以用來產(chǎn)生一代碼,也可以用來產(chǎn)生 指令，甚至可用來對輸入串進行。3、當源程序中的標號出現(xiàn)“先引用后定義” 時，中間代碼的轉(zhuǎn)移地址須持 時才能確定,因而要進行。4、文法符號的屬性有兩種，一種稱為 ,另一種稱為 。5、后綴式abc-/所代表的表達式是 ,表達式(a-b)*c可用后綴式 表不。6、用一張 輔以 的辦法來表示中間代碼,這種表示法稱為間接三元式。一四、綜合題1、給出下列表達式的逆波蘭表示(后綴式)： a*(-b+c)(A VB)A(CVnD AE)2、寫出算術(shù)表達式：A+B*(C-D)+E/(C-D) 僅 的四元式序列；三元

42、式序列；間接三元式序列單選解答1、選 c。2、四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的，故選 bo3、選 b。4、選 b。5、選 d。6、四元式表示法的優(yōu)點與間接三元式相同，故選 co7、選 d o多選解答1、選 a、c、d、e。2、b、d的中間代碼不能正確表示a+b+c ,而e不是中間代碼：故選 a、c。3-凡涉及到跳轉(zhuǎn)的語句都需要采用拉鏈一一回填技術(shù)，故選 b、c、d。4、選 b、Co5、選 b、 do6、選 b、e。7、選 b、c、e。填空解答1、逆波蘭記號、樹形表示、三元式、四元式目標代碼的優(yōu)化容易實現(xiàn)2、中間 目標解釋執(zhí)行3、標號定義回填4、繼承屬性綜合屬性5、a/(b-c) ab-c*

43、6、間接碼表三兀式表綜合解答1、abc+*;2、表達式的四元式序列:AB VCDr EA 2、表達式的四元式序列:(1)(-,C,D,T 1)(1)(-,C,D)(1)(-CD)(2)(*,B,T i,T2)(2)(*,B,(1)(2)(*,B,(1)(3)(+,A,T 2,T3)(3)(+,A,(2)(3)(+,A,(2)(4)(-,C,D,T 4)(4)(-,C,D)(4)(T ,(1),N)(5)(T ,T4,N,T5)(5)(4),N)(4)(/,E,(4)(6)(/,E,T5,T6)(6)(/,E,(5)(6)(+,(3),(5)(+,T3,T6,T7)感謝下載載(+,(3),(6)

44、(6)表達式的二兀式序列間接三元式序列精品第八章、單項選擇題1、編譯程序使用 區(qū)別標識符的作用域。a.說明標識符的過程或函數(shù)名b.說明標識符的過程或函數(shù)的靜態(tài)層次c.說明標識符的過程或函數(shù)的動態(tài)層次d.標識符的行號2、在目標代碼生成階段，符號表用于 。a.目標代碼生成b.語義檢查c.語法檢查d.地址分配3、過程信息表不包含 。a.過程入口地址 b.過程的靜態(tài)層次c.過程名 d.過程參數(shù)信息4、下列關(guān)于標識符和名字敘述中，正確的是 。a.標識符有一定的含義b.名字是一個沒有意義的字符序列c.名字有確切的屬性d. a-c都不正確、多項選擇題1、符號表的每一項均包含 。a.名字欄 b.類型欄c.信息

45、欄d.值欄 e. ad均包含2、對編譯程序所用到的符號表，涉及的操作有 。a.填寫或更新信息欄內(nèi)容b.填入新名c.給定名字，訪問它的有關(guān)信息感謝下載載精品d.雜湊技術(shù)e,線性表和排序二叉樹3、源程序中的錯誤一般有 。a,詞法錯誤b,語法錯誤c,語義錯誤d,編譯錯誤 e,違反環(huán)境限制的錯誤三、填空題1、符號表中名字欄內(nèi)容有兩種填寫方式，它們是 填寫和 填寫。2、詞法分析階段的錯誤主要是 ,可通過 的辦法糾正錯誤。3、符號表中名字的有關(guān)信息在 和 過程中陸續(xù)填入。4、在目標代碼生成階段，符號表是 的依據(jù)。四、問答題：1、在編譯過程中為什么要建立符號表？單選解答：1、b 2、d 3、b4、c多選解答

46、：1、a、c 2、a、b、c 3、a、b、c、e填空解答：1、標識符標識符地址及長度 2、拼寫錯誤 最小距離匹配 3、詞法分析 語法語義分析4、地址分配問答題解答：在編譯過程中始終要涉及到對一些語法符號的處理，這就需要用到語法符號的相關(guān)屬性。為了 在需要時能找到這些語法成分及其相關(guān)屬性，就必須使用一些表格來保存這些語法成分及其屬性， 這些表格就是符號表。第九章、單項選擇題1、程序所需的數(shù)據(jù)空間在程序運行前可確定，稱為 管理技術(shù)。a.動態(tài)存儲b.棧式存儲c,靜態(tài)存儲d,堆式存儲2、堆式動態(tài)分配申請和釋放存儲空間遵守 原則。a,先請先放b,先請后放c,后請先放d,任意3、靜態(tài)分配允許程序出現(xiàn) 。a

47、,遞歸過程b,可變體積的數(shù)據(jù)項目c,靜態(tài)變量d,待定性質(zhì)的名字4、在編譯方法中，動態(tài)存儲分配的含義是 。a,在運行階段對源程序中的數(shù)組、變量、參數(shù)等進行分配感謝下載載精品b.在編譯階段對源程序中的數(shù)組、變量、 精品b.在編譯階段對源程序中的數(shù)組、變量、 c.在編譯階段對源程序中的數(shù)組、變量、 數(shù)的地址可根據(jù)需要改變d.以上都不正確5、在編譯時有傳名功能的高級程序語言是參數(shù)進行分配參數(shù)等進行分配，在運行時這些數(shù)組、變量、參a. Fortranb. Basic c. Pascal d. ALGOL6、棧式動態(tài)分配與管理在過程返回時應(yīng)做的工作有 。a.保護SP b.恢復(fù)SP c.保護TOP d.恢復(fù)

48、TOP二、多項選擇題1、下面 需要在運行階段分配存儲空間。a.數(shù)組b.指針變量c.動態(tài)數(shù)組d.靜態(tài)變量e.動態(tài)變量2、棧式動態(tài)分配允許。a.遞歸過程b.分程序結(jié)構(gòu)c.動態(tài)變量d.動態(tài)數(shù)組e.靜態(tài)數(shù)組3、動態(tài)存儲分配可采用的分配方案有 。a.隊式存儲分配b.棧式存儲分配c.鏈式存儲分配d.堆式存儲分配e.線性存儲分配4、棧式動態(tài)分配與管理因調(diào)用而進入過程之后，要做的工作是 。a.定義新的活動記錄的 SP b.保護返回地址 c.傳遞參數(shù)值d.建立DISPLAY表e.定義新的活動記錄的TOP5、靜態(tài)分配不允許程序出現(xiàn) 。a.遞歸過程b.靜態(tài)數(shù)組c.可變體積的數(shù)據(jù)項目d.待定性質(zhì)的名字e.靜態(tài)變量6、活動記錄包括。a.局部變量b.連接數(shù)據(jù)c.形式單元d.局部數(shù)組的內(nèi)情變量e.臨時工作單元三、填空題1、FORTRAN語言采