計(jì)算機(jī)編譯原理練習(xí)題

1、編譯原理練習(xí)題一一、選擇題1. 下列文法中， 不是產(chǎn)生語言 abnan1 的文法。 AAaBa BbbB BAaB BbabB CAaB BbabBa DAaB BbC CbCa2. 設(shè)有文法GS：SaAB AbAc BbBAe則經(jīng)消去-產(chǎn)生式后與G等價(jià)的文法G1S為 。ASaAaBaABa AbcbAc BbBAebeBSaAB AbAc BbBAe CSaAaB Abc BbeDSaAaBa AbcbAc BbBAebe3. 下列文法中， 是LL(1)文法。 ASbBSa SaBS ASa BAcBSbSbAb AaAa CEE+TT TT*FF F(E)iDSbBS SaBS ASa B

2、Ac4. 下列文法中， 是簡單優(yōu)先文法。 AEE+TT TT*FF F(E)i BSA/ AaAAS/ CEE+EE*E(E)i DEE1 E1E1+T1T1 T1T TT*FF F(E)i5. 當(dāng)掃視到數(shù)組說明進(jìn)行語義處理時(shí)，必須把一個(gè)數(shù)組的如維數(shù)、各維的上、下界等記錄下來。為了便于引用，通常是把上述內(nèi)容存放于數(shù)組相應(yīng)的 之中。 A信息向量 B內(nèi)情向量 C地址向量 D指針向6. 設(shè)有文法GS： SaSWU Ua VbVac WaW則經(jīng)化簡后與G等價(jià)的文法G1S為 。ASaSW VbVac WaW BSaSU Ua CSaSWU Ua WaW DSaS VbVac7. 下列文法中， 是LL（1

3、）文法。 ASaSaA AbAac BSASb ASAaCEE+EE*E(E)i DSaSbA AbAac8. 所謂相容，是指在一個(gè)項(xiàng)目集中，不出現(xiàn)這樣的情況， 和歸約項(xiàng)目并存，或多個(gè)歸約項(xiàng)目并存。 A移進(jìn)項(xiàng)目 B基本項(xiàng)目 C待約項(xiàng)目 D后繼項(xiàng)目9. 下列表示中， 不是目前經(jīng)常使用的中間語言的形式。 A逆波蘭式 B四元式 C五元式 D樹形表示10. 如果從流程圖的首結(jié)點(diǎn)到流程圖中某一結(jié)點(diǎn)n的所有通路都要經(jīng)過結(jié)點(diǎn)d，我們就說結(jié)點(diǎn)d控制了結(jié)點(diǎn)n，或者把d稱為n的必經(jīng)結(jié)點(diǎn)，記作 。 Ad DFA n Bd DOM n Cd DAG n Dd DAM n二、證明題1、試證明文法 SaBbA AaSbA

4、Aa BaBBbSb 為二義性文法。三、簡答題對于如下文法，求各候選式的FIRST集和各非終結(jié)符號的FOLLOW集。SACAB|bA| AaAd|e BbB|c CcC|四、應(yīng)用題 1、對于如下的狀態(tài)轉(zhuǎn)換矩陣分別畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖；（10分） (2) 寫出相應(yīng)的3型文法。2、將如圖所示的DFA最小化。五、應(yīng)用題1、設(shè)有文法GE： EE+T|T TT*F|F F(E)|i 其相應(yīng)的算符優(yōu)先矩陣如下圖所示，試給出對符號串i*i+i進(jìn)行算符優(yōu)先分析的過程。(i*+)#(i*+)#2、試描述由文法：SaAd AaAdbBc BbBce 所產(chǎn)生的語言。六、應(yīng)用題1、設(shè)有文法GS： SaABb AAcd

5、d BBcee(1) 將其改寫為LL(1)文法；(2) 構(gòu)造改寫后文法的LL(1)分析表。2、已知文法GS：SaAB AbAa BcBb 的LR(0)項(xiàng)目集及狀態(tài)轉(zhuǎn)換圖如下圖所示，(1) 構(gòu)造LR(0)分析表； (2) 給出對輸入符號串a(chǎn)bacb的LR分析過程。七、簡答題1、設(shè)有二維PASCAL數(shù)組A1··10, 1··20，給出賦值語句 AI,J:=X+Y*Z 的四元式序列。2、將逆波蘭式： ABCD/-*EF*+ 改寫為中綴式。八、簡答題1、設(shè)有如下的三地址碼（四元式）序列：A:=5I:=1J:=2 L1 : if IJ goto L3 X:=I*A

6、L2 : I:=I-Jif I>J goto L2 J:=J+1I:=Ngoto L1 L3: X:=J*A試將它劃分為基本塊，并作控制流程圖。2、設(shè)有如下的三地址碼（四元式）序列： I:=1read L,ML1 ： if I>10 goto L2A:=L*MB:=L*I C:=M*AD:=M+BI:=I+1goto L1L2 ： halt對其中的循環(huán)進(jìn)行循環(huán)不變運(yùn)算外提的優(yōu)化。編譯原理練習(xí)題二一、選擇題1. 文法 G 產(chǎn)生的 的全體是該文法描述的語言。 A 句型 B. 終結(jié)符集 C. 非終結(jié)符集 D. 句子2. 設(shè)M為一DFA，并設(shè)s 和t是M的兩個(gè)不同狀態(tài)。如果s和t ，則稱s

7、和t等價(jià)。 A不可區(qū)分 B可劃分 C可區(qū)分 D待區(qū)分3. 下列說法中正確的是 。A. 所謂遞歸下降法，是指只能對具有左遞歸性的文法進(jìn)行分析的一種語法分析方法。B. 如果一個(gè)文法具有二義性，則它必然不是LL(1)文法。C. 對于文法G，當(dāng)進(jìn)行自頂向下的語法分析時(shí)，不會出現(xiàn)回溯的主要條件是，對于G中的每個(gè)AVN，A產(chǎn)生式的所有不同候選式均能推導(dǎo)出以同一終結(jié)符號開始的符號串。D. 對任意非LL(1)文法而言，通過消除左遞歸和反復(fù)提取左因子，都能將其改造為LL(1)文法。4. 簡單優(yōu)先分析每次歸約的是 。 A. 最左直接短語 B.直接短語 C.最左素短語 D.控制結(jié)點(diǎn)5. 下列表示中， 是與f

8、5;(e+(a×d+c)/d)相應(yīng)的逆波蘭式。 Afead×c+d/+× Bf×e+a×d+c/d Cfad×+c/d+e× Dad×c+d/e+f×6設(shè)G=(VN,VT,P,S)是一文法，我們說文法G中的一個(gè)符號XVNVT是有用的，是指X至少出現(xiàn)在 的推導(dǎo)過程中，否則，就說X是無用的。我們將不含形如AA的產(chǎn)生式和不含無用符號及無用產(chǎn)生式的文法稱為 。7我們常采用形如 (class, value)的二元式作為一個(gè)單詞的 。其中,class是一個(gè)整數(shù)，用來指示該單詞的 ，value則是單詞之值。8LL(1)

9、分析表可用一個(gè) 表示，它的每一行與文法的一個(gè)非終結(jié)符號相關(guān)聯(lián)，而其每一列則與文法的一個(gè)終結(jié)符號或 相關(guān)聯(lián)。9若在一個(gè)文法G中，不含有形如 的產(chǎn)生式，其中A,BVN，則稱G為算符文法。 10將每一運(yùn)算符都置于其 的表達(dá)式稱為后綴表示，也稱為逆波蘭表示。 11把流程圖中具有如下性質(zhì)的一組結(jié)點(diǎn)稱為程序中的一個(gè)循環(huán)：() 在這組結(jié)點(diǎn)中，有惟一的 ，使得從循環(huán)外到循環(huán)內(nèi)任何結(jié)點(diǎn)的所有通路，都必通過此結(jié)點(diǎn)；() 這一組結(jié)點(diǎn)是 。12設(shè)GS是一個(gè)文法，我們把能由文法的 推導(dǎo)出來的符號串稱為G的一個(gè)句型。當(dāng)句型僅由 組成時(shí) (即VT*)，則將它稱為G產(chǎn)生的句子。 13從某一給定的狀態(tài)q出發(fā)，僅經(jīng)過若干條 的矢

10、線所能達(dá)到的狀態(tài)所組成的集合稱為-CLOSURE(q)。 14所謂遞歸下降法，是指對文法的每一非終結(jié)符號，都根據(jù)相應(yīng)產(chǎn)生式各候選式的結(jié)構(gòu)，為其編寫一個(gè) ，用來識別該非終結(jié)符號所表示的 。15在每一LR(0)項(xiàng)目A·中放置一個(gè) a ，使之成為A·,a的形式，我們將此種項(xiàng)目稱為一個(gè) 。16所謂 ，就是對文法中的 都附加一個(gè)語義動作或語義子程序，且在語法分析過程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除執(zhí)行相應(yīng)的 外，還要執(zhí)行相應(yīng)的語義動作或調(diào)用相應(yīng)的語義子程序。二、簡答題1、消除文法: SAbBA AABcaBB BAab 中的單產(chǎn)生式。2、消除文法: SABb

11、a AaBcaB BaAb 中的-產(chǎn)生式。3、試構(gòu)造一文法，使其描述語言： L(G)= anbmcmdnm,n1 三、應(yīng)用題1、設(shè)有文法GS： SaBcbAB AaAbb Bb(1) 構(gòu)造該文法的LL(1)分析表； (2) 分析符號串baabbb是否為該文法的句子。2、將如圖所示的具有動作的NFA確定化：3、將如圖所示的NFA確定化：四、簡答題（1、對正規(guī)式(ab) *ab*)b ，構(gòu)造與其相應(yīng)的狀態(tài)轉(zhuǎn)換圖。2、設(shè)有文法GZ： ZZAcBa AAba BBdc ，將其改寫為LL(1)文法。3、消除文法: SaAc ABba BAdc 的左遞歸性。五、應(yīng)用題1、設(shè)有文法GE： EE1 E1E1+

12、T1|T1 T1T TT*F|F F(E)|i其相應(yīng)的簡單優(yōu)先矩陣如下圖所示，試給出對符號串i+i進(jìn)行簡單優(yōu)先分析的過程。2、設(shè)有文法GS： SABAC AaD Bb Cd Dc（1）構(gòu)造此文法的LR(0)項(xiàng)目集及狀態(tài)轉(zhuǎn)換圖；） （2）構(gòu)造SLR(1)分析表。3、設(shè)有文法GS： SaAB AbAa BcBb （1）構(gòu)造此文法的LR(0)項(xiàng)目集及狀態(tài)轉(zhuǎn)換圖； （2）構(gòu)造LR(0)分析表。六、簡答題1、將語句： IF a<b c<0 THEN b:=b+2 ELSE a:=a-2 翻譯成四元式序列。2、將語句： while A<CB>0 do C:=C+B*D翻譯成四元式序列。3、將中綴式 A+B*(C-D)/(E+F) 改寫為逆波蘭式。七、應(yīng)用題1、對于如右所示的基本塊，若