編譯原理復(fù)習(xí)題及答案(共20頁(yè))

1、編譯(biny)原理復(fù)習(xí)(fx)題及答案(d n)選擇題一個(gè)正規(guī)語(yǔ)言只能對(duì)應(yīng)(B)A 一個(gè)正規(guī)文法B 一個(gè)最小有限狀態(tài)自動(dòng)機(jī)文法GA：A AaB BAb Ba是(A)A 正規(guī)文法B 二型文法下面說(shuō)法正確的是(A)A 一個(gè)SLR（1）文法一定也是LALR（1）文法B 一個(gè)LR（1）文法一定也是LALR（1）文法一個(gè)上下文無(wú)關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL（1）文法的(A)A 必要條件B 充分必要條件下面說(shuō)法正確的是(B)A 一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)B 一個(gè)正規(guī)語(yǔ)言可能對(duì)應(yīng)多個(gè)正規(guī)文法算符優(yōu)先分析與規(guī)范歸約相比的優(yōu)點(diǎn)是(A)A 歸約速度快B 對(duì)文法限制少一個(gè)LR（

2、1）文法合并同心集后若不是LALR（1）文法(B)A 則可能存在移進(jìn)/歸約沖突B 則可能存在歸約/歸約沖突C 則可能存在移進(jìn)/歸約沖突和歸約/歸約沖突下面說(shuō)法正確的是(A)A Lex是一個(gè)詞法分析器的生成器B Yacc是一個(gè)語(yǔ)法分析器下面說(shuō)法正確的是(A)A 一個(gè)正規(guī)文法也一定是二型文法B 一個(gè)二型文法也一定能有一個(gè)等價(jià)的正規(guī)文法編譯原理是對(duì)(C)。A、機(jī)器語(yǔ)言的執(zhí)行B、匯編語(yǔ)言的翻譯C、高級(jí)語(yǔ)言的翻譯D、高級(jí)語(yǔ)言程序的解釋執(zhí)行(A)是一種典型的解釋型語(yǔ)言。ABASICBCCFORTRANDPASCAL把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A. 編譯器B. 匯編器C.

3、 解釋器D. 預(yù)處理器用高級(jí)語(yǔ)言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)A源程序B目標(biāo)程序C連接程序D解釋程序(C)不是編譯程序的組成部分。A.詞法分析程序B.代碼生成程序C.設(shè)備管理程序D.語(yǔ)法分析程序通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等六個(gè)部分，還應(yīng)包括(C)。A模擬(mn)執(zhí)行器B解釋器C表格處理(chl)和出錯(cuò)處理 D符號(hào)執(zhí)行器編譯程序(bin y chn x)絕大多數(shù)時(shí)間花在(D)上。A出錯(cuò)處理B詞法分析C目標(biāo)代碼生成D表格管理源程序是句子的集合，(B)可以較好地反映句子的結(jié)構(gòu)。A. 線性表B. 樹C. 完全圖D. 堆棧詞法分析

4、器的輸出結(jié)果是(D)。A、單詞自身值B、單詞在符號(hào)表中的位置C、單詞的種別編碼D、單詞的種別編碼和自身值詞法分析器不能(D)A. 識(shí)別出數(shù)值常量B. 過(guò)濾源程序中的注釋C. 掃描源程序并識(shí)別記號(hào)D. 發(fā)現(xiàn)括號(hào)不匹配文法：G：SxSx | y所識(shí)別的語(yǔ)言是(D)。A、xyxB、(xyx)*C、x*yx*D、xnyxn (n0)如果文法G是無(wú)二義的，則它的任何句子(A)A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同B最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同C最左推導(dǎo)和最右推導(dǎo)必定相同D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹相同正則文法(A)二義性的。A. 可以是B. 一定不是C. 一定是(B)這樣

5、一些語(yǔ)言，它們能被確定的有窮自動(dòng)機(jī)識(shí)別，但不能用正則表達(dá)式表示。A. 存在B. 不存在C. 無(wú)法判定是否存在給定文法AbA | ca，為該文法句子的是(C)A. bbaB. cabC. bcaD. cba設(shè)有文法GS：SS1|S0|Sa|Sc|a|b|c，下列符號(hào)串中是該文法的句子有(D)A. ab0B. a0c01C. a0b0aD. bc10文法G產(chǎn)生的(D)的全體是該文法描述的語(yǔ)言。A句型B. 終結(jié)符集C. 非終結(jié)符集D.句子若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是(A)A遞歸的B. 上下文無(wú)關(guān)的C. 二義性的D. 無(wú)二義性的描述一個(gè)語(yǔ)言的文法是(B)A唯一的B. 不唯一的C. 可能唯一

6、一個(gè)(y )文法所描述的語(yǔ)言是(A)A唯一(wi y)的B. 不唯一(wi y)的C. 可能唯一采用自上而下分析，必須(A)。A、消除回溯B、消除左遞歸C、消除右遞歸D、提取公共左因子編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是(A)分析單詞的構(gòu)成分析單詞串如何構(gòu)成語(yǔ)句分析語(yǔ)句是如何構(gòu)成程序分析程序的結(jié)構(gòu)A. B. C. D. 詞法分析器的輸入是( A)。A符號(hào)串 B源程序 C語(yǔ)法單位 D目標(biāo)程序兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的(C)。A狀態(tài)數(shù)相等 B有向弧數(shù)相等C所識(shí)別的語(yǔ)言相等D狀態(tài)數(shù)和有向弧數(shù)相等若狀態(tài)k含有項(xiàng)目“A ”，且僅當(dāng)輸入符號(hào)aFOLLOW(A)時(shí)，才用規(guī)則“A ”歸約的語(yǔ)法分析方法是(D)。A

7、LALR分析法BLR(0)分析法CLR(1)分析法 DSLR(1)分析法若a為終結(jié)符，則A a為(B)項(xiàng)目。A歸約B移進(jìn)C接受D待約在使用高級(jí)語(yǔ)言編程時(shí),首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部和部分(A)錯(cuò)誤。A. 語(yǔ)法B. 語(yǔ)義C. 語(yǔ)用D. 運(yùn)行喬姆斯基(Chomsky)把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是(B)A. 非限制文法B. 正則文法C. 上下文有關(guān)文法D. 上下文無(wú)關(guān)文法一個(gè)句型中的(A)稱為該句型的句柄。A. 最左直接短語(yǔ)B. 最右直接短語(yǔ)C. 終結(jié)符D. 非終結(jié)符在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是(D)A. 尋找句柄B. 尋找句型C. 消除遞歸D.

8、選擇候選式在自頂向下的語(yǔ)法分析方法中，分析的關(guān)鍵是(C)A. 尋找句柄B. 尋找句型C. 消除遞歸D. 選擇候選式在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型(C)的DFA狀態(tài)。A.句柄B. 前綴C. 活前綴D. LR(0)項(xiàng)目一個(gè)(y )上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組(B)A. 句子B. 產(chǎn)生(chnshng)式C. 單詞D. 句型詞法(cf)分析器用于識(shí)別(C)A. 句子B. 產(chǎn)生式C. 單詞D. 句型編譯程序是一種(B)A. 匯編程序B. 翻譯程序C. 解釋程序D. 目標(biāo)程序按邏輯上劃分，編譯程序第三步工作是(A)A. 語(yǔ)

9、義分析B. 詞法分析C. 語(yǔ)法分析D. 代碼生成在語(yǔ)法分析處理中，F(xiàn)IRST集合、FOLLOW集合均是(B)A. 非終結(jié)符集B.終結(jié)符集C. 字母表D. 狀態(tài)集編譯程序中語(yǔ)法分析器接收以(A)為單位的輸入。A. 單詞B. 表達(dá)式C. 產(chǎn)生式D. 句子編譯過(guò)程中，語(yǔ)法分析器的任務(wù)就是(B)A. 分析單詞是怎樣構(gòu)成的B. 分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的C. 分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的D. 分析程序的結(jié)構(gòu)若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子(A)。A.是無(wú)窮多個(gè)B.是有窮多個(gè)C.是可枚舉的D.個(gè)數(shù)是常量識(shí)別上下文無(wú)關(guān)語(yǔ)言的自動(dòng)機(jī)是(C)A. 下推自動(dòng)機(jī)B. NFAC. DFAD. 圖靈機(jī)

10、編譯原理各階段工作都涉及(B)A.詞法分析B.表格管理C.語(yǔ)法分析D.語(yǔ)義分析正則表達(dá)式R1和R2等價(jià)是指(C)A. R1和R2都是定義在一個(gè)字母表上的正則表達(dá)式B. R1和R2中使用的運(yùn)算符相同C. R1和R2代表同一正則集D. R1和R2代表不同正則集已知文法GS:SA1， AA1|S0|0。與G 等價(jià)的正規(guī)式是(C)A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*0與(a|b)*(a|b)等價(jià)的正規(guī)式是(C)。A.a*| b*B.(ab)*(a|b)C. (a|b)(a|b)*D.(a|b)*(D)文法不是LL(1)的。A. 遞歸B. 右遞歸C. 2

11、型D.含有(hn yu)公共左因子的給定(i dn)文法AbA|cc，則符號(hào)串cc bcbc bcbcc bccbcc bbbcc中，是該文法(wnf)句子的是(D)A. B. C. D. LR(1)文法都是()A. 無(wú)二義性且無(wú)左遞歸B. 可能有二義性但無(wú)左遞歸C. 無(wú)二義性但可能是左遞歸D. 可以既有二義性又有左遞歸文法EE+E|E*E|i的句子i*i+i*i有(C)棵不同的語(yǔ)法樹。A. 1B. 3C. 5D.7文法 SaaS|abc 定義的語(yǔ)言是(C)。A.a2kbc|k0B.akbc|k0C.a2k-1bc|k0D.akakbc|k0若B為非終結(jié)符，則 A.B 為(D)。A.移進(jìn)項(xiàng)目B

12、.歸約項(xiàng)目C.接受項(xiàng)目D.待約項(xiàng)目同心集合并可能會(huì)產(chǎn)生新的(D)沖突。A.二義B.移進(jìn)/移進(jìn)C.移進(jìn)/歸約D.歸約/歸約就文法的描述能力來(lái)說(shuō)，有(C)ASLR(1) LR(0)BLR(1) LR(0)CSLR(1) LR(1)D無(wú)二義文法 LR(1)如圖所示自動(dòng)機(jī)M，請(qǐng)問(wèn)下列哪個(gè)字符串不是M所能識(shí)別的(D)。A. bbaaB. abbaC. ababD. aabb有限狀態(tài)自動(dòng)機(jī)能識(shí)別(C)A.上下文無(wú)關(guān)語(yǔ)言B.上下文有關(guān)語(yǔ)言C.正規(guī)語(yǔ)言D.0型文法定義的語(yǔ)言已知文法G是無(wú)二義的，則對(duì)G的任意句型(A)A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能相同C.最左推

13、導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但他們對(duì)應(yīng)的語(yǔ)法樹相同(B)不是(b shi)DFA的成分A.有窮字母表B.多個(gè)(du )初始狀態(tài)的集合C.多個(gè)終態(tài)的集合D.轉(zhuǎn)換函數(shù)與逆波蘭(b ln)式(后綴表達(dá)式)ab+c*d+對(duì)應(yīng)的中綴表達(dá)式是(B)A. a+b+c*dB. (a+b)* c+dC. (a+b)* (c+d)D. a+b*c+d后綴式abc+d+可用表達(dá)式(B)來(lái)表示。A( (a+b)c)+d B(a+(bc)+d C (a(b+c)+d D(a(b+c)+d表達(dá)式A*(B-C*(C/D)的后綴式為(B)。AABC-CD/* BABCCD/*-* CABC-*CD/*

14、 D以上都不對(duì)(D)不是NFA的成分。A. 有窮字母表B. 初始狀態(tài)集合C. 終止?fàn)顟B(tài)集合D. 有限狀態(tài)集合問(wèn)答題將文法GS 改寫為等價(jià)的GS，使GS不含左遞歸和左公共因子。GS： SbSAe | bA AAb | d答：文法GS 改寫為等價(jià)的不含左遞歸和左公共因子的GS為：SbB BSAe | AAd A A bA | 將文法GS 改寫為等價(jià)的GS，使GS不含左遞歸和左公共因子。GS： SSAe|Ae AdAbA|dA|d答：文法GS 改寫為等價(jià)的不含左遞歸和左公共因子的GS為： S AeSS AeS| A dA A AB| B bA | 將文法GS 改寫為等價(jià)的GS，使GS不含左遞歸和左公

15、共因子。GS： SA AB|AS BaB|a答：文法GS 改寫為等價(jià)的不含左遞歸和左公共因子的GS為：S AA BAASA|B aBBB|判斷下面文法是否為L(zhǎng)L(1)文法，若是,請(qǐng)構(gòu)造相應(yīng)(xingyng)的LL(1)分析表。SaHHaMd | dMAb | AaM | e答：首先(shuxin)計(jì)算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非終結(jié)符FIRST集FOLLOW集Sa.# .Ha ，d.# .Ma ，e ，d ，bAa ，e.b.由于(yuy)predict（HaMd）predict（Hd）=ad = predict（MAb）predict（

16、M）=a ，ed ，b = predict（AaM）predict（Ae）= a e = 所以該文法是LL(1)文法，LL(1)分析表如下表。adbe#SaH.HaMdd.MAb.AbAaM.e.判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。SaDDSTe|TbH|HHd|答：首先計(jì)算文法的 FIRST集和FOLLOW集如下表。 非終結(jié)符FIRST集FOLLOW集Sa#，b，d，e.Da，#，b，d，e Tb，d，eHd，e由于predict（DSTe）predict（D）=a# ，b ，d ，e =predict（TbH）predict（TH）=be =predict

17、（Hd）predict（H）= d e =所以該文法是LL(1)文法，LL(1)分析表如下表：aebd#SaD.DSTeTH.bHH.Hd.判斷下面(xi mian)文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。SaDDSTe|TbMMbHHM|答：文法(wnf)的 FIRST集和FOLLOW集非終結(jié)符FIRST集FOLLOW集Sa.# ，bDa ，# ，bTb.e.Mb.e.Hb ，e.由于(yuy)predict（DSTe）predict（D）=a# ，b=predict（HM）predict（H）= b e =所以該文法是LL(1)文法，LL(1)分析表如下表：aeb#S

18、aD.DSTeTbMMbHHM.某語(yǔ)言的拓廣文法G為：(0) SS(1) S Db|B(2) D d|(3) B Ba|證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式SS在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目D d 歸約項(xiàng)目D 和B 存在移進(jìn)-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序?yàn)椋?0) SS(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)項(xiàng)目集族及識(shí)別活前綴(qinzhu)的DFA如下圖：由產(chǎn)生(chnshng)式知Follow(S)=# Follow(D)= bFollow(

19、B)= a ,#在I0中:Follow(D) d= b d=Follow(B) d= a ,# d=Follow(D) Follow(B)= ba ,# =在I3中:Follow(S) a=#a=所以(suy)在I0，I3中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法, 構(gòu)造的SLR(1)分析表如下表：狀態(tài)ACTIONGOTObda#SDB0r4S4r6r61231acc2S53S6r24r35r16r5r5給出與正規(guī)式R（ab）*（a|b*）ba等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖給出與正規(guī)(zhnggu)式R（(ab)*|b）*（a|(ba)*）

20、a 等價(jià)(dngji)的NFA。答：與正規(guī)式R等價(jià)(dngji)的NFA如下圖給出與正規(guī)式 R（aba）*（(ba)*|b）b等價(jià)的NFA。答：與正規(guī)式R等價(jià)的NFA如下圖將下圖的NFA確定化為DFA。答：用子集法確定化如下表IIaIb狀態(tài)X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123確定化后如下圖：將下圖的NFA確定化為DFA。答：用子集(z j)法確定化如下表IIaIb狀態(tài)X,0,1,30,1,3.2,3,Y.1,3.2,Y.Y.0,1,30,1,31,3.1,3.2,3,Y2,3,YY.2,Y.Y.X1234Y確定

21、(qudng)化后如下圖某語(yǔ)言(yyn)的拓廣文法G為：(0) ST (1) T aBd|(2) B Tb| 證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式ST 在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目T aBd和歸約項(xiàng)目T 存在移進(jìn)-歸約沖突，所以G不是LR(0)文法。 若產(chǎn)生式排序?yàn)椋?(0) ST(1) T aBd(2) T (3) B Tb(4) B G的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖所示：識(shí)別G活前綴的DFA由產(chǎn)生(chnshng)式知：Follow(T)=#,b Follow(B)= d在I0中： Follow(T) a=# ，b

22、 a=在I2中：Follow(B) a= d a=Follow(T) a=# ，b a=Follow(B) Follow(T) = d# ，b=所以(suy)在I0，I2，中的移進(jìn)-歸約和歸約-歸約沖突可以(ky)由Follow集解決，所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r3某語(yǔ)言的文法G為： E aTd| T Eb|a證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出該文法的SLR(1)分析表。答：拓廣文法G，增加產(chǎn)生式SE在項(xiàng)目集I0中：

23、 有移進(jìn)項(xiàng)目E aTd和歸約項(xiàng)目E 存在移進(jìn)-歸約沖突，所以G不是LR(0)文法。 .若產(chǎn)生(chnshng)式排序?yàn)椋?0) SE (1) E aTd (2) E (3) T Eb (4) T aG的LR(0)項(xiàng)目集族及識(shí)別(shbi)活前綴的DFA如下圖：由產(chǎn)生(chnshng)式知：Follow(E)=# ，b Follow(T)= d在I0 ，I2中:Follow(E) a=# ，b a=在I5 中:Follow(E) a=# ，b a=Follow(T) a= d a=Follow(T) Follow(E) = d # ，b=所以在I0 ， I2 ， I5中的移進(jìn)-歸約和歸約-歸約沖

24、突可以由Follow集解決,所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表：nameACTIONGOTOabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r2436r1r17r3給出文法GS的LR(1)項(xiàng)目(xingm)集規(guī)范族中I0項(xiàng)目(xingm)集的全體項(xiàng)目。GS為： S BD|D B aD|b D BI0:答：I0：給出文法GS的LR(1)項(xiàng)目(xingm)集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。GS為： S D;D|D D DB|B B a|bI0:答：I0:給出文法GS的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。GS為： S S;V|V V Va

25、A|A A b(S)| I0:答：I0:文法GM及其LR分析(fnx)表如下，請(qǐng)給出對(duì)串dbba#的分析過(guò)程。GM: 1) M VbA2) V d3) V 4) A a5) A Aba6) A nameACTIONGOTObda#MAV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對(duì)串dbba#的分析(fnx)過(guò)程如下表步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作12345678900302024024602467024678024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移進(jìn)用V d歸約移進(jìn)用

26、A 歸約移進(jìn)移進(jìn)用A Aba 歸約用M VbA 歸約接受文法(wnf)GS及其LR分析表如下，請(qǐng)給出對(duì)輸入串da;aoa#的分析過(guò)程。GS: 0) SS1) SdSoS2) S dS3) S S;S 4) S a nameACTIONGOTOda;a#S0S2S3S311S4acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1S4r1答：輸入(shr)串da;aoa#的分析過(guò)程(guchng)如下表：步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作123456789101112 002023025025402543025460250257025730257801#d#

27、da#dS#dS;#dS;a#dS;S#dS#dSo#dSoa#dSoS#Sda;aoa#a;aoa#;aoa#;aoa#aoa#oa #oa #oa #a #移進(jìn)移進(jìn)用S a 歸約移進(jìn)移進(jìn)用S a 歸約用S S;S 歸約移進(jìn)移進(jìn)用S a 歸約用SdSoS 歸約接受文法GM及其LR分析表如下，請(qǐng)給出對(duì)串dada#的分析過(guò)程。GM: 1) S VdB2) V e3) V 4) B a 5) B Bda6) B 狀態(tài)ACTIONGOTOdea#SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5答：對(duì)串dada#的分析(fnx)過(guò)程如下表步驟狀態(tài)棧文法符號(hào)

28、棧剩余輸入符號(hào)動(dòng)作1234567890020240245024602467024678024601#V#Vd#Vda#VdB#VdBd#VdBda#VdB#Sdada#dada#ada#da#da#a#用V 歸約移進(jìn)移進(jìn)用B a歸約移進(jìn)移進(jìn)用B Bda 歸約用S VdB 歸約接受文法(wnf)GE為： EE+T|T TT*F|F F(E)|i試給出句型(j xn)(E+F)*i的短語(yǔ)，簡(jiǎn)單(直接)短語(yǔ),句柄和最左素短語(yǔ)。答：短語(yǔ)有: (E+F)*i ，(E+F) ，E+F ，F(xiàn) ，i 簡(jiǎn)單(直接)短語(yǔ)有：F ，i 句柄是：F最左素短語(yǔ)是：E+F文法GS為：SV VT | ViT TF| T+F

29、F)V* |( 試給出句型ViFi( 的短語(yǔ)，簡(jiǎn)單(直接)短語(yǔ),句柄和最左素短語(yǔ)。答：短語(yǔ)有: ViFi( ，ViF ， F ，(簡(jiǎn)單(直接)短語(yǔ)有: F ，( 句柄是: F 最左素短語(yǔ)是: ViF文法GS為：SSdT | TTTG | GG(S) | a試給出句型(SdG)a的短語(yǔ)、簡(jiǎn)單(直接)短語(yǔ)、句柄和最左素短語(yǔ)。答：句型(SdG)a的短語(yǔ)：(SdG)0 用正規(guī)(zhnggu)文法。(2) L2= a0n1n bdm | n0，m0 用二型文法。 答：(1) 描述(mio sh)L1語(yǔ)言的正規(guī)文法如下： S aS|AA bA|bB B c(2) 描述L2語(yǔ)言的二型文法如下：S AB A

30、aT T 0T1|01 B bD D dD|d 下列語(yǔ)言或文法確切屬于按喬姆斯基（Chomsky）分類的哪種類型,請(qǐng)?zhí)钤冢?）內(nèi)。（1） L1= a0n1nbdm | n0，m 0 ( ) （2） L2= anbncnbm | n0,m0 ( ) （3） L3= anbmc| n0,m0 ( ) （4） GA:AaB| BAb|a ( )（5） GE:EE+E|E*E|(E)|i ( )答：（1） L1= a0n1nbdm | n0，m 0 ( 2 型 ) （2） L2= anbncnbm | n0,m0 ( 1型 ) （3） L3= anbmc| n0,m0 ( 3型 ) （4） GA:AaB| BAb|a ( 2型 ) （5） GE:EE+E|E*E|(E)|i ( 2型 )按指定類型給出下列語(yǔ)言的文法。(1) L1= candbm| n0,m0 用正規(guī)文法。(2) L2= 0na