編譯原理試卷

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