編譯原理試題匯總

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

1、一、選擇題（每個(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可能唯一，好可能不唯一5．?dāng)?shù)組的內(nèi)情向量中肯定不含有數(shù)組的⑻的信息A

2、．維數(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）分析法對(duì)文法有哪些要求？2．常見的存儲(chǔ)分配策略有幾種？它們都適合于什么性質(zhì)的語言？3．常見循環(huán)優(yōu)化都有哪些項(xiàng)目？4．什么是活動(dòng)記錄？它主要由哪些內(nèi)容構(gòu)成？五、（12分）已給文法G[S]：S→SaP

3、Sf

4、P

5、P→qbP

6、q將G[S]改造成LL（1）文法，并給出LL（1）分析表。七、（8分）將下面的條件語句表示成逆波蘭式和四元式序列：ifa>bthenx:=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

7、γ2

8、…

9、γm，其各候選式均應(yīng)滿足：（1）不同的候選式不能推出以同一終結(jié)符號(hào)打頭的符號(hào)串，即FI

10、RST(γi)∩FIRST(γj)=φ（1≤i，j≤m；i≠j）（2）若有γjε，則其余候選式γi所能推出的符號(hào)串不能以FOLLOW(A)中的終結(jié)符號(hào)開始，即有FIRST(γi)∩FOLLOW(A)=φ（i≤1,2,…,m；i≠j）五、改造后的文法：S→PS'S'→aPS'

11、fS'

12、eP→qP'P'→bP

13、e各候選式的FIRST集，各非終結(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)分析表為七、（

14、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)(5)(:=,T2,,x)(6)(j,,,(9))(7)(-,b,a,T3)(8)(:=,T3,,x)(9)(……)八、化簡后的的四元式序列為A:=D+12E:=E+FC:=28二、填空題(每題2分，共20分)1、從功能上說，程序語言的語句大體可分為_______語句和______語句兩大類。2、掃描器的任務(wù)是從________中識(shí)別出一個(gè)個(gè)_______。3、所謂

15、最右推導(dǎo)是指：_______。4、語法分析最常用的兩類方法是________和_________分析法。5、一個(gè)上下文無關(guān)文法所含四個(gè)組成部分是_______________。6、所謂語法制導(dǎo)翻譯方法是_____________________。7、符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如_________等等。8、一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為________。9、常用的兩種動(dòng)態(tài)存貯分配辦法是_____動(dòng)態(tài)分配和_____動(dòng)態(tài)分配。10、產(chǎn)生式是用于定義_____的一種書寫規(guī)則。四、簡述題(每題4分，共24分)1、考慮下面程序　　………

16、…　　Vara：integer；　　ProcedureS(X)；　　　VarX：integer；　　　Begin　　　　a：＝a＋1；　　　　X：＝a＋X　　　End；　　Begin　　　　a：＝5；　　　　S(a)；　　　　Print(a)　　End．試問：若參數(shù)傳遞方式分別采取傳名和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？3、寫出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示及三元式序列。4、已知文法G(S)　　S→a

17、∧

18、(T)　　T→T，S

19、S　　寫出句子((a，a)，a)的規(guī)范歸約過程及每一步的句柄。五、計(jì)算題(共41分)1、寫一個(gè)文法，使其語言

20、是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。(5分)2、設(shè)文法G(S)：　　S→(L)

21、aS