《編譯原理》試卷答案2010中南大學(xué)

1、編譯原理試卷答案2010中南大學(xué)編譯原理試卷答案2010中南大學(xué) 編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對文中內(nèi)容進(jìn)行仔細(xì)校對，但是難免會有疏漏的地方，但是任然希望（編譯原理試卷答案2010中南大學(xué)）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來便利。同時(shí)也真誠的希望收到您的建議和反饋，這將是我們進(jìn)步的源泉，前進(jìn)的動(dòng)力。本文可編輯可修改，如果覺得對您有幫助請收藏以便隨時(shí)查閱，最后祝您生活愉快 業(yè)績進(jìn)步，以下為編譯原理試卷答案2010中南大學(xué)的全部內(nèi)容。中南大學(xué)考試試卷答案2009 - 2010 學(xué)年 二 學(xué)期 時(shí)間110分鐘 2010年

2、6月10 日 編譯原理 課程 64 學(xué)時(shí) 4 學(xué)分 考試形式：開卷 專業(yè)年級： 計(jì)算機(jī)07級 總分100分，占總評成績 70 一、選擇題(本題10分，每小題2分）c，c,b,b,a二、名詞解釋（本題20分，每小題4分）1遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。 2無環(huán)路有向圖(dag）如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為 無環(huán)路有向圖,簡稱dag。 3語法分析按文法的產(chǎn)生式識別輸入的符號串是否為一個(gè)句子的分析過程。 4短語令g是一個(gè)文法。s劃文法的開始符號，假定是文法g的一個(gè)句 型，如果有sa且ab，則稱是句型相對非終結(jié)符a的短語。 5算符文法當(dāng)一個(gè)文法的所有產(chǎn)生式的右部

3、均不出現(xiàn)兩個(gè)非終結(jié)符號相鄰的情況時(shí),該就被稱為算符文法.三、簡答題（本題45分，每小題15分)1、寫出表達(dá)式（a+b)/（a-b)-a（a+b*c）的三元式序列及四元序列。解：三元式：.（+,a,b）.(-,a，b).（/,，)。（,b,c).(+，a，）.(-，,)四元式：。（+，a，b，t1)。(-，a,b，t2).（/,t1，t2，t3).(，b，c，t4）。(+,a，t4,t5）。(-,t3，t5，t6）2、將文法gs 改寫為等價(jià)的gs，使gs不含左遞歸和左公共因子.gs： sbsae ba aab | d解:文法gs 改寫為等價(jià)的不含左遞歸和左公共因子的gs為：sbbbsae aad

4、 aa ba 3、判斷下面文法是否為ll(1)文法，若是,請構(gòu)造相應(yīng)的ll(1)分析表.sahhamd | dmab | aam | e解:首先計(jì)算文法的 first集和follow集如下表:非終結(jié)符 first集 follow集 s a。.。.。. # 。. h a ，d。.。 .。. m a ，e , d ,b a a ，e。.。.。 b.。.。 由于select（hamd)select（hd）=ad = select（mab）select(m）=a ,ed ，b = select（aam）select(ae）= a e = 所以該文法是ll(1）文法,ll(1）分析表如下表。 ll（1）

5、分析表 a d b e # s ah。 h amd d. m ab. ab a am。 e. 4、 給出與正規(guī)式r（(ab)*b)(a|(ba)）a 等價(jià)的nfa。解：與正規(guī)式r(（ab)|b）(a(ba）)a 等價(jià)的nfa如下圖5、文法ge為: ee+t|t ttff f（e）|i試給出句型（e+f）i的短語，簡單（直接)短語，句柄和最左素短語。解：短語有： （e+f)*i ，（e+f) ,e+f ，f ，i簡單（直接)短語有： f ，i句柄是： f最左素短語是： e+f四、綜合題（本題25分,每小題5分）1、將下圖的nfa確定化為dfa.解：用子集法確定化如下表 用子集法對所給圖的確定化i

6、 ia ib 狀態(tài) x，1,21,2.1，2,31，2，y 1,2。.1，2.1，2,y1，2.。 1，2，31,2,31，2，31，2,3 x123 確定化后如下圖:2、文法gm及其lr分析表如下,請給出對串dbba的分析過程。gm: 1） m vba 2） v d3） v 4) a a5) a aba 6) a action goto b d a m a v 0 r3 s3 1 2 1 acc 2 s4 3 r2 4 r6 s5 r6 6 5 r4 r4 6 s7 r1 7 s8 8 r5 r5 解：對串dbba的分析過程如下表 對輸入串dbba#的分析過程步驟 狀態(tài)棧 文法符號棧 剩余輸

7、入符號動(dòng)作 12345678900302024024602467024678024601 #dv#vb#vbavbab#vbabavbam dbbabba#bbababa#a#移進(jìn)用v d歸約移進(jìn)用a 歸約移進(jìn)移進(jìn)用a aba 歸約用m vba 歸約接受 3、某語言的拓廣文法g為：（0） st（1） t abd(2) b tb證明g不是lr（0)文法而是slr（1)文法,請給出slr（1）分析表。解：在項(xiàng)目集i0中：有移進(jìn)項(xiàng)目t abd和歸約項(xiàng)目t 存在移進(jìn)-歸約沖突，所以g不是lr(0)文法。 若產(chǎn)生式排序?yàn)椋海?) st(1) t abd（2） t (3) b tb（4） b g的lr(0）項(xiàng)目集族及識別活前綴的dfa如下圖所示：識別g活前綴的dfa：由產(chǎn)生式知:follow（t）=#，bfollow（b)= d在i0中：follow（t) a=# ，b a=在i2中：follow(b) a= d a=follow(t) a= ,b a=follow(b) follow(t） = d ，b=所以在i0，i2,中的移進(jìn)-歸約和歸約-歸約沖突可以由follow集解決，所以g是s