注：文章来自于我的博客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 的文章
