編譯原理試題

《編譯原理試題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、注意：不是每個(gè)題型或者題目都是我們的考試內(nèi)容，大家參考就好，有些內(nèi)容是我們考的！模擬試題一一、選擇題（每個(gè)選擇題2分，共20分）1．文法G產(chǎn)生的⑴的全體是該文法描述的語(yǔ)言。A．句型B.終結(jié)符集C.非終結(jié)符集D.句子2．若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是⑵：A．遞歸的B前后文無(wú)關(guān)的C二義性的D無(wú)二義性的3．Chomsky定義的四種形式語(yǔ)言文法中，0型文法又稱為⑶文法；1型文法又稱為⑷文法；2型語(yǔ)言可由⑸識(shí)別。A．短語(yǔ)結(jié)構(gòu)文法B前后文無(wú)關(guān)文法C前后文有關(guān)文法D正規(guī)文法E圖靈機(jī)F有限自動(dòng)機(jī)G下推自動(dòng)機(jī)4．一個(gè)文法所描述的語(yǔ)言是⑹；描述一個(gè)語(yǔ)言的文法是⑺。A．唯一的B不唯一的C可能唯一，

2、好可能不唯一5．?dāng)?shù)組的內(nèi)情向量中肯定不含有數(shù)組的⑻的信息A．維數(shù)B.類型C.維上下界D.各維的界差6．在下述的編譯方法中，自底向上的方法有⑼，自頂向下的分析方法有⑽。①簡(jiǎn)單優(yōu)先分析②算符優(yōu)先分析③遞歸下降分析④預(yù)測(cè)分析技術(shù)⑤LR（K）分析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F.①②⑤⑥⑧二、簡(jiǎn)答題（每小題5分，共20分）1．LL（1）分析法對(duì)文法有哪些要求？2．常見(jiàn)的存儲(chǔ)分配策略有幾種？它們都適合于什么性質(zhì)的語(yǔ)言？3．常見(jiàn)循環(huán)優(yōu)化都有哪些項(xiàng)目？4．什么是活動(dòng)記錄？它主要由哪些內(nèi)容構(gòu)成？三、（8分）化簡(jiǎn)文法G[S

3、]：S→ASe

4、BCaD

5、aD

6、ACA→Cb

7、DBSC→bC

8、dB→AcD→aD四、（12分）設(shè)Lí{a,b,c}*是滿足下述條件的符號(hào)串構(gòu)成的語(yǔ)言：(1)若出現(xiàn)a，則其后至少緊跟兩個(gè)c；(2)若出現(xiàn)b，其后至少緊跟一個(gè)c。試構(gòu)造識(shí)別L的最小化的DFA，并給出描述L的正規(guī)表達(dá)式。五、（12分）已給文法G[S]：S→SaP

9、Sf

10、PP→qbP

11、q將G[S]改造成LL（1）文法，并給出LL（1）分析表。六、（12分）給定文法G[S]：S→Aa

12、dAb

13、Bb

14、dBaA→cB→c構(gòu)造文法G[S]的LR（1）分析表。七、（8分）將下面的條件語(yǔ)句表示成逆波蘭式和四元式序列：ifa>bthenx:=

15、a+b*celsex:=b-a;八、（8分）給定基本塊：A:=3*5B:=E+FC:=A+12D:=E+FA:=D+12C:=C+1E:=E+F假定出基本塊后，只有A、C、E是活躍的，給出用DAG圖完成優(yōu)化后的代碼序列。參考答案：一、⑴D⑵A⑶A⑷C⑸G.⑹A⑺B⑻A⑼F⑽A二、1．對(duì)于G中的每個(gè)產(chǎn)生式A→γ1

16、γ2

17、…

18、γm，其各候選式均應(yīng)滿足：（1）不同的候選式不能推出以同一終結(jié)符號(hào)打頭的符號(hào)串，即FIRST(γi)∩FIRST(γj)=φ（1≤i，j≤m；i≠j）（2）若有γjε，則其余候選式γi所能推出的符號(hào)串不能以FOLLOW(A)中的終結(jié)符號(hào)開(kāi)始，即有FIRST(γi)∩F

19、OLLOW(A)=φ（i≤1,2,…,m；i≠j）2．有三種分配存儲(chǔ)空間的方式：（1）靜態(tài)分配若在編譯階段就能確定源程序中各個(gè)數(shù)據(jù)實(shí)體的存儲(chǔ)空間大小，則可以采用較簡(jiǎn)單的靜態(tài)存儲(chǔ)管理。適合靜態(tài)管理的語(yǔ)言應(yīng)具備條件：數(shù)組上下界是常數(shù)、過(guò)程調(diào)用不允許遞歸、不允許動(dòng)態(tài)建立數(shù)據(jù)實(shí)體。（2）棧式分配適用于允許遞歸調(diào)用的程序設(shè)計(jì)語(yǔ)言；（3）堆式分配對(duì)于允許程序在運(yùn)行時(shí)為變量動(dòng)態(tài)申請(qǐng)和釋放存儲(chǔ)空間的語(yǔ)言，采用堆式分配是最有效的解決方案。3．不變運(yùn)算外提；運(yùn)算強(qiáng)度削弱；消除歸納變量；下標(biāo)變量地址計(jì)算優(yōu)化。4．一個(gè)過(guò)程的一次執(zhí)行所需信息的管理，是通過(guò)稱為活動(dòng)記錄的連續(xù)存儲(chǔ)塊來(lái)實(shí)現(xiàn)的?；顒?dòng)記錄的主要內(nèi)容有：

20、（1）臨時(shí)變量域存放目標(biāo)程序臨時(shí)變量的值；（2）局部數(shù)據(jù)域存放過(guò)程本次執(zhí)行時(shí)的局部數(shù)據(jù)、簡(jiǎn)單變量及數(shù)組內(nèi)情向量等；（3）機(jī)器狀態(tài)域保存在調(diào)用過(guò)程前有關(guān)機(jī)器狀態(tài)的信息，包括各寄存器的當(dāng)前值及返回地址等；（4）存取鏈為訪問(wèn)其它活動(dòng)記錄中所存放的非局部數(shù)據(jù)所提供的鏈地址；（5）控制鏈指向主調(diào)過(guò)程的活動(dòng)記錄；（6）實(shí)參存放主調(diào)過(guò)程為被調(diào)用過(guò)程所提供的實(shí)參信息；（6）返回值為主調(diào)過(guò)程存放被調(diào)過(guò)程的返回值三、化簡(jiǎn)后：S→ASe

21、ACA→CbC→bC

22、d四、DFA如圖所示。相應(yīng)的正規(guī)式為(c

23、acc

24、bc)*。五、改造后的文法：S→PS'S'→aPS'

25、fS'

26、eP→qP'P'→bP

27、e各候選式的F

28、IRST集，各非終結(jié)符的FOLLOW集為產(chǎn)生式FIRST集FOLLOW集S→PS'{q}{#}S'→aPS'→fS'→e{a}{f}{e}{#}P→qP'{q}{a,f,#}P'→bP→e{e}{a,f,#}LL(1)分析表為六、分析表如下圖所示七、（1）逆波蘭式：,其中，BLE表示汪或等于時(shí)的轉(zhuǎn)向指令；[…]表示標(biāo)號(hào)。（2）四元式：(1)(j>,a,b,(3))(2)(j,,,(7))(3)(*,b,c,T1)(4)(+,a,T1,T2