《編譯原理》樣卷及答案.docx

一、簡答題（每題4分，共24分）1、 構造一個文法G，使得：L(G)=(m )m|m0 解答： GS: s- ()|(S)2、 構造一個正規(guī)式，它接受S=0，1上符合以下規(guī)則的字符串： 串內有且只有2個1的0、1字符串全體。解答： 0*10*10*3、 消除文法GS中的直接左遞歸和回溯 S (L) | aS | aL L，S | S解答： S (L) | aSS S | L S LL，S L | 4、 文法GS是喬姆斯基幾型文法？ S ABS | AB AB BA A 0 B 1解答：1型文法/上下文有關文法5、按Thmopson算法構造與正則表達式 (1*|0) * 等價的NFA。解答：略6、設計一個狀態(tài)轉換圖，其描述的語言規(guī)則為：如果以a開頭，則其后是由a、b組成的任意符號串；如果以b開頭，則其后是至少包含一個a的由a、b組成的任意符號串。解答：略二、（本題10分）對于文法GE：EET+|T TTF* | F FF | a (1) 給出句子FF*的最左推導和語法樹； (2) 給出句子FF*的短語、直接短語和句柄。解答： (1) 2分： 句子FF*的最左推導 2分： 句子FF*的語法樹 E=T=TF*=FF*=FF*=FF* (2) 3分:句子FF*的短語 FF*、FF*、F、F、F 2分:句子FF*的直接短語 F、F 1分:句子FF*的句柄 F三、（本題15分）構造與下列NFA等價的最小化DFA。解答：（1）10分：構造與NFA等價的DFA（2）5分：對DFA最小化 首先，將所有的狀態(tài)集合分成子集： k1=0,1,2,4 k2=3,5四、（本題15分）對下列文法GS：s eT | RTT DR | R dR | D a | bd (1) 寫出文法GS每個非終結符的FIRST集和FOLLOW集； (2) 判斷文法GS是否LL(1)文法（注：必須給出判斷過程，否則不得分）； (3) 寫出文法文法GS的預測分析表。解答：（1）8分：每個First集合和FOLLOW集合各1分FIRST集FOLLOW集s eT | RT e a, b, d, #T DR | a, b #R dR | d a,b,#D a | bd a bD,# (2) 2分： 判斷文法GS是LL(1)文法。 對于產(chǎn)生式s eT | RT：FIRST(eT)FIRST(RT)- =ea,b,d= FIRST(eT)FOLLOW(S)=e#= 對于產(chǎn)生式T DR | ： FIRST(DR)FOLLOW(T)=a,b#= 對于產(chǎn)生式R dR | ： FIRST(dR)FOLLOW(R)=da,b,#= 對于產(chǎn)生式D a | bd： FIRST(a)FIRST(bd)=ab= 所以，對于文法GS是LL(1)文法。 (3) 5分：文法GS的預測分析表。五、（本題18分）已知文法GS：S r D D D ，i | i(1) 畫出識別文法活前綴的完整DFA，并判斷該文法是否LR(0)文法(必須說明判斷依據(jù))；(2) 構造該文法的SLR(1)分析表，并判斷該文法是否SLR(1)文法(必須說明判斷依據(jù))。解答：(1) 8分：畫出識別文法活前綴的完整DFA 文法拓展并對產(chǎn)生式編號： （0）S S （1）S r D （2）D D ，i （3）D i (2) 2分：判斷該文法不是LR(0)文法 對于狀態(tài)3，項目集中存在“移進-規(guī)約”沖突，所以該文法不是LR(0)文法。 (3) 6分：構造該文法的SLR(1)分析表狀態(tài)ACTIONGOTOr ，i#SD0S211acc2S433S5r14r3r35S66r2r2 (4) 2分：判斷文法是SLR(1)分析表 回答1： 因為SLR(1)分析表不存在沖突，所以文法是SLR(1)分析表。 回答2： 對于狀態(tài)3， FOLLOW(S),=(#),=，“移進-規(guī)約”沖突可以用 SLR(1)方法解決，所以文法是SLR(1)分析表。六、（本題8分）文法GE的LR分析表如下圖所示：(1) E E+T (2) E T (3) T T*F(4) T F (5) F (E) (6) F i 寫出對輸入串 i * i + i的LR分析過程 (即狀態(tài)，符號，輸入串的變化過程)。解答: 七、（本題10分）寫出下列語句的四元式序列if(yz & (cn) while(ab) x=x+y*a; else m=m+n;解答：1 (j, y, z, 3)2 (j , -,-, 13)3 (j,m,n, 7)6 (j,-,-, 13)7 (j,a,b, 9) 8 (j,-,-,13/16