廣工編譯原理試卷A

1、學(xué)習(xí)必備歡迎下載編譯原理試卷A一、選擇題（每空2 分，共 20 分）1.一個(gè)正規(guī)語言只能對應(yīng)(B)？A 一個(gè)正規(guī)文法；B 一個(gè)最小有限狀態(tài)自動(dòng)機(jī)；2.文法 GA ： A A aB B Ab B a是(B)：A 正規(guī)文法B 二型文法3.下面說法正確的是(A)：A 一個(gè) SLR （ 1）文法一定也是 LALR （ 1）文法B 一個(gè) LR （ 1）文法一定也是 LALR （ 1）文法4.一個(gè)上下文無關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL （ 1）文法的 (A)：A 必要條件B 充分必要條件5. （ D ）不是 NFA 的成分。A 由窮字母表B 初始狀態(tài)集合C 終止?fàn)顟B(tài)集合D 有限狀態(tài)集合6

2、（ C）不是編譯程序的組成部分A 詞法分析程序B 代碼生成程序C 設(shè)備管理程序D 語法分析程序7有文法G=(S,a,S SaS, S ,S),該文法是（B）。A. LL(1)文法B.二義性文法C算符優(yōu)先文法D SLR(1)文法8 給定文法 A bA|cc ，則符號串 cc bcbc bcbcc bccbcc bbbcc 中，是該文法句子的是（D ）A BCD9 表達(dá)式A*(B-C*(C/D)的逆波蘭表示為（B）A. ABC-CD/*B. ABCCD/*-*C. ABC-*CD/*D.前三個(gè)選項(xiàng)都不對10 LR(1)文法都是（A）A 無二義性且無左遞歸B可能有二義性但無左遞歸C 無二義性但可能有

3、無左遞歸D可以既有二義性又有左遞歸二、問答題第 1 題 (10 分 )將文法 GS 改寫為等價(jià)的GS，使 GS不含左遞歸和左公共因子。學(xué)習(xí)必備歡迎下載GS ： SbSAe | bAAAb | d答： 文法 GS改寫為等價(jià)的不含左遞歸和左公共因子的G'S 為：SbBBSAe | AAd A'A' bA' |第 2 題（10分）給出與正規(guī)式R（ ab） * （ a|b*） ba 等價(jià)的 NFA 。答：與正規(guī)式 R（ ab）* （ a|b * ）ba 等價(jià)的 NFA如下圖第 3 題（ 10 分） 將下圖的NFA 確定化為DFA 。答：用子集法確定化如下表用子集法對所給

4、圖的確定化IIaIb狀態(tài)X,1,21,2 .1,2,3X1,2 .1,2 .1,2,311,2,31,2,Y1,2,321,2,Y1,2 .1,2,33學(xué)習(xí)必備歡迎下載確定化后如下圖第 4 題（ 10 分）給出文法GS 的 LR(1) 項(xiàng)目集規(guī)范族中I 0 項(xiàng)目集的全體項(xiàng)目。GS 為：S BD|DB aD|b D B答：解:I0第 5題 (10分)文法 GM 及其 LR 分析表如下，請給出對串dbba#的分析過程。GM: 1) M VbA2) V d3) V4) A a5) AAba6) AnameACTIONGOTO學(xué)習(xí)必備歡迎下載bda#MAV0r3S3121acc2S43r24r6S5r

5、665r4r46S7r17S88r5r5答：對串 dbba#的分析過程如下表對輸入串dbba#的分析過程步驟狀態(tài)棧文法符號棧剩余輸入符號10#dbba#203#dbba#302#Vbba#4024#Vbba#50246#VbAba#602467#VbAba#7024678#VbAba#80246#VbA#901#M#第 6 題(20 分 )某語言的拓廣文法G為： (0) S T(1) TaBd|(2) BTb| 證明 G 不是 LR(0) 文法而是SLR(1) 文法，請給出SLR(1) 分析表。動(dòng)作移進(jìn)用 V d歸約移進(jìn)用 A 歸約移進(jìn)移進(jìn)用 A Aba 歸約用 M VbA 歸約接受學(xué)習(xí)必備歡

6、迎下載答：拓廣文法G'，增加產(chǎn)生式S' T在項(xiàng)目集I 0 中：有移進(jìn)項(xiàng)目T · aBd和歸約項(xiàng)目T ·存在移進(jìn) -歸約沖突，所以G 不是 LR(0) 文法。若產(chǎn)生式排序?yàn)椋?0) S' T(1) T aBd(2) T (3) B Tb(4) B G' 的 LR(0) 項(xiàng)目集族及識別活前綴的DFA如下圖所示：識別 G活前綴的DFA由產(chǎn)生式知：Follow(T)=#,bFollow(B)= d在 I0中：Follow(T)a=#，b a=在 I2中：Follow(B)a= da=學(xué)習(xí)必備歡迎下載Follow(T)a=#，ba=Follow(B)Follow(T) = d#， b=所以在 I 0， I 2 ，中的移進(jìn) - 歸約和歸約 - 歸約沖突可以由 Follow 集解決，所以 G是 SLR(1)文法。構(gòu)造的 SLR(1)分析表如下表。SLR(1) 分析表nameACTIONGOTOabd#TB0S2r2r211acc2S2r2r4r2433S54S65r1r16r3第 7 題（ 10 分） 對產(chǎn)生 C 語言中的條件表達(dá)式的文法GE ： EE?E:E寫出相應(yīng)的翻譯文法。答 : E1 E? BackPatch($1.TC,NXQ);$.FC=$1.FC;E2E1E2: