-.z.一、簡(jiǎn)答題（每題4分，共24分）構(gòu)造一個(gè)文法G，使得：L(G)={(m)m|m>0}解答：G[S]:s->()|(S)構(gòu)造一個(gè)正規(guī)式，它接受={0，1}上符合以下規(guī)則的字符串：串有且只有2個(gè)1的0、1字符串全體。解答：0*10*10*消除文法G[S]中的直接左遞歸和回溯S→(L)|aS|aL→L，S|S解答：S→(L)|aS'S'→S|εL→SL' L'→，SL'|ε4、文法G[S]是喬姆斯基幾型文法？S→ABS|ABAB→BAA→0B→1解答：1型文法/上下文有關(guān)文法5、按Thmopson算法構(gòu)造與正則表達(dá)式(1*|0)*等價(jià)的NFA。解答：略6、設(shè)計(jì)一個(gè)狀態(tài)轉(zhuǎn)換圖，其描述的語言規(guī)則為：如果以a開頭，則其后是由a、b組成的任意符號(hào)串；如果以b開頭，則其后是至少包含一個(gè)a的由a、b組成的任意符號(hào)串。解答：略二、（本題10分）對(duì)于文法G[E]：E→ET+|TT→TF*|FF→F^|a(1)給出句子FF^^*的最左推導(dǎo)和語法樹；(2)給出句子FF^^*的短語、直接短語和句柄。解答：(1)2分：句子FF^^*的最左推導(dǎo)2分：句子FF^^*的語法樹E=>T=>TF*=>FF*=>FF^*=>FF^^*(2)3分:句子FF^^*的短語FF^^*、FF^^*、F、F^、F^^2分:句子FF^^*的直接短語F、F^1分:句子FF^^*的句柄F三、（本題15分）構(gòu)造與下列NFA等價(jià)的最小化DFA。解答：（1）10分：構(gòu)造與NFA等價(jià)的DFA（2）5分：對(duì)DFA最小化首先，將所有的狀態(tài)集合分成子集：k1={0,1,2,4}k2={3,5}四、（本題15分）對(duì)下列文法G[S]：s→eT|RTT→DR|εR→dR|εD→a|bd(1)寫出文法G[S]每個(gè)非終結(jié)符的FIRST集和FOLLOW集；(2)判斷文法G[S]是否LL(1)文法（注：必須給出判斷過程，否則不得分）；(3)寫出文法文法G[S]的預(yù)測(cè)分析表。解答：（1）8分：每個(gè)First集合和FOLLOW集合各1分FIRST集FOLLOW集s→eT|RT{e}{a,b,d,ε}*T→DR|ε{a,b}{ε}*R→dR|εgeaosea{ε}a,b,*D→a|bd{a}D,*(2)2分：判斷文法G[S]是LL(1)文法。對(duì)于產(chǎn)生式s→eT|RT：FIRST(eT)∩FIRST(RT)-ε={e}∩{a,b,d}=ΦFIRST(eT)∩FOLLOW(S)={e}∩{*}=Φ對(duì)于產(chǎn)生式T→DR|ε：FIRST(DR)∩FOLLOW(T)={a,b}∩{*}=Φ`對(duì)于產(chǎn)生式R→dR|ε：FIRST(dR)∩FOLLOW(R)=mqgesoa∩{a,b,*}=Φ對(duì)于產(chǎn)生式D→a|bd：FIRST(a)∩FIRST(bd)={a}∩=Φ所以，對(duì)于文法G[S]是LL(1)文法。(3)5分：文法G[S]的預(yù)測(cè)分析表。五、（本題18分）已知文法G[S]：S→rDD→D，i|i(1)畫出識(shí)別文法活前綴的完整DFA，并判斷該文法是否LR(0)文法(必須說明判斷依據(jù))；(2)構(gòu)造該文法的SLR(1)分析表，并判斷該文法是否SLR(1)文法(必須說明判斷依據(jù))。解答：(1)8分：畫出識(shí)別文法活前綴的完整DFA文法拓展并對(duì)產(chǎn)生式（0）S'→S（1）S→rD（2）D→D，i（3）D→i(2)2分：判斷該文法不是LR(0)文法對(duì)于狀態(tài)3，項(xiàng)目集中存在“移進(jìn)-規(guī)約”沖突，所以該文法不是LR(0)文法。(3)6分：構(gòu)造該文法的SLR(1)分析表狀態(tài)ACTIONGOTOr，i*SD0S211acc2S433S5r14r3r35S66r2r2(4)2分：判斷文法是SLR(1)分析表回答1：因?yàn)镾LR(1)分析表不存在沖突，所以文法是SLR(1)分析表?；卮?：對(duì)于狀態(tài)3，F(xiàn)OLLOW(S)∩{,}=(*)∩{,}=Ф，“移進(jìn)-規(guī)約”沖突可以用SLR(1)方法解決，所以文法是SLR(1)分析表。六、（本題8分）文法G[E]的LR分析表如下圖所示：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i寫出對(duì)輸入串i*i+i的LR分析過程(即狀態(tài)，符號(hào)，輸入串的變化過程)。解答:七、（本題10分）寫出下列語句的四元式序列if(y>z&&(c<d||m>n))while(a>b)*=*+y*a;elsem=m+n;解答：1(j>,y,z,3)2(j,-,-,13)3(j<,c,d,7)4(j,-,-,5)5(j>,m,n,7)6(j,-,-,13)7(j>,a,b,9)8(j,-,-,