編譯原理試題

1、德州學(xué)院期末考試試題德州學(xué)院期末考試試題（1至學(xué)年第學(xué)年第學(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是文法的開(kāi)始符號(hào)，如果S?X，則稱X是。二、

2、選擇題（本大題共15小題，每小題1分，共15分）1、編譯程序生成的目標(biāo)程序是機(jī)器語(yǔ)言程序。A、一定B、不一定2、設(shè)有文法G[S]=（bSBSS→b|bBB→bS）該文法描述的語(yǔ)言是。A、bi|i≥0B、b2i|i≥0C、b2i1|i≥0D、b2i1|i≥13、設(shè)有文法G[S]：S→SS|SS|（S）|a該文法二義性文法A、是B、不是C、無(wú)法判斷4、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成_______

3、___。A、匯編語(yǔ)言程序B、機(jī)器語(yǔ)言程序C、高級(jí)語(yǔ)言程序D、匯編語(yǔ)言或機(jī)器語(yǔ)言程序5、給定文法A→bA|cc下面符號(hào)串中，為該文法句子的是。①cc②bcbc③bcbcc④bccbcc⑤bbbccA、①B、①③④⑤C、①⑤D、①④⑤E、①②③④⑤6、語(yǔ)法分析的常用方法是。①自頂向下②自底向上③自左向右④自右向左A、①②③④B、①②C、③④D、①②③7、已知語(yǔ)言L=anbbn|n≥1，則下述文法中，可以產(chǎn)生語(yǔ)言LA、Z→aZb|aAb|bA

4、→aAb|bB、A→aAbA→bC、Z→AbBA→aA|aB→bB|bD、Z→aAbA→aAb|b8、下列正規(guī)表達(dá)式中________與(a|b)(c|d)等價(jià)。A、（a|b）(c|d)B、（a|b）(c|d)C、(ab)(d|c)D、（ab）(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ǔ)

5、11、下列文法G[S]]：S→AAA→Aa|a不是LR（1）文法，理由是A.、FIRST(S)∩FIRST（A）≠?B、FIRST（A）∩FOLLOW（A）≠?C、FIRST（Aa）∩FIRST（a）≠?D、都不是12、設(shè)有文法G[E]：E→EE|EE|（E）|a該文法LR（1）文法A、是B、不是C、無(wú)法判斷13、對(duì)于文法G[A]：A→aABe|BaB→dB|?有人說(shuō)，因?yàn)镕IRST（aABe）∩FOLLOW（A）≠?并且FIRST（B

6、a）∩FOLLOW（A）≠?，所以文法G[A]不是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(zhuǎn)、②④E、③⑤F、③⑦G、②⑦15、表達(dá)式A（BC（CD））的逆波蘭式為A、ABCCDB、AB

7、CCDC、ABCCDD、都不正確三、簡(jiǎn)答題（共35分）1、(10分)現(xiàn)有文法G[E]:E→ET|ET|TT→TF|TF|FF→(E)|i畫(huà)出句型EF（Ei）的語(yǔ)法樹(shù)找出它的短語(yǔ)，直接短語(yǔ)，句柄和素短語(yǔ)2、(5分)對(duì)下面的文法G[S]構(gòu)造狀態(tài)轉(zhuǎn)換圖并說(shuō)明符號(hào)串a(chǎn)aba是否是該文法接受的句子：S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB3、(10分)將下面具有?的NFA確定化4、(5分)求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)

8、式。S→aAA→bA|aB|bB→aA。5、(5分)構(gòu)造識(shí)別下面正規(guī)式的NFA（a|b）ba。四、綜合題（共40分）1、（10分）下面的文法G[S]是否是LL（1）文法，說(shuō)明理由，構(gòu)造LL（1）分析表S→aBc|bABA→aAb|BbB→cB|?2、（5分）消除下列文法的左遞歸，消除左遞歸后判斷是否是LL（1）文法。S→SaB|bBA→S|aB→Ac3、（5分）構(gòu)造下面算符文法的優(yōu)先矩陣，判斷是否是算符優(yōu)先文法S→A[]A→[A→aAA

9、→B]B→a4、（10分）將表達(dá)式AB(CD)EF↑G分別表示為三元式、四元式、逆波蘭式序列5、（10分）現(xiàn)有文法如下：S→aS|bS|a判斷該文法是哪一類LR文法，說(shuō)明理由，并構(gòu)造相應(yīng)的分析表。SABZaba??可選項(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

10、、②④b、①②③c、③④①d、②③④三、簡(jiǎn)答題：（每小題5分，共35分）1、證明下面文法是二義性的。S::=ibtSeS|ibtS|a2、現(xiàn)有文法S::=SaA|AA::=AbB|BB::=cSd|e請(qǐng)證實(shí)是文法的一個(gè)句型，并寫(xiě)出該句型的所有短語(yǔ)、素短語(yǔ)以及句柄。3、求出下列文法所產(chǎn)生語(yǔ)言對(duì)應(yīng)的正規(guī)式。S::=bS|aAA::=aA|bBB::=aA|bC|bC::=bS|aA4、將表達(dá)式((adc)de)fg分別表示三元式、四元式、逆

11、波蘭式序列5、消除下列文法的左遞歸。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e6、給出與下圖的NFA等價(jià)的正規(guī)文法。abεε7、對(duì)基本塊P畫(huà)出DAG圖B:=3D:=ACE::=ACF:=EDG:=BFH:=ACI:=ACJ:=HIK:=B5L:=KJM:=L假定只有L在基本塊出口之后活躍，寫(xiě)出優(yōu)化后的四元式序列。四、問(wèn)答題：（共計(jì)45分）1、已知文法GA::=aABe|aB::=Bb|d（1）給出與上述文法等價(jià)的LL（

12、1）文法G’。（2）構(gòu)造預(yù)測(cè)分析表并給出輸入串a(chǎn)ade#分析過(guò)程。（10分）2、設(shè)已給文法G:E::=ETE::=TT::=TFT::=FF::=P↑FF::=PP::=(E)P::=i構(gòu)造此文法的算符優(yōu)先矩陣。（10分）3、有正規(guī)式babb(abb)（1）構(gòu)造該正規(guī)式所對(duì)應(yīng)的NFA（畫(huà)出狀態(tài)轉(zhuǎn)換圖）。（2）將所求的NFA確定化。（畫(huà)出確定化的狀態(tài)轉(zhuǎn)換圖）。（3）將所求的NFA最小化。（畫(huà)出最小化后的狀態(tài)轉(zhuǎn)換圖）。（10分）4、若有文法

13、G（S）的產(chǎn)生式如下：S::=L=RS::=RL::=RL::=iR::=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é)院期末考試試題德州學(xué)院期末考試試題（3至學(xué)年第學(xué)年第學(xué)期）學(xué)期）課程名稱：考試對(duì)象：試卷類型：（1）考試時(shí)間：分鐘一、

14、單項(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、編譯程序必須完成的工作有①詞法分析②語(yǔ)法分析③語(yǔ)義分析④代碼生成⑤中間代碼生成⑥代碼優(yōu)化①②③④B、①②③④⑤C、①②③④⑥D(zhuǎn)、①②③④⑤⑥3、LR（K）文法________二義性的。A、都是B、都不是C、不一定都是4、語(yǔ)法分析的常用方法是________。

15、①自頂向下②自底向上③自左向右④自右向左A、①②③④B、①②C、③④D、①②③5、用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須經(jīng)過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行，這種說(shuō)法A、不正確B、正確6、生成非0開(kāi)頭的正偶數(shù)集的文法是______________。A、Z::=ABCB、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|

16、2|3|4|5|6|7|8|9C、Z::=ABCD、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=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、由文法的開(kāi)始符號(hào)推出的所有符號(hào)串D、由文法的開(kāi)始符號(hào)推出的所