Cal_First_Follow_Select

c++实现求FIRST集、FOLLOW集、SELECT集 ####前提：

• 终结符仅考虑小写字母和部分符号
• 非终结符仅考虑大写字母
• ^代表空
• #代表结束
• 输入产生式完成后，换行，输入END来结束输入

---

####思路简介：

对产生式进行预处理

将产生式中"->"左部的非终结符存为left，将右部的符号依次存入right，若遇到"|"，则新建一个产生式，左边依然为left，右部为"|"后的内容

求FIRST集

• 若产生式右部的第一个字符是终结符，将其加入left的FIRST集中
• 若产生式右部的第一个字符是非终结符E,将E的FIRST集全部复制到left的FIRST集中：

1. 若E不能推出空，结束
2. 若E可以推出空，将"^"加入left的FIRST集中，并将E后的一个字符F看作是产生式右部第一个字符，重新进行上述分析

• 重复以上步骤至FIRST集无更新(本代码中利用固定进行多次循环来保证无更新)

求FOLLOW集

• 将"#"加入开始符号S的FOLLOW集中
• 对产生式的右部进行如下分析,若右部中存在非终结符E,：

1. 若E后为终结符a,将终结符a加入E的FOLLOW集中
2. 若E后为非终结符F，且F不能推出空，将F的FIRST集复制到E的FOLLOW集中
3. 若E后为非终结符F，且F能推出空，将F的FIRST集（除了"^"）复制到E的FOLLOW集中，并将F之后的符号看作E的下一个字符，重新进行上述分析

• 若产生式右部的最后一个字符为非终结符P,将P的FOLLOW集复制到left的FOLLOW集:

1. 若P不能推出空，结束
2. 若P能推出空，将P的前一个字符看作此产生式的右部最后一个字符，重新进行上述分析

• 重复以上步骤至FOLLOW集无更新(本代码中利用固定进行多次循环来保证无更新)

求SELECT集

对处理后的每个产生式进行如下分析：

• 若为空产生式，SELECT集为left的FOLLOW集,结束
• 若为非空产生式，且右部第一个符号为终结符a，将a加入SELECT集，结束
• 若为非空产生式，且右部第一个符号为非终结符E，且E的FIRST集中不含"^"，将E的FIRST复制到SELECT集，结束
• 若E的FIRST集中含"^"，将E的FIRST复制到SELECT集，将E后一个符号看作右部第一个符号重新分析（若E已经为右部最后一个符号，将left的FOLLOW集加入SELECT集,结束）