編譯原理復(fù)習(xí)題.doc

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

2、13、設(shè)有文法GS： SS*S|S+S|（S）|a 該文法 二義性文法 A、是 B、不是 C、無法判斷4、匯編程序是將_翻譯成_；編譯程序是將_翻譯成_。A、匯編語言程序 B、機器語言程序 C、高級語言程序 D、匯編語言或機器語言程序5、給定文法AbA|cc, 下面符號串中，為該文法句子的是 。 cc bcbc bcbcc bccbcc bbbccA、 B、 C、 D、 E、6、語法分析的常用方法是 。自頂向下 自底向上 自左向右 自右向左A、 B、 C、 D、7、已知語言L=anbbn|n1，則下述文法中， 可以產(chǎn)生語言L A、ZaZb|aAb|b AaAb|b B、AaAb Ab C、ZA

3、bB AaA|a BbB|b D、ZaAb AaAb|b 8、下列正規(guī)表達式中_與(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 ：SAA AAa|a不是LR（1）文法，理由是 A.、FIRST(S)FIRST（A） B、FIRST（A）FOLLOW（A） C、FIRST（Aa）

4、FIRST（a） D、都不是 12、設(shè)有文法GE：EE*E|E+E|（E）|a 該文法 LR（1）文法A、是 B、不是 C、無法判斷13、對于文法GA： AaABe|Ba BdB|e 有人說，因為FIRST（aABe）FOLLOW（A） 并且FIRST（Ba）FOLLOW（A），所以文法GA不是LL（1）文法。這種說法 A、正確 B、不正確14、素短語是指_的短語。至少包含一個符號至少包含一個非終結(jié)符號至少包含一個終結(jié)符號除自身外不再包含其它終結(jié)符號除自身外不再包含其它非終結(jié)符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：A、 B、 C、 D、 E、 F、 G、15、表達式A*

5、（B-C*（C/D）的逆波蘭式為 A、 ABC-CD/* B、 ABCCD/*-* C、 ABC-*CD/* D、都不正確三、簡答題（共35分）1、 (10分)現(xiàn)有文法GE: EE+T|E-T|T TT*F|T/F|F F(E)|i畫出句型E+F*（E+i）的語法樹,找出它的短語，直接短語，句柄和素短語2、 (5分)對下面的文法GS構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aba是否是該文法接受的句子： SaA SB AabS AbB Bb BcC CD Dd DbB3、 (10分)將下面具有e的NFA確定化SABZabaee4、 (5分)求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。SaA AbA|aB|b Ba

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

7、ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0|0 B:=BA|B0|A:=1|2|3|4|5|6|7|8|9 A:=1|2|3|4|5|6|7|8|94、設(shè)有文法GI：II0|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有_。ab0 a0c01 aaa bc10 可選項有a、 b、 c、 d、5、現(xiàn)有前綴表示的表達式文法G1：E:=-EE E:=-E E:=a|b|c則文法的句子a-bc的所有可能語法樹有_棵。a、1 b、2 c、3 d、46、一個上下文無關(guān)文法G包括四個組成部分依次為：一組_、一個_、一組_、一組_。a、字符串 b、字

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

9、步的一種編譯方法。b、從左到右分析，每次向前預(yù)測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。11、在編譯中產(chǎn)生語法樹是為了_。a、語法分析 b、語義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼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、 b、 c、

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

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

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

13、定只有L在基本塊出口之后活躍，寫出優(yōu)化后的四元式序列。1、 文法G1：P aPQR| abR，RQ QR，BQ bb，bR bc，cR cc，它是chomsky哪一型文法？ A、0型 B、1型 C、2型 D、3型2、編譯程序必須完成的工作有 詞法分析 語法分析 語義分析 代碼生成 中間代碼生成 代碼優(yōu)化 B、 C、 D、3、LR（K）文法_二義性的。A、都是 B、都不是 C、不一定都是4、語法分析的常用方法是_。自頂向下 自底向上 自左向右 自右向左A、 B、 C、 D、5、用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標(biāo)代碼后才能投入運行，這種說法 A、不正確 B、正確6、生成非0開頭的正偶數(shù)

14、集的文法是_。A、Z:=ABC B、Z:=ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0| B:=BA|B0|0A:=1|2|3|4|5|6|7|8|9 A:=1|2|3|4|5|6|7|8|9 C、Z:=ABC D、 Z:=ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0|0 B:=BA|B0|A:=1|2|3|4|5|6|7|8|9 A:=1|2|3|4|5|6|7|8|97、文法G所描述的語言是 的集合A、文法G的字匯表V中所有符號組成的符號串B、文法G的字匯表V的閉包V*中的所有符號串C、由文法的開始符號

15、推出的所有符號串D、由文法的開始符號推出的所有終結(jié)符號串。8、給定文法GI:II1|I0|Ia|Ic|a|b|c, 下面符號串中，為該文法句子的是 。 ab0 a0c01 aaa bc10A、 B、 C、 D、 9、_這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：A、存在 B、不存在 C、無法判定是否存在10、LR（K）文法是_。A、從左到右分析，共經(jīng)過K步的一種編譯方法。B、從左到右分析，每次向前預(yù)測K步的一種編譯方法。C、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。D、從左到右分析，每次走K步的一種編譯方法。11、-a-（b*c/（c-d）+（-

16、b）*a）的逆波蘭表示是_。A、a-bc*cd-/b-a*+- B、a-bc*/cd-b-a*+-C、abc*cd-b-a*+/- D、a-bc*cd-b-a*+/-12、設(shè)有文法GS=（b,S,B,S,Sb|bB, BbS）,該文法描述的語言是 。 A、b2i+1 | i1 B、b2i+1 | i0 C、bi | i0 D、b2i | i013、素短語是指_的短語。至少包含一個符號至少包含一個非終結(jié)符號至少包含一個終結(jié)符號除自身外不再包含其它終結(jié)符號除自身外不再包含其它非終結(jié)符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：A、 B、 C、 D、 E、 F、 G、14、算符優(yōu)先

17、分析屬于 分析方法。A、自頂向下 B、自底向上 C、 自左向右 D、自右向左15、簡單優(yōu)先分析法每次都是對 進行歸約A、最左短語 B、直接短語 C、句柄 D、素短語 E、最左素短語16、文法GS：SaS SW SU Ua VbV Vac WaW其中的全部無用符號是 A、W，V ，U B、V，b C、 W，V，a, b ,c D、W，V，b，c17、程序基本塊是指 A、一個子程序 B、一個僅有一個入口和一個出口的語句C、一個沒有嵌套的程序段 D、一組順序執(zhí)行的程序段，僅有一個入口和一個出口18、設(shè)有文法GZ：ZZ*Z|Z+Z|（Z）|a 該文法 二義性文法 A、是 B、不是 C、無法判斷19、下

18、列正規(guī)表達式中_與(a|b)*(c|d)等價。A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)20、語法分析的任務(wù)是 分析單詞是怎樣構(gòu)成的 分析單詞串是如何構(gòu)成語句和說明的分析語句和說明是如何構(gòu)成程序的 分析程序的結(jié)構(gòu) A、 B、 C、 D、二、（簡答題，共計20分）1、(10分)已知文法G（T)：TT*F|FFFP|PP(T)|i (1)寫出句型T *P（T*F）推導(dǎo)過程，畫出語法樹；(2)寫出句型T *P（T*F）的短語、直接短語、句柄和素短語。2、(5分)構(gòu)造識別下面正規(guī)式的NFAb（aa|bb）*ab3、（5分）消除文法G

19、S的左遞歸 GS：SAB AbB|Aa BSb|a 三、（綜合題，共計30分）1、(10分)將下面具有e的NFA確定化和最小化SABZabaee 專業(yè) 年級（本、?？疲?學(xué)號_ 姓 名 _密封線2、(10分)（1）對下面的文法GZ ZaB AaB BbB BaA Bb 構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子（2） 寫出GZ文法相應(yīng)的正規(guī)式：3、（10分）設(shè)有以下文法GS：SaAbDe|d ABSD|e BSAc|cD|e DSe|e（1）求出文法中每個非終結(jié)符的FOLLOW集（2）該文法是LL（1）文法嗎？構(gòu)造LL（1）分析表一、選擇題（本大題共20小題，每小題1分，

20、共20分）1、描述一個語言的文法是_。a、唯一的 b、不是唯一的 c、個數(shù)有限的2、簡單優(yōu)先分析法每次都是對_進行歸約。a、最左短語 b、直接短語 c、句柄 d、素短語 e、最左素短語3、設(shè)有文法GI：II0 |I1 |Ia |Ic |a |b |c下列符號串中是該文法的句子的有_。ab0 a0c01 aaa bc10 可選項有a、 b、 c、 d、4、LR（K）文法_二義性的。a、都是 b、都不是 c、不一定都是5、一個上下文無關(guān)文法G包括四個組成部分依次為：一組_、一個_、一組_、一組_。a、字符串 b、字母數(shù)字串 c、產(chǎn)生式 d、結(jié)束符號 e、開始符號 f、文法 g、非終結(jié)符號 h、終結(jié)

21、符號6、文法G所描述的語言是_的集合a、文法G的字匯表V中所有符號組成的符號串b、文法G的字匯表V的閉包V*中的所有符號串c、由文法的開始符號推出的所有符號串d、由文法的開始符號推出的所有終結(jié)符號串。7、設(shè)有文法GZ：ZZ*Z|Z+Z|（Z）|a 該文法_二義性文法 a、是 b、不是 c、無法判斷8、語法分析的常用方法是_：自頂向下 自底向上 自左向右 自右向左 可選項有：a、 b、 c、 d、9、LR（K）文法是_。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預(yù)測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右

22、分析，每次走K步的一種編譯方法。10、素短語是指_的短語。至少包含一個符號至少包含一個非終結(jié)符號至少包含一個終結(jié)符號除自身外不再包含其它終結(jié)符號除自身外不再包含其它非終結(jié)符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：a、 b、 c、 d、 e、 f、 g、11、文法的二義性和語言的二義性是兩個_概念。a、不同 b、相同 c、無法判斷12、在編譯中產(chǎn)生語法樹是為了_。a、語法分析 b、語義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼13、下列正規(guī)表達式中_與(a|b)*(c|d)等價。a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*

23、）(cd)15、 _這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示：a、存在 b、不存在 c、無法判定是否存在16、 文法GS：SaS SW SU Ua VbV Vac WaW其中的全部無用符號是（ ） 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/（c-d）+（-b）*a）的逆波蘭表示是_。a、abc*

24、cd-b-a*+/- b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+- d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_。便于進行存儲空間的組織利于目標(biāo)代碼優(yōu)化利于編譯程序的移植利于目標(biāo)代碼的移植利于提高目標(biāo)代碼的質(zhì)量可選項有：a、 b、 c、 d、20、設(shè)有文法GS=（b,S,B,S,Sb|bB, BbS）,該文法描述的語言是（ ）。 a、b2i+1 | i1 b、b2i+1 | i0 c、bi | i0 d、b2i | i0二、簡答題：（每小題5分，共30分）1、證明下面文法是二義性的。PPaP|PbP|cP|Pe|f 2、設(shè)一文法ET|E

25、+T|E-T TF|T*F|T/F F(E)|i 證明E+T*(E-T)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。SbS|aA AaA|bB BaA|bC|b CbS|aA4、將表達式（B*D+A）/E+D）*F+G分別表示為三元式、四元式、逆波蘭式序列5、消除文法GS的左遞歸(GS)GS：SAB AbB|Aa BSb|a 6、對下面的文法GZZaB AaB BbB BaA Bb 構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子一、選擇題（本大題共20小題，每小題1分，共20分）1、要在某一臺機器上為某種語言構(gòu)造一個

26、編譯程序，必須找掌握下述三方面的內(nèi)容：_。高級語言 源語言 目標(biāo)語言 程序設(shè)計方法 編譯方法 測試方法 機器語言 可選項有 a、 b、 c、 d、2、“用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標(biāo)代碼后才能投入運行?！边@種說法_。a、不正確 b、正確3、若一個文法是遞歸的，則它所產(chǎn)生的句子個數(shù)_。a、必定是無窮的 b、是有限個的 c、根據(jù)具體情況而定4、下列文法_二義文法E:=EiT|T T:=T+F|iF|F F:=ET|(可選項有： a、是 b、不是 c、無法判斷。5、編譯程序的語法分析器接受以_為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用?？蛇x項有： a、表達式 b、產(chǎn)生式 c、 單詞

27、 d、語句 6、文法GZ：ZBe AAe|e BAf Df 中，_是多余產(chǎn)生式a、 ZBe b、 AAe|e c、BAf d、Df7、算符優(yōu)先文法屬于_。a、自頂向下語法分析法 b、LR分析法 c、SLR分析法 d、自底向上語法分析法8、設(shè)有文法GS=（a，S,B，S，Sa|aB, BaS）,該文法描述的語言是_a、ai|i0 b、 a2i|i0 c、 a2i+1|i0 d、 a2i+1|i19、描述語言L=ambn|nm1的文法是_a、ZABb b、ZABb c、ZAb d、ZaAbAaA|a AAa|a AaAb|a AAb|aAb|BbB|b BaBb|b 10、一個句型中的最左_稱為該

28、句型的句柄。a、短語 b、直接短語 c、素短語 d、終結(jié)符號11、通常高級語言的詞法規(guī)則可用正規(guī)式描述，詞法分析器可用_來實現(xiàn)a、語法樹 b、有限自動機 c、棧 d、堆12、文法GS：SAA AAa|a不是LR（1）文法，理由是_。a、FIRST(S)FIRST(A)b、FIRST(A)FOLLOW(A)c、FIRST(Aa)FIRST(a)d、都不是13、素短語是指_的短語。至少包含一個符號至少包含一個非終結(jié)符號至少包含一個終結(jié)符號除自身外不再包含其它終結(jié)符號除自身外不再包含其它非終結(jié)符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：a、 b、 c、 d、 e、 f、 g、14

29、、給定文法GS：SACc AaA|Sb CDef DhACDd|eC| EbDe| 該文法是_。 （1）右線性文法 （2）前后文無關(guān)文法 （3）左遞歸文法 （4）LL（1）文法可選項有：a、 b、 c、 d、15、算符文法是指_的文法。沒有形如UVW的規(guī)則 （U、V、W為非終結(jié)符）終結(jié)符號集中任意兩個符號對之間至多有一種優(yōu)先關(guān)系成立沒有相同的規(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)生式的

30、右部，則此右部_是該句型的句柄a、一定 b、不一定18、前后文無關(guān)文法和正規(guī)文法所產(chǎn)生的語言類相比_a、前后文無關(guān)文法產(chǎn)生的語言類大 b、正規(guī)文法產(chǎn)生的語言類大 c、兩者產(chǎn)生的語言類一樣大 d、無法比較19、編譯過程中，比較常見的中間語言有_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項有：a、 b、 c、 d、20、LL（1）文法的條件是_。a、對形如UX1|X2|Xn的規(guī)則，要求FIRST（Xi）)FIRST (Xj)= (ij)b、對形如UX1|X2|Xn的規(guī)則 若Xi* 則要求FIRST(Xj) FOLLOW (U)=c、a和bd、都不是二、簡答題：（每小題5分，共30分）1、對于下面

31、的文法GS SSa|Ab|b|c ABc|a BSb|b 構(gòu)造狀態(tài)轉(zhuǎn)換圖,并說明符號串bcbabcba是否是該文法接受的句子2、設(shè)一文法GT：TT*F|F FFP|P P(T)|i 證明T*P(T*F)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。ZaZ|bZ|aA AaB BaA|b 4、將表達式（A+B*D）/E+F）*F+GE分別表示為三元式、四元式、逆波蘭式序列。5、（5分）消除文法GS的左遞歸GS：SSA|A ASB|B|(S)|() BS | 專業(yè) 年級（本、?？疲?學(xué)號_ 姓 名 _密封線6、（5分）對下面的文法GEEE+

32、T|T|T TT*F|F FPF|P Pi (+、*、i是終結(jié)符號)構(gòu)造文法的算符優(yōu)先矩陣表，判斷此文法是否是算符優(yōu)先文法。一、 填空題（每空1分，共20分）1、假設(shè)G是一個文法，S是文法的開始符號，如果S*X，則稱X是 。2、喬姆斯基定義的四種形式語言分別為： 文法、 文法、 文法、 文法。3、設(shè)有文法GI： II1|I0|Ia|Ic|a|b|c ,下列符號串中是該文法的句子的有 （1）ab0 (2)a0c01 (3)aaa (4)bc104、一個上下文無關(guān)文法G包含四個組成部分依次為：一組 ，一組 ，一個 ，以及一組 。5、確定的有窮自動機是一個 ，通常表示為 。6、編譯程序一般含有八部分

33、，分別是 、 、 、 、 、 、 、 。二、 簡答題（每題5分，共30分）1、已知文法GZ：ZU0|V1UZ1|1VZ0|0寫出全部由此文法描述的只含有四個符號的句子。2、文法GN為：ND|NDD0|1|2|3|4|5|6|7|8|9GN的語言是什么？3、設(shè)一文法GSS（AS） S（b） A（SaA） A（a）對于句子（b）a（a）（b），寫出該句子的最左推導(dǎo)，畫出語法樹，寫出其全部短語，直接短語和句柄。4、 構(gòu)造下述文法GS的自動機： SA0 AA0|S1|05、將表達式(a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列6、消除下列文法的左遞歸。S:=SaP|Sf|P P:

34、=QbP|Q Q:=cSd|e一、選擇題（本大題共20小題，每小題1分，共20分）1、描述一個語言的文法是_。a、唯一的 b、不唯一的 c、個數(shù)有限的2、匯編程序是將_翻譯成_；編譯程序是將_翻譯成_。a、匯編語言程序 b、機器語言程序 c、高級語言程序 d匯編語言或機器語言程序3、設(shè)有文法GI：II0|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有_。ab0 a0c01 aaa bc10 可選項有a、 b、 c、 d、4、生成非0開頭的正偶數(shù)集的文法是_。a、Z:=ABC c、Z:=ABC|2|4|6|8C:=0|2|4|6|8 C:=0|2|4|6|8B:=BA|B0| B:

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

36、bc的所有可能語法樹有_棵。a、1 b、2 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、從左到右分析，每次向前預(yù)測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指_的短語。至少包含一個符號至少包含一個非終結(jié)符號至少包含一個終結(jié)符號除

37、自身外不再包含其它終結(jié)符號除自身外不再包含其它非終結(jié)符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：a、 b、 c、 d、 e、 f、g、11、文法的二義性和語言的二義性是兩個_概念。a、不同 b、相同 c、無法判斷12、在編譯中產(chǎn)生語法樹是為了_。a、語法分析 b、語義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼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、 b、 c、 d、 e、 f、 g、17、

38、 _這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達式表示： a、存在 b、不存在 c、無法判定是否存在15、LL（K）文法_二義性的。 a、都是 b、都不是 c、不一定都是16、下面的文法是_。S:=aAa|aBb|bAb|bBa A:=x B:=x 可選項有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b17、編譯過程中，比較常見的中間語言有_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項有：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*

39、cd-/b-a*+- d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_。便于進行存儲空間的組織利于目標(biāo)代碼優(yōu)化利于編譯程序的移植利于目標(biāo)代碼的移植利于提高目標(biāo)代碼的質(zhì)量可選項有：a、 b、 c、 d、20、代碼優(yōu)化的主要目標(biāo)是_。如何提高目標(biāo)程序的運行速度如何減少目標(biāo)程序運行所需的空間。 專業(yè) 年級（本、?？疲?學(xué)號_ 姓 名 _密封線如何協(xié)調(diào)和 如何使生成的目標(biāo)代碼盡可能簡短可選項有：a、 b、 c、 d、二、簡答題：（每小題5分，共30分）1、寫一個文法使其語言為L(G)= anbmambn | m,n1。2、對于文法G(E): ET|E+TTF|T*FF(E

40、)|i（1） 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。（2） 寫出上述句型的短語，直接短語、句柄和素短語。3、求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。S:=bS|aA A:=aA|bB B:=aA|bC|b C:=bS|aA4、將表達式(a*d+c)/d+e)*f+g分別表示三元式、四元式、逆波蘭式序列5、消除下列文法的左遞歸。S:=SaP|Sf|P P:=QbP|Q Q:=cSd|e6、給出與下圖的NFA等價的正規(guī)文法。S0S2S1S3ab c一、 選擇題（本大題共20小題，每小題1分，共20分）1、素短語是指_的短語。至少包含一個符號至少包含一個非終結(jié)符號至少包含一個終結(jié)符號除自身外不再包含其它終結(jié)符號除自身外不再包含其它非終結(jié)符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：A、 B、 C、 D、 E、 F、 G、2、表達式ab+cd+*的逆波蘭式表達式所表示的中綴形式的表達式是 A、 a+b+c*d B、 (a+b)*(c+d) C、 (a+b)*