編譯原理復習題教材

1、一、填空題：(10分，第1小題每2個1分，其余每空1分)1 編譯程序一般含有八部分，分別是、2、編譯程序與解釋程序的根本區(qū)別是3、一個上下文無關文法G包括四個組成部分依次為:一組、一個、一組、一組O4、設G是一個文法,S是文法的開始符號,如果Sn* X,則稱X是o二、選擇題(本大題共15小題，每小題1分，共15分)1、編譯程序生成的目標程序是機器語言程序。A、一定B、不一定2、設有文法GS= (b,S,B,S,S-b|bB, B-bS)，該文法描述的語言是CA、B、b2i|i0 C、b2i+1|i0 D、b2i+1 |il3、設有文法 GS：S-S*S|S十S| (S) |a該文法二義性文法A

2、、是 B、不是 C、無法判斷4、匯編程序是將翻譯成；編譯程序是將翻譯成A、匯編語言程序B、機器語言程序C、高級語言程序 D、匯編語言或機器語言程序5、給定文法A-bA|cc,下面符號串中，為該文法句子的是o cc bcbc bcbcc bccbccbbbccA、 B. C、 D、 E、6、語法分析的常用方法是。 自頂向下自底向上自左向右自右向左A、B、 C、 D、7、己知語言L=anbbn|nl,則下述文法中，可以產(chǎn)生語言LA、Z-*aZb|aAb|b A-*aAb|b B、A-*aAb A-*bC、ZAbB A-*aA|a B-*bB|b D、Z-*aAb A-*aAb|b8、下列正規(guī)表達式

3、中與(a|b)*(c|d)等價。A、(a*|b*) (c|d) B、(a*|b*) *(c|d) C、(ab)*(d|c) D、(a*b*) (cd)9、算符優(yōu)先分析法每次都是對進行歸約。A、最左短語 B、直接短語 C、句柄 D、素短語 E、最左素 短語10、簡單優(yōu)先分析法每次都是對進行歸約A、最左短語 B、直接短語 C、句柄 D、素短語 E、最左素 短語11、下列文法GS： S-AA A-*Aa|a不是LR (1)文法，理由是A.、FIRST(S) Cl FIRST (A) H0 B、FIRST (A) A FOLLOW (A)H0C、FIRST (Aa) A FIRST (a) H0 D、

4、都不是12、設有文法 GE： E-E*E|E+E| (E) |a 該文法LR (1)文法A、是 B、不是 C、無法判斷13、對于文法 GA：A-aABe|Ba B-dB|s有人說，因為 FIRSTC aABe) A FOLLOW( A) H 0 并且 FIRSTC Ba) D FOLLOW(A)工0,所以文法GA不是LL (1)文法。這種說法A、正確 B、不正確14、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：A、B、 C、 D、

5、E、 F、 G、15、表達式A* (B-C* (C/D)的逆波蘭式為A、ABC-CD/*B、ABCCD/*-*C、 ABC-*CD/*D、都不正確三、簡答題(共35分)1、(10分)現(xiàn)有文法GEE1：E-E 十 T|E-T|T T-T*F|T/F|F F-(E)|i畫出句型E+F* (E+i)的語法樹，找出它的短語，直接短語，句柄和素短 語2、(5分)對下面的文法GS構造狀態(tài)轉(zhuǎn)換圖，并說明符號串a(chǎn)aba是否 是該文法接受的句子：S-aA S-B A-abS A-bB B-b B- cC C-D D-d D-*bB3、(10分)將下面具有w的NFA確定化4、(5分)求出下列文法所產(chǎn)生語言對應的正

6、規(guī)式o S-*aAA-*bA| aB| bB*aAo(5分)構造識別下面正規(guī)式的NFA (a|b) la。二、選擇題(本大題共20小題，每小題1分，共20分)1、匯編程序是將翻譯成；編譯程序是將翻譯成oa、匯編語言程序 b、機器語言程序c、高級語言程序d匯編語言或機器語言程序2、描述一個語言的文法是。a. 唯一的 b.不唯一的 c、個數(shù)有限的3、生成非0開頭的正偶數(shù)集的文法是c、Z:=ABC|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0|0 A:=l|2|3|4|5|6|7|8|9d、Z:=ABC|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0| A:=l|2|3|4

7、|5|6|7|8|9a、Z:=ABCC:=0|2|4|6|8B:=BA|BO| A:=l|2|3|4|5|6|7|8|9b、Z:=ABCC:=0|2|4|6|8B:=BA|BO|OA:=l|2|3|4|5|6|7|8|94、設有文法GI：I-IO|Il|Ia|Ic|a|b|cF列符號串中是該文法的句子的有. abO aOcOl 眈a bclO 可選項有a、b、c、 d.5、現(xiàn)有前綴表示的表達式文法Gl：E:=-EEE:=-E E:=a|b|c則文法的句子a-bc的所有可能語法樹有棵。a 1 b、 2 c、 3 d、 46、一個上下文無關文法G包括四個組成部分依次為:一組、一個、一組、一組。a、

8、字符串 b、字母數(shù)字串c、產(chǎn)生式 d、結束符號e、開始符號f、文法g、非終結符號h、終結符號7、語法分析的常用方法是: 自頂向下自底向上自左向右 自右向左可選項有：a、 b、c、d、8、下列文法二義文法E:=E 訂 |T T:=T+F|iF|F F:=E*|(可選項有：a、是b、不是c、無法判斷。9、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：a、 b、c、 d、 e、f、g、10、LR (K)文法是oa、從左到右分析，共經(jīng)過K步的

9、一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。11、在編譯中產(chǎn)生語法樹是為了。a、語法分析b、語義分析c、詞法分析d、產(chǎn)生目標代碼12、文法的二義性和語言的二義性是兩個概念。a不同 b、相同 c、無法判斷13、下述正規(guī)表達式中與(a*+b)*(c+d)等價。 a* (c+d) +b (c+d) a* (c+d) *+b (c+d) * a* (c+d) +b* (c+d) (a+b) *c+ (a+b) *d (a*+b) *c+ (a*+b) *d可選項有:a

10、、b、c、d、e、f、g、14、這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示:a、存在b、不存在c、無法判定是否存在15、LL (K)文法二義性的。a、都是 b、都不是 c、不一定都是16、下面的文法是。S:=aAa|aBb|bAb|bBa A:=x E:=x可選項有：a、LR (1)文法b、LALR (1)文法c、都不是d、n和b17、編譯過程中，比較常見的中間語言有o 波蘭表示 逆波蘭表示 三元式 四元式 樹形表示可選項有：a、b、 c、 d、18、-a- (b*c/ (c-d) + (-b) *a)的逆波蘭表示是。a abc*cd-b-a*+/b、a-bc*cd-b-

11、a*+/-c、a-bc*cd-/b-a*+-d a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是o 便于進行存儲空間的組織 利于目標代碼優(yōu)化 利于編譯程序的移植 利于目標代碼的移植 利于提高目標代碼的質(zhì)量可選項有：a、 b、 c、 d、20、 代碼優(yōu)化的主要目標是o 如何提高目標程序的運行速度 如何減少目標程序運行所需的空河。 如何協(xié)調(diào)和 如何使生成的目標代碼盡可能簡短可選項有：a、 b、c、d、三、簡答題：(每小題5分，共35分)1、證明下面文法是二義性的。S:=ibtSeS|ibtS|a2、現(xiàn)有文法 S: :=SaA|A A: =AbBIB B: :=cSd|e請證

12、實是文法的一個句型，并寫出該句型的所有短語、素短語以及句柄。3、求出下列文法所產(chǎn)生語言對應的正規(guī)式。S:=bS|aA A:=aA bB B:=aA bC bC:=bS|aA4、將表達式(a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列5、消除下列文法的左遞歸。S:=SaP|Sf|PP:二QbP|QQ:=cSd|e6、給出與下圖的NFA等價的正規(guī)文法。7、對基本塊P畫出DAG圖B:=3D:二A+CE:=A*CF:=E+DG:=B*FH:二A+CI:=A*CJ:=H+IK:=B*5L:二K+JM:=L假定只有L在基本塊出口之后活躍，寫出優(yōu)化后的四元式序列。1、文法 Gl： P a

13、PQR| abR, RQ- QR, BQ- bb, bR- be, cR- cc,它是 chomsky哪一型文法？A、0型 B、1型 C、2型 D、3型2、編譯程序必須完成的工作有 詞法分析語法分析語義分析代碼生成中間代碼生成代碼 優(yōu)化(DE、(DC、D、3、LR (K)文法二義性的。A、都是 B、都不是 C、不一定都是4、語法分析的常用方法是o自頂向下自底向上自左向右自右向左A、B、 C、 D、5、用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標代碼后才能投入運行, 這種說法A、不正確B、正確6、生成非0開頭的正偶數(shù)集的文法是oA、Z:=ABCC:=0|2|4|6|8B:=BA|B0| eA:

14、=l|2 卩 |4|5|6 卩8|9B. Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0|0A:=l|2 卩 |4|5|6 卩8|9C、Z:=ABCC:=0|2|4|6|8B:=BA|BO|OA:=l|2 卩 |4|5|6 卩 |8|97、文法G所描述的語言是D、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|BO| eA:=l|2|3|4|5|6|7|8|9 的集合A、文法G的字匯表V中所有符號組成的符號串B、文法G的字匯表V的閉包V*中的所有符號串C、由文法的開始符號推出的所有符號串D、由文法的開始符號推出的所有終結符號串。8、給定文法GI:I-Il|

15、IO|Ia|Ic|a|b|c,下面符號串中，為該文法句子的是。 abO aOcOlaaabe 10A、 B、C、 D、9、這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表A、存在B、不存在C、無法判定是否存在 10、LR (K)文法是A、從左到右分析，共經(jīng)過K步的一種編譯方法。B、從左到右分析，每次向前預測K步的一種編譯方法。C、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種 編譯方法。D、從左到右分析，每次走K步的一種編譯方法。11、-a- (b*c/ (c-d)十(-b) *a)的逆波蘭表示是。A、a-bc*cd-/b-a*+-B、a-bc*/cd-b-a*+-C

16、、abc*cd-b-a*+/ D、a-bc*cd-b-a*+/-12、設有文法 GS= (b,S,B,S,S-*b|bB, B-*bS)，該文法描述的語言是。A、b2i+1 | il B、b2i+1 110 C、0 D、b21|i2013、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語 可選項有：A、B、C、D、E、F、 G、14、算符優(yōu)先分析屬于分析方法。A、自頂向下B、自底向上C、自左向右 D、自右向左15、簡單優(yōu)先分析法每次都是對進行歸約

17、A、最左短語 B、直接短語 C、句柄 D、素短語 E、最左素 短語16、文法 GS：S-aS S-W S-U U-a V-bV V-ac W f aW其中的全部無用符號是A、W, V , U B、V, b C、W, V, a,b,c D、W, V, b,c17、程序基本塊是指A、一個子程序B、一個僅有一個入口和一個出口的語句C、一個沒有嵌套的程序段D、一組順序執(zhí)行的程序段，僅有一個入口和一個出口18、設有文法GZ： Z-Z*Z|Z+Z| (Z) |a 該文法二義性文法A、是 B、不是 C、無法判斷19、下列正規(guī)表達式中與(a|b)*(c|d)等價。A、(a*|b*) (c|d) B、(a*|b

18、*) *(c|d) C、(ab)*(d|c) D、(a*b*) (cd)20、語法分析的任務是分析單詞是怎樣構成的分析單詞串是如何構成語句和說明的分析語句和說明是如何構成程序的分析程序的結構A、B、C、 D、二、(簡答題，共計20分)1、(10 分)己知文法 G (T)： TT*F|F FtF t P|P PT(T)|i(1) 寫出句型T*Pt (T*F)推導過程，畫出語法樹；(2) 寫出句型T*Pt (T*F)的短語、直接短語、句柄和素短語。2、(5分)構造識別下面正規(guī)式的NFA*b (aa|bb) ab3、(5分)消除文法GS的左遞歸GS： S-ABA-*bB|Aa B-Sb|a三、(綜合

19、題，共計30分)1、(10分)將下面具有sNFA確定化和最小化2、（10 分）（1）對下面的文法GZZ-*aB AaB BbB BaA B-*b構造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子（2）寫出GZ文法相應的正規(guī)式：3、（10 分）設有以下文法 GS： S-aAbDe|d A-BSD|e B-*SAc|cD|e D -*Se|s（1）求出文法中每個非終結符的FOLLOW集（2）該文法是LL （1）文法嗎？構造LL （1）分析表一、選擇題（本大題共20小題，每小題1分，共20分）1、描述一個語言的文法是。a. 唯一的 b、不是唯一的 c、個數(shù)有限的2、簡單優(yōu)先分析法每次都

20、是對進行歸約。a. 最左短語 b、直接短語c、句柄 d、素短語 e、最左素短語3、設有文法GI：1 10 |I1 |Ia |Ic |a |b |c下列符號串中是該文法的句子的有abO a0c01 aaa be 10可選項有a、b、 c、d、4、LR （K）文法二義性的。a. 都是 b、都不是 c、不一定都是5、一個上下文無關文法G包拾四個組成部分依次為：一組、一個、一組、_組Oa、字符串 b、字母數(shù)字串 c、產(chǎn)生式 d、結束符號 e、開始符號f、文法 g、非終結符號h、終結符號6、文法G所描述的語言是的集合a、文法G的字匯表V中所有符號組成的符號串b、文法G的字匯表V的閉包V*中的所有符號串c

21、、由文法的開始符號推出的所有符號串d、由文法的開始符號推出的所有終結符號串。7、設有文法GZ： ZZ*Z|Z+Z| （Z） |a 該文法二義性文法a、是 b、不是 c、無法判斷8、語法分析的常用方法是: 自頂向下自底向上自左向右 自右向左可選項有：a、b、c、d、9、LR （K）文法是。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再

22、包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：a、 b、c、 d、 e、f、g、11、文法的二義性和語言的二義性是兩個概念。a不同 b、相同 c、無法判斷12、在編譯中產(chǎn)生語法樹是為了oa、語法分析b、語義分析c、詞法分析 d、產(chǎn)生目標代碼13、下列正規(guī)表達式中與(a|b)*(c|d)等價。a (a*|b*) (c|d) b、(a*|b*) *(c|d) c、(ab)*(d|c) d、(a*b*) (cd)15、這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示:a、存在b、不存在 c、無法判定是否存在16、文法

23、GS： S-*aS S-*W S-U U-a V-*bV V-ac W-aW其中的全部無用符號是()a、(W, V, U) b、(V, b) c、(W, V, a,b,c) d、(W, V, b, c)16. ab3的另一種表示方法是()a、abbb b、ababab c、abbaab d aaabbb17、編譯過程中，比較常見的中間語言有 波蘭表示 逆波蘭表示 三元式 四元式 樹形表示可選項有：a、b、 c、 d、18、a (b*c/ ( cd) + (b ) *a)的逆波蘭表示是。a、 abc*cd-b-a*+/b、a-bc*cd-b-a*+/_c、a-bc*cd/b-a*+-d、a-bc

24、*/cd-b-a*+一19、在編譯程序中安排中間代碼生成的目的是 便于進行存儲空間的組織 利于目標代碼優(yōu)化 利于編譯程序的移植 利于目標代碼的移植 利于提高目標代碼的質(zhì)量 可選項有：a、b、 c、20、設有文法 GS= (b, S,B,S, S-b|bB, B-*bS)，該文法描述的語言是()。a、b21*1 i$l b、bE i$0 c、b1 I i$0d、b：1i$0二、簡答題：(每小題5分，共30分)1、證明下面文法是二義性的。P-PaP|PbP|cP|Pe|f2、設一文法 E-*T|E+T|E-T T-*F|T*F|T/F F (E) |i 證明 E+T* (E-T)是它的一個句 型，

25、并指出該句型的全部短語，直接短語，句柄和素短語。3、求出下列文法所產(chǎn)生語言對應的正規(guī)式。S*bS | aA A*aA bB B*aA bC b C*bS aA4、將表達式(B*D+A) 任+D) *FKi分別表示為三元式、四元式、逆波蘭式序列5、消除文法GS的左遞歸(GS)GS： SAB AbE|AaSb|a6、對下面的文法GZZ-*aB AaE Ef E B aA Bb構造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子一、選擇題(本大題共20小題，每小題1分，共20分)1、要在某一臺機器上為某種語言構造一個編譯程序，必須找掌握下述三方面的內(nèi)容: 高級語言 源語言 目標語言 程序

26、設計方法 編譯方法 測試方法機器語言可選項有 b、C、d、2、“用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標代碼后才能投入運行。”這種說法oa、不正確 b、正確3、若一個文法是遞歸的，則它所產(chǎn)生的句子個數(shù)a、必定是無窮的b、是有限個的c、根據(jù)具體情況而定4、下列文法二義文法E:=EiT|T T:=T+F|1F|F F:=ET|(可選項有：a、是b、不是 c、無法判斷。5、編譯程序的語法分析器接受以為單位的輸入，并產(chǎn)生有關信息供以后各階段使用?？蛇x項有：a、表達式 b、產(chǎn)生式 c、單詞 d、語句6、文法 GZ： Z-*Be A-*Ae|e B-Af D-*f 中，是多余產(chǎn)生式a、 Z-*Be

27、b、 A-*Ae|e c、B-*Af d、D*f7、算符優(yōu)先文法屬于。a、自頂向下語法分析法b、LR分析法 c、SLR分析法 d、自底向上語法分析法8、設有文法GS= (a, S,B, S, Sa|aE.aS),該文法描述的語言是a、ai|i$O b、aiO c、a2i+1|i0 d、a2i+1|il9、描述語言L=ambQ|nml的文法是a ZABbb ZABb c、ZAbd、ZaAbA_aA|aB-bB|bAAa|a B-aBb|bAaAb|aAAb|aAb| e10、一個句型中的最左稱為該句型的句柄。a、短語 b、直接短語c、素短語 d、終結符號11、通常高級語言的詞法規(guī)則可用正規(guī)式描述

28、，詞法分析器可用來實現(xiàn)a、語法樹b、有限自動機c、棧d、堆12、文法 GS： S-*AA A-*Aa|a 不是 LR (1)文法，理由是。a、FIRST(S)HFIRSTCAJOb、FIRST(A) A FOLLOW(A)工 0c、FIRST(Aa)QFIRST(a)工 0d、都不是13、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語可選項有：a、 b、c、 d、 e、f、g、14、給定文法 GS： S-ACc A-aA|Sb C-*Def D

29、-*liACDd|eC| E-*bDe|該文法是o (1)右線性文法 (2)前后文無關文法 (3)左遞歸文法 (4) LL (1)文法可選項有：a、 b、 c、 d、15、算符文法是指的文法。 沒有形如U-VW的規(guī)則(U、V、W為非終結符) 終結符號集中任意兩個符號對之間至多有一種優(yōu)先關系成立 沒有相同的規(guī)則右部 沒有形如U-的規(guī)則可選項有a、b、c、 d、16、下列正規(guī)表達式中與(a|b)*(c|d)等價。a、(a*|b*) (c|d) b、(a*|b*) *(c|d) c、(ab)*(d|c) d、(a*b*) (cd)17、若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部是該句型的句柄a、一

30、定b、不一定18、前后文無關文法和正規(guī)文法所產(chǎn)生的語言類相比a.前后文無關文法產(chǎn)生的語言類人b、正規(guī)文法產(chǎn)生的語言類大c、兩者產(chǎn)生的語言類一樣大d、無法比較19、編譯過程中，比較常見的中間語言有c 波蘭表示 逆波蘭表示 三元式 四元式 樹形表示可選項有：a、b、 c、 d、20、LL (1)文法的條件是oa、對形如 U-Xl|X2|-|Xii 的規(guī)則，要求 FIRST (Xi) )QFIRST (Xj)=0 (iHj)b、對形如 UXl|X2|-|Xn 的規(guī)則 若 Xi=* 則要求 FIRST(Xj) Cl FOLLOW (U)=0c、a 和 bd、都不是二、簡答題：(每小題5分，共30分)1

31、、對于下面的文法GSS-*Sa|Ab|b|c A-*Bc|a B*Sb|b構造狀態(tài)轉(zhuǎn)換圖,并說明符號串bcbabcba是否是該文法接受的句子2、設一文法 GT： T-*T*F|F F-*F t P|P P-*(T)|i 證明 T*P t (T*F)是它的一個句 型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出下列文法所產(chǎn)生語言對應的正規(guī)式。Z-*aZ|bZ|aA A-*aB B-*aA|b4、將表達式(A+E*D) /E+F) *F+G-E分別表示為三元式、四元式、逆波蘭式序列。5、(5分)消除文法GS的左遞歸GS： S-*SA|A A-*SB|B|(S)|()B*S |6、(5分

32、)對下面的文法GEE-*E+T|T|T T-T*F|F F-P t F|P P-i (+、*、f、i 是終結符號)構造文法的算符優(yōu)先矩陣表，判斷此文法是否是算符優(yōu)先文法。一、填空題(每空1分，共20分)1、假設G是一個文法，S是文法的開始符號，如果S0X,則稱X是o2、喬姆斯基定義的四種形式語言分別為：文法、文法、文法、文法。3、設有文法GI：I-Il|IO|Ia|Ic|a|b|c，下列符號串中是該文法的句子的有(1) abO (2)a0c01 (3)aaa (4)bcl04、一個上下文無關文法G包含四個組成部分依次為：一組, 一組,個，以及一組o5、確定的有窮自動機是一個,通常表示為。6、

33、編譯程序一般含有八部分，分別7E、 、 二、簡答題(每題5分，共30分)1、己知文法GZ：Z-UO|V1U-Z1|1V-Z0|0寫出全部由此文法描述的只含有四個符號的句子。2、文法GN為:ND|NDD-*0|l|2 卩 |4|5|6 卩 |8|9GN的語言是什么？3、設一文法GSSf (AS)S- (b)A (SaA)A (a)對于句子(b) a (a) (b),寫出該句子的最左推導，畫出語法樹，寫出 其全部短語，直接短語和句柄。4、構造下述文法GS的自動機：S-AOA_AO|S1|O5、將表達式(a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列6、消除下列文法的左遞歸。S:

34、=SaP|SfP P:=QbP|Q Q:=cSd|e一、選擇題(本犬題共20小題，每小題1分，共20分)1、描述一個語言的文法是。a.唯一的 b、不唯一的c、個數(shù)有限的2、匯編程序是將翻譯成；編譯程序是將翻譯成oa、匯編語言程序 b、機器語言程序c、高級語言程序d匯編語言或機器語言程序3、設有文法GI：IIO|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有 abO aOcOl aaa bclO可選項有a、b、c、 d、4、生成非0開頭的正偶數(shù)集的文法是oa Z:=ABCC:=0|2|4|6|8B:=BA|B0| eA:=l|2|3|4|5|6|7|8|9b、Z:=ABCC:=0|

35、2|4|6|8B:=BA|B0|0A:=l|2|3|4|5|6|7|8|95、一個上下文無關文法G包括四個組成部分依次為:一組一組。a、字符串 b、字母數(shù)字串g、非終結符號h、終結符號6、現(xiàn)有前綴表示的表達式文法G1：c、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0|0A:=l|2|3|4|5|6|7|8|9d、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0| A:=l|2|3|4|5|6|7|8|9、一個.一組c、產(chǎn)生式d、結束符號e、開始符號f、文法E:=-EEE:=-E E:=a|b|c則文法的句子a-bc的所有可能語法樹有棵。a 1 b、2

36、 c、3 d、47、下列文法二義文法E:=EiT|T T:=T+F|iF|F F:=E*|(可選項有：a、是b、不是c、無法判斷。8語法分析的常用方法是:自頂向卞 可選項有:自底向上自左向右 自右向左a、 b、c、d、 9、LR (K)文法是a. 從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析,每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指的短語。至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符

37、號 除自身外不再包含其它短語 除自身外不再包含其它素短語 可選項有：a b、c、 d、 e.f、g、11、文法的二義性和語言的二義性是兩個概念。a不同 b、相同 c、無法判斷12、在編譯中產(chǎn)生語法樹是為了oa、語法分析b、語義分析c、詞法分析 d、產(chǎn)生目標代碼13、下述正規(guī)表達式中與(a*+b)*(c+d)等價。 a* (c-rd) +b (c+d) a* (c+d) *+b (c+d) * a* (c+d) +b* (c+d) (a+b) *c+ (a+b) *d (a*+b) *c+ (a*+b) *d可選項有:a、b、c、d、e、f、g、17、這樣的語言，他們能被確定的有限自動機識別，但

38、不能用正規(guī)表達式表示:a、存在b、不存在c、無法判定是否存在15、LL (K)文法二義性的。a.都是 b、都不是 c、不一定都是16、下面的文法是o S:=aAa|aBb|bAb|bBa A:=x B:=x可選項有：a、LR (1)文法b、LALR (1)文法c、都不是d、a和b17、編譯過程中，比較常見的中間語言有o 波蘭表示 逆波蘭表示 三元式 四元式 樹形表示可選項有：a、b、 c、 d、18、-a- (b*c/ (c-d) + (-b) *a)的逆波蘭表示是a abc*cd-b-a*+/b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*

39、+-19、在編譯程序中安排中間代碼生成的目的是o 便于進行存儲空間的組織 利于目標代碼優(yōu)化 利于編譯程序的移植 利于目標代碼的移植 利于提高目標代碼的質(zhì)量可選項有：a、 b、 c、 d、20、 代碼優(yōu)化的主要目標是o 如何提高目標程序的運行速度 如何減少目標程序運行所需的空間。 如何協(xié)調(diào)和 如何使生成的目標代碼盡可能簡短可選項有：、 b、c、d、二、簡答題：(每小題5分，共30分)1、寫一個文法使其語言為L(G)= anbmbn | 111,11 lo2、對于文法G(E):EtT IE+TTtF 丨 T*FFt (E) I i(1) 寫出句型(T*F+i)的最右推導并畫出語法樹。(2) 寫出上

40、述句型的短語，直接短語、句柄和素短語。3、求出下列文法所產(chǎn)生語言對應的正規(guī)式。S:=bS|aA A:=aA|bB B:=aA bC bC:=bS|aA4、將表達式(a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列5、消除下列文法的左遞歸。S：=SaP|Sf|P P：=QbP|Q Q:=cSd|e、給出與下圖的NFA等價的正規(guī)文法。選擇題(本大題共20小題，每小題1分，共20分)1、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語 除自身外不再包含其它素短語

41、可選項有：A、 B、 C、 D、 E、 F、G、I2、表達式ab+cd+*的逆波蘭式表達式所表示的中綴形式的表達式是A、a+b+c*dB、(a+b)*(c+d)C、(a+b)*c+dD a+b*c+d3、Chomsky的3型語言是這樣一種語言，其產(chǎn)生式限制為(a、兀、卩為字符 串)。A、 ApB、 Aa AaBC、a卩D、aA卩f 01兀卩4、設有文法GS= (b,S,B,S,S-b|bB, B-bS)，該文法描述的語言是。A、iy|0 B、b2i|i0 C、b2i+11 iO D、b2i+1 |il5、設有文法GS：S-S*S|S十S| (S) |a該文法 A、是二義性文法B、不是 C、無法

42、判斷6、匯編程序是將翻譯成；編譯程序是將翻譯成A、匯編語言程序 B、機器語言程序 C、高級語言程序 D、匯編語言或 機器語言程序7、給定文法A-bA|cc,下面符號串中，為該文法句子的是。 cc bcbc bcbcc bccbccbbbccA、 B. C、 D、 E、8、遞歸下降分析語法分析的屬于分析方法。A、自頂向下B、自底向上C、自左向右 D、自右向左9、己知語言L=aW|nl,則下述文法中，可以產(chǎn)生語言LA、Z-*aZb|aAb|b A-*aAb|b B、A-*aAb AbC、Z-AbB A-aA|a B-bB|bD、Z-aAb A-aAb|b10、若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則

43、此右部是句柄。A、一定 B、不一定11、考慮文法 GA： A-AVB|B C-AD BBC| D- (A) |i,該文法LL(1)文法。A、是 B、不是12、簡單優(yōu)先分析法每次都是對進行歸約A、最左短語B、直接短語C、句柄 D、素短語 E、最左素短語13、下列文法GS： S-AA A-*Aa|a不是LR (1)文法，理由是A.、FIRST(S) Cl FIRST (A) H0 B、FIRST (A) n FOLLOW (A) H0C、FIRST (Aa) A FIRST (a) H0 D、都不是14、設有文法 GE： E-E*E|E+E| (E) |a 該文法LR (1)文法A、是 B、不是

44、C、無法判斷15、對于文法GAA-*ABe|Ba B-*dB|s有人說，因為 FIRST (aABe) DFOLLOW (A) H0 并且 FIRST (Ba) AFOLLOW (A)工0,所以文法GA不是LL (1)文法。這種說法A、正確 B、不正確16、下列正規(guī)表達式中與(a|b)*(c|d)等價。A、(a*|b*) (c|d) B、(a*|b*) *(c|d) C、(ab)*(d|c) D、(a*b*) (cd)17、若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部是該句型的句柄A、一定B、不一定18、前后文無關文法和正規(guī)文法所產(chǎn)生的語言類相比A、前后文無關文法產(chǎn)生的語言類大B、正規(guī)文法產(chǎn)生

45、的語言類大C、兩者產(chǎn)生的語言類一樣大D、無法比較19、編譯過程中，比較常見的中間語言有o 波蘭表示 逆波蘭表示 三元式 四元式 樹形表示可選項有：A、B.C、 D、20、LL (1)文法的條件是oA、對形如 U_Xl|X2|Xn 的規(guī)則,要求 FIRST (Xi) )nFIRST (Xj)=0 (1 Hj)B、對形如U-Xl|X2|Xn的規(guī)則 若Xi=* e則要求FIRST(Xj) A FOLLOW (U)=0C、a和bD、都不是二、綜合題：(共35分)1、(10分)對于文法G(S):SbMbM t (L | aLt Ma)(1) 寫出句型b(Ma)b的最右推導并畫出語法樹。(2) 寫出上述句

46、型的短語，直接短語和句柄。2、(5分)對下面的文法GS構造狀態(tài)轉(zhuǎn)換圖，并說明符號串a(chǎn)abca是否是該 文法接受的句子：S Aa SB ACc ABb BBb Ba CD CBab Dd3、(10分)將下面具有的肛人確定化ill4、(5分)求出下列文法所產(chǎn)生語言對應的正規(guī)式。S-aS S-bA S-b A-aS5、(5分)構造識別下面正規(guī)式的NFA ab (a|b) *一、選擇題(本大題共20小題，每小題1分，共20分)1、文法的二義性和語言的二義性是兩個概念。a不同 b、相同 c、無法判斷2、在編譯中產(chǎn)生語法樹是為了。a、語法分析b、語義分析c、詞法分析d、產(chǎn)生目標代碼3、卞述正規(guī)表達式中與(

47、a*+b)*(c+d)等價。 a* (c+d) +b (c+d) a* (c+d) *+b (c+d) * a* (c+d) +b* (c+d)(a+b) *c+ (a+b) *d(a*+b) *c+ (a*+b) *d可選項有:a、b、c、d、e、f、g、4、這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示:a、存在b、不存在c、無法判定是否存在5、LL (K)文法二義性的。a、都是 b、都不是 c、不一定都是6、現(xiàn)有前綴表示的表達式文法G1：E:=-EEE:=-E E:=a|b|c則文法的句子a-bc的所有可能語法樹有棵。a 1 b、2 c、3 d、47、下列文法二義文法E

48、:=EiT|T T:=T+F|iF|F F:=E*|(可選項有：a、是b、不是c、無法判斷。8、語法分析的常用方法是: 自頂向下 自底向上 自左向右 自右向左 可選項有：a b、c、d、 9、LR (K)文法是a. 從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析,每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指的短語。 至少包含一個符號 至少包含一個非終結符號 至少包含一個終結符號 除自身外不再包含其它終結符號 除自身外不再包含其它非終結符號 除自身外不再包含其它短語

49、除自身外不再包含其它素短語可選項有：a、 b、c、 d、 e、f、g、11、描述一個語言的文法是o a、唯一的 b、不唯一的 c、個數(shù)有限的12、匯編程序是將翻譯成；編譯程序是將翻譯成oa、匯編語言程序 b、機器語言程序c、高級語言程序d匯編語言或機器語言程序13、設有文法GI：I-*IO|Il|Ia|Ic|a|b|c下列符號串中是該文法的句子的有:abO aOcOl aaa bclO可選項有a、b、c、 d、14、生成非0開頭的正偶數(shù)集的文法是。a、Z:=ABCC:=0|2|4|6|8B:=BA|B0| eA:=l|2|3|4|5|6|78|9b、Z:=ABCC:=0|2|4|6|8B:=BA|B0|0A:=l|2|3|4|5|6|78|9c、Z:=ABC|2|4|6|8C:=0|2|4|6|8B:=BA|B0|0A:=l|2|3|4|5