編譯原理試題(5)

1、德州學院期末考試試題（ 1 至學年第學期）課程名稱： 考試對象：試卷類型：（1）考試時間：分鐘一、填空題：（10分，第1小題每2個1分，其余每空1分）1、編譯程序一般含有八部分，分別是、。2、編譯程序與解釋程序的根本區(qū)別是3、一個上下文無關文法G包括四個組成部分依次為：一組_、一個_、一組_、一組_。4、設G是一個文法，S是文法的開始符號，如果S* X，則稱X是。二、選擇題（本大題共15小題，每小題1分，共15分）1、編譯程序生成的目標程序是機器語言程序。A、一定 B、不一定2、設有文法GS=（b,S,B,S,Sb|bB, BbS）,該文法描述的語言是。A、bi | i0 B、b2i | i0

2、 C、b2i 1 | i0 D、b2i 1 | i13、設有文法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)生語言LA、ZaZb|aAb|b AaAb|b B、

3、AaAb Ab C、ZAbB 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、F

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

5、*（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構造狀態(tài)轉換圖,并說明符號串a(chǎn)aba是否是該文法接受的句子： SaA SB AabS AbB Bb BcC CD Dd DbB3、 (10分)將下面具有的NFA確定化4、 (5分)求出下列文法所產(chǎn)生語言對應的正規(guī)式。SaA AbA|aB|b BaA。5、 (5分)構造識別下面正規(guī)

6、式的NFA （a|b）*ba。 四、 綜合題（共40分）1、 （10分）下面的文法GS是否是LL（1）文法，說明理由，構造LL（1）分析表SaBc|bAB AaAb|Bb BcB|2、 （5分）消除下列文法的左遞歸，消除左遞歸后判斷是否是LL（1）文法。 SSaB|bB AS|a BAc3、 （5分）構造下面算符文法的優(yōu)先矩陣，判斷是否是算符優(yōu)先文法SA A AaA AB Ba4、 （10分）將表達式A B*(C-D)-E/FG分別表示為三元式、四元式、逆波蘭式序列5、 （10分）現(xiàn)有文法如下：SaS|bS|a 判斷該文法是哪一類LR文法，說明理由，并構造相應的分析表。德州學院期末考試試題（

7、2 至學年第學期）課程名稱： 考試對象：試卷類型：（1）考試時間：分鐘二、 選擇題（本大題共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

8、 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|94、設有文法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、一個上下文無關文法G包括四個組成部分依次為：一組_、一個_、一組_、一組_。a、字

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

10、析，共經(jīng)過K步的一種編譯方法。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)等價。1 a*（c d） b（c d）2 a*（c d）* b（c d）*3 a*（c d） b*（c d）4 （a b）*c （a b）*d5 （a* b）*c （a* b）*d可選

11、項有:a、 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 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

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

13、|e請證實是文法的一個句型，并寫出該句型的所有短語、素短語以及句柄。3、 求出下列文法所產(chǎn)生語言對應的正規(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ī)文法。ab7、對基本塊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)化后的四元式序列

14、。四、 問答題：（共計45分）1、 已知文法G A:=aABe|a B:=Bb|d（1） 給出與上述文法等價的LL（1）文法G。（2） 構造預測分析表并給出輸入串a(chǎn)ade#分析過程。（10分）2、 設已給文法G: E:=E T E:=T T:=T*F T:=F F:=PF F:=P P:=(E) P:=i構造此文法的算符優(yōu)先矩陣。（10分）3、 有正規(guī)式b*abb*(abb*)*（1） 構造該正規(guī)式所對應的NFA（畫出狀態(tài)轉換圖）。（2） 將所求的NFA確定化。（畫出確定化的狀態(tài)轉換圖）。（3） 將所求的NFA最小化。（畫出最小化后的狀態(tài)轉換圖）。（10分）4、 若有文法G（S）的產(chǎn)生式如下：

15、S:=L=R S:=R L:=*R L:=i R:=L,構造識別所有項目集規(guī)范族的DFA。（15分）（1） 判斷該文法是否是LR（0）文法，說明理由。（2） 判斷該文法是否是SLR（1）文法，說明理由。（3） 判斷該文法是否是LR（1）文法，說明理由。（4） 判斷該文法是否是LALR（1）文法，說明理由德州學院期末考試試題（ 3 至學年第學期）課程名稱： 考試對象：試卷類型：（1）考試時間：分鐘一、 單項選擇題（20分，每小題1分）1、文法G1：P aPQR| abR，RQ QR，BQ bb，bR bc，cR cc，它是chomsky哪一型文法？A、0型 B、1型 C、2型 D、3型2、編譯程

16、序必須完成的工作有詞法分析語法分析語義分析代碼生成中間代碼生成代碼優(yōu)化 B、 C、 D、3、LR（K）文法_二義性的。A、都是 B、都不是 C、不一定都是4、語法分析的常用方法是_。自頂向下自底向上自左向右自右向左A、 B、 C、 D、5、用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目標代碼后才能投入運行，這種說法A、不正確 B、正確6、生成非0開頭的正偶數(shù)集的文法是_。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、

17、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、由文法的開始符號推出的所有符號串D、由文法的開始符號推出的所有終結符號串。8、給定文法GI:II1|I0|Ia|Ic|a|b|c,下面符號串中，為該文法句子的是。 ab0 a0c01aaabc10A、 B、 C、 D、9、_這樣的語言，他們能被確定的有限自動機

18、識別，但不能用正規(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、abc*cd-b-a* /- D、a-bc*cd-b-a* /-12、設有文法GS=（b,S,B,S,Sb|bB, BbS）,該文法描述的語言是。A、b2

19、i 1 | i1 B、b2i 1 | i0 C、bi | i0 D、b2i | i013、素短語是指_的短語。至少包含一個符號至少包含一個非終結符號至少包含一個終結符號除自身外不再包含其它終結符號除自身外不再包含其它非終結符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：A、 B、 C、 D、 E、 F、 G、14、算符優(yōu)先分析屬于分析方法。A、自頂向下 B、自底向上 C、自左向右 D、自右向左15、簡單優(yōu)先分析法每次都是對進行歸約A、最左短語 B、直接短語 C、句柄 D、素短語 E、最左素短語16、文法GS：SaS SW SU Ua VbV Vac WaW其中的全部無用符號是A

20、、W，V ，U B、V，b C、 W，V，a, b ,c D、W，V，b，c17、程序基本塊是指A、一個子程序 B、一個僅有一個入口和一個出口的語句C、一個沒有嵌套的程序段D、一組順序執(zhí)行的程序段，僅有一個入口和一個出口18、設有文法GZ：ZZ*Z|Z Z|（Z）|a 該文法二義性文法A、是 B、不是 C、無法判斷19、下列正規(guī)表達式中_與(a|b)*(c|d)等價。A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)20、語法分析的任務是分析單詞是怎樣構成的分析單詞串是如何構成語句和說明的分析語句和說明是如何構成程序的分析程序的結構

21、A、 B、 C、 D、二、（簡答題，共計20分）1、(10分)已知文法G（T)：TT*F|FFFP|PP(T)|i(1)寫出句型T *P（T*F）推導過程，畫出語法樹；(2)寫出句型T *P（T*F）的短語、直接短語、句柄和素短語。2、(5分)構造識別下面正規(guī)式的NFAb（aa|bb）*ab3、（5分）消除文法GS的左遞歸GS：SAB AbB|Aa BSb|a三、（綜合題，共計30分）1、(10分)將下面具有的NFA確定化和最小化2、(10分)（1）對下面的文法GZZaB AaB BbB BaA Bb 構造狀態(tài)轉換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子（2）寫出GZ文法相應的正規(guī)

22、式：3、（10分）設有以下文法GS：SaAbDe|d ABSD|e BSAc|cD|DSe|（1）求出文法中每個非終結符的FOLLOW集（2）該文法是LL（1）文法嗎？構造LL（1）分析表四、（綜合題，共計30分）1、（10分）將表達式（B*D A）/E D）*F G分別表示為三元式、四元式、逆波蘭式序列2、（10分）對基本塊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)化后的四元式序列。3、（10分）對于文法GS：SaBb | aAa |bAb|bBa Ax Bx

23、 （1）判斷該文法是否是LR（1）文法，構造LR（1）分析表（2）判斷該文法是否是LALR（1）文法，說明理由德州學院期末考試試題（ 4 至學年第學期）課程名稱： 考試對象：試卷類型：（1）考試時間：分鐘一、選擇題（本大題共20小題，每小題1分，共20分）1、描述一個語言的文法是_。a、唯一的 b、不是唯一的 c、個數(shù)有限的2、簡單優(yōu)先分析法每次都是對_進行歸約。a、最左短語 b、直接短語 c、句柄 d、素短語 e、最左素短語3、設有文法GI：II0 |I1 |Ia |Ic |a |b |c下列符號串中是該文法的句子的有_。ab0 a0c01 aaa bc10 可選項有a、 b、 c、 d、4

24、、LR（K）文法_二義性的。a、都是 b、都不是 c、不一定都是5、一個上下文無關文法G包括四個組成部分依次為：一組_、一個_、一組_、一組_。a、字符串 b、字母數(shù)字串 c、產(chǎn)生式 d、結束符號 e、開始符號 f、文法 g、非終結符號 h、終結符號6、文法G所描述的語言是_的集合a、文法G的字匯表V中所有符號組成的符號串b、文法G的字匯表V的閉包V*中的所有符號串c、由文法的開始符號推出的所有符號串d、由文法的開始符號推出的所有終結符號串。7、設有文法GZ：ZZ*Z|Z Z|（Z）|a 該文法_二義性文法a、是 b、不是 c、無法判斷8、語法分析的常用方法是_：自頂向下 自底向上 自左向右

25、自右向左 可選項有：a、 b、 c、 d、9、LR（K）文法是_。a、從左到右分析，共經(jīng)過K步的一種編譯方法。b、從左到右分析，每次向前預測K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。10、素短語是指_的短語。至少包含一個符號至少包含一個非終結符號至少包含一個終結符號除自身外不再包含其它終結符號除自身外不再包含其它非終結符號除自身外不再包含其它短語除自身外不再包含其它素短語可選項有：a、 b、 c、 d、 e、 f、 g、11、文法的二義性和語言的二義性是兩個_概念。a、不同 b、相同 c、無法判斷12

26、、在編譯中產(chǎn)生語法樹是為了_。a、語法分析 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、 文法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

27、 b、ababab c、abbaab d、aaabbb17、編譯過程中，比較常見的中間語言有_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項有：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* -19、在編譯程序中安排中間代碼生成的目的是_。便于進行存儲空間的組織利于目標代碼優(yōu)化利于編譯程序的移植利于目標代碼的移植利于提高目標代碼的質(zhì)量可選項有：a、 b、 c、 d、20、設有文法GS=（b,S,B,S,Sb|bB, Bb

28、S）,該文法描述的語言是（ ）。 a、b2i 1 | i1 b、b2i 1 | i0 c、bi | i0 d、b2i | i0二、簡答題：（每小題5分，共30分）1、證明下面文法是二義性的。PPaP|PbP|cP|Pe|f 2、設一文法ET|E T|E-T TF|T*F|T/F F(E)|i 證明E T*(E-T)是它的一個句型，并指出該句型的全部短語，直接短語，句柄和素短語。3、求出下列文法所產(chǎn)生語言對應的正規(guī)式。SbS|aA AaA|bB BaA|bC|b CbS|aA4、將表達式（B*D A）/E D）*F G分別表示為三元式、四元式、逆波蘭式序列5、消除文法GS的左遞歸(GS)GS：S

29、AB AbB|Aa BSb|a 6、對下面的文法GZZaB AaB BbB BaA Bb 構造狀態(tài)轉換圖,并說明符號串a(chǎn)aaabbb是否是該文法接受的句子三、問答題：(共50分)1、已知文法G S:=bBc|aAB A:=bAa|a B:=a|寫出所有非終結符號的First集和Follow集，構造預測分析表并給出輸入串a(chǎn)bbaaa分析過程。（10分） 2、正規(guī)式0（0|1）*1構造該正規(guī)式所對應的NFA（畫出狀態(tài)轉換圖）。將所求的NFA確定化和最小化。（分別畫出確定化和最小化的狀態(tài)轉換圖）。（10分）3、若有文法G（S）的產(chǎn)生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構造

30、識別所有項目集規(guī)范族的DFA。（20分）判斷該文法是否是LR（0）文法，說明理由。判斷該文法是否是SLR（1）文法，說明理由。判斷該文法是否是LR（1）文法，說明理由。判斷該文法是否是LALR（1）文法，說明理由。4、簡述編譯的整個過程（10分）。德州學院期末考試試題（ 5 至學年第學期）課程名稱： 考試對象：試卷類型：考試時間：分鐘一、選擇題（本大題共20小題，每小題1分，共20分）1、要在某一臺機器上為某種語言構造一個編譯程序，必須找掌握下述三方面的內(nèi)容：_。高級語言 源語言 目標語言 程序設計方法 編譯方法 測試方法 機器語言可選項有 a、 b、 c、 d、2、“用高級語言書寫的源程序都必須經(jīng)過編譯，產(chǎn)生目