計算機編譯原理練習題課案

1、編譯原理練習題一、選擇題1.下列文法中，不是產(chǎn)生語言ab a I n> 1的文法。A.At aBaBt b I bBB. At aBBt ba IbBC.At aBBtba I bBaD . At aBBT bCCt bC I a2.設(shè)有文法GS:St aABAtbAc I £BtbB I AeI £則經(jīng)消去£ -產(chǎn)生式后與G等價的文法GS為。A.St aA I aBI aABI aAtbc I bAcBt bB IAe I bI eB.St aABAt bAc BT bB I AeC.St aA I aBAt bc Bt b I eD.St aA I aB

2、I aAt bcI bAc B t bB IAe I b Ie3.下列文法中，是LL(1)文法。A.St bBS' aS't aBS'I £ A t S I a Bt AcB.St bS I bAI bA t aA IaC.Et E+TI TTT T*F I FF t (E) I iD.St bBS'S't aBS'I £ A t S I a Bt Ac4.下列文法中，是簡單優(yōu)先文法。A.EtE+TI TTT T*F I FFT (E) I iB.St a/At aA I AS 1/C.EtE+EI E*E I(E) I iD

3、.Et E1 E 1 t E1+T1 I T1 T1T T T T T*F I FF T (E)I i5.當掃視到數(shù)組說明進行語義處理時，必須把一個數(shù)組的如維數(shù)、各維的上、下界等記錄之中。D.指針向t bVI ac W t aW下來。為了便于引用，通常是把上述內(nèi)容存放于數(shù)組相應的A. 信息向量B.內(nèi)情向量C.地址向量6. 設(shè)有文法 GS : S t aS I Wl U U宀 aV則經(jīng)化簡后與 G等價的文法GS為。A.St aS IWVtbV I ac Wt aWB.St aS IUUt aC.St aS IWlUUt aWt aWD.St aSVt bV I ac7. 下列文法中， 是LL (

4、1)文法。A.St aS IaAAt bA I acB.St AS IbAt SA I aC. Et E+EI E*E I (E) I i8. 所謂相容，是指在一個項目集中，不出現(xiàn)這樣的情況，和歸約項目并存，或多個歸約項目并存。A.移進項目B .基本項目 C.待約項目D .后繼項目9. 下列表示中， 不是目前經(jīng)常使用的中間語言的形式。A.逆波蘭式B .四元式 C .五元式 D .樹形表示10. 如果從流程圖的首結(jié)點到流程圖中某一結(jié)點n的所有通路都要經(jīng)過結(jié)點d，我們就說結(jié)點d控制了結(jié)點n,或者把d稱為n的必經(jīng)結(jié)點，記作 。A. d DFA nB . d DOM n C . d DAG n D .

5、 d DAM n二、證明題1、試證明文法S taB I bA A taS I bAA I a B taBB I bS I b為二義性文法。三、簡答題對于如下文法，求各候選式的FIRST集和各非終結(jié)符號的 FOLLOW!。StACAB|bA| £At aAd|eB t bB|c C tcC|四、應用題1、對于如下的狀態(tài)轉(zhuǎn)換矩陣abcSAAAABCDBACADA初杰：S 終態(tài):分別畫出相應的狀態(tài)轉(zhuǎn)換圖；（10分） （2） 寫出相應的3型文法。2、將如圖所示的 DFA最小化。五、應用題1 設(shè)有文法 GE :E+T|TTtT*F|F(E)|i其相應的算符優(yōu)先矩陣如下圖所示，試給出對符號串i*

6、i+i進行算符優(yōu)先分析的過程。(i*+)#(ggggigggg*ggggg+gggg ；g)gggg#gggg2、試描述由文法： St aAd A t aAd I bBcB tbBcI e所產(chǎn)生的語言。六、應用題1 設(shè)有文法 GS : S t aABb A tAcd I d B t Bee I e(1) 將其改寫為LL(1)文法；(2) 構(gòu)造改寫后文法的LL(1)分析表。2、已知文法 GS : St aAB A t bA I a B t cB I b 的LR(0)項目集及狀態(tài)轉(zhuǎn)換圖如 下圖所示，(1)構(gòu)造LR(0)分析表;給出對輸入符號串 abacb的LR分析過程。七、簡答題1 設(shè)有二維 PA

7、SCAL數(shù)組A1 10, 1 20，給出賦值語句AI,J:=X+Y*Z的四元式序列。2、將逆波蘭式：ABCD/-*EF*+改寫為中綴式。八、簡答題1、設(shè)有如下的三地址碼（四元式）序列:A:=5I:=1J:=2L 1 : if I < J goto L 3X:=I*AL2: I:=I-Jif I>J goto L 2J:=J+1I:=Ngoto L 1L 3： X:=J*A試將它劃分為基本塊，并作控制流程圖。2、設(shè)有如下的三地址碼(四元式)序列:Li :|:=1read L,Mif I>10 goto L2A:=L*MB:=L*IC:=M*AD:=M+BI:=I+1L2 :go

8、to L 1halt對其中的循環(huán)進行循環(huán)不變運算外提的優(yōu)化。編譯原理練習題二一、選擇題1. 文法G產(chǎn)生的 的全體是該文法描述的語言。A .句型B.終結(jié)符集C.非終結(jié)符集D.句子2. 設(shè)M為一 DFA并設(shè)s和t是M的兩個不同狀態(tài)。如果 s和t，則稱s和t等價。A.不可區(qū)分B.可劃分C.可區(qū)分D.待區(qū)分3. 下歹y說法中正確的是 。A. 所謂遞歸下降法，是指只能對具有左遞歸性的文法進行分析的一種語法分析方法。B. 如果一個文法具有二義性，則它必然不是LL(1)文法。C. 對于文法G,當進行自頂向下的語法分析時，不會出現(xiàn)回溯的主要條件是，對于G中的每個A Vn, A產(chǎn)生式的所有不同候選式均能推導出以

9、同一終結(jié)符號開始的符號串。D. 對任意非LL(1)文法而言，通過消除左遞歸和反復提取左因子，都能將其改造為LL(1) 文法。4. 簡單優(yōu)先分析每次歸約的是A.最左直接短語B.直接短語C.最左素短語D.控制結(jié)點5.下列表示中,是與f x (e+(a x d+c)/d)相應的逆波蘭式。A. fead x c+d/+ x.f x e+ax d+c/dC. fad x +c/d+e x.ad x c+d/e+f x6.設(shè) G=(Vn,Vt,P,S)是一文法,我們說文法G中的一個符號 X VnU Vt是有用的，是指 X至少出現(xiàn)在的推導過程中，否則，就說X是無用的。我們將不含形如 AA 的產(chǎn)生式和不含無用

10、符號及無用產(chǎn)生式的文法稱為。7.我們常采用形如(class, value)的二元式作為一個單詞的 。其中,class是一個整數(shù)，用來指示該單詞的 , value則是單詞之值。& LL(1)分析表可用一個 表示，它的每一行與文法的一個非終結(jié)符號相關(guān)聯(lián)，而其每一列則與文法的一個終結(jié)符號或 相關(guān)聯(lián)。9.若在一個文法 G中，不含有形如 的產(chǎn)生式，其中 A,B Vn,則稱G為算符文法。10 .將每一運算符都置于其 的表達式稱為后綴表示，也稱為逆波蘭表示。11. 把流程圖中具有如下性質(zhì)的一組結(jié)點稱為程序中的一個循環(huán)：(i )在這組結(jié)點中，有惟一的 ，使得從循環(huán)外到循環(huán)內(nèi)任何結(jié)點的所有通路，者E必通

11、過此結(jié)點；(ii ) 這一組結(jié)點是 。12 .設(shè)G S是一個文法，我們把能由文法的 推導出來的符號串a(chǎn)稱為G的一個句型。當句型 a僅由組成時(即a Vt*)，則將它稱為 G產(chǎn)生的句子。13 .從某一給定的狀態(tài)q出發(fā)，僅經(jīng)過若干條 的矢線所能達到的狀態(tài)所組成的集合稱為& -CLOSURE(q)o14 .所謂遞歸下降法，是指對文法的每一非終結(jié)符號，都根據(jù)相應產(chǎn)生式各候選式的結(jié)構(gòu)，為其編寫一個,用來識別該非終結(jié)符號所表示的。15 .在每一 LR(0)項目At a 3 中放置一個 a ，使之成為:At a 3 ,a 的形式，我們將此種項目稱為一個 。16.所謂，就是對文法中的 都附加一個語義動

12、作或語義子程序，且在語法分析過程中，每當需要使用一個產(chǎn)生式進行推導或歸約時，語法分析程序除執(zhí)行相應的 外，還要執(zhí)行相應的語義動作或調(diào)用相應的語義子程序。二、簡答題1、消除文法:StAbBI a at ABI caB I BB t Aa I b中的單產(chǎn)生式。2、消除文法:StABbl a At aB I caB I &B t aA I b I£中的S-產(chǎn)生式。3、試構(gòu)造一文法，使其描述語言：L(G)= a nbmcmdn Im,n > 1 三、應用題1、設(shè)有文法 GS : StaBcl bAB A taAb I b B tb I £(1)構(gòu)造該文法的LL(1)分

13、析表；(2)分析符號串baabbb是否為該文法的句子。2、將如圖所示的具有 £動作的NFA確定化：b3、將如圖所示的 NFA確定化:四、簡答題(1對正規(guī)式(a I b)* I ab*)b，構(gòu)造與其相應的狀態(tài)轉(zhuǎn)換圖。2、 設(shè)有文法 GZ ： Z t ZAcI Ba A 宀 Ab I a B Bd I c，將其改寫為LL(1)文法。3、 消除文法：S taAc A tBbl a B tAd I c的左遞歸性。五、應用題1、設(shè)有文法G E:EtE i E ite 1+T1 |T i T ittTt T*F|FFt (E)|i其相應的簡單優(yōu)先矩陣如下圖所示，試給出對符號串i+i進行簡單優(yōu)先分

14、析的過程。E1 T1 T F +*()EE1T1TF+=>>=>>>= < < < < =< < << -< -< < < >>>>BC t d D t c2、設(shè)有文法 GS : S t ABACA taD(1)構(gòu)造此文法的LR(0)項目集及狀態(tài)轉(zhuǎn)換圖;(2)構(gòu)造SLR(1)分析表。33、設(shè)有文法 GS : S t aAB A t bA I a B t cB I b(1)構(gòu)造此文法的LR(0)項目集及狀態(tài)轉(zhuǎn)換圖;(2)構(gòu)造LR(0)分析表。六、簡答題翻譯成四元1、將語句：IF a<b V c<0 THEN b:=b+2 ELSE a:=a-2式序列。2、將語句：while A<C A B>0 do C:=C+B*D 翻譯成四元式序列。3、將