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

1、北科大編譯原理期末試題一、選擇題（本大題共20小題，每小題1分，共20分）1、描述一個語言的文法是_。a、唯一的 b、不唯一的 c、個數(shù)有限的2、匯編程序是將_翻譯成_；編譯程序是將_翻譯成_。a、匯編語言程序 b、機(jī)器語言程序 c、高級語言程序 d匯編語言或機(jī)器語言程序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:=BA|

2、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)有前綴表示的表達(dá)式文法G1：E:=-EE E:=-E E:=a|b|c則文法的句子a-bc的所

3、有可能語法樹有_棵。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é)符號除自身外不

4、再包含其它終結(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、14、 _這樣

5、的語言，他們能被確定的有限自動機(jī)識別，但不能用正規(guī)表達(dá)式表示： 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*cd-/

6、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分）1、 證明下面文法是二義性的。P:=PaP|PbP|cP|Pe|f2、設(shè)一文法SAB Sc AbA Aa BaSb Bc 對于句子bbaacb寫出其全部短語，直接短語和句柄。3、求

7、出下列文法所產(chǎn)生語言對應(yīng)的正規(guī)式。S:=aA A:=bA|aB|b B:=aA4、表達(dá)式（a+b）*c/d-e*f分別表示三元式、四元式、逆波蘭式序列5、消除下列文法的左遞歸。E:=T|EAT T:=F|TMF F:=(E)|i A:=+|- M:=*/6、給出與下圖的NFA等價的正規(guī)式。bS0S1S3S2a c三、問答題：1、已知文法G S:=aBc|bAB A:=aAb|b B:=b|e構(gòu)造預(yù)測分析表并給出輸入串baabbb分析過程。（10分）2、 正規(guī)式（0*|1）（1*0）* （10分）（1） 構(gòu)造該正規(guī)式所對應(yīng)的NFA（畫出狀態(tài)轉(zhuǎn)換圖）。（2） 將所求的NFA確定化。（畫出確定化的狀態(tài)轉(zhuǎn)換圖）。3、 若有文法G（S）的產(chǎn)生式如下：S:=bASB|bA A:=dSa|b B:=cAa|c構(gòu)造識別所有項目集規(guī)范族的DFA。（15分）（1） 判斷該文法是否是LR（0）文法，說明理由。（2） 判斷該文法是否是SLR（1）文法，說明理由。（3） 判斷該文法是否是LR（1）文法，說