注：文章來自於我的博客shawnluo.com，歡迎訪問~！
文法G[S]如下：
S->aAaB|bAbB
A->S|db
B->bB|a
分析句子adbaba
要求：
提前消除文法的左遞歸及提取左公共因子。
求出FIRST集、FOLLOW集、SELECT集、判空、輸出預測分析表、
輸出對句子的分析過程。
一、主要內容
1、檢查文法是否為LL(1)文法
2、代碼介紹：
（1）初始定義參數，給定文法的開始符號、非終結符、終結符、文法產生式。定義三個字典用來表示FIRST集、FOLLOW集、SELECT集。
（移植到其他文法上只需修改這一部分初始定義的參數，其餘的程序都是通用的。）
（2）初始化函數init()，打印開始符號、文法產生式。並將每個非終結符加入FIRST集、FOLLOW集作為“鍵”，同時將其“值”置空；將每個產生式加入SELECT集作為“鍵”，同時將其“值”置空。
再向開始符號G的FOLLOW集中加入“#”
（3）求FIRST集
①getFirst()函數，根據每條產生式，求出每個非終結符的FIRST集。
這裡有兩種情況：
I.產生式右部第一個元素為終結符（也即小寫字母）的情況。將產生式按“->”分為左部、右部，然後判斷右部第一個元素是否為小寫字母（if not part_right[0].isupper()）。如果是，說明該元素為終結符，則直接將其加入左部的非終結符的FIRST集中。
II.產生式右部第一個元素為非終結符，則將其自身的FIRST集取出，加入產生式左部的非終結符的FIRST集中。
②first()函數，去除FIRST集中的重複元素，並打印輸出最終的FIRST集。
（4）求FOLLOW集
①getFollow()函數，根據每條產生式，求出每個非終結符的FOLLOW集。
I.產生式右部只有一個元素並且該元素為終結符（也即小寫字母）的情況。（if len(part_right) == 1 and part_right.islower()）。對於這種情況，直接略過該產生式。
II.解決了I情況後， 先將產生式右部逆序存入列表中
然後開始進行判斷：
a.產生式右部最後一個元素是非終結符（也即大寫字母，即列表的第一個元素為大寫字母：if temp[0].isupper()），則直接將產生式左部非終結符的FOLLOW加入該非終結符的FOLLOW集中。
然後，開始對產生式右部元素逐個處理。當再次找到一個非終結符時（即if not i.isupper()不成立，此時i代表當前非終結符），
b.若其後一位元素為非終結符（if temp1.isupper()）時，則將其FIRST集去除ε後加入i的FOLLOW集。
c.同時判斷該非終結符能否推出ε（if (‘ε’ in FIRST.get(temp1))），若能，則將標誌位flag加一。然後在判斷flag長度是否等於產生式右部減一，若相等，說明i後面全是非終結符，並且非終結符全都能推出空，則將產生式左部的非終結符的FOLLOW集加入i的FOLLOW集中。
d.若其後一位元素為終結符時，則直接將終結符加入i的FOLLOW集
②follow()函數，去除FOLLOW集中的重複元素，並打印輸出最終的FOLLOW集。
（5）求SELECT集
①getSelect()函數，根據每條產生式，求出每個產生式的SELECT集。
I.當產生式右部第一個元素為終結符時，則直接將該非終結符加入產生式的SELECT集
II.當產生式右部第一個元素為非終結符時，判斷其是否為空，
a.若為空，則將其FIRST集去除ε後加入產生式的SELECT集，同時也將產生式左部非終結符的FOLLOW集加入產生式的SELECT集
b.若不為空，則直接將其FIRST集加入產生式的SELECT集。
②select()函數，去除SELECT集中的重複元素，並打印輸出最終的SELECT集。
（6）輸出預測分析表predTable()函數
（7）主控程序，對於輸入的句子，根據每條產生式進行處理。
①當分析棧的棧頂符號等於某個產生式的左部非終結符時，同時當輸入串的當前符號存在於產生式的SELECT集中，則使用該條產生式進行推導，將分析棧棧頂符號彈出，然後將產生式右部符號入棧
②當分析棧棧頂符號等於輸入串當前符號時，判斷相等的元素是否為“#”。
I.若為“#”，說明分析已經完成，分析成功，輸出“ACCEPT”
II.若不為“#”，說明當前只是匹配到符號，則輸出匹配信息
③最後，根據標誌位，判斷是否分析成功。
二、實驗截圖
【實驗小結】
1、在求解FOLLOW集時，要根據每個產生式右部逐個符號分析。即對每個產生式進行循環判斷，從產生式右部入手，對右部每個符號分析處理，而不是對每個非終結符處理，這樣就避免了多次嵌套循環。同時，使用python中的字典數據結構，十分方便的實現FOLLOW集的存儲和賦值（同樣FIRST集與SELECT集）
也就是這個getFollow()函數，思考了好幾個小時才搞出來。然後類似的FIRST集和SELECT集求解實現就簡單得多了。
2、注意要對FIRST集、FOLLOW集、SELECT集中元素去重，去掉重複的元素。
3、輸出預測分析表時，考慮到每個產生式的順序隨機，採用列表中的insert方法，將對應終結符的匹配的產生式插入相應的位置。也即按照VT列表中的位置順序。
不然的話，有可能出現順序錯亂的問題。
注：文章來自於我的博客shawnluo.com，歡迎訪問~！
閱讀更多 Shawnl111 的文章
