LL(1) 基础 求可推导出空的非终结符

题目详情(ε在题目中用@表示)：
题目链接：https://pintia.cn/problem-sets/1635283457335554048/exam/problems/1635283976988848128

输入样例1:

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

输出样例1:

B

输入样例2:

10
S->AB
S->* C
A->@
A-> *
B->@
B->(D
C- >A      D
C->*
D->(S
D->c

输出样例2:

A B S

思考:
数据结构方面:
对于产生式，我么把左部和右部各看成一个string，将一个产生式去掉->，分成两个string，所以我们用pair<string,string>来存储一个产生式，然后用vector来存储这个类型，即

#define x first
#define y second
typedef pair<string,string> PSS;
vector<PSS> p;

要得到左部,即p[i].x,右部即,p[i].y

算法方面:
对于输入，先要收集所有的非终结符，同时记录以这个非终结符为左部的产生式的个数（init()）

具体的核心算法

1. 设一个标志位数组，代码中为st，一开始设为未定，即为0，为1表示是，即能推出ε，否则则为2

2. 对于所有右部含终结符的产生式，因为终结符肯定是推不出ε的，所以可以直接删掉，如果有关的以某个非终结符为左部的产生式被全部删掉了，即cnt[p[i].x[0]]==0，那么就说明这个非终结符是一定推不出ε的，标记为2（delete_terminal()）

3. 若某一非终结符的某产生式右部为ε，则数将该非终结符标记为1，并删除该非终结符为左部的所有产生式（sign_not_terminal()）

4. 循环扫描每个产生式的右部的每个非终结符（dealing_right()）这个时候产生式里就没有终结符了，因为都删完了
   4.1 如果扫描到的非终结符是推不出ε，即st数组标记为2，那么在这个在这个产生式内是无法判断这个左部的非终结符是不是可以推出ε，所以删掉这个产生式；但是，如果删掉之后，以这个非终结符为左部的产生式被全部删掉了（即cnt[p[i].x[0]]==0），那么就一定可以确定这个非终结符式推不出ε的，即标记为2。
   4.2 如果扫描到的终结符能够推出ε，那么就删掉这个符号，如果删掉之后右部为空（即这个符号的右边没有能推出终结符的符号），说明对应的左部的非终结符是可以推出ε，st标记为1的同时将以这个非终结符为左部的产生式全部删掉。
   4.3 循环的中止条件，因为每一次标记都会要break,那么我们引入一个标记量sign，初值为0，如果break了，sign就赋值为1，在循环的最后判断一下sign，来作为中止循环的条件

相关的具体做法：
删掉一个符号：即将string中对应下标的字符删掉,假设下标为j,我们用这个下标将string分成两个子串然后链接即可
right=right.substr(0,j)+right.substr(j+1,right.size()-j-1);
删掉产生式：
p.erase(p.begin()+i,p.begin()+i+1)可以实现删除vector中下标为i的元素

下面是具体的代码实现:

#include<iostream>
#include<vector>
#include<unordered_set>
#include<cstring>
#include<algorithm>
#include<string.h>

using namespace std;

//vector删除元素可以用: p.erase(p.begin()+1,p.begin()+2);//删除的是下标为l一直到r-1的元素
#define x first
#define y second
typedef pair<string,string> PSS;//可以用这样的数据结构来存产生式
const int N = 1010;
vector<PSS> p;
int st[N];//状态数组,为0表示未定,为1表示是,即能推出ε,否则则为2
int cnt[N];//用来记录以这个非终结符为左部的产生式有多少,这样用来判断一个以某个非终结符为左部的产生式是不是多被删掉了就很方便

vector<char> Vn;//非终结符
unordered_set<char> Vn_set;
vector<char> result;

void init()
{
    for(int i=0;i<p.size();i++)//遍历所有的产生式,收集所有的非终结符
    {
        string a=p[i].x,b=p[i].y;
        cnt[a[0]]++;//记录以这个非终结符为左部的产生式的个数
        for(int j=0;j<a.size();j++)
        if(a[j]>='A'&&a[j]<='Z'&&!Vn_set.count(a[j]))
        {Vn.push_back(a[j]);Vn_set.insert(a[j]);}
        for(int j=0;j<b.size();j++)
        if(b[j]>='A'&&b[j]<='Z'&&!Vn_set.count(b[j]))
        {Vn.push_back(b[j]);Vn_set.insert(b[j]);}
    }
}

void delete_terminal()//删除所有右部含终结符的产生式
{
    for(int i=0;i<p.size();i++)
    {
        string right=p[i].y;
        string left = p[i].x;
        bool sign=false;
        for(int j=0;j<right.size();j++)
        {
            // if(right[j]>='a'&&right[j]<='z')
            if((right[j]<'A'||right[j]>'Z')&&right[j]!='@')
            {
                sign=true;break;
            }
        }
        if(sign)//说明含终结符,需要删掉这一个
        {
            cnt[left[0]]--;
            p.erase(p.begin()+i,p.begin()+i+1);
            i--;continue;
        }
    }

    for(int i=0;i<Vn.size();i++)
    {
        if(!cnt[Vn[i]])//这个终结符为左部的所有产生式都被删除
        st[Vn[i]]=2;//标记为否
    }
}

void sign_not_terminal()
{
    unordered_set<string> temp;
    for(int i=0;i<p.size();i++)
    {
        if(p[i].y=="@")//右部为ε
        {
            string a=p[i].x;
            st[a[0]]=1;//标记为是
            cnt[a[0]]=0;//直接全部删掉
            result.push_back(p[i].x[0]);
            if(!temp.count(a))
            temp.insert(a);
        }
    }
    //根据temp里的统一做删除
    for(int i=0;i<p.size();i++)
    {
        if(temp.count(p[i].x))
        {
            p.erase(p.begin()+i,p.begin()+i+1);
            i--;
            continue;
        }
    }
}

void dealing_right()
{
    //这个时候,所有产生式的右部不可能含终结符,也不可能含有ε,只可能是各种非终结符
    while(1)
    {
        int sign=0;
        char d;//需要删除的有关产生式的左部的非终结符
        for(int i=0;i<p.size();i++)
        {
            string right=p[i].y,left=p[i].x;
            for(int j=0;j<right.size();j++)
            {
                if(st[right[j]]==1)//对应标志是“是”,则删去该符号
                {
                    if(right.size()==1)//删完这个之后就为空了
                    {
                        d=left[0];
                        st[left[0]]=1;//将这个产生式左部的非终结符对应的标志改为“是”
                        result.push_back(d);
                        sign=1;
                        break;
                    }
                    else
                    {
                        right=right.substr(0,j)+right.substr(j+1,right.size()-j-1);//去掉中间那个字符
                        p[i].y=right;//再写回去
                        j--;continue;
                    }
                }
                else if(st[right[j]]==2)//对应标志是“否”,则直接把这个产生式删掉
                {
                    if(cnt[left[0]]==1)//一删就都删掉了
                    {
                        st[left[0]]=2;
                    }
                    p.erase(p.begin()+i,p.begin()+i+1);
                    cnt[left[0]]--;
                    sign=2;//标记需要删掉下标为i的产生式
                    break;
                }
            }
            if(sign)break;
        }
        if(sign==1)
        {
            for(int i=0;i<p.size();i++)
            {
                string left = p[i].x;
                if(left[0]==d)
                {
                    p.erase(p.begin()+i,p.begin()+i+1);
                    cnt[d]--;
                }
            }
        }
        else if(sign==0)break;//没有改变,说明已经收敛,循环停止
    }

    sort(result.begin(),result.end());
}

int main()
{

    int n;cin>>n;getchar();
    for(int i=0;i<n;i++)
    {
        char in[99];
        string temp;
        fgets(in,99,stdin);
        for(int i=0;i<strlen(in);i++)//需要忽略空格
        {
            if(in[i]!=' '&&in[i]!='\t'&&in[i]!='\n')
            temp+=in[i];
        }
        int t=0;
        for(int j=0;j<temp.size();j++)
        {
            if(temp[j]=='-')
            {t=j;break;}
        }
        string a=temp.substr(0,t);//从下标为0开始,长度位t的子串
        string b=temp.substr(t+2,temp.size()-t-1);//'-'的下标是t,'>'的下标是t+1
        p.push_back({a,b});
    }
    init();
    delete_terminal();
    sign_not_terminal();
    dealing_right();//扫描右部

    for(int i=0;i<result.size();i++)
    {
        cout<<result[i];
        if(i!=result.size()-1)cout<<" ";
    }
    if(result.size()==0)cout<<"Nothing";

    return 0;
}