句子识别程序(预测分析法).cpp

一个句子识别程序(预测分析法)原程序,是用vc++编写的,很不错哦

#include<iostream.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define maxsize 200
struct cnode
{
	char s[maxsize];
	int top;
};
void push(struct cnode *st,char ch)  //进栈
{
	if (st->top==maxsize-1)
		cout<<"栈上溢出！"<<endl;
	else
	{
		st->top++;
		st->s[st->top]=ch;
	}
}
void pop(struct cnode *st)           //栈顶元素出栈
{
	if (st->top==-1)
		cout<<"栈下溢出！"<<endl;
	else
		st->top--;
}
char readtop(struct cnode *st)       //读栈顶元素
{
	if (st->top==-1)
		cout<<"无栈顶元素！"<<endl;
	else
		return(st->s[st->top]);
}
/*char ptop(struct cnode *st)          //取栈顶元素
{
	char c;
	c=readtop(st);
	pop(st);
	return(c);
}*/
void main()
{
	char string[100][100],ch,VN[500],VT[500];
	int count=0,i=0;
	cout<<"请输入规则,各规则之间以“;”分开，其中空串用“$”表示，并以#作为输入的结束标志："<<endl;
	cin>>ch;
	while(ch!='#')
	{
		if (ch!=';')
		{
			string[count][i]=ch;
			i++;
		}
		else if (ch==';')
		{
			string[count][i]='\0';
			count++;
			i=0;
		}
		cin>>ch;
	}
	string[count][i]='\0';
	int v1=0,v2=0;
	for(i=0;i<=count;i++)
	for(int j=0;j<strlen(string[i]);j++)
	{
		if (string[i][j]<='Z' && string[i][j]>='A')
		{
			int sign=0;
			for(int v11=0;v11<v1;v11++)
				if (string[i][j]==VN[v11])
					sign=1;
			if (sign==0)
			{
		    	VN[v1]=string[i][j];
		    	v1++;
			}
		}
		else if (string[i][j]!=':' && string[i][j]!='=' && string[i][j]!='|' && string[i][j]!='$')
		{
			int sign1=0;
			for(int v22=0;v22<v2;v22++)
				if (string[i][j]==VT[v22])
					sign1=1;
			if (sign1==0)
			{
		    	VT[v2]=string[i][j];
		    	v2++;
			}
		}
	}
	VN[v1]='\0';
	VT[v2]='#';
	v2++;
	VT[v2]='\0';
	char str[200][200],str1[200],str2[200],ch1[200];
	int t=0;
	for(i=0;i<=count;i++)
	{
		int k=0;
    	for(int j=0;j<strlen(string[i]);j++)
		{
			if (string[i][j]!='=')
			{
	        	str1[k]=string[i][j];
				k++;
			}
			else
			{
				str1[k]=string[i][j];
				break;
			}
		}
		for(int q=k+1;q<200;q++)
			str1[q]='\0';
		j++;
		strcpy(ch1,str1);
		int m;
go1:	m=0;
		for(j;j<strlen(string[i]);j++)
		{
			if (string[i][j]!='|')
			{
				str2[m]=string[i][j];
				m++;
			}
			else
			{
				break;
			}
		}
		for(int s=m;s<200;s++)
			str2[s]='\0';
		j++;
		strcat(str1,str2);
		strcpy(str[t],str1);
		t++;
		strcpy(str1,ch1);
		if (j<strlen(string[i]))
		goto go1;
	}
	cout<<"有穷非空的重写规则集合如下："<<endl;
	for(i=0;i<t;i++)
		cout<<"第"<<i<<"条"<<"  "<<str[i]<<endl;
	int M,N,j;
	M=strlen(VN);
	N=strlen(VT);
	int num[200][200];
	cout<<"下面开始构造预测分析表！"<<endl;
	cout<<"此表的第一行终结符（包括“#”）的排列顺序为："<<endl;
	cout<<VT<<endl;
	cout<<"此表的第一列非终结符的排列顺序为："<<endl;
	cout<<VN<<endl;
	cout<<"如果表中的终结符和非终结符所对应的表的元素为一规则，那么请输入它在有穷非空的重写规则集合中相应的行号（行号从0开始计数）："<<endl;
	cout<<"如果表中的终结符和非终结符所对应的表的元素为空，那么请输入-1："<<endl;
	cout<<"  ";
	for(i=0;i<N;i++)
		cout<<VT[i]<<' ';
	cout<<endl;
	for(i=0;i<M;i++)
	{
		cout<<VN[i]<<' ';
    	for(j=0;j<N;j++)
    	cin>>num[i][j];
	}
	int s=-1;
	cout<<"构建的预测分析表如下："<<endl;
	for(i=0;i<M;i++)
	{
		for(j=0;j<N;j++)
		{
			s=num[i][j];
			if (s!=-1)
				cout<<str[s]<<" ";
			else
				cout<<s<<" ";
		}
		cout<<endl;
	}
	struct cnode *stack;
	stack=(struct cnode *)malloc(sizeof(struct cnode));
	stack->top=-1;
	push(stack,'#');
	push(stack,VN[0]);
	cout<<"请输入要识别的句子，并以“#”作为输入的结束符："<<endl;
	char sentence[200],ss;
	for(i=0;i<200;i++)
	{
		cin>>ss;
		if (ss!='#')
			sentence[i]=ss;
		else
			break;
	}
	sentence[i]='#';
	i++;
	sentence[i]='\0';
	int flag=1;
	for(i=0;i<strlen(sentence);i++)
	{
		while(flag==1)
		{
			ss=readtop(stack);
			int sign=0;
			for(j=0;j<strlen(VT);j++)
				if (ss==VT[j])
				{
					sign=1;
					break;
				}
			if (sign==1)
				if (ss==sentence[i])
					if (sentence[i]=='#')
					{
						cout<<"此句能够被识别！"<<endl;
						flag=0;
					}
					else
					{
						pop(stack);
						i++;
						continue;
					}
				else
				{
					cout<<"出现错误,此句不能识别！"<<endl;
					flag=0;
					break;
				}
			else
			{
				int x,y,l;
				for(j=0;j<strlen(VN);j++)
					if (ss==VN[j])
					{
						x=j;
						break;
					}
				for(l=0;l<strlen(VT);l++)
					if (sentence[i]==VT[l])
					{
						y=l;
						break;
					}
                 if (num[x][y]!=-1)
				 {
					 int o;
					 o=num[x][y];
					 pop(stack);
					 for(j=strlen(str[o])-1;j>=0;j--)
						 if (str[o][j]!='=' && str[o][j]!='$')
							 push(stack,str[o][j]);
						 else if (str[o][j]=='=')
							 break;
                     cout<<str[o]<<endl;
				 }
				 else
				 {
					 cout<<"出现错误，此句不能识别！"<<endl;
					 flag=0;
				     break;
				 }
			}
		}
	}
}