#include<iostream>
#include<cstdlib>
#include<string>
#include<cctype>
#include<stack>
#include<iomanip>
using std::stack;
using std::setw;
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::right;
//using std::left;
const int count=10;//记录产生式 的最大条数
const int size=20; //每条产生式 的最大长度
int pos=0; //指示空字符的位置
int num=0; //记录当前输入文法的产生式条数
string gene[count];//保存输入的产生式
string vt; //保存终结符
string left; //保存非终结符
int first[count][size]; //记录first表的值
int follow[count][size];//记录follow表的值
//设置first表的值
void ff(const string &str,int n)
{
size_t start=2;
size_t index=0;
size_t count1=0;
do
{
start++;
//如果该条产生式是以终结符开头
if(!isupper(str[start]))
{//将该终结符添加到对应的first中
index=vt.find(str[start]);
first[n][index]=count1;
count1++;
}
else
{
size_t s=start;
int m;
//是以非终结符开头
do
{
m=count-1;
while(m>=0&&str[s]!=gene[m][0])m--;//找到该非终结符对应的索引号
if(first[m][0]==-1)//如果没查找过m条产生式的first则查找
{
ff(gene[m],m);
}
for(int i=1;i<size;i++)//将该非终结符的first/^添加到当前产生式的first中
{
if(first[m][i]!=-1&&i!=pos)
first[n][i]=count1;
}
s++;
//若该终结符包含空字^且后接非终结符
}while(first[m][pos]!=-1&&isupper(str[s]));
if(first[m][pos]!=-1&&str[s]=='|')//如果前面的非终结符都包含^且后面没有字符
first[n][pos]=count1; //将^包含到当前产生式的first中
else if(first[m][pos]!=-1&&!isupper(str[s]))//如果前面的非终结符都包含^且后面接终结符
first[n][vt.find(str[s])]=count1;//将该终结符添到first中
count1++;
}
start=str.find_first_of('|',start);
}while(start!=string::npos);
first[n][0]=1;
}
void ll(const char ch)
{
int m=num-1;
while(m>=0&&gene[m][0]!=ch)m--;//m确定ch所在gene的索引
follow[m][0]=1;
if(m<0)return ;
for(int i=0;i<num;i++)//检查每条产生式的右部
{
size_t j=3;
size_t index=0;
size_t cc=0;
while(1)
{
size_t dex=gene[i].find_first_of(ch,j);//找到i条产生式右部出现ch的位置
if(dex==string::npos)break ;//没找到ch则找下一条产生式
dex++;
//cout<<gene[i][dex]<<endl;
//getchar();
if(dex==gene[i].length())//如果ch位于该条产生式的末尾
{
if(follow[i][0]==-1)
{
ll(gene[i][0]);
}
for(int l=1;l<size;l++)//将该条产生式左部所对应的follow加到m的follow中
if(follow[i][l]!=-1)
follow[m][l]=1;
break; //检查下一条
}
//如果是终结符
else if(cc=vt.find(gene[i][dex]),cc!=string::npos&&cc!=pos)
{
follow[m][cc]=1;
}
//如果是非终结符
else if(cc=left.find(gene[i][dex]),cc!=string::npos)
{
int kk;
do
{
kk=num-1;
//cout<<"i="<<i<<" dex="<<dex<<' ';
//cout<<"gene[i][dex]="<<gene[i][dex]<<endl;
while(kk>=0&&gene[kk][0]!=gene[i][dex])kk--;
//把该非终结符所对应的first/^加到follow中
if(kk<0)break;
for(int ii=1;ii<size;ii++)
{
if(first[kk][ii]!=-1&&ii!=pos)
{
follow[m][ii]=1;
}
}
dex++;
if(dex==gene[i].length())break;
//getchar();
//cout<<"kk="<<kk<<' ';
//cout<<"first[kk][pos]="<<first[kk][pos]<<endl;
//如果该非终结符的first包含^且后面是非终结符,继续循环
}while(first[kk][pos]!=-1&&left.find(gene[i][dex])!=string::npos);
//如果前面的非终结符都可推出^且已达本条产生式的末尾
if(first[kk][pos]!=-1&&dex==gene[i].length())
{
if(follow[i][0]==-1)
{
ll(gene[i][0]);
}
for(int l=1;l<size;l++)//将该条产生式左部所对应的follow加到m的follow中
if(follow[i][l]!=-1)
follow[m][l]=1;
break;
}
//如果前面的非终结符都可推出^且后面是|
else if(first[kk][pos]!=-1&&gene[i][dex]=='|')
{
if(follow[i][0]==-1)
{
ll(gene[i][0]);
}
for(int l=1;l<size;l++)//将该条产生式左部所对应的follow加到m的follow中
if(follow[i][l]!=-1)
follow[m][l]=1;
}
//如果前面的非终结符都可推出^且当前为终结符
else if(first[kk][pos]!=-1&&vt.find(gene[i][dex])!=string::npos&&vt.find(gene[i][dex])!=pos)
{
follow[m][vt.find(gene[i][dex])]=1;
}
}
j=dex+1;
}
}
}
int first1[count][size];
void foutputtable()
{
for(int i=0;i<count;i++)
for(int j=1;j<size;j++)
first1[i][j]=first[i][j];
for( i=0;i<num;i++)
{
if(first1[i][pos]!=-1)
{
for(int j=0;j<size;j++)
if(follow[i][j]!=-1)
first1[i][j]=-2;
}
}
cout<<"预测分析表的内容为:"<<endl;
cout<<" ";
for(i=1;i<vt.length();i++)
if(i!=pos)
cout<<vt[i]<<" ";
cout<<endl;
for( i=0;i<num;i++)
{
cout<<gene[i][0]<<" ";
for(int j=1;j<size;j++)
{
if(j==pos)continue;
if(first1[i][j]!=-1)
{
if(first1[i][j]==-2)
{
cout<<gene[i][0]<<"->^"<<" ";
}
else
{
int c=first1[i][j];
size_t start=3;
size_t end=0;
c++;
string tt;
while(c--)
{
end=gene[i].find_first_of('|',start+1);
if(end==string::npos)end=gene[i].length();
tt=gene[i].substr(start,end-start);
start=end+1;
}
cout<<gene[i][0]<<"->"<<tt;
for(int k=0;k<(8-tt.length()-3);k++)cout<<' ';
}
//cout<<setw(8-tt.length()-3);
}
else
{
cout<<" ";
}
}
cout<<endl;
}
}
void foutput()
{
cout<<"first表的内容为:"<<endl;
for(int i=0;i<num;i++)
{
cout<<gene[i][0]<<" ";
for(int j=1;j<size;j++)
{
if(first[i][j]!=-1)
cout<<vt[j]<<' ';
}
cout<<endl;
}
}
void loutput()
{
cout<<"follow表的内容为:"<<endl;
for(int i=0;i<num;i++)
{
cout<<gene[i][0]<<" ";
for(int j=1;j<count;j++)
{
if(follow[i][j]!=-1)
cout<<vt[j]<<' ';
}
cout<<endl;
}
}
int main(int argc,char * argv[])
{
int i=0,j=0;
for(;i<count;i++)
for(j=0;j<size;j++)
{
first[i][j]=-1;
follow[i][j]=-1;
}
cout<<"请输入文法的条数:";
cin>>num;
cout<<"请输入文法:"<<endl;
for(i=0;i<num;i++)
cin>>gene[i];
//for(i=0;i<num;i++) cout<<endl<<gene[i]<<endl;
for(i=0;i<num;i++)
{
left+=gene[i][0];
}
//cout<<"left="<<left<<endl;
size_t index=0;
vt+='@';
for(i=0;i<num;i++)
{
index=2;
while(index!=string::npos)
{
index++;
index=gene[i].find_first_not_of(left,index);
if(index==string::npos)break;
if(gene[i][index]=='|'||vt.find(gene[i][index])!=string::npos)continue;
vt+=gene[i][index];
}
}
vt+='#';
follow[0][vt.find('#')]=1;
pos=vt.find('^');
//cout<<"pos="<<pos<<endl;
//cout<<"vt="<<vt<<endl;
for(i=0;i<num;i++)
{
if(first[i][0]==-1)
{
ff(gene[i],i);
}
}
foutput();
for(i=0;i<num;i++)
{
if(follow[i][0]==-1)
ll(gene[i][0]);
}
loutput();
foutputtable();
/*for(i=0;i<count;i++)
{
for(int j=0;j<size;j++)
cout<<setw(2)<<first1[i][j]<<' ';
cout<<endl;
}*/
while(1)
{
string str;
cout<<"请输入需要识别的语句:"<<endl;
cin>>str;
str+='#';
stack<char> sta;
sta.push('#');
sta.push(gene[0][0]);
int indecate=0;
char temp=0;
//cout<<"left="<<left<<endl;
//cout<<"vt="<<vt<<endl;
while(!sta.empty())
{
temp=sta.top();
sta.pop();
if(str[indecate]==temp)
{
if(temp=='#')
{
cout<<"该句子能被本文法识别!!!"<<endl;
break;
}
indecate++;
}
else if(left.find(temp)!=string::npos)
{
int cou=0;
while(gene[cou][0]!=temp)cou++;
size_t loc=vt.find(str[indecate]);
if(loc==string::npos)
{
cout<<"该句子不能被本文法识别!!"<<endl;
break;
}