LL(1)基础 7-2 求FIRST集

题目详情（ε在题目中用@表示）：

题目链接：https://pintia.cn/problem-sets/1635283457335554048/exam/problems/1635283976988848129

提醒：题目中相关算法的原理说的不是很清楚，可以看下面写的，这个题是基于上一个文章LL(1) 基础 7-1 求可推导出空的非终结符来写的

输入样例1:

4
D-> B  c
D ->c
B->bD
B -> a

输出样例1:

FIRST(B)={ a b }
FIRST(D)={ a b c }

FIRST(Bc)={ a b }
FIRST(c)={ c }
FIRST(bD)={ b }
FIRST(a)={ a }

输入样例2:

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

输出样例2:

FIRST(A)={ * @ }
FIRST(B)={ ( @ }
FIRST(C)={ ( * c }
FIRST(D)={ ( c }
FIRST(S)={ ( * @ }

FIRST(AB)={ ( * @ }
FIRST(*C)={ * }
FIRST(@)={ @ }
FIRST(*)={ * }
FIRST(@)={ @ }
FIRST((D)={ ( }

first集的定义和性质:
对于first集的定义,first集就是这个式子能够推出的第一个非终结符的集合（包括ε）
例如: fisrt(bC)={b}
若现有: B->ε,B->aD,则肯定有:first(B)={a,ε}
如果有first(C)={a,b,c},那么如果对于B->CD这个产生式,first(B)=first(C)

但如果first(C)={a,b,c,ε},那么C就可能为空,那么如果对于B->CD这个产生式,first(B)=first(C)∪first(D)

思考:
代码是已经求完了每个非终究符是否能够推出ε的基础上写的,产生式原来存在p当中,由于在求能够推出ε的非终结符的过程中产生式全删完了,所以就用p_mirror来存了备份的产生式

我们首先先求每个非终结符的first集:
我们用一个string数组来存所有非终结符的first集
第一层循环遍历所有的非终结符(first_for_each)

（其实下面就是一个递归的过程了）

第二层循环遍历所有的产生式（其实是遍历产生式的右部）,找到左部为对应的非终结符(first_operation)
如果遇到的符号是一个终结符,那么将这个终结符加入到对应的first集里去,第二层循环break
如果遇到的符号是一个非终结符N,那么看这个非终结符能不能推出ε：

• 如果不能推出ε,就将first(N)加入到对应的first集中去,第二层循环break

• 如果能推出ε,那么就把first(N)-{ε}加入到对应的first集里去,那什么时候需要将ε加入到first集里去呢,那就是右部全部都是能够推出ε的非终结符或者只有一个ε。

如何做到判断需不需要将ε加入到集合里去呢？
我们在最开始维持一个标记sign，初值为1，如果遇到了是不能推出ε非终结符或者终结符,则遍历这个右部的循环会被 break掉,sign标记为0,如果一直不break,那么说明遇到的一直都是能够推出ε的非终结符,sign一直为1,循环结束后如果sign为1,就会把ε加入到集合中去。

对于上面所说的把一个集合加入到一个集合中去,就是并集的意思,在代码中其实就是用string来表示集合,两个集合的并集就是两个string相加然后排序去重,具体的代码实现如下:

sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());

而对于所有的右部的first集(first_for_right),既然有了所有的非终结符的first集和能够推出ε的非终结符的判断,这个算法其实就跟上面的一样,只不过上面递归函数的参数是一个char,而这个右部的是一个string

同时,有一个小坑:就是题目要求把ε放在最后面,由于一开始sort的时候我以为@肯定是在第一位的,导致出现了错误,所以这里输出的时候是需要特别处理一下的。

2023.4.2更新：

由于我们求first集采用的是递归的思想，所以当我们遇到有左递归的文法的时候是会出现无穷递归的情况的，如遇到A->AD的情况，在求A的first集的时候又需要求A的first集，然后又遍历一遍所有的产生式然后又求A的first集，对于这样的情况，我们可以用多次循环直到所有的first集合都收敛了来解决。

也就是说，当我们遇到A->AD的情况的时候，我们为了求A的first集合不需要再对A求first集合，而是直接将A的当前已经求得的first集合加入到A中即可，更一般的说，我们遇到A->BC的时候，为了求A的first集合，我们首先需要将B的first集合加入到A的first集合中，而不是对B进行递归求first集，而收敛的情况，就是在first_for_each这个函数中所有的first集合都不再变化的时候（加一个while循环即可），那么就说明我们的first集合就求完了。

递归和非递归的区别在于first_operation函数中得到非终结符的first集的语句，前者是string temp = first_operation(right[j]);，而后者是string temp = first[right[j]];

这里给上含递归的样例：

输入：

8
E->E+T
E->T
T->T*F
T->F
F->P^F
F->P
P->(E)
P->i

输出：

FIRST(E)={ ( i }
FIRST(F)={ ( i }
FIRST(P)={ ( i }
FIRST(T)={ ( i }

FIRST(E+T)={ ( i }
FIRST(T)={ ( i }
FIRST(T*F)={ ( i }
FIRST(F)={ ( i }
FIRST(P^F)={ ( i }
FIRST(P)={ ( i }
FIRST((E))={ ( }
FIRST(i)={ i }

下面是递归的实现的过程：

void first_for_each()//对所有的非终结符求first集合
{
    for(int i=0;i<Vn.size();i++)
    {
        char t=Vn[i];
        string res = first_operation(t);
        res=check(res);
        cout<<"FIRST("<<t<<")={ ";
        for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
        cout<<"}"<<endl;
    }
}

string first_operation(char t)
{
    if(first[t].size()!=0)return first[t];
    // 对所有的非终结符都求first集合

    string res;

    for(int i=0;i<p_mirror.size();i++)//遍历所有有关t的产生式
    {
        string left=p_mirror[i].x,right=p_mirror[i].y;
        if(left[0]==t)
        {
            int sign=1;//用来标志t的first集存不存在ε
            for(int j=0;j<right.size();j++)
            {
                //遇到终结符就可以结束
                //遇到非终结符就并ε
                if(right[j]!='@'&&(right[j]<'A'||right[j]>'Z'))//遇到的是终结符,包括ε
                {
                    res+=right[j];sign=0;
                    break;
                }
                else//遇到非终结符
                {
                    if(right[j]=='@')continue;
                    string temp = first_operation(right[j]);
                    if(result_set.count(right[j]))//如果可以直接推导出ε,则要继续往下并
                    {
                        temp = check(temp);//把“@”放到最后面
                        temp = temp.substr(0,temp.size()-1);
                        res += temp;
                    }
                    else 
                    {
                        res += temp;
                        sign=0;break;//绝对不存在ε
                    }

                }
            }
            if(sign==1)res+="@";
        }
    }

    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    first[t]=res;
    return res;
}

然后再附上解决了不用递归的循环做法：

void first_for_each()
{
    /*
        由于用递归求first集会出现无限递归，所以我们这里选用不断循环直到收敛为止的算法
    */
   while(1)
   {
        bool sign=true;
        for(int i=0;i<Vn.size();i++)//遍历每个非终结符，并求first集合
        {
            char t=Vn[i];
            string temp = first[t];
            string res = first_operation(t);
            if(res!=temp)sign = false;
            res=check(res);
        }
        if(sign)break;
   }

    //下面只是输出而已，不用看
    for(int i=0;i<Vn.size();i++)
    {
        char t=Vn[i];
        string res = first_operation(t);
        res = check(res);
        cout<<"FIRST("<<t<<")={ ";
        for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
        cout<<"}"<<endl;
    }
}

string first_operation(char t)
{
    // if(first[t].size()!=0)return first[t];
    // 对所有的非终结符都求first集合

    string res = first[t];

    for(int i=0;i<p_mirror.size();i++)//遍历所有有关t的产生式
    {
        string left=p_mirror[i].x,right=p_mirror[i].y;
        if(left[0]==t)
        {
            int sign=1;//用来标志t的first集存不存在ε
            for(int j=0;j<right.size();j++)
            {
                //遇到终结符就可以结束
                //遇到非终结符就并ε
                if(right[j]!='@'&&(right[j]<'A'||right[j]>'Z'))//遇到的是终结符,包括ε
                {
                    res+=right[j];sign=0;
                    break;
                }
                else//遇到非终结符
                {
                    if(right[j]=='@')continue;
                    string temp = first[right[j]];
                    if(result_set.count(right[j]))//如果可以直接推导出ε,则要继续往下并
                    {
                        temp = check(temp);//把“@”放到最后面
                        temp = temp.substr(0,temp.size()-1);
                        res += temp;
                    }
                    else 
                    {
                        res += temp;
                        sign=0;break;//绝对不存在ε
                    }

                }
            }
            if(sign==1)res+="@";
        }
    }

    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    first[t]=res;
    return res;
}

下面是具体的代码实现:

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

using namespace std;


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

vector<char> Vn;//非终结符
unordered_set<char> Vn_set;
vector<char> result;//可以直接推导出ε的非终结符
unordered_set<char> result_set;

string first[N];//first集合
vector<string> right_s;//所有的右部

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]);}
    }
    sort(Vn.begin(),Vn.end());
}

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]);
            result_set.insert(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);
                        result_set.insert(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());
}

string check(string s)
{
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='@')
        return s.substr(0,i)+s.substr(i+1,s.size()-i-1)+"@";
    }
    return s;
}

string first_operation(char t)
{
    if(first[t].size()!=0)return first[t];
    // 对所有的非终结符都求first集合

    string res;

    for(int i=0;i<p_mirror.size();i++)//遍历所有有关t的产生式
    {
        string left=p_mirror[i].x,right=p_mirror[i].y;
        if(left[0]==t)
        {
            int sign=1;//用来标志t的first集存不存在ε
            for(int j=0;j<right.size();j++)
            {
                //遇到终结符就可以结束
                //遇到非终结符就并ε
                if(right[j]!='@'&&(right[j]<'A'||right[j]>'Z'))//遇到的是终结符,包括ε
                {
                    res+=right[j];sign=0;
                    break;
                }
                else//遇到非终结符
                {
                    if(right[j]=='@')continue;
                    string temp = first_operation(right[j]);
                    if(result_set.count(right[j]))//如果可以直接推导出ε,则要继续往下并
                    {
                        temp = check(temp);//把“@”放到最后面
                        temp = temp.substr(0,temp.size()-1);
                        res += temp;
                    }
                    else 
                    {
                        res += temp;
                        sign=0;break;//绝对不存在ε
                    }

                }
            }
            if(sign==1)res+="@";
        }
    }

    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    first[t]=res;
    return res;
}



void first_for_each()
{
    for(int i=0;i<Vn.size();i++)
    {
        char t=Vn[i];
        string res = first_operation(t);
        res=check(res);
        cout<<"FIRST("<<t<<")={ ";
        for(int i=0;i<res.size();i++)
        cout<<res[i]<<" ";
        cout<<"}"<<endl;
    }
}

string first_for_right(string t)
{
    string res;
    if(t=="@")
    res="@";
    else
    {
        int sign=1;
        for(int j=0;j<t.size();j++)
        {
            if(t[j]!='@'&&(t[j]<'A'||t[j]>'Z'))//遇到的是终结符,包括ε
            {
                res+=t[j];sign=0;
                break;
            }
            else//遇到非终结符
            {
                if(t[j]=='@')continue;
                string temp = first_operation(t[j]);
                if(result_set.count(t[j]))//如果可以直接推导出ε,则要继续往下并
                {
                    temp = check(temp);//把“@”放到最后面
                    temp = temp.substr(0,temp.size()-1);
                    res += temp;
                }
                else 
                {
                    res += temp;
                    sign=0;break;//绝对不存在ε
                }

            }
        }
        if(sign==1)res+="@";
    }

    sort(res.begin(),res.end());
    res.erase(unique(res.begin(),res.end()),res.end());
    res=check(res);
    cout<<"FIRST("<<t<<")={ ";
    for(int j=0;j<res.size();j++)
    cout<<res[j]<<" ";
    cout<<"}"<<endl;
    return res;
}

void cin_init();

int main()
{
    cin_init();

    init();
    delete_terminal();
    sign_not_terminal();
    dealing_right();

    first_for_each();
    cout<<endl;
    for(int i=0;i<right_s.size();i++)
    first_for_right(right_s[i]);

    return 0;
}

void cin_init()
{
    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
        right_s.push_back(b);
        p.push_back({a,b});
    }
    p_mirror=p;
}