編譯原理期末考試試卷及答案

期末考試試卷〔A〕卷一、填空題〔每題2分，共20分〕1、字母表∑，用∑*表示∑上所有有窮長的串集合，∑*稱為∑的①。2、設(shè)z=abc，那么z的固有頭是①。3、如何由語言根本符號組成程序中各個語法成分〔包括程序〕的一組規(guī)那么叫①。4、設(shè)?＝{a,b}，?上的正規(guī)式(a|b)(a|b)相應(yīng)的正規(guī)集為①5、NFA的映象f是從"狀態(tài)×字"映射到"狀態(tài)子集"，f為①值函數(shù)。6、LR分析是按標(biāo)準(zhǔn)句型的①為可歸約串。7、結(jié)點(diǎn)的①屬性值由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)的屬性值計(jì)算。8、如果分析樹中一結(jié)點(diǎn)的屬性b依賴于屬性c，那么這個結(jié)點(diǎn)的屬性b的語義規(guī)那么的計(jì)算必須在定義屬性c的語義規(guī)那么的計(jì)算①。9、對于棧式符號表，引入一個顯示嵌套層次關(guān)系表-①表，該表總是指向當(dāng)前正在處理的最內(nèi)層的過程的子符號表在棧符號表中的起始位置。10、任一有向邊序列n1→n2,n2→n3,…,nk-1→nk為從結(jié)點(diǎn)n1到結(jié)點(diǎn)nk的一條通路。如果n1=nk，那么稱該通路為①。二、單項(xiàng)選擇〔每題2分，共14分〕1、喬姆斯基把文法分成4種類型，即0型、1型、2型和3型。其中3型文法也稱為〔〕。A．上下無關(guān)文法B.正規(guī)文法2、生成非0開頭的正偶數(shù)集的文法是〔〕。A．Z::=ABCB.Z::=ABCC::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|…|9A::=1|2|3|…|9C.Z::=ABC|2|4|6|8D.Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|…|9A::=1|2|3|…|93、簡單優(yōu)先分析法從左到右掃描輸入串,當(dāng)棧頂出現(xiàn)〔〕時進(jìn)歸約。4、同心集合并有可能產(chǎn)生新的〔〕沖突。A.歸約B.移進(jìn)／移進(jìn)C.移進(jìn)／歸約D.歸約／歸約5、在編譯中，動態(tài)存儲分配的含義是〔〕。A．在運(yùn)行階段對源程序中的量進(jìn)展存儲分配B.在編譯階段對源程序中的量進(jìn)展存儲分配C.在說明階段對源程序中的量進(jìn)展存儲分配D.以上都不正確6、活動記錄中的連接數(shù)據(jù)不包含〔〕。A.老SPB.返回地址C.全局DISPLAY地址D形式單元7、有一語法制導(dǎo)翻譯如下：S→bAb{printer(“1”A→(B{printer(“2”A→a{printer(“3”B→Aa){printer(“4”假設(shè)輸入序列為b(((aa)a)a)b，且采用自下而上的分析法，那么輸出序列為()。A．32224441B．34242421C三、寫出條件語句IFa>0THENx:=x+1ELSEx:=4*(x-1)的四元式序列〔6分〕四、設(shè)有根本塊〔8分〕B1：B:=3D:=A+CB1：B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L(1)畫出DAG圖；(2)(1)畫出DAG圖；(2)假設(shè)只有L在根本塊后被引用，請寫出優(yōu)化后的四元序列。五、將以下圖DFA最小化，并寫出最小化后DFA的正規(guī)式?！?0分〕cbba631cbba631dbdbadbca5adbca5bb742bb742六、對下面的文法進(jìn)展改寫，并判斷改寫后是否是LL〔1〕文法?！?5分〕SA?SBB?ab七、文法:S?S；G|GG?G〔T〕|HH?a|(S)T?T+S|S求句型#a;(T+S);H;(S)#短語、句柄、素短語、最左素短語〔12分〕八、【注意】計(jì)算機(jī)061/062班和計(jì)教061/062請做第1、2題，計(jì)算機(jī)063〔海外班〕請做第3題，做錯題得0分?！?5分〕【計(jì)算機(jī)061/062班和計(jì)教061/062班做】1、給出文法G[S]的LR(1)工程集標(biāo)準(zhǔn)族中I0工程集的全體工程?！?分〕G[S]為：(1)E?E+T(2)E?T(3)T?T*F(4)T?F(5)F?(E)(6)F?a2、文法G[M]及其LR分析表如下，請給出對串dbba#的分析過程?！?0分〕G[M]:1)M→VbA2)V→d3)V→ε4)A→a5)A→Aba6)A→εACTIONGOTObda#MAV0r3S3

1

21

acc

2S4

3r2

4r6

S5r6

6

5r4

r4

6S7

r1

7

S8

8r5

r5

【計(jì)算機(jī)063海外班做】3、判斷以下各題所示是否為LR類文法，假設(shè)是請說明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一種，并構(gòu)造相應(yīng)分析表。〔15分〕S?aAd?eBd?aBr?eArA?aB?a答案：一、填空題〔每空2分，共20分〕1、閉包2、ε，a，ab3、語法4、｛aa，bb,ab,ba}5、多6、句柄7、繼承8、之后9、DISPLAY10、環(huán)路二、單項(xiàng)選擇〔每題2分，共14分〕題號1234567答案BDCDADB三、寫出條件語句IFa>0THENx:=x+1ELSEx:=4*(x-1)的四元式序列〔6分〕解：①(j>,a,0,③)評分標(biāo)準(zhǔn)：標(biāo)號對給1分，②(j,,,⑥)四元式格式對給1分，③(+,x,1,T1)每2條四元式序列對給1分。④(:=,T1,,T2)⑤(j,,,⑨)⑥(-,x,1,T3)⑦(*,4,T3,T4)⑧(:=,T4,,x)⑨四、設(shè)有根本塊〔8分〕(1)畫出DAG圖；(2)假設(shè)只有L在根本塊后被引用，請寫出優(yōu)化后的四元序列。評分標(biāo)準(zhǔn)：DAG圖正確給4分，代碼每條1分。解：〔1〕對于B1其DAG圖：L,ML,Mn1n9n3n4n2n7n6n5n8153KBAC+G*+F,JD,HE,I+*假設(shè)只有L活潑，那么代碼為D:=A+C

E:=A*C

F:=D+E

L:=F+15五、將以下圖DFA最小化，并寫出最小化后DFA的正規(guī)式。〔10分〕解：P0=({6,7},{1,2,3,4,5})P0=({6,7},{1,2}，{3,4,5})輸入b進(jìn)入不同狀態(tài)。P0=({6,7},{1,2}，{3,4},{5})3，4對d有定義，5沒有定義最小化DFA如下：bcbba631bcbba631dda5a5正規(guī)式為：b*a(c|da)*bb*評分標(biāo)準(zhǔn)：劃分狀態(tài)集過程給3分，圖對得5分，圖局部對根據(jù)對的多少給2-4分，正規(guī)上式對給2分。六、對下面的文法進(jìn)展改寫，并判斷改寫后是否是LL〔1〕文法?！?5分〕SA?SBB?ab【解法1】first(S)=first(A)=first(B)={a}follow(S)={#,a}follow(A)={a}follow(B)={a}select(S?AS)=first(AS)=select(S?b)=first(b)=select(S?AS)∩select(S?b)=≠φ所以該文法不是LL〔1〕文法改寫為：S?Aa|bS?SBa|bA?SBA?SBB?abB?ab消除左遞歸：S?bS’化簡得：S?bS’S?BaS’|εS’?BaS’|εA?SB(多余)B?abB?abfirst(S)=first(S’)={a,ε}first(B)={a}follow(S)={#}follow(S’)={#}follow(B)={a}select(S?bS’)=first(bS’)=select(S’?BaS’)=first(BaS’)={a}select(S’?ε)=first(ε)Ufollow(S’)={#,ε}select(S’?BaS’)∩select(S’?ε)=φ所以改寫后是LL(1)文法。評分標(biāo)準(zhǔn)：改寫前判斷LL〔1〕全對4分，改寫正確4分，改寫后判斷LL〔1〕正確得6分，最后結(jié)論1分?！窘夥?】first(S)=first(A)=first(B)={a}follow(S)={#,a}follow(A)={a}follow(B)={a}select(S?AS)=first(AS)=select(S?b)=first(b)=select(S?AS)∩select(S?b)=≠φ所以該文法不是LL〔1〕文法用S的產(chǎn)生式右部代替A的產(chǎn)生式右部的S得：S→Aa|b

A→AaB|bBB→ab消除左遞歸后文法變?yōu)椋?)S→Aa

1)S→b2)A→bBN3)N→aBN4)N→ε5)B→ab非終結(jié)符

FIRST集

FOLLOW集S

{#}A



{a}B

{a}

{a}N

{a,ε}

{a}SELECT(S→Aa)∩SELECT(S→b)=∩=≠φSELECT(N→aBN)∩SELECT(N→ε)={a}∩{a}={a}≠φ所以文法不是LL(1)的。評分標(biāo)準(zhǔn)：改寫前判斷LL〔1〕全對4分，改寫正確4分，改寫后判斷LL〔1〕正確得6分，最后結(jié)論1分。七、文法:S?S；G|GG?G〔T〕|HH?a|(S)T?T+S|S求句型#a;(T+S);H;(S)#短語、句柄、素短語、最左素短語〔12分〕解：語法圖見以下圖短語有：a相對非終結(jié)符H、G短語T+S相對非終結(jié)符T短語H相對非終結(jié)符G短語(S)相對非終結(jié)符H、G短語a(T+S)相對非終結(jié)符G短語a(T+S);H相對非終結(jié)符S短語a(T+S);H;(S)相對非終結(jié)符S短語句柄是a素短語a，T+S，〔S〕最左素短語aSSS；GS；GHGH〔S〕G〔T〕HT+Sa評分標(biāo)準(zhǔn)：語法圖正確4分，短語正確5分，句柄正確1分，素短語正確1分，最左素短語正確1分。八、1、給出文法G[S]的LR(1)工程集標(biāo)準(zhǔn)族中I0工程集的全體工程?！?分〕G[S]為：(1)E?E+T(2)E?T(3)T?T*F(4)T?F(5)F?(E)(6)F?a解：I0I0：S’·?E，#E·?E+T，#,+E·?T，#,+T·?T*F，#,+,*T·?F，#,+,*F·?(E)，#,+,*F·?a，#,+,*評分標(biāo)準(zhǔn)：前4條工程，每條0.5分，后面3條下面。每條1分2、文法G[M]及其LR分析表如下，請給出對串dbba#的分析過程?！?0分〕G[M]:1)M→VbA2)V→d3)V→ε4)A→a5)A→Aba6)A→ε解：對串dbba#的分析過程如下表對輸入串dbba#的分析過程步驟狀態(tài)棧文法符號棧剩余輸入符號動作1

2

3

4

5

6

7

8

90

03

02

024

0246

02467

024678

0246

01#

#d

#V

#Vb

#VbA

#VbAb

#VbAba

#VbA

#Mdbba#

bba#

bba#

ba#

ba#

a#

#

#

#移進(jìn)

用V→d歸約

移進(jìn)

用A→ε歸約

移進(jìn)

移進(jìn)

用A→Aba歸約

用M→VbA歸約

承受評分標(biāo)準(zhǔn)：每條1分，格式1分。3、判斷以下各題所示是否為LR類文法，假設(shè)是請說明是LR(0)，SLR(1)，LALR(1)或LR(1)的哪一種，并構(gòu)造相應(yīng)分析表?！?5分〕S?aAd?eBd?aBr?eArA?aB?a解：LR(0)工程集標(biāo)準(zhǔn)族如圖：I0：I0：S’?·SS?·aAdS?·eBdS?·aBrS?·eArI2：S?a·AdS?a·BrA?·a