LL(1)分析算法 是 自顶向下语法分析算法 的一种。从左(L)向右读入程序，最左(L)推导，每个分析表项只有一(1)个前看字符。是一种表驱动的分析算法。

流程：消去左递归->推导Vn的nullbale集 ->推导Vn的first集->推导Vn的follow集->推导select集，判别是LL(1)->构造分析表(列表示栈顶符号，也是生成式非终结符，行表示条件符号)->预测分析

• 1 NULLABLE集：求可推导出空的非终结符
• 2 FIRST集：求FIRST集
• 3 FOLLOW集：Vn中每个非终结符在生成式右部紧跟的可能终结符集合

1 NULLABLE集：求可推导出空的非终结符

NULLABLE集：Vn中可以推导为空@的非终结符的集合。

归纳定义：(用@代表空) 归纳非终结符X属于集合NULLABLE。

• 基本情况：X->@

NULLABLE += {X}

• 归纳情况：X->Y1…Yn (其中Yi~Yn是n个非终结符，且都属于NULLABLE集)

NULLABLE += {X}

• 不符情况：X->a 或 X->Y1…Yn (其中Yi~Yn是n个非终结符，但某一Yi不属于NULLABLE集)

求NULLABLE集伪代码：

NULLABLE={};
while(nullable is still changing)for each (Production p: X->β)if (β == '@')NULLABLE += {X}if (β == Y1... Yn)if (Y1 属于 NULLABLE &&...&& Yn 属于 NULLABLE）NULLABLE += {X}

实验要求：

在本实验中，您需要使用C++进行编程，实现如下功能。
对文法求取能够推导出ε的非终结符，其算法如下：

1.建立一个以非终结符的个数为上限的一维数组X[ ]，数组元素为非终结符，对应每个元素有一标志位；（该标志位记录能否推出ε，其值为：“未定”、“是”、“否” ）
2.置初值——将数组X[ ]中对应的每个非终结符的标记置为“未定”；
3.扫描文法中的产生式

• 删除所有右部含终结符的产生式，若某一非终结符为左部的所有产生式都被删除，则将数组中对应的标记值改为“否”；
• 若某一非终结符的某产生式右部为ε，则数组中对应的标记置为“是”，并删除该非终结符为左部的所有产生式。

4.扫描产生式右部的每个非终结符

• 若该符号在数组中对应标志为“是”，则删去该符号；若删去后，产生式右部为空，则将该产生式左部的非终结符在数组中对应的标志改为“是”，并删去该非终结符为左部的所有产生式；
• 若该符号在数组中对应标志为“否”，则删去该产生式；若这使该产生式左部非终结符的有关产生式都被删去，则把数组中该非终结符对应的标志改为“否”；

5.重复4，直至扫描完一遍文法的产生式，数组中的标志不再改变为止。

输入格式:
输入第1行是文法总行数n，第2行至第n行是文法。

输出格式:
按ASCII码从小到大的顺序输出所有能推导出ε的非终结符（符号之间用一个空格分隔，且最后一个符号后没有空格）；如果没有能推导出ε的非终结符，则输出“Nothing”。

输入样例:

3
A->Bc
B->b
B->@

输出样例:

B

代码长度限制:100 KB
时间限制:400 ms
内存限制:100 MB

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;//生成式个数
int num_VN;
string VN;//非终结符集合string get_nullable(string P[]){string nullable;int last_nullable_num=-1;while(last_nullable_num!=int(nullable.size())){// cout<<"nullable:"<//查看生成式P[i]右部, 向右推进for(int j=3;j//右部是@if(P[i][j]=='@'&&nullable.find(P[i][0]==string::npos)){nullable+=P[i][0];break;}//右部遇到belse if(VN.find(P[i][j])==string::npos){break;}//如果Yi本轮迭代不在nullable集内，就breakelse if(VN.find(P[i][j])!=string::npos&&nullable.find(P[i][j])==string::npos){break;}//当前Yi为P[i]的结尾，把P[i][0]加入nullable集else if(VN.find(P[i][j])!=string::npos && nullable.find(P[i][j])!=string::npos && j==P[i].size()-1 && nullable.find(P[i][0]==string::npos)){nullable+=P[i][0];break;}//如果Yi本轮迭代在nullable集内，默认continue}}//去重复sort(nullable.begin(),nullable.end());nullable.erase(unique(nullable.begin(),nullable.end()),nullable.end());}return nullable;
}int main(){//1.数据输入cin>>n;string P[n];//n个生成式getchar();for(int i=0;igetline(cin,P[i]);//除去空格P[i].erase(std::remove(P[i].begin(), P[i].end(), ' '), P[i].end());//获取非终结符符号P[i][0]，并插入VNif(VN.find(P[i][0])==VN.npos)VN+=P[i][0];}//VN排序，P不进行排序sort(VN.begin(),VN.end());num_VN=VN.size();   string res= get_nullable(P);if(res.size()==0){cout<<"Nothing";}else{sort(res.begin(),res.end());for(int i=0;icout<

for each(nonterminal N)FIRST(N)={};
while(some set is changing)foreach (production p: N-> β1...βn)foreach (βi from β1 upto βn)if (βi== a)FIRST(N)+={a};break;if (βi== M...)FIRST(N)+=FIRST (M);if (M is mot in NULLABLE)break;