編譯原理試題

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

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

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

16、γ2

17、…

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

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

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