編譯原理試卷

一、判斷對(duì)錯(cuò)：（對(duì)√；錯(cuò)；每小問2分共24分）<1>算符優(yōu)先分析法是一種規(guī)范歸約分析法。（）<2>若文法Gs中不含形如T→…BD…的產(chǎn)生式，T、B、D∈VN，則稱Gs為算符文法。（√）<3>若一個(gè)語(yǔ)言是有窮集合，則定義該語(yǔ)言的文法一定是遞歸的。（）<4>若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是等價(jià)的。（√）<5>LR分析法是一種規(guī)范歸約分析法。（√）<6>一個(gè)LR(0)項(xiàng)目集I={B→α.bβ,P→aA.},則說I中含有“移進(jìn)—?dú)w約”沖突。（√）<7>SLR(1)文法是無(wú)二義性文法。（√）<8>消除左遞歸后的文法一定是LL(1)文法。（）<9>對(duì)任何編譯程序而言，代碼優(yōu)化是必不可少的。（）<10>編譯程序與具體的機(jī)器無(wú)關(guān)。（）<11>在自動(dòng)機(jī)的概念中，終態(tài)與非終態(tài)是可區(qū)別的。（√）<12>逆波蘭式ab+cd+*所代表的中綴表達(dá)式是：(a+b)*(c+d)（√）1.一個(gè)語(yǔ)言有文法是不惟一的。（√）2.若一個(gè)語(yǔ)言是無(wú)窮集合，則定義該語(yǔ)言的文法一定是遞歸的。（√）3.緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句是基本塊的入口語(yǔ)句。（√）4.算符優(yōu)先分析法是一種規(guī)范歸約分析法。（）5.自下而上語(yǔ)法自導(dǎo)翻譯的特點(diǎn)：當(dāng)棧頂形成句柄時(shí)，在歸約的同時(shí)執(zhí)行其語(yǔ)義動(dòng)作。（√）6.LR(0)文法、SLR(1)文法都是無(wú)二義性文法。（√）7．K、∑分別表示有限狀態(tài)集和有窮字母表,DFAM的轉(zhuǎn)換函數(shù)f是一個(gè)從K∑到K的單值映射。（√）8.對(duì)任何編譯程序而言，代碼優(yōu)化是必不可少的。（）9.直接短語(yǔ)是某規(guī)則的右部，它對(duì)應(yīng)簡(jiǎn)單子樹葉結(jié)點(diǎn)從左到右排列形成的符號(hào)串。（√）10.兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的狀態(tài)數(shù)和有向弧數(shù)相等。（）11.一個(gè)LR(0)項(xiàng)目集為：I={A→.bβ,D→β.},則說I中含有“移進(jìn)--歸約”沖突。（√）12.若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是等價(jià)的。（√）13.無(wú)左遞歸的文法是LL(1)文法。（）14.逆波蘭式abcde/+*+所代表的中綴表達(dá)式是：a+b*(c+d/e)（√）15.編譯程序結(jié)構(gòu)中，中間代碼優(yōu)化及目標(biāo)代碼生成兩個(gè)階段與具體的機(jī)器有關(guān)。（）16.LALR分析法中，同心集的合并不會(huì)產(chǎn)生“移進(jìn)--歸約”沖突。（√）<1>算符優(yōu)先分析法是一種規(guī)范歸約分析法。（錯(cuò)）<2>若文法Gs中不含形如T→…BD…的產(chǎn)生式，T、B、D∈VN，則稱Gs為算符文法。（對(duì)）<3>若一個(gè)語(yǔ)言是有窮集合，則定義該語(yǔ)言的文法一定是遞歸的。（錯(cuò)）<4>若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是等價(jià)的。（對(duì)）<5>LR分析法是一種規(guī)范歸約分析法。（對(duì)）<6>一個(gè)LR(0)項(xiàng)目集I={B→α.bβ,P→aA.},則說I中含有“移進(jìn)—?dú)w約”沖突。（對(duì)）<7>SLR(1)文法是無(wú)二義性文法。（對(duì)）<8>消除左遞歸后的文法一定是LL(1)文法。（錯(cuò)）<9>對(duì)任何編譯程序而言，代碼優(yōu)化是必不可少的。（錯(cuò)）<10>編譯程序與具體的機(jī)器無(wú)關(guān)。（錯(cuò)）二、<1>將下圖所示的NFA確定化。(狀態(tài)轉(zhuǎn)換矩陣4分；狀態(tài)轉(zhuǎn)換圖2分)解：<1>狀態(tài)轉(zhuǎn)換矩陣4分狀態(tài)轉(zhuǎn)換圖2分<2>給出語(yǔ)言L={danb|n≥1}相應(yīng)的文法。GA：A→dBbGA：A→dBB→aB|aB→aB|ab三、①編譯程序的工作過程一般劃分為五個(gè)基本階段：B；D、語(yǔ)義分析和中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。A.出錯(cuò)處理B.詞法分析C.表格管理D.語(yǔ)法分析②已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，該文法終結(jié)符集合VT=A；C，GE稱2型文法或上下文無(wú)關(guān)文法。A.{+,(,),*,b}B.{+,(,),*,E}C.{+,*,(,),b}D.{E,T,F}③已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，該文法的非終結(jié)符集VN=B，GE稱2型文法或上下文無(wú)關(guān)文法。A.{+,(,),*,b}B.{E,T,F}C.{+,*,(,),b}D.{E,T,F,*,+}④文法用于描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)，它由如下四個(gè)部分組成：A；C；D和文法開始符號(hào)。A.文法終結(jié)符集B.字母數(shù)字串C.文法非終結(jié)符集D.文法產(chǎn)生式集⑤一個(gè)文法被稱為是二義性的，如果A,D。A.文法的某一個(gè)句子有兩個(gè)以上的最右或最左推導(dǎo)。B.文法的預(yù)測(cè)分析表中有多重入口。C.文法的某個(gè)LR(0)項(xiàng)目集中有沖突項(xiàng)目。D.文法的某一個(gè)句子有兩棵以上不同的語(yǔ)法樹。⑥程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)一般可分為五種，它們是保留字、A；D及運(yùn)算符和定界符。A.常數(shù)B.表達(dá)式C.注解D.標(biāo)識(shí)符⑦設(shè)有一個(gè)LR(0)項(xiàng)目集I={A→β.bδ，B→β.，D→δ.}，I中存在沖突項(xiàng)目，它們是A；D。A.“移進(jìn)-歸約”沖突B.“移進(jìn)-接受”沖突C.“移進(jìn)-待約”沖突D.“歸約-歸約”沖突⑧一個(gè)文法的SLR(1)方法和與其相應(yīng)的LR(0)方法的狀態(tài)數(shù)A。A.相同B.不相同的C.前者大于后者D.后者大于前者1．編譯程序的工作過程一般劃分為五個(gè)基本階段：詞法分析、BD、中間代碼優(yōu)化、目標(biāo)代碼生成。A.出錯(cuò)處理B.語(yǔ)法分析C.表格管理D.語(yǔ)義分析與中間代碼生成2．識(shí)別某文法所有LR(0)項(xiàng)目集簇的DFA中，若項(xiàng)目集k中含有項(xiàng)目“A→δ.”，且僅當(dāng)輸入符號(hào)a∈FOLLOW(A)時(shí)，才用規(guī)則“A→δ”歸約的語(yǔ)法分析方法是D。A．LALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法3．程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)一般可分為五種，它們是常數(shù)、CD及運(yùn)算符和定界符。A.注解B.表達(dá)式C.標(biāo)識(shí)符D.保留字4．文法用于描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)，它由如下四個(gè)部分組成：ACD和文法開始符號(hào)。A.文法終結(jié)符集B.字母數(shù)字串C.文法非終結(jié)符集D.文法產(chǎn)生式集5．一個(gè)文法被稱為是二義性的，如果AC。A.文法的某一個(gè)句子有兩個(gè)以上的最右或最左推導(dǎo)。B.文法的預(yù)測(cè)分析表中有多重入口。C.文法的某一個(gè)句子有兩棵以上不同的語(yǔ)法樹。D.文法的某個(gè)LR(0)項(xiàng)目集中有沖突項(xiàng)目。6．已知文法GB：B→B+T|TT→T*F|FF→(B)|b那么，該文法終結(jié)符集合VT=AB，GE稱2型文法或上下文無(wú)關(guān)文法。A.VT={+,*,(,),b}B.VT={b,(,+,*,)}C.VT={B,T,F}D.VT={B,T,F,+,*,(,b,)}7．在動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法有BC。A.分時(shí)動(dòng)態(tài)存儲(chǔ)分配B.棧式動(dòng)態(tài)存儲(chǔ)分配C.堆式動(dòng)態(tài)存儲(chǔ)分配D.最佳動(dòng)態(tài)存儲(chǔ)分配8．設(shè)有一個(gè)LR(0)項(xiàng)目集I={A→β.dδ；A→b.Bδ；B→βd.；D→dB.}，I中存在沖突項(xiàng)目，它們是AB。A.“移進(jìn)-歸約”沖突B.“歸約-歸約”沖突C.“移進(jìn)-待約”沖突D.“移進(jìn)-接受”沖突9．在編譯程序采用的優(yōu)化方法中，BCD是在循環(huán)語(yǔ)句范圍內(nèi)進(jìn)行的。A.刪除多余運(yùn)算B.代碼外提C.刪除歸納變量D.強(qiáng)度消弱10．編譯程序生成的目標(biāo)代碼通常有3種形式，它們是ACD。A.能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼B.中間語(yǔ)言代碼C.匯編語(yǔ)言程序D.待裝配的機(jī)器語(yǔ)言代碼①編譯程序的工作過程一般劃分為五個(gè)基本階段：BD、語(yǔ)義分析和中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。A.出錯(cuò)處理B.詞法分析C.表格管理D.語(yǔ)法分析②已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，該文法終結(jié)符集合VT=AC，GE稱2型文法或上下文無(wú)關(guān)文法。A.{+,(,),*,b}B.{+,(,),*,E}C.{+,*,(,),b}D.{E,T,F}③已知文法GE：E→E+T|TT→T*F|FF→(E)|b那么，該文法的非終結(jié)符集VN=B，GE稱2型文法或上下文無(wú)關(guān)文法。A.{+,(,),*,b}B.{E,T,F}C.{+,*,(,),b}D.{E,T,F,*,+}④文法用于描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)，它由如下四個(gè)部分組成：ACD和文法開始符號(hào)。A.文法終結(jié)符集B.字母數(shù)字串C.文法非終結(jié)符集D.文法產(chǎn)生式集⑤一個(gè)文法被稱為是二義性的，如果D。A.文法的某一個(gè)句子有兩個(gè)以上的最右或最左推導(dǎo)。B.文法的預(yù)測(cè)分析表中有多重入口。C.文法的某個(gè)LR(0)項(xiàng)目集中有沖突項(xiàng)目。D.文法的某一個(gè)句子有兩棵以上不同的語(yǔ)法樹。⑥程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)一般可分為五種，它們是保留字、AD及運(yùn)算符和定界符。A.常數(shù)B.表達(dá)式C.注解D.標(biāo)識(shí)符⑦設(shè)有一個(gè)LR(0)項(xiàng)目集I={A→β.bδ，B→β.，D→δ.}，I中存在沖突項(xiàng)目，它們是AD。A.“移進(jìn)-歸約”沖突B.“移進(jìn)-接受”沖突C.“移進(jìn)-待約”沖突D.“歸約-歸約”沖突⑧一個(gè)文法的SLR(1)方法和與其相應(yīng)的LR(0)方法的狀態(tài)數(shù)A。A.相同B.不相同的C.前者大于后者D.后者大于前者四、計(jì)算題（共10分；畫出語(yǔ)法樹4分；其余按要求分別得：1分+1分+2分+2分）對(duì)于如下文法GB：B→B+D|DD→D*F|F給出句型D+D*d+d的最左素短語(yǔ)、句柄、F→(B)|d所有直接短語(yǔ)、短語(yǔ)。解：已知NFA如下圖所示。(8分=6分+2分)<1>確定化。(狀態(tài)轉(zhuǎn)換矩陣4分；狀態(tài)轉(zhuǎn)換圖2分)<2>寫出與其等價(jià)的右線性文法。解：<1>計(jì)算出DFA的狀態(tài)轉(zhuǎn)換矩陣4分；畫出相應(yīng)的狀態(tài)轉(zhuǎn)換圖2分<2>與其等價(jià)的右線性文法為：GA：A→dA|bB|bA→dA|bA|bB|BA代表結(jié)點(diǎn)1B→bB|dA|bB→bC|bB代表結(jié)點(diǎn)2按確定化后的DFA構(gòu)造的結(jié)果；按NFA構(gòu)造的結(jié)果對(duì)于文法GE：（共8分：語(yǔ)法樹2分；其余按要求分別得1分、1分、2分、2分）E→E+B|BB→B*F|F給出句型B+B*b+b的最左素短語(yǔ)、句柄、F→(E)|b直接短語(yǔ)和所有短語(yǔ)。解：五、1給出以下表達(dá)式的三地址指令（或四元式序列）：(8分)d+b*d+b/m*(m-b*d+2)解：四元式序列為(三地址指令略)（*,b,d,T1）（+,d,T1,T2）（/,b,m,T3）（*,b,d,T4）(-,m,T4,T5)(+,T5,2,T6)(*,T3,T6,T7)(+,T2,T7,T8)2①給出以下表達(dá)式的三地址指令（即四元式序列）：(8分=3分+3分+2分)d+b*d+d*(d+b*d)②寫出四種以上常用的代碼優(yōu)化技術(shù)？解：①四元式序列為：1（*,b,d,T1）2（+,d,T1,T2）3（*,b,d,T3）4（+,d,T3,T4）5（*,d,T4,T5）6（+,T2,T5,T6）上述中間代碼可以采用的優(yōu)化措施有：合并（或稱刪除）公共子表達(dá)式即合并公共四元式1和3合并4中T3改為T12和4合并5中T4改為T2刪除四元式3和41（*,b,d,T1）2（+,d,T1,T2）3刪除4刪除5（*,d,T2,T5）6（+,T2,T5,T6）②常用的代碼優(yōu)化技術(shù)有：循環(huán)上的優(yōu)化包括：代碼外提；強(qiáng)度削弱；刪除歸納變量等基本塊上的優(yōu)化包括：合并公共子表達(dá)式；合并常數(shù)等六、綜合題（每小題4分，共32分。若缺少必要的計(jì)算或分析步驟，扣適當(dāng)?shù)姆謹(jǐn)?shù)）已知文法GS：S→dDb提示：.ε=ε.=.且|ε|=0D→aD|ε①求每個(gè)非終結(jié)符的First集、Follow集。求每條規(guī)則的Select集，判定是LL(1)文法。②構(gòu)造GS的遞歸下降分析程序。③構(gòu)造GS的預(yù)測(cè)分析表。④給出字符串daabb的LL(1)分析過程。⑤構(gòu)造識(shí)別GS拓廣文法的所有規(guī)范句型活前綴的DFA。⑥構(gòu)造SLR(1)分析表。⑦GS是LR(0)文法嗎？GS是SLR(1)文法嗎？為什么？⑧給出字符串daab的SLR(1)分析過程。解：①每個(gè)非終結(jié)符的First集、Follow集:每條產(chǎn)生式的Select集，判斷該文法是否為L(zhǎng)L(1)文法。Select(S→dDb)=enbssioSelect(D→aD)={a}<1>Select(D→ε)=<2>因?yàn)?lt;1>式∩<2>式=Φ，因此，GS是LL(1)文法。②遞歸下降分析器：Read()函數(shù)讀一個(gè)單詞到全局變量SYM中ERROR()出錯(cuò)處理；SKIP空操作Main()函數(shù)；略S(){ifsym=’d’then{read();D();Ifsym=’b’thenread();}ElseError()}D(){ifsym=’a’then{read();D()}Elseifsym=’b’thenskip;ElseError();}③構(gòu)造GS的預(yù)測(cè)分析表如下：④分析棧輸入流動(dòng)作#Sdaabb#dDb#bDddaabb#匹配#bDaabb#aD#bDaaabb#匹配#bDabb#aD#bDaabb#匹配#bDbb#D→ε#bbb#匹配#b#出錯(cuò)⑤識(shí)別GS拓廣文法的所有規(guī)范句型活前綴的DFA構(gòu)造如下：說明：產(chǎn)生式編號(hào)可以不從1開始，但是與歸約符r的下標(biāo)必須一致；SLR(1)表中的行可以任意排列，但是必須與項(xiàng)目集編號(hào)一致。⑥SLR(1)分析表構(gòu)造如下：⑦顯然項(xiàng)目集I2、I4中有“移進(jìn)—?dú)w約”沖，GS不是LR(0)文法。因?yàn)镾LR(1)分析表中無(wú)多重入口，所以GS是SLR(1)文法。⑧字符串daab的SLR(1)分析過程如下：狀態(tài)棧符號(hào)棧輸入流動(dòng)作0#daab#S202#daab#S4024#daab#S40244#daab#r402446#daaDb#r30246#daDb#r3023#dDb#S50235#dDb#r201#S#OK已知文法GD：D→aD|dAb（共40分，每小題5分）A→dA|ε提示：.ε=ε.=.且|ε|=0①求每個(gè)非終結(jié)符的First集、Follow集。求每條規(guī)則的Select集，判定是LL(1)文法。②構(gòu)造GD的遞歸下降分析程序。③構(gòu)造GD的預(yù)測(cè)分析表。④給出字符串a(chǎn)ddb的LL(1)分析過程⑤構(gòu)造識(shí)別GD拓廣文法的所有規(guī)范句型活前綴的自動(dòng)機(jī)。⑥構(gòu)造SLR(1)分析表。⑦GD是LR(0)文法嗎？GD是SLR(1)文法嗎？GD是LL(1)文法嗎？為什么？⑧給出字符串a(chǎn)ddbb的SLR(1)分析過程。解：①每個(gè)非終結(jié)符的First集、Follow集:每條產(chǎn)生式的Select集，判斷該文法是否為L(zhǎng)L(1)文法。Select(D→dDb)=grkgkpm<1>Select(D→aD)={a}<2>Select(A→dA)=o72tfta<3>Select(A→ε)=<4>因?yàn)?<1>式∩<2>式=Φ;<3>式∩<4>式=Φ因此，GD是LL(1)文法。②遞歸下降分析程序構(gòu)造如下：(1分+2分+2分)Main()/*Read函數(shù)表示把輸入流首符讀入變量SYM中*/{Read();D();/*SYM存放輸入流首符的全局變量*/ifSYM=’#’then/*Write為輸出函數(shù)；Skip為空操作*/write(“分析成功!”)/*Error出錯(cuò)處理程序*/elsewrite(“失敗…”)}/*可以使用其它符合標(biāo)識(shí)符定義規(guī)則的名稱*/D(){ifSYM=’a’then{Read;D()}elseifSYM=’d’then{Read();A();ifSYM=’b’thenRead()ElseError();}ElseError();}A(){ifSYM=’d’then{Read();A();}ElseifSYM=’b’thenSkipElseError();}③構(gòu)造GD的預(yù)測(cè)分析表如下：④字符串a(chǎn)ddb的LL(1)分析過程分析棧輸入流動(dòng)作分析棧輸入流動(dòng)作#Daddb#替換D→aD#Daaddb#匹配[a,a]#Dddb#替換D→dA