《編譯原理》練習(xí)題.doc

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