編譯原理(A卷)答案

1、編譯原理a卷答案 第3頁(yè)，共9頁(yè)得分評(píng)卷人1.詞法分析程序是逐個(gè)識(shí)別（字符）,形成單詞級(jí)別的（字符）串，詞法分析程序輸出湖北第二師范學(xué)院2014 2015學(xué)年度第二學(xué)期編譯原理課程考試答案（a卷）院 系：計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)班級(jí)： 學(xué)生姓名： 學(xué) 號(hào)： 考試方式：閉卷題號(hào)一一二四五總分簽名分?jǐn)?shù)、填空題（每空i分，共io分）的數(shù)據(jù)是（2）個(gè)，它們分別是（種別編碼）和（自身值）。2 .語(yǔ)法分析程序是逐個(gè)識(shí)別（單詞），形成語(yǔ)句級(jí)別的（單詞 ）串。3 . 一遍掃描的編譯方法，是以語(yǔ)法分析程序?yàn)橹鳎{(diào)用（詞法分析）程序、語(yǔ)義分析程序，再由語(yǔ)義程序調(diào)用中間代碼生成、中間代碼優(yōu)化等。4 .程序設(shè)計(jì)語(yǔ)言的發(fā)展帶來(lái)

2、了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類(lèi)，即（靜態(tài)存儲(chǔ)分配 ）方案和（動(dòng)態(tài)存儲(chǔ)分配）方案。得分評(píng)卷人二、綜合題（共90分)1. (5分)將下面文法改寫(xiě)成3型文法：g=(s,a,b ,a,b,c,d,e,p,s)其中：p=sfabca|edb,a f beb,bfd答案：改寫(xiě)后的3型文法是(5分)g=(s,abc,d,e,f ,a,b,c,d,e,p,s)其中：p=sfac|ef, c -bd,d-ca,a - be,e - eb,f - db,bfd2. (5分)給出下面表達(dá)式的四元式形式：a*b+(c-d)/e答案：四元式形式(5分)(*, a, b, t1 )(-,c, d, t2)

3、(/, t2 , e, t3)(+, t1 , t3, t4)3 ( 30 分)給定文法 ge ：e f e+t | e-t | tt f t*f | t/f | ff - (e) i i該文法是 ll(1) 文法嗎？為什么？不是的能否改造為 ll ( 1)文法，如果能夠改造，給出改造后的文法，并給出改造后文法是ll( 1 )文法的證明過(guò)程。無(wú)論改造前還是改造后的文法，如果是 ll( 1 )文法，則給出( i+i ) *i 的分析過(guò)程(要求給出詳細(xì)過(guò)程，并給出 ll ( 1)的分析表)答案： ( 1)該文法不是ll( 1)文法，因?yàn)槲姆ǖ漠a(chǎn)生式含有左遞歸(2 分)( 2 )該文法可改造為 ll

4、 ( 1 )文法，即消除左遞歸，改造后的文法是( 3 分)e f te ef +te| -te|t f ft tf *ft |/ft|f - (e) i i證明改造后的文法是ll ( 1)文法的過(guò)程a.求可達(dá)的非終結(jié)符(1分)可達(dá)的是 e ,t b. 求每個(gè)非終結(jié)符的 first 集合 ( 3 分)first(e)= (,i first(e )=+,- first(t)= (,i first(t )=*,/ first(f)= (,ic. 求每個(gè)產(chǎn)生式右部字符串的 first 集合( 3 分)first(te )= (,ifirst(+te )=+ first(-te )=- first(ft

5、 )= (,ifirst(*ft )=* first(/ft )=/ first(e)= ( first(i)= i first( e )= d. 求每個(gè)非終結(jié)符的 follow 集合( 3 分)follow(e)=$,)follow(e )= follow(e)=$,)follow(t尸first(e ) u follow(e尸$,+,-,)follow(t )= follow(t)=$,+,-,)follow(f)= first(t ) u follow(t尸$,+,-, *,/,)e. 求每個(gè)非終結(jié)符的 select 集合( 5 分)select(e f te )=first(te )=

6、 (,i select(e f +te尸first(+te )= + select(e - te 尸first(-te )= - select(e一 )=first( )- u follow(e)=$,)select(t 一 ft )=first(ft )= (,i select(t一*ft )=first(*ft )= * select(t一/ft )=first(/ft )= / select(t一e )=first( )- u follow(t)=$,+,-,) select(f 一 (e)=first(e)= ( select(f 一 i)=first(te )= i f.求有多個(gè)產(chǎn)生

7、式的非終結(jié)符select集合的交集(2分)顯然有select(e 一 +te ) n select(e - -te ) n select(e 一 e )= select(t 一 *ft ) n select(t 一 /ft ) n select(t 一 e )= select(f 一 (e)= n select(f i)=所以改造后的文法是ll (1)文法（3）、根據(jù)e給出預(yù)測(cè)分析表（4分）非終 結(jié)符終結(jié)符+-*/()i$e一 te一 tee，f+te-tef f t一 ft一 ftt，一 *ft 一 *ft f一(e)一 i符號(hào)串（i+i ） *i的分析過(guò)程（4分）步驟符號(hào)棧si輸入符號(hào)串產(chǎn)

8、生式1$e(i+i)*i$e - te2$e t(i+i)*i$t - ft3$e t f(i+i)*i$f一（ e）4$e t ) e (i+i)*i$e t ) ei+i)*i$e - te$e t ) e ti+i)*i$t - ft$e t ) e t fi+i)*i$ffi$e t ) e t ii+i)*i$e t ) e t+i)*i$t一 e$e t ) e+i)*i$e 一 +te$e t ) e t+i)*i$e t ) e ti)*i$t-ft$e t ) e t fi)*i$ffi$e t ) e t ii)*i$e t ) e t)*i$t一 e$e t ) e)*i

9、$e一 e$e t)*i$e t*i$t一 *ft $e t f*i$e t fi$ffi$e t$t一 e$ee 一 e$4. （10分）對(duì)下面的 nfa進(jìn)行確定化答題：第1步：確定化過(guò)程（5分）新?tīng)顟B(tài)ixiy0q00q11q221q11q2,q332q22q1,q3 43q2,q33q3,q45q1,q3 414q1,q3 4q2,q3,q4 6q375q3,q45q3,q45q376q2,q3,q4 6q3,q45q1,q3 47q37q3,q45q37第2步：確定化的 dfa5. （15分）給定文法gee e+t | e-t | tt 一 t*f | t/f | ff 一 （e） |

10、ii+i ) *i的分析該文法是算符優(yōu)先文法嗎？是，則構(gòu)造該文法的算符優(yōu)先關(guān)系矩陣，并給出（ 過(guò)程（要求給出詳細(xì)過(guò)程）答案：（1）該文法是算符優(yōu)先文法（1分）（2）構(gòu)造該文法的算符優(yōu)先矩陣a.求各非終結(jié)符的firstvt集合（3分）firstvt （e） =+,-,*,/,（一firstvt （t） =*,/,（, i firstvt （f） = （, i (3分)b.求各非終結(jié)符的lasttvt集合 lastvt(e)= + ,-,*,/,), i lastvt(t)= *, /, ) , i lastvt(f)= ), i c.構(gòu)造優(yōu)先關(guān)系表（4分）+-*/()i$+-*/(=i$=分析（

11、i+i ） *過(guò)程（4分）步驟符號(hào)棧s關(guān)系輸入符號(hào)串最左素短語(yǔ)$(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編譯原理a卷答案 第5頁(yè)，共9頁(yè)e f e+t | tt f t*f | ff - （e） i i該文法是 lr（ 0 ）文法嗎？是，則構(gòu)造該文法的 lr（ 0 ）分析表，并給出（ i+i ） *i 的分析過(guò)程，不是的，是slr（ 1）文法嗎，是，則構(gòu)造該文法的 slr（ 1）分析表，并給出（ i+i ） *i 的分析過(guò)程。 （要求給出詳細(xì)過(guò)

12、程）答案： （ 1）拓廣文法（ 2 分）0、e f e1、e . e+t2、e f t3、t . t*f4、t f f5、f f （e）6、f f i（2）構(gòu)造 lr（ 0）項(xiàng)目集規(guī)范簇（ 10分）（3）在下圖的dfa中，i1、12、i9均發(fā)生了規(guī)約一一移進(jìn)沖突，所以該文法不是 lr （ 0）文 法。 （ 2 分）（4）在i1規(guī)范項(xiàng)目集中規(guī)約項(xiàng)目e -e.的follow （e ） = $,而移進(jìn)項(xiàng)目的移進(jìn)符號(hào)集=+, follow （e） c +=在i2規(guī)范項(xiàng)目集中規(guī)約項(xiàng)目e ft.的follow （e） = $, +,）,而移進(jìn)項(xiàng)目的移進(jìn)符號(hào)集=*, follow （e） n *=在i9規(guī)范

13、項(xiàng)目集中規(guī)約項(xiàng)目e fe+t.的follow （e） =$, +,）,而移進(jìn)項(xiàng)目的移進(jìn)符號(hào)集= *, follow （e） a *=所以， 在 3 個(gè)發(fā)生沖突的項(xiàng)目集中可解決沖突， 因此該文法是slr（ 1 ） 文法（ 5 分）a 卷答案 第 # 頁(yè)，共 9 頁(yè)i6ei0i1i9+ef e+.te e+t.e f.et 一 .t*fe-.e+td e.+tt-t.*fftf.fef.ti4ff(e)t 一 .t*f(*ff.itf.fi5ti2if-.(e)e-t.ff.it- t.*ftff.ii5i3t -f.e -e.i3i7tf t*.ff-.(e)i4f-(.e).e+tt一 .t*

14、ft一 .ff-.(e)ff.ii8f 一(e.)ef e.+ti10t-t*f.i11f- ( e).編譯原理a卷答案 第7頁(yè)，共9頁(yè)(4分)(5)根據(jù)上面的 dfa建立slr (1)的分析表狀態(tài)actiongotoi+*()$etf0s5s41231s6acc2r2s7r2r23r4r4r4r4r4r44s5s48235r6r6r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r3r3r311r5r5r5r5r5r5(6)分析(i+i ) *i的過(guò)程(4分)棧內(nèi)容輸入符號(hào)串動(dòng)作0(i+i ) *i$移進(jìn)0(4i+i ) *i$移進(jìn)0(4i5+i ) *i$r