【正文】 人教是學不會的。關鍵問題是基本概念不清楚） 2. 所答非所問 (例如：沒有要求 LL分析卻將文法改為 LL的 ) 3. 畫蛇添足 (例如：僅問有無沖突卻將分析表先構造出來 ) 4. 偷工減料 (例如：有若干問，僅回答部分或問題僅答一半 ) 警示 千萬不要作弊！命運掌握在自己的手中！ 實際試題舉例 一、簡答題 1（ 2分 ） 有哪些方法可以去除文法的二義性 。 3（ 4分 ） 試證明正規(guī)式 (ab)*a與 a(ba)*是等價的 。 也可以用歸納法證明（提示：以 ab重復 0次、 1次作為歸納基礎，假設 ab重復 n次成立，證明 ab重復 n+1次也成立）。 2（ 1分 ） 正規(guī)式 r和 s等價說明 相同 。 4（ 4分） 已知文法 G定義如下： S→eT|RT T→DR|ε R→dR|ε D→a|bd 則 FIRST(S)= ， FIRST(D)= ， FIRST(T)= ， FIRST(R)= 。 三、計算題（ 1） 1（ 13分 ） 已知一個 NFA如圖 。 (b)（ 3分 ） 寫出與該自動機等價的正規(guī)式 r。 0 1 2b ba,ba,b 解： 1. 含有至少兩個連續(xù) b的 a、 b串 ， 例如 bb、 bbb等 。 3. 直接用狀態(tài)轉換矩陣構造： 初態(tài)： {0} 子集法得： （ 2是終態(tài) ） a b {0} {0} {0,1} {0,1} {0} {0,1,2} {0,1,2} {0,2} {0,1,2} {0,2} {0,2} {0,1,2} 令： {0}=A， {0,1}=B， {0,1,2}=C， {0,2}=D 得： a b A A B B A C C D C D D C 最小化 DFA得： （ C和 D不可區(qū)分 ） a b A A B B A C C C C A B Cb baaa , b三、計算題（ 2） 2（ 15分 ） 有文法 G和 G的語法制導翻譯如下： E→E 1*T { =newtemp。 } | T { =。 emit(+,。 } F→(E) { =。 } (a)（ 4分 ） 求句型 (T+F)*id 的短語 、 直接短語以及句柄； (b)（ 4分 ） 根據(jù)語法制導翻譯寫出句子 a*b+c*d的中間代碼； (c)（ 3分 ） 若 a=3， b=5， c=7， d=8， 請給出中間代碼計算結果； (d)（ 4分） 將文法 G簡化為： E→E*T|T ， T→T+F|F ， F→id 。 解： (a) 短 語： (T+F)*id、 (T+F)、 T+F、 id 直接短語： T+F、 id 句柄： T+F (b) a*b+c*d的中間代碼： (1) (+, b, c, t1) (2) (*, a, t1, t2) (3) (*, t2, d, t3) (c) 計算結果： t3=288 (d) 識別活前綴的 DFA： E ’→. EE →. E * TE →. TT →. T + FT →. FF →. i dE ’→E .E →E . * TE →T .T →T . + FT →F .F →i d .E →E * . TT →. T + FT →. FF →. i dT →T + . FF →. i dE →E * T .T →T . + FFETFid*+ +TididI0I1I2I3I4I5I6I7T →T + F . I8F28 部分習題解答 習題 寫出下述語言的正規(guī)式描述 （ 1） 由偶數(shù)個 0和奇數(shù)個 1構成的所有 01串 （ 2） 所有不含子串 011的 01串 （ 3） 每個 a后面至少緊隨兩個 b的 ab串 （ 4） C的形如 /*…*/ 的注釋 。其中 …代表不含 */的字符串 思路： 注釋中若遇到 *：若后邊是 /則結束注釋否則仍然是注釋 步驟： 1. 注釋串是空； 2. 考慮沒有 *的注釋； 3. 考慮含 *的注釋 結果： (4) /* ([^*]|*[^/])* */ （ 2） 所有不含子串 011的 01串： 1*(01|0)* （ 3） 每個 a后面至少緊隨兩個 b的 ab串： (b|abb)* 習題 有一 NFA的狀態(tài)轉換矩陣下表，其中 S為初態(tài)， D為終態(tài) a b c ε S A,B C,D D A,B,C A A C B B A D C C B A A D C B S 1. 求出它的最小 DFA 2. 用正規(guī)式描述 DFA所接受的語言 問題： 根據(jù) DFA寫出對應的正規(guī)式 ， 通常的考慮和步驟是什么 ？ 再重復一遍： 正規(guī)式 、 DFA是從兩個不同的側面表示一個集合 (即正規(guī)集 )。 反之亦然 。 解： 正規(guī)式： 個位： [13579] 個位以上： [09]* 最高位： [19] 三段連起來： [19][09]*[13579] 兩種情況： [19][09]*[13579] | [13579] 產(chǎn)生式： S→ACB|B A→ 1|2|3|4|5|6|7|8|9 B→ 1|3|5|7|9 C→ε| 0C|AC 習題 對于文法 id+id*id 和 (id+id)*id E → E+T|T T → T*F|F () F → (E) |F|id （ 1） 構造基于 LR(0)項目集的識別活前綴的 DFA （ 2） 指出 DFA中所有含有沖突的項目集 ， 并說明這些沖突可以用 SLR(1)方法解決； （ 3） 構造文法 SLR(1)分析表 （ 4） 用分析表對句子 id+id*id 和 (id+id)*id進行分析 （ 以格局變化的方式 ） （ 5） 根據(jù) （ 4） 的分析給出 id+id*id的分析樹和剪句柄的過程 解： 作為練習 ， 本題的每一步都是必要的 。 習題 （解） （ 1） 構造基于 LR(0)項目集的識別活前綴的 DFA （ 2） 指出 DFA中所有含有沖突的項目集 ， 并說明這些沖突可以用 SLR(1)方法解決； E 39。 → E . E → E . + T