北京科技大學(xué)編譯原理試習(xí)題

PAGE4北科大編譯原理期末試題一、選擇題（本大題共20小題，每小題1分，共20分）1、描述一個語言的文法是___________。a、唯一的b、不唯一的c、個數(shù)有限的2、匯編程序是將______翻譯成______；編譯程序是將_______翻譯成__________。a、匯編語言程序b、機器語言程序c、高級語言程序d匯編語言或機器語言程序3、設(shè)有文法G[I]：I→I0|I1|Ia|Ic|a|b|c下列符號串中是該文法的句子的有___________________。①ab0②a0c01③aaa④bc10可選項有a、①b、②③④c、③④d、①②③④4、生成非0開頭的正偶數(shù)集的文法是______________。a、Z::=ABCc、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|2|3|4|5|6|7|8|9b、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|95、一個上下文無關(guān)文法G包括四個組成部分依次為：一組_____、一個_____、一組_____、一組______。a、字符串b、字母數(shù)字串c、產(chǎn)生式d、結(jié)束符號e、開始符號f、文法g、非終結(jié)符號h、終結(jié)符號6、現(xiàn)有前綴表示的表達(dá)式文法G1：E::=-EEE::=-EE::=a|b|c則文法的句子—a-bc的所有可能語法樹有______棵。a、1b、2c、3d、47、下列文法__________二義文法E::=EiT|TT::=T+F|iF|FF::=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é)符號④除自身外不再包含其它終結(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ī)表達(dá)式中________與(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、③④⑤_______這樣的語言，他們能被確定的有限自動機識別，但不能用正規(guī)表達(dá)式表示：a、存在b、不存在c、無法判定是否存在15、LL（K）文法________二義性的。a、都是b、都不是c、不一定都是16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=xB::=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*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在編譯程序中安排中間代碼生成的目的是_______________。①便于進(jìn)行存儲空間的組織②利于目標(biāo)代碼優(yōu)化③利于編譯程序的移植④利于目標(biāo)代碼的移植⑤利于提高目標(biāo)代碼的質(zhì)量可選項有：a、②④b、①②③c、③④①d、②③④⑤20、代碼優(yōu)化的主要目標(biāo)是_____________。①如何提高目標(biāo)程序的運行速度②如何減少目標(biāo)程序運行所需的空間。③如何協(xié)調(diào)①和②④如何使生成的目標(biāo)代碼盡可能簡短可選項有：a、②④b、①②③c、③④①d、②③④二、簡答題：（每小題5分，共30分）證明下面文法是二義性的。P::=PaP|PbP|cP|Pe|f2、設(shè)一文法S→ABS→cA→bAA→aB→aSbB→c對于句子bbaacb寫出其全部短語，直接短語和句柄。3、求出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。S::=aAA::=bA|aB|bB::=aA4、表達(dá)式（a+b）*c/d-e*f分別表示三元式、四元式、逆波蘭式序列5、消除下列文法的左遞歸。E::=T|EATT::=F|TMFF::=(E)|iA::=+|-M::=*//6、給出與下圖的NFA等價的正規(guī)式。 b a ε ε c三、問答題：1、已知文法GS::=aBc|bABA::=aAb|bB::=b|構(gòu)造預(yù)測分析表并給出輸入串baabbb分析過程。（10分）正規(guī)式（（0*|1）（1*0））*（10分）構(gòu)造該正規(guī)式所對應(yīng)的NFA（畫出狀態(tài)轉(zhuǎn)換圖）。將所求的NFA確定化。（畫出確定化的狀態(tài)轉(zhuǎn)換圖）。若有文法G（S）的產(chǎn)生式如下：S::=bASB|bAA::=dSa|bB::=cAa|c構(gòu)造識別所有項目集規(guī)范族的DFA。（15分）判斷該文法是