編譯原理(A卷)答案

1、湖北第二師范學(xué)院20142015學(xué)年度第二學(xué)期編譯原理課程考試答案(A卷)院 系： 計算機(jī)學(xué)院 專業(yè)班級： 學(xué)生姓名： 學(xué) 號： 考試方式 ： 閉卷 題號一二三四五總分簽名分?jǐn)?shù)得分評卷人一、填空題（每空1分，共10分）1詞法分析程序是逐個識別（字符 ），形成單詞級別的（字符 ）串，詞法分析程序輸出的數(shù)據(jù)是（2 ）個，它們分別是（種別編碼 ）和（自身值 ）。 2語法分析程序是逐個識別（單詞 ），形成語句級別的（單詞 ）串。3一遍掃描的編譯方法，是以語法分析程序為主，調(diào)用（詞法分析 ）程序、語義分析程序，再由語義程序調(diào)用中間代碼生成、中間代碼優(yōu)化等。4程序設(shè)計語言的發(fā)展帶來了日漸多變的運(yùn)行時存儲管

2、理方案，主要分為兩大類，即（靜態(tài)存儲分配 ）方案和（動態(tài)存儲分配 ）方案。得分評卷人二、綜合題（共90分）1（5分）將下面文法改寫成3型文法： G=（S,A,B,a,b,c,d,e,P,S）其中：P=SabcA|edB,AbeB,Bd答案：改寫后的3型文法是（5分）G=（S,A,B,C,D,E,F,a,b,c,d,e,P,S）其中：P=SaC|eF, CbD,DcA,AbE,EeB,FdB,Bd2（5分）給出下面表達(dá)式的四元式形式： a*b+(c-d)/e答案：四元式形式（5分）（*，a，b，t1）（-，c，d，t2）（/，t2，e，t3）（+，t1，t3，t4）3（30分）給定文法 GE ：

3、 E E+T | E-T | T T T*F | T/F | FF (E) | i 該文法是 LL(1) 文法嗎？為什么？不是的能否改造為LL（1）文法，如果能夠改造，給出改造后的文法，并給出改造后文法是LL（1）文法的證明過程。無論改造前還是改造后的文法，如果是LL（1）文法，則給出（i+i）*i的分析過程（要求給出詳細(xì)過程，并給出LL（1）的分析表）答案：（1）該文法不是LL（1）文法，因為文法的產(chǎn)生式含有左遞歸 （2分）（2）該文法可改造為LL（1）文法，即消除左遞歸，改造后的文法是 （3分）E TEE +TE | -TE | T FTT *FT | /FT |F (E) | i 證明改

4、造后的文法是LL（1）文法的過程A. 求可達(dá)的非終結(jié)符 （1分）可達(dá)的是E,TB. 求每個非終結(jié)符的First集合 （3分）First(E)= (,iFirst(E)=+,-First(T)= (,iFirst(T)=*,/First(F)= (,iC. 求每個產(chǎn)生式右部字符串的First集合 （3分）First(TE)= (,iFirst(+TE)=+First(-TE)=-First(FT)= (,iFirst(*FT)=*First(/FT)=/First(E)= ( First(i)= i First()= D. 求每個非終結(jié)符的Follow集合 （3分）Follow(E)=$,)Fo

5、llow(E)= Follow(E)=$,)Follow(T)=First(E) Follow(E)=$,+,-,)Follow(T)= Follow(T)=$,+,-,)Follow(F)= First(T) Follow(T)=$,+,-, *,/,)E. 求每個非終結(jié)符的Select集合 （5分）Select(E TE)=First(TE)= (,i Select(E +TE)=First(+TE)= + Select(E -TE)=First(-TE)= - Select(E )=First()- Follow(E)= $,) Select(T FT)=First(FT)= (,i S

6、elect(T *FT)=First(*FT)= * Select(T /FT)=First(/FT)= / Select(T )=First()- Follow(T)= $,+,-,) Select(F (E)=First(E)= ( Select(F i)=First(TE)= i F. 求有多個產(chǎn)生式的非終結(jié)符Select集合的交集 （2分）顯然有Select(E +TE)Select(E -TE) Select(E )=Select(T *FT) Select(T /FT) Select(T )= Select(F (E)= Select(F i)= 所以改造后的文法是LL（1）文法（

7、3）、根據(jù)E給出預(yù)測分析表 （4分）非終結(jié)符終結(jié)符+-*/()i$ETETEE+TE-TET FTFTT *FT *FTF(E)i符號串（i+i）*i的分析過程 （4分）步驟符號棧Si輸入符號串產(chǎn)生式1$E(i+i)*i$ETE2$ET(i+i)*i$T FT3$ETF(i+i)*i$F（E）4$ET）E（(i+i)*i$ET）Ei+i)*i$ETE$ET）ETi+i)*i$T FT$ET）ETFi+i)*i$Fi$ET）ETii+i)*i$ET）ET+i)*i$T $ET）E+i)*i$E +TE$ET）ET+i)*i$ET）ETi)*i$TFT$ET）ETFi)*i$Fi$ET）ETii)

8、*i$ET）ET)*i$T $ET）E)*i$E $ET）)*i$ET*i$T *FT$ETF*i$ETFi$Fi$ET$T $EE $4（10分）對下面的NFA進(jìn)行確定化xxxx,yyyxyq0q1q2q3q4答題：第1步：確定化過程（5分）新狀態(tài)IxIy0q0 0q1 1q2 21q1 1q2,q3 32q2 2q1,q3 43q2,q3 3q3,q4 5q1,q3 44q1,q3 4q2,q3,q4 6q3 75q3,q4 5q3,q4 5q3 76q2,q3,q4 6q3,q4 5q1,q3 47q3 7q3,q4 5q3 7第2步：確定化的DFAxyyyxxyxyq0q1q2q3q5

9、q4q7xyxq6yx5（15分）給定文法 GE ： E E+T | E-T | T T T*F | T/F | FF (E) | i 該文法是算符優(yōu)先文法嗎？是，則構(gòu)造該文法的算符優(yōu)先關(guān)系矩陣，并給出（i+i）*i的分析過程（要求給出詳細(xì)過程）答案：（1）該文法是算符優(yōu)先文法 （1分）（2）構(gòu)造該文法的算符優(yōu)先矩陣A. 求各非終結(jié)符的FirstVT集合 （3分）FirstVT（E）=+，-，*，/，（，iFirstVT（T）=*，/，（，iFirstVT（F）=（，iB. 求各非終結(jié)符的LasttVT集合 （3分）LastVT(E)= +，-，*，/，)，i LastVT(T)= *，/，)

10、，i LastVT(F)= )，i C. 構(gòu)造優(yōu)先關(guān)系表 （4分）+-*/()i$+-*/(=i$=(3)分析（i+i）*過程 （4分）步驟符號棧S關(guān)系輸入符號串最左素短語$(i+i)*i$(+i)*i$i$(V+i)*i$(V+)*i$i$(V+V)*i$V+V$(V=)*i$(V)*i$(V)$V*i$V*i$V*i$V*V$V=$6（25分）給定文法 GE ： E E+T | T T T*F | FF (E) | i 該文法是LR（0）文法嗎？是，則構(gòu)造該文法的LR（0）分析表，并給出（i+i）*i的分析過程，不是的，是SLR（1）文法嗎，是，則構(gòu)造該文法的SLR（1）分析表，并給出（i

11、+i）*i的分析過程。（要求給出詳細(xì)過程）答案：（1）拓廣文法 （2分）0、E E1、 E E+T 2、 E T 3、T T*F 4、T F 5、F (E) 6、F i （2）構(gòu)造LR（0）項目集規(guī)范簇 （10分）（3）在下圖的DFA中，I1、I2、I9均發(fā)生了規(guī)約移進(jìn)沖突，所以該文法不是LR（0）文法。 （2分）（4）在I1規(guī)范項目集中規(guī)約項目E E. 的Follow（E）=$，而移進(jìn)項目的移進(jìn)符號集=+，F(xiàn)ollow（E）+= 在I2規(guī)范項目集中規(guī)約項目E T. 的Follow（E）=$，+，），而移進(jìn)項目的移進(jìn)符號集=*，F(xiàn)ollow（E）*= 在I9規(guī)范項目集中規(guī)約項目E E+T. 的

12、Follow（E）=$，+，），而移進(jìn)項目的移進(jìn)符號集=*，F(xiàn)ollow（E）*= 所以，在3個發(fā)生沖突的項目集中可解決沖突，因此該文法是SLR（1）文法 （5分）iI5(I4FI3）I9EE+T.TT.*FF(iI0E .EE.E+TE.TT.T*FT.FF.(E)F.iI1E E.EE.+TEI2ET.TT.*FTI3T F.FI5Fi.iI4F(.E)E.E+TE.TT.T*FT.FF.(E)F.i(I6EE+.TT.T*FT.FF.(E)F.i+I7TT*.FF.(E)F.i*+FTI8F(E.)EE.+TE+I10TT*F.*(iI11F（E）.（5）根據(jù)上面的DFA建立SLR（1）的分析表 （4分）狀態(tài)ActionGotoi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r4r4r44S5S48235r6r6r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r3r3r311r5r5r5r5r5r5（6）分析（i+i）*i的過程 （4分）棧內(nèi)容輸入符號串動作0（i+i）*i$移進(jìn)0(4i+i）*i$移進(jìn)0(4i5+i）*i$r6規(guī)約0(4F3+i）*i