《編譯原理》試卷答案2010中南大學

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

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

3、均不出現兩個非終結符號相鄰的情況時,該就被稱為算符文法.三、簡答題（本題45分，每小題15分)1、寫出表達式（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 改寫為等價的gs，使gs不含左遞歸和左公共因子.gs： sbsae ba aab | d解:文法gs 改寫為等價的不含左遞歸和左公共因子的gs為：sbbbsae aad

4、 aa ba 3、判斷下面文法是否為ll(1)文法，若是,請構造相應的ll(1)分析表.sahhamd | dmab | aam | e解:首先計算文法的 first集和follow集如下表:非終結符 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 等價的nfa。解：與正規(guī)式r(（ab)|b）(a(ba）)a 等價的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、入符號動作 12345678900302024024602467024678024601 #dv#vb#vbavbab#vbabavbam dbbabba#bbababa#a#移進用v d歸約移進用a 歸約移進移進用a aba 歸約用m vba 歸約接受 3、某語言的拓廣文法g為：（0） st（1） t abd(2) b tb證明g不是lr（0)文法而是slr（1)文法,請給出slr（1）分析表。解：在項目集i0中：有移進項目t abd和歸約項目t 存在移進-歸約沖突，所以g不是lr(0)文法。 若產生式排序為：（0) st(1) t abd（2） t (3) b tb（4） b g的lr(0）項目集族及識別活前綴的dfa如下圖所示：識別g活前綴的dfa：由產生式知: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,中的移進-歸約和歸約-歸約沖突可以由follow集解決，所以g是s