編譯原理試題(5)

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

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

3、AaAb Ab C、ZAbB AaA|a BbB|b D、ZaAb AaAb|b 8、下列正規(guī)表達(dá)式中_與(a|b)*(c|d)等價(jià)。A、（a*|b*）(c|d) B、（a*|b*）*(c|d) C、(ab)*(d|c) D、（a*b*）(cd)9、算符優(yōu)先分析法每次都是對(duì)進(jìn)行歸約。A、最左短語(yǔ) B、直接短語(yǔ) C、句柄 D、素短語(yǔ) E、最左素短語(yǔ)10、簡(jiǎn)單優(yōu)先分析法每次都是對(duì)進(jìn)行歸約A、最左短語(yǔ) B、直接短語(yǔ) C、句柄 D、素短語(yǔ) E、最左素短語(yǔ)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、設(shè)有文法GE：EE*E|E E|（E）|a 該文法LR（1）文法A、是 B、不是 C、無(wú)法判斷13、對(duì)于文法GA： AaABe|Ba BdB|有人說(shuō)，因?yàn)镕IRST（aABe）FOLLOW（A）并且FIRST（Ba）FOLLOW（A），所以文法GA不是LL（1）文法。這種說(shuō)法A、正確 B、不正確14、素短語(yǔ)是指_的短語(yǔ)。至少包含一個(gè)符號(hào)至少包含一個(gè)非終結(jié)符號(hào)至少包含一個(gè)終結(jié)符號(hào)除自身外不再包含其它終結(jié)符號(hào)除自身外不再包含其它非終結(jié)符號(hào)除自身外不再包含其它短語(yǔ)除自身外不再包含其它素短語(yǔ)可選項(xiàng)有：A、B、C、D、E、F、G、15、表達(dá)式A*（B-C

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

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

7、2 至學(xué)年第學(xué)期）課程名稱： 考試對(duì)象：試卷類型：（1）考試時(shí)間：分鐘二、 選擇題（本大題共20小題，每小題1分，共20分）1、匯編程序是將_翻譯成_；編譯程序是將_翻譯成_。a、匯編語(yǔ)言程序 b、機(jī)器語(yǔ)言程序 c、高級(jí)語(yǔ)言程序 d匯編語(yǔ)言或機(jī)器語(yǔ)言程序2、描述一個(gè)語(yǔ)言的文法是_。a、唯一的 b、不唯一的 c、個(gè)數(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、設(shè)有文法GI：II0|I1|I a|Ic|a|b|c下列符號(hào)串中是該文法的句子的有_。ab0 a0c01 aaa bc10 可選項(xiàng)有a、 b、 c、 d、5、現(xiàn)有前綴表示的表達(dá)式文法G1：E:=-EE E:=-E E:=a|b|c則文法的句子a-bc的所有可能語(yǔ)法樹有_棵。a、1 b、2 c、3 d、46、一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分依次為：一組_、一個(gè)_、一組_、一組_。a、字

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

10、析，共經(jīng)過(guò)K步的一種編譯方法。b、從左到右分析，每次向前預(yù)測(cè)K步的一種編譯方法。c、從左到右分析，每次向貌似句柄的符號(hào)串后看K個(gè)輸入符號(hào)的一種編譯方法。d、從左到右分析，每次走K步的一種編譯方法。11、在編譯中產(chǎn)生語(yǔ)法樹是為了_。a、語(yǔ)法分析 b、語(yǔ)義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼12、文法的二義性和語(yǔ)言的二義性是兩個(gè)_概念。a、不同 b、相同 c、無(wú)法判斷13、下述正規(guī)表達(dá)式中_與(a* b)*(c d)等價(jià)。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、項(xiàng)有:a、 b、 c、 d、 e、 f、 g、14、 _這樣的語(yǔ)言，他們能被確定的有限自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示：a、存在 b、不存在 c、無(wú)法判定是否存在15、LL（K）文法_二義性的。a、都是 b、都不是 c、不一定都是16、下面的文法是_。S:=aAa|aBb|bAb|bBa A:=x B:=x可選項(xiàng)有：a、LR（1）文法 b、LALR（1）文法 c、都不是 d、a和b17、編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項(xiàng)有：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、在編譯程序中安排中間代碼生成的目的是_。便于進(jìn)行存儲(chǔ)空間的組織利于目標(biāo)代碼優(yōu)化利于編譯程序的移植利于目標(biāo)代碼的移植利于提高目標(biāo)代碼的質(zhì)量可選項(xiàng)有：a、 b、 c、 d、20、代碼優(yōu)化的主要目標(biāo)是_。如何提高目標(biāo)程序的運(yùn)行速度如何減少目標(biāo)程序運(yùn)行所需的空間。如何協(xié)調(diào)和 如何使生成的目標(biāo)代碼盡可能簡(jiǎn)短可選項(xiàng)有：a、 b、 c、 d、三、 簡(jiǎn)答題：（每小題5分，共35分）1、 證明下面文法是二義性的。S:=ibtSeS|ibtS|a2、 現(xiàn)有文法S:=SaA|A A:=AbB|B B:=cSd

13、|e請(qǐng)證實(shí)是文法的一個(gè)句型，并寫出該句型的所有短語(yǔ)、素短語(yǔ)以及句柄。3、 求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)式。S:=bS|aA A:=aA|bB B:=aA|bC|b C:=bS|aA4、 將表達(dá)式(a*d c)/d e)*f g分別表示三元式、四元式、逆波蘭式序列5、 消除下列文法的左遞歸。S:=SaP|Sf|P P:=QbP|Q Q:=cSd|e6、 給出與下圖的NFA等價(jià)的正規(guī)文法。ab7、對(duì)基本塊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、。四、 問(wèn)答題：（共計(jì)45分）1、 已知文法G A:=aABe|a B:=Bb|d（1） 給出與上述文法等價(jià)的LL（1）文法G。（2） 構(gòu)造預(yù)測(cè)分析表并給出輸入串a(chǎn)ade#分析過(guò)程。（10分）2、 設(shè)已給文法G: E:=E T E:=T T:=T*F T:=F F:=PF F:=P P:=(E) P:=i構(gòu)造此文法的算符優(yōu)先矩陣。（10分）3、 有正規(guī)式b*abb*(abb*)*（1） 構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA（畫出狀態(tài)轉(zhuǎn)換圖）。（2） 將所求的NFA確定化。（畫出確定化的狀態(tài)轉(zhuǎn)換圖）。（3） 將所求的NFA最小化。（畫出最小化后的狀態(tài)轉(zhuǎn)換圖）。（10分）4、 若有文法G（S）的產(chǎn)生式如下：

15、S:=L=R S:=R L:=*R L:=i R:=L,構(gòu)造識(shí)別所有項(xiàng)目集規(guī)范族的DFA。（15分）（1） 判斷該文法是否是LR（0）文法，說(shuō)明理由。（2） 判斷該文法是否是SLR（1）文法，說(shuō)明理由。（3） 判斷該文法是否是LR（1）文法，說(shuō)明理由。（4） 判斷該文法是否是LALR（1）文法，說(shuō)明理由德州學(xué)院期末考試試題（ 3 至學(xué)年第學(xué)期）課程名稱： 考試對(duì)象：試卷類型：（1）考試時(shí)間：分鐘一、 單項(xiàng)選擇題（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ǔ)法分析語(yǔ)義分析代碼生成中間代碼生成代碼優(yōu)化 B、 C、 D、3、LR（K）文法_二義性的。A、都是 B、都不是 C、不一定都是4、語(yǔ)法分析的常用方法是_。自頂向下自底向上自左向右自右向左A、 B、 C、 D、5、用高級(jí)語(yǔ)言書寫的源程序都必須經(jīng)過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行，這種說(shuō)法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所描述的語(yǔ)言是的集合A、文法G的字匯表V中所有符號(hào)組成的符號(hào)串B、文法G的字匯表V的閉包V*中的所有符號(hào)串C、由文法的開始符號(hào)推出的所有符號(hào)串D、由文法的開始符號(hào)推出的所有終結(jié)符號(hào)串。8、給定文法GI:II1|I0|Ia|Ic|a|b|c,下面符號(hào)串中，為該文法句子的是。 ab0 a0c01aaabc10A、 B、 C、 D、9、_這樣的語(yǔ)言，他們能被確定的有限自動(dòng)機(jī)

18、識(shí)別，但不能用正規(guī)表達(dá)式表示：A、存在 B、不存在 C、無(wú)法判定是否存在10、LR（K）文法是_。A、從左到右分析，共經(jīng)過(guò)K步的一種編譯方法。B、從左到右分析，每次向前預(yù)測(cè)K步的一種編譯方法。C、從左到右分析，每次向貌似句柄的符號(hào)串后看K個(gè)輸入符號(hào)的一種編譯方法。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、設(shè)有文法GS=（b,S,B,S,Sb|bB, BbS）,該文法描述的語(yǔ)言是。A、b2

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

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

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

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

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

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

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

26、、在編譯中產(chǎn)生語(yǔ)法樹是為了_。a、語(yǔ)法分析 b、語(yǔ)義分析 c、詞法分析 d、產(chǎn)生目標(biāo)代碼13、下列正規(guī)表達(dá)式中_與(a|b)*(c|d)等價(jià)。a、（a*|b*）(c|d) b、（a*|b*）*(c|d) c、(ab)*(d|c) d、（a*b*）(cd)15、 _這樣的語(yǔ)言，他們能被確定的有限自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示：a、存在 b、不存在 c、無(wú)法判定是否存在16、 文法GS：SaS SW SU Ua VbV Vac WaW其中的全部無(wú)用符號(hào)是（ ） 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、編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項(xiàng)有：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、在編譯程序中安排中間代碼生成的目的是_。便于進(jìn)行存儲(chǔ)空間的組織利于目標(biāo)代碼優(yōu)化利于編譯程序的移植利于目標(biāo)代碼的移植利于提高目標(biāo)代碼的質(zhì)量可選項(xiàng)有：a、 b、 c、 d、20、設(shè)有文法GS=（b,S,B,S,Sb|bB, Bb

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

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

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