《編譯原理》練習題.doc

編譯原理練習題一 一、填空題（每空1分）1設GS是一個文法，我們把能由文法的 （1） 推導出來的符號串稱為G的一個句型。當句型僅由 （2） 組成時 (即VT*)，則將它稱為G產生的句子。 2從某一給定的狀態(tài)q出發(fā)，僅經過若干條 (3) 的矢線所能達到的狀態(tài)所組成的集合稱為-CLOSURE(q)。3設G=(VN,VT,P,S)是一文法，我們說G中的一個符號XVNVT是有用的，是指X至少出現在 （4） 的推導過程中，否則，就說X是無用的。我們將不含形如AA的產生式和不含無用符號及無用產生式的文法稱為 （5） 。4我們常采用形如 (class, value)的二元式作為一個單詞的 (6) 。其中,class是一個整數，用來指示該單詞的 (7) ，value則是單詞之值。5一個文法GS可表示成形如 （8） 的四元式。其中VN,VT,P均為非空的有限集，分別稱為非終結符號集、終結符號集和產生式集， SVN為文法的開始符號。此外，將出現在各產生式左部和右部的一切符號所組成的集合稱為 （9） ，記作V。顯然，V=VNVT,VNVT=。 6通常，可通過兩種途徑來構造詞法分析程序。其一是根據對語言中各類單詞的某種描述或定義，用 (10) 構造詞法分析程序；另外一種途徑是所謂詞法分析程序的 (11) 。7設G為一文法，A是G的一個產生式，如果具有A的形式，其中，不同時為，則稱產生式A是 （12） 。若存在推導，則稱產生式A是 （13） 。 8設M=(K,f,S0,Z)為一DFA，并設s和t是M的兩個不同狀態(tài)，我們說狀態(tài)s,t為某一輸入串w (14) ，是指從s,t中之一出發(fā)，當掃視完w之后到達M的終態(tài)，但從其中的另一個狀態(tài)出發(fā)，當掃視完同一個w后而進入 (15) 。9把最右推導稱為 （16） ，而把右句型稱為 （17） 。10如果從狀態(tài)轉換圖的初態(tài)出發(fā)，分別沿著一切可能的路徑到達 (18) ，并將每條路徑各矢線上的 (19) 依次連接起來，便得到狀態(tài)轉換圖所能識別的全部字符串，這些字符串所組成的集合也就是該狀態(tài)轉換圖所識別的語言。二、選擇題（每空2分） 1. 下列文法中， 不是產生語言 abnan1 的文法。 AAaBa BbbB BAaB BbabB CAaB BbabBaDAaB BbC CbCa2. 設有文法GS： SaAB AbAc BbBAe則經消去-產生式后與G等價的文法G1S為 。ASaAaBaABa AbcbAc BbBAebeBSaAB AbAc BbBAe CSaAaB Abc BbeDSaAaBa AbcbAc BbBAebe3. 文法 G 產生的 的全體是該文法描述的語言。 A 句型 B. 終結符集 C. 非終結符集 D. 句子4. 設M為一確定有限自動機，并設s 和t是M的兩個不同狀態(tài)。如果s和t ，則稱s和t等價。 A不可區(qū)分 B可劃分 C可區(qū)分 D待區(qū)分5. 設有文法GS： SaSWU Ua VbVac WaW則經化簡后與G等價的文法G1S為 。ASaSW VbVac WaWBSaSU Ua CSaSWU Ua WaWDSaS VbVac 6. 若文法 G 定義的語言是無限集，則文法G必然是 。 A前后文無關的 B遞歸的 C二義性的 D無二義性的 7. 下列說法中正確的是 。 A一個確定的有限自動機實際上是相應的狀態(tài)轉換圖的一種形式描述。 B一個狀態(tài)轉換圖是由一組矢線連接的有限個結點所組成的無回路有向圖。 C所謂一個DFA M狀態(tài)數的最小化，是指構造一個與之等價的DFA M，使它們有相同的接受集。 D對于有同一接受集的FA，與之等價的DFA在同構意義下是唯一的。8. 下列文法中， 不是產生語言 的文法。 AAaBa BaaBa BAaB BaaBaa CAaAA AaDAaBB BaaBB9. 如下的表示形式中，不能表示程序語言中單詞結構的是 。 A左線性文法 B形如（Class，Value）的二元式 C正規(guī)式 D正規(guī)文法三、證明題1試證明文法 SaBbA AaSbAAa BaBBbSb 為二義性文法。 （10分）2 試證明文法: SaAB AaAa BaBb 為二義性文法。 （10分）四、簡答題1試構造一文法，使其描述如下語言： （15分）L(G)= anbmcmdnm,n1 2消除下列文法中的單產生式。 （10分）SAbBA AABcaBB BAab3對正規(guī)式(ab) *ab*)b ，構造與其相應的狀態(tài)轉換圖。 （15分）4消除下列文法中的-產生式。 （10分）SABba AaBcaB BaAb5試描述由下列文法所產生的語言。 （10分）SaAd AaAdbBc BbBce6 消除下列文法中的單產生式。 （10分）SaFbMF FMabc MabFc7化簡下列文法： （10分）SBabcC BbSb CDa DCbCDa8 對正規(guī)式(aab)*ab* ，構造與其相應的狀態(tài)轉換圖。 （15分）9試構造一正規(guī)文法，使其描述如下語言： （10分）L(G)= abmcbnam1, n0 10試描述由下列文法所產生的語言。 （15分）SaAbB AAab BaAaC CcCd 五、應用題 1對于如下的狀態(tài)轉換矩陣(1) 分別畫出相應的狀態(tài)轉換圖；（10分）(2) 寫出相應的3型文法。 （10分）2 將如圖所示的NFA確定化。 （20分）3 將如圖所示的具有動作的NFA確定化。 （20分）4 將如圖所示的DFA最小化。 （20分）5將如圖所示的DFA最小化。 （25分）6對于如下的狀態(tài)轉換矩陣(1) 畫出相應的狀態(tài)轉換圖；（10分）(2) 寫出相應的3型文法。 （10分）7設有如下正規(guī)文法GS：SaAaB AbBb BbBbC CbCa （1）構造與文法GS相應的狀態(tài)轉換圖； （10分） （2）將所得的NFA確定化。 （15分）8將如圖所示的NFA確定化。 （15分）編譯原理練習題二一、填空題（每空1分，共10分） 1所謂遞歸下降法，是指對文法的每一非終結符號，都根據相應產生式各候選式的結構，為其編寫一個 (1) ，用來識別該非終結符號所表示的 (2) 。2在每一LR(0)項目A中放置一個 (3) a，使之成為A,a的形式，我們將此種項目稱為一個 (4) 。3所謂 (5) ，就是對文法中的 (6) 都附加一個語義動作或語義子程序，且在語法分析過程中，每當需要使用一個產生式進行推導或歸約時，語法分析程序除執(zhí)行相應的 (7) 外，還要執(zhí)行相應的語義動作或調用相應的語義子程序。 4LL(1)分析表可用一個 (8) 表示，它的每一行與文法的一個非終結符號相關聯，而其每一列則與文法的一個終結符號或 (9) 相關聯。5若在一個文法G中，不含有形如 (10) 的產生式，其中A,BVN，則稱G為算符文法。 6將每一運算符都置于其 (11) 的表達式稱為后綴表示，也稱為逆波蘭表示。 7把流程圖中具有如下性質的一組結點稱為程序中的一個循環(huán)：() 在這組結點中，有惟一的 (12) ，使得從循環(huán)外到循環(huán)內任何結點的所有通路，都必通過此結點；() 這一組結點是 (13) 。 8語法分析的基本任務是：根據語言的語法規(guī)則 (即根據描述該語言的前后文無關文法)，分析源程序的 (14) ，即分析如何由這些單詞組成各種語法范疇，并在分析過程中，對源程序進行 (15) 。 9所謂句型的素短語，是指一個句型中具有這樣性質的短語：短語中至少含有一個 (16) ，且除它自身外，不再包含其它的 (17) 。10一個文法符號X的 (18) 我們稱之為語義屬性或簡稱為屬性，用形如X.ATTR的記號來表示文法符號X的相關語義屬性。 11表示流程圖中各結點間控制關系的一種直觀而有效的方法是用樹形結構，稱之為 (19) 。 12目前，已存在許多語法分析方面的方法。但就產生語法樹的方向而言，可大致把它們分為 (20) 和 (21) 兩大類。 13將形如AX的項目稱為AX的 (22) 。14記錄和一個數組有關的信息，如維數n、各維的上、下界lk和uk的數據結構稱為數組的 (23) 。 15基本塊是程序中具有下述性質的 (24) ：它有惟一的入口和惟一的出口，它們分別是塊中的第1個操作和最末一個操作，且塊中的各個操作按順序執(zhí)行，不出現 (25) 。 16若一文法G的任何兩個符號之間 (26) 一種優(yōu)先關系，且任意兩個不同的產生式均無 (27) ，則稱G為簡單優(yōu)先文法。 17把在數據區(qū)給變量分配的存儲單元地址稱為 (28) ，而把在目標程序運行時存放在相應單元中的值稱為 (29) 。18如果從流程圖的首結點到流程圖中某一結點n的所有通路都要經過結點d，我們就說結點d控制了結點n，或者把d稱為n的 (30) ，記作 (31) 。二、選擇題（每空2分） 1. 下列文法中， 是LL(1)文法。 ASbBSa SaBS ASa BAcBSbSbAb AaAaCEE+TT TT*FF F(E)i DSbBS SaBS ASa BAc2. 下列文法中， 是簡單優(yōu)先文法。 AEE+TT TT*FF F(E)iBSA/ AaAAS/CEE+EE*E(E)i DEE1 E1E1+T1T1 T1T TT*FF F(E)i3. 當掃視到數組說明進行語義處理時，必須把一個數組的如維數、各維的上、下界等記錄下來。為了便于引用，通常是把上述內容存放于數組相應的 之中。 A信息向量 B內情向量 C地址向量 D指針向量4. 下列說法中正確的是 。A. 所謂遞歸下降法，是指只能對具有左遞歸性的文法進行分析的一種語法分析方法。B. 如果一個文法具有二義性，則它必然不是LL(1)文法。C. 對于文法G，當進行自頂向下的語法分析時，不會出現回溯的主要條件是，對于G中的每個AVN，A產生式的所有不同候選式均能推導出以同一終結符號開始的符號串。D. 對任意非LL(1)文法而言，通過消除左遞歸和反復提取左因子，都能將其改造為LL(1)文法。5. 簡單優(yōu)先分析每次歸約的是 。 A. 最左直接短語 B.直接短語 C.最左素短語 D.控制結點6. 下列表示中， 是與f(e+(ad+c)/d)相應的逆波蘭式。 Afeadc+d/+ Bfe+ad+c/d Cfad+c/d+e Dadc+d/e+f7. 下列文法中， 是LL（1）文法。 ASaSaA AbAac BSASb ASAa CEE+EE*E(E)i DSaSbA AbAac8. 所謂相容，是指在一個項目集中，不出現這樣的情況， 和歸約項目并存，或多個歸約項目并存。 A移進項目 B基本項目 C待約項目 D后繼項目9. 下列表示中， 不是目前經常使用的中間語言的形式。 A逆波蘭式 B四元式 C五元式 D樹形表示10. 如果從流程圖的首結點到流程圖中某一結點n的所有通路都要經過結點d，我們就說結點d控制了結點n，或者把d稱為n的必經結點，記作 。 Ad DFA n Bd DOM n Cd DAG n Dd DAM n11. 下列說法中錯誤的是 。 A. 任何LL(1)文法都是無二義性的。B. 左遞歸文法必然不是LL(1)文法。C. 對于任意一個前后文無關文法G，都能為其構造一個無多重定義的預測分析表。D. 如果文法是左遞歸的，則自頂向下的分析過程將不能正常地進行。12. 如下的語法分析方法中， 要求文法中不含-產生式。 A預測分析法 BLR（1）分析法 C遞歸下降分析法 D算符優(yōu)先分析法13. 如下四元式中正確的是 。 A（jnz， ， ，p） B（j，A1，A2，p）C（jJ goto L2 J:=J+1I:=Ngoto L1 L3: X:=J*A試將它劃分為基本塊，并作控制流程圖。 （10分）3 消除下列文法的左遞歸性。 （10分） SaAc ABba BAdc 4 將下列中綴式改寫為逆波蘭式。 （10分）A+B*(C-D)/(E+F) 5將下列語句翻譯成四元式序列。 （10分）IF ab c0 THEN b:=b+2 ELSE a:=a-2 6 將下列語句翻譯成四元式序列。 （10分）while A0 do C:=C+B*D 7設有文法GZ： ZZAcBa AAba BBdc將其改寫為LL(1)文法。 （15分）8對于如下的程序，試對其中的循環(huán)進行削弱運算強度的優(yōu)化。 （10分）9對于如下文法，求各候選式的FIRST集和各非終結符號的FOLLOW集。 （共15分）SACAB|bA| AaAd|e BbB|c CcC|10將下面的逆波蘭式改寫為中綴式。 （8分） ABCD/-*EF*+11設有如下的三地址碼（四元式）序列： I:=1 read L,ML1 ： if I10 goto L2A:=L*MB:=L*I C:=M*A D:=M+B I:=I+1 goto L1L2 ： halt(1) 將它劃分為基本塊，并作控制流程圖； （6分）(2) 對其中的循環(huán)進行循環(huán)不變運算外提的優(yōu)化。 （6分）12將下列語句翻譯成四元式序列。 （10分）IF ad THEN b:=c+d*3 ELSE a:=a-c/d 13將下列語句翻譯成四元式序列。 （10分）IF ab c0 THEN BEGIN b:=b+2；c:=c-1 END ELSE WHILE a=d DO BEGIN a=a-2； d:=d+1 END14將下列逆波蘭式改寫為中綴式。 （10分）AB+C*DEF*-/15 將下列語句翻譯成四元式序列。 （10分）while A0 do X:=A+B*C16對于如下的程序，試對其中的循環(huán)進行削弱運算強度的優(yōu)化。（10分）17設有二維PASCAL數組A110, 120, 130，將下列語句翻譯成四元式序列。（10分）X := AI+1,J*2,I * B+C18對于如下的基本塊，若變量G，L，M在基本塊出口之后被引用： A:=B*C D:=5 E:=C/D F:=2*D G:=C/D H:=B*C L:=H*E M:=L(1) 構造相應的DAG； （5分） (2) 重建經優(yōu)化后的四元式序列。 （5分）四、應用題 1設有文法GS： SaABb AAcdd BBcee(1) 將其改寫為LL(1)文法； （10分）(2) 構造改寫后文法的LL(1)分析表。 （10分）2設有文法GE： EE+T|T TT*F|F F(E)|i 其相應的算符優(yōu)先矩陣如圖所示，試給出對符號串i*i+i進行算符優(yōu)先分析的過程。（20分）(i*+)#(i*+)#文法GE的算符優(yōu)先矩陣3設有文法GS： SaAB AbAa BcBb （1）構造此文法的LR(0)項目集及狀態(tài)轉換圖； （15分）（2）構造LR(0)分析表。 （10分）4對于如圖所示的控制流程圖：(1) 求出各個結點的必經結點集； （5分）(2) 求出各個回邊，并找出流程圖的全部循環(huán)。 （5分）5 設有文法GS： SaBcbAB AaAbb Bb(1) 構造該文法的LL(1)分析表； （10分）(2) 分析符號串baabbb是否為該文法的句子。（15分）6設有文法GE：EE1 E1E1+T1|T1 T1T TT*F|F F(E)|i 其相應的簡單優(yōu)先矩陣如下圖所示，試給出對符號串i+i進行簡單優(yōu)先分析的過程。（20分）7對于如下的基本塊，若變量G,M在基本塊出口之后被引用： A:=B+C D:=3 E:=6 F:=D*E G:=B+C H:=A+D L:=H*F M:=L(1) 構造相應的DAG； （5分） (2) 重建經優(yōu)化后的四元式序列。 （5分）8設有文法GS： SABAC AaD Bb Cd Dc（1）構造此文法的LR(0)項目集及狀態(tài)轉換圖； （15分）（2）構造SLR(1)分析表。 （10分）9已知文法GS： SaAB AbAa BcBb 的LR(0)項目集及狀態(tài)轉換圖如下：(1) 構造LR(0)分析表； （10分）(2) 給出對輸入符號串abacb的LR分析過程。 （15分）10 消除下列文法的左遞歸性。 （15分） ZAaB ABba BZdc11設有文法GE：EE1 E1E1+T1|T1 T1T TT*F|F F(E)|i 其相應的簡單優(yōu)先矩陣如圖所示，試給出對符號串i*i進行簡單優(yōu)先分析的過程。（20分）12對于如圖所示的控制流程圖： （共10分）(1) 求出各個結點的必經結點集；(2) 求出各個回邊，并找出流程圖的全部循環(huán)。13設有文法GS： SaAbDad ABSDb BcD DSac(1) 構造該文法的LL(1)分析表； （10分）(2) 分析