編譯原理習題課1、寫一個文法，使其語言是奇數集，且每一個奇數不以零開頭。分析：按規(guī)定的語言寫對應的文法，結論可能不只一個，它可以是一組等價文法中的一個。但必須做到的是：文法的句子必在語言之中。而且語言中的每一個句子必須可由文法識別符號推導出來。即文法所對應的語言的句子既不能多一個，也不能少一個。編譯原理習題課寫文法沒有一個形式化的算法，但可以使用“串聯”和“并聯”兩種手段。串聯：是把一個句子結構分解為幾個相連接的子結構。并聯：是把難以用統一形式表達的句子用幾種不同的方式表達出來。（這些方式應構成不相交的劃分。）編譯原理習題課就本題而言，句子由數字串構成，結尾是1、3、5、7、9，首字符不為零，所以句子形式按串聯方式應寫為：<非零數字><數串><奇數字>這樣的三部分串聯，使一位數和二位數不在其中，考慮對數串的定義若包含空串，則二位數就在其中了，剩下的一位數就可以通過并聯定義。編譯原理習題課G[S]可以定義為：S→<非零數字><數串><奇數字>|<奇數字>再加上對<數串>和<奇數字>及其他相關內容的產生式的書寫，最后結論為:S→<非零數字><數串><奇數字>|<奇數字><數串>→<數串><數字>|ε<數字>→<非零數字>|0<非零數字>→1|2|…|8|9<奇數字>→1|3|5|7|9編譯原理習題課2、說明下面的文法是二義文法，并把它改寫為無二義性的等價文法。S→SS|（S）|（）首先，不存在一個一般性的在有限步驟中證明一個文法是二義文法的方法。只要找到文法中的某一句子對應兩棵不同的語法樹，該文法的二義性就得到證明。編譯原理習題課鑒別文法是二義文法有如下一些方法：⑴二義文法的同構文法是二義文法。⑵二義文法作為產生式集合的子集的文法。如（）（）（）作為句子。改寫這類文法，可以參考表達式的非二義文法的寫法。把右部原來并列的相同非終結符改為不同的非終結符，從而消除其二義性。編譯原理習題課得到文法G‘[S]：S→ST|TT→（S）|（）顯然，該文法是非二義文法。3、已知文法G[Z]如下：Z→RS⑴R→aAc⑵A→aAc|bBb⑶S→aSb|ε⑷B→bB|ε編譯原理習題課請寫出它對應的語言L（G）。對于已知文法寫對應語言，處理過程是已知語言寫對應的文法的逆過程，可以借鑒串聯和并聯的方法。由⑴可知，句子被分為前后兩部分。⑵⑶是關于前部R的含義的產生式，明顯地，R由前綴的若干a和后綴的等量個c再在中間加若干個b組成。由⑵可知，a和c至少有一個，由⑶⑸知，b至少是二個。編譯原理習題課⑷是關于后部S的含義的產生式，S由前綴的若干a和后綴的等量個b構成。S→ε可知，a和b的個數可以為0。綜上，該文法所對應的語言是：L（G）={ambpcmanbn|m≥1，p≥2，n≥0}編譯原理習題課練習：1、生成非0開頭的正偶數集的文法。2、試構造生成語言L={anbnci|n≥1，i≥0}的文法。3、有文法G[N]：N→SE|ES→SD|DE→0|2|4|6|8|10D→0|1|2|3|4|5|6|7|8|9編譯原理習題課證明此文法有二義性，此文法所描述的語言是什么？改寫該文法為無二義性的。4、對如下文法:S→aB|bAA→aS|bAA|aB→bS|aBB|b寫出文法的開始符號，終結符號集，非終結符號集。編譯原理習題課給出串aaabbabbba的最左推導、最右推導。畫出語法樹。5、自動機與正規(guī)式的等價變換NFA與正規(guī)式的變換函蓋了DFA與正規(guī)式的變換。變換方法是：⑴在NFAM的狀態(tài)圖上加上唯一的初態(tài)X和唯一的終態(tài)Y，由X到每一個原來的初態(tài)引出一條ε箭弧，由原來的每一個終態(tài)引出一條ε箭弧到Y，這樣一來就形成了一個等價編譯原理習題課的只含唯一初態(tài)與終態(tài)的NFAM‘。⑵逐步消去M’上的節(jié)點，直至只剩下X和Y節(jié)點，消去節(jié)點的規(guī)則如下：對①→（u）②→（v）③，改為：①→（uv）③對①→（u）→（v）②，改為：①→（u|v）②對①→（u）②（r）→（v）③，改為：①→（ur*v）③最后，X和Y之間的弧標記為正規(guī)式。編譯原理習題課6、將下圖的NFA轉化成對應的DFA。分析：1）設I是給定NFA狀態(tài)集的一個子集，定義如下：

定義對狀態(tài)集合I的幾個有關運算：

1.狀態(tài)集合I的ε-閉包，表示為ε-closure（I），定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經任意條ε弧而能到達的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure（I）。若q∈I，q∈ε-closure（I），且從q出發(fā)，經過任意條ε弧能到達的任何狀態(tài)都屬于ε-closure（I）。2.狀態(tài)集合I的a弧轉換，表示為move（I，a）。定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經過一條a弧而到達的狀態(tài)結點的全體。編譯原理習題課2）從初始子集出發(fā)，填寫下表，每產生一個新的集合就檢驗它是否已經在第一列中出現過，將未曾出現者填入到第一列后面的空行中，重復此過程，直到產生的所有狀態(tài)子集均在第一列中出現。由于NFA的狀態(tài)子集總數是有限的，上述過程一定會在有限的步驟內終止。編譯原理習題課例子4f35621iaaaabbbb4f35621iaaaabbbb編譯原理習題課表中的初態(tài)是{i，1，2}，終態(tài)是所有含f的子集。對表中的所有狀態(tài)子集用新的字母或一個整數命名，就可以得到一個新的狀態(tài)矩陣。如上頁圖。等價的DFAaCDBAEFSbaaaaabbbbbabF編譯原理習題課7、將上述的DFA最小化。DFA的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)（死狀態(tài)）沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t可區(qū)別：不滿足兼容性——同是終態(tài)或同是非終態(tài)傳播性——從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達的狀態(tài)等價?！胺指罘ā盌FA的最小化算法的核心把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的.算法假定每個狀態(tài)射出的弧都是完全的，否則，引入一個新狀態(tài)，叫死狀態(tài)，該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己.“分割法”DFA的最小化算法的核心把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的.算法假定每個狀態(tài)射出的弧都是完全的，否則，引入一個新狀態(tài)，叫死狀態(tài)，該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己.

DFA的最小化算法DFAM=（K，∑，f，k0，，kt），最小狀態(tài)DFAM’1.構造狀態(tài)的一初始劃分：終態(tài)kt和非終態(tài)K-kt兩組（group）2.對∏施用過程PP構造新劃分∏new3.如∏new=∏，則令∏final=∏并繼續(xù)步驟4，否則∏:=∏new重復2.4.為∏final中的每一組選一代表，這些代表構成M’的狀態(tài)。若k是一代表且f（k，a）=t，令r是t組的代表，則M’中有一轉換f’（k，a）=r編譯原理習題課M’的開始狀態(tài)是含有S0的那組的代表M’的終態(tài)是含有F的那組的代表5.去掉M’中的死狀態(tài).

狀態(tài)圖表示SPZ00,1111

編譯原理習題課C和D同是終態(tài)，讀入a到達C和F，C和F同是終態(tài)，C和F讀入a都到達C，讀入b都到達E.C和D等價aCDBAEFSbaaaaabbbbbabF編譯原理習題課8、對正規(guī)式R=（a|ab）*bb*，畫出其所對應的DFA。編譯原理習題課對于正規(guī)式向NFA或DFA的變化，只需按原式分成若干串聯或并聯的部分，中間加上相應的狀態(tài)即可。接受正規(guī)式的最小狀態(tài)有窮自動機不計同構是唯一的。編譯原理習題課9、已知增廣文法G’[S]為：0、S’→S1、S→aSb2、S→aSc3、S→ab求它的LR（0）項目集規(guī)范族，寫出LR（0）分析表。編譯原理習題課分析：在文法中的任何一個產生式的右部的任何位置添加一個圓點就成了一個LR（0）的項目，XX說，若A→Ab是產生式，則A→.AbA→A.bA→Ab.這三種形式就是這個產生式對應的全部LR（0）項目形式。產生式表示的是一個歸約的規(guī)則，項目則是動態(tài)地表示歸約的一個階段。對于項目A→A.b，可以這樣理解它，”.”之前的A表示的是在識別Ab過程中已輸入到符號棧中編譯原理習題課的部分，”.”之后的b表示的是在識別Ab過程中期望出現的部分，”.”表示的則是在識別Ab過程中當前識別進度的定位。項目A→Ab.已具備了識別Ab的一切條件，因此也被稱為歸約項目。LR（0）分析表中的狀態(tài)，是一個項目集，初態(tài)的得到，狀態(tài)的形成，次態(tài)的取得，就是構造LR（0）分析表的三項主要工作。編譯原理習題課為了使接受狀態(tài)容易識別，我們總把原文法加以拓廣，引入一個不在G[S]中出現的非終結符S’，并加入一個產生式S’→S，形成了文法G’[S]，顯然它和原文法等價。A→β．刻劃產生式A→β的右