zmm.cpp

编译原理的LR语法分析器

// Zmm.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Zmm.h"
#include "string.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// The one and only application object

CWinApp theApp;

using namespace std;

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
	int nRetCode = 0;

	// initialize MFC and print and error on failure
	if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
	{
		// TODO: change error code to suit your needs
		cerr << _T("Fatal Error: initialization failed") << endl;
		nRetCode = 1;
	}
	else
	{
		// TODO: code your application's behavior here.
		CString strHello;
		strHello.LoadString(IDS_HELLO);
		cout <<"\t\t\t\t"<<(LPCTSTR)strHello<< endl<<endl;
		GetData();
		if(!FirstFollow())
			cout<<_T("构造FIRST和FOLLOW失败！")<<endl;
		else
		{
			cout<<"\n\t\t"<<_T("FIRST集和FOLLOW集如下：")<<endl<<endl;
			for(int i=0;i<mline;i++)
			{
				cout<<_T("FRIST(")<<unendchar[i]<<_T(")={")<<(LPCTSTR)first[i]<<"}"<<"\t\t";
				cout<<_T("FOLLOW(")<<unendchar[i]<<_T(")={")<<(LPCTSTR)follow[i]<<"}"<<endl;
			}
			cout<<endl;
			if(!StartUpM())
				cout<<_T("预测分析表建立失败！")<<endl;
		    else 
			{
			    int i,j,k;
			    cout<<"\n\t\t\t\t"<<_T("预测分析表")<<endl<<"\t";
			    for(i=0;i<mcol;i++)
				    cout<<endchar[i]<<"\t";
			    cout<<endl<<endl;
			    for(i=0;i<mline;i++)
				{
				    cout<<unendchar[i]<<"\t";
				    for(j=0;j<mcol;j++)
					{
					    k=M[i][j];
					    if(k!=-1)
						    cout<<(LPCTSTR)produce[k]<<'\t';
					    else cout<<_T("NULL")<<"\t";
					}
				    cout<<endl<<endl;
				}
			    char temp[255];int length=0;
			    while(1)
				{
				    ctop=itop=0;
				    cout<<_T("请输入表达式(以单个字母为变量),并以回车结束输入,字符串exit结束程序!")<<endl;
				    cout<<">>";cin>>temp;
				    if(!strcmp(temp,"exit"))
					    break;
				    length=strlen(temp);
				    inputstack[itop]='#';
				    itop++;
				    for(int i=length-1;i>-1;i--)
					{
					    if(temp[i]!=' ')
						    inputstack[itop]=temp[i];
					    itop++;
					}
				    if(!Analyse())
					    cout<<"\n\t\t\t\t"<<_T("表达式出错！")<<endl<<endl;
				    else cout<<"\n\t\t\t\t"<<_T("分析成功！")<<endl<<endl;
				}              
			}
		}
	}
	return nRetCode;
}


bool StartUpM()
{
	char ch;
	int A,T,a,i,j,k;
	M=(int**)new int[mline];
	for(i=0;i<mline;i++)
		M[i]=new int[mcol];
	for(i=0;i<mline;i++)
		for(j=0;j<mcol;j++)
			M[i][j]=-1;
	i=0;
	while(i<plen)
	{
		ch=produce[i][0];
		A=Isunendchar(ch);
		if(A==-1)
			return false;
		ch=produce[i][3];
		T=Isunendchar(ch);
		if(T!=-1)
		{
			for(j=0;j<strlen(first[T]);j++)
			{
				ch=first[T][j];
				if(ch!='0')
				{
					a=Isendchar(ch);
				    if(a==-1)
						return false;
				    if(M[A][a]==-1)
						M[A][a]=i;
				}
			}
		}
		else if(ch=='0')
		{
			for(k=0;k<strlen(follow[A]);k++)
			{
				ch=follow[A][k];
				a=Isendchar(ch);
				if(a==-1)
					return false;
				if(M[A][a]==-1)
					M[A][a]=i;
			}
		}
		else if((a=Isendchar(ch))!=-1)M[A][a]=i;
		else return false;
		i++;
	}
	return true;
}

int Isendchar(char ch)
{
	for(int i=0;i<mcol;i++)
		if(endchar[i]==ch)
			return i;
	return -1;
}

int Isunendchar(char ch)
{
	for(int i=0;i<mline;i++)
		if(unendchar[i]==ch)
			return i;
	return -1;
}

bool Analyse()
{
	int count=0;
	chstack[ctop]='#';
	ctop++;
	chstack[ctop]='E';
	ctop++;
	cout<<_T("步骤")<<"\t"<<_T("符号栈")<<"\t\t\t"<<_T("输入串")<<"\t\t\t"<<_T("所用产生式")<<endl;
	Display(count,false,0);count++;
	int A,a,sn,i,length;
	char ich,cch;
	bool flag;
	while(1)
	{
		ich=inputstack[itop-1];
		if((a=Isendchar(ich))!=-1);
		else if((ich>='a'&&a<='z')||(ich>='A'&&a<='Z')){ich='i';a=Isendchar(ich);}
		else return false;
		cch=chstack[ctop-1];
		if(cch=='#')
		{
			if(cch==ich)break;
			else return false;
		}
		else if(Isendchar(cch)!=-1)
		{
			if(cch==ich)
			{
				itop--;ctop--;
				Display(count,false,0);
			}
		}
		else if((A=Isunendchar(cch))!=-1&&((sn=M[A][a])!=-1))
		{
			ctop--;flag=false;
			length=strlen(produce[sn]);
			for(i=3;i<length;i++)
				if(produce[sn][i]=='0')
					flag=true;
			if(flag)Display(count,true,sn);
			else
			{
				for(i=length-1;i>2;i--)
				{
					chstack[ctop]=produce[sn][i];
					ctop++;
				}
				Display(count,true,sn);
			}
		}
		else return false;
		count++;
	}
	return true;
}

void Display(int count,bool pro,int sn)
{
	inputstack[itop]=chstack[ctop]='\0';
	cout<<count<<"\t";
	cout<<chstack<<"\t\t\t";
	cout<<inputstack<<"\t\t\t";
	if(pro)
		cout<<(LPCTSTR)produce[sn];
	cout<<endl;
}

bool FirstFollow()
{
	int i,j,k,sn,p,strlen;
	CString temp="";
	char uch,ech;
	for(i=0;i<mline;i++)
	{
		first.Add(temp);
		follow.Add(temp);
	}
	char S=unendchar[0];//对于开始符号S，要置#于FOLLOW(S)中
//***********************************构造FIRST****************************************//
	p=0;
	while(p<mline)
	{
		uch=unendchar[p];
		sn=0;
		while(sn<plen)
		{
			if(produce[sn][0]==uch)
			{
				ech=produce[sn][3];
				if(endchar.Find(ech)!=-1)
				{
					if(first[p].Find(ech)==-1)
						first[p]+=ech;
				}
				else
				{
					if((i=unendchar.Find(ech))!=-1)
					{
						if(p>i)
						{
							for(k=0;k<first[i].GetLength();k++)
								if(first[p].Find(first[i][k])==-1)
									first[p]+=first[i][k];
							if(first[i].Find('0')!=-1)
							{
							    for(j=4;j<produce[sn].GetLength();j++)
								{
								    ech=produce[sn][j];
								    if((i=unendchar.Find(ech))!=-1)
									{
										if(p>i)
										{
											if(first[i].Find('0')!=-1)
											{
									            for(k=0;k<first[i].GetLength();k++)
								                    if((first[p].Find(first[i][k])==-1)&&(first[i][k]!='0'))
									                    first[p]+=first[i][k];
											}
										    else break;
										}
										else
										{
											if(p==mline-2)
											{
												if(first[i].Find('0')!=-1)
												{
									                for(k=0;k<first[i].GetLength();k++)
								                        if((first[p].Find(first[i][k])==-1)&&(first[i][k]!='0'))
									                        first[p]+=first[i][k];
												}
											}
											else
											{
												unendchar.SetAt(i,uch);
												uch=unendchar[p+1];
						                        unendchar.SetAt(p+1,ech);
												unendchar.SetAt(p,uch);
						                        temp=first[p];first[p]=first[i];first[i]=temp;
												temp=first[p+1];first[p+1]=first[p];first[p]=temp;
						                        goto TURN;
											}
										}
									}
									else break;
								}
								if(j==produce[sn].GetLength())
									if(first[p].Find('0')==-1)
										first[p]+='0';
							}
						} 
						else
						{
						    unendchar.SetAt(i,uch);
						    unendchar.SetAt(p,ech);
						    temp=first[p];first[p]=first[i];first[i]=temp;
						    goto TURN;
						}
					}
					else if(ech=='0')
					{
					    if(first[p].Find(ech)==-1)
						    first[p]+=ech;
					}
					else return false;
				}
			}
			sn++;
		}
		p++;
TURN:   ;
	}
//***********************************构造FOLLOW****************************************//
	follow[unendchar.Find(S)]+="#";
	cyclestack.Empty();
	p=0;int m=0;char pc;
	while(p<mline)
	{
		uch=unendchar[p];
		sn=0;
		while(sn<plen)
		{
			strlen=produce[sn].GetLength();
			for(i=3;i<strlen;i++)
				if(produce[sn][i]==uch)
				    break;
			if(i<strlen)
			{
				if(i<strlen-1)
				{
					pc=produce[sn][i+1];
					m=unendchar.Find(pc);
				}
				if(i==(strlen-1)||((m>-1)&&(first[m].Find('0')!=-1)))//?????????
				{
					if((j=unendchar.Find(produce[sn][0]))!=-1)
					{
						if(p>j)
						{
							for(k=0;k<follow[j].GetLength();k++)
								if(follow[p].Find(follow[j][k])==-1)
									follow[p]+=follow[j][k];
						}
						else if(p==j)goto KIP;
						else
						{
							if(cyclestack.Find(uch)==-1)
							{
								cyclestack+=uch;
							    ech=unendchar[j];
							    unendchar.SetAt(j,uch);
							    unendchar.SetAt(p,ech);
							    temp=follow[p];follow[p]=follow[j];follow[j]=temp;
							    temp=first[p];first[p]=first[j];first[j]=temp;
							    goto JUMP;
							}
							else
							{
								if(sn==plen-1&&follow[j].IsEmpty())
								{
									ech=unendchar[j];
							        unendchar.SetAt(j,uch);
							        unendchar.SetAt(p,ech);
							        temp=follow[p];follow[p]=follow[j];follow[j]=temp;
							        temp=first[p];first[p]=first[j];first[j]=temp;
							        goto JUMP;
								}
								if(sn==plen-1&&!follow[j].IsEmpty())
								{
									cyclestack.Empty();
									for(k=0;k<follow[j].GetLength();k++)
								        if(follow[p].Find(follow[j][k])==-1)
									        follow[p]+=follow[j][k];
									p++;goto JUMP;
								}
								cyclestack.Empty();goto KIP;
							}
						}
					}
					else return false;
					if(i==(strlen-1))
					    goto KIP;
				}
				if(m>-1)
				{
					for(k=0;k<first[m].GetLength();k++)
						if(follow[p].Find(first[m][k])==-1&&first[m][k]!='0')
							follow[p]+=first[m][k];
					goto KIP;
				}
				if(endchar.Find(pc)!=-1)
				{
					if(follow[p].Find(pc)==-1)
						follow[p]+=pc;
				}
				else return false;
			}
KIP:
			sn++;
		}
		p++;
JUMP:   ;
	}

	return true;
}

void GetData()
{
	cout<<_T("产生式格式:非终结符用大写字母表示,终结符用小写字母(只用i表示变量)表示,例E->+FG")<<endl;
	cout<<_T("请输入产生式，以回车结束本次输入，以end结束产生式的输入：")<<endl;
	char temp[512];CString str;
	cout<<">>";cin>>temp;
	while(strcmp(temp,"end"))
	{
		str.Format("%s",temp);
		produce.Add(str);
		cout<<">>";cin>>temp;
	}
	cout<<_T("请输入终结符，并以回车结束：")<<endl;
	cout<<">>";cin>>temp;
	endchar.Format("%s",temp);endchar+="#";
	cout<<_T("请输入非终结符(先输入开始符号)，并以回车结束：")<<endl;
	cout<<">>";cin>>temp;
	unendchar.Format("%s",temp);
	mline=unendchar.GetLength();
	mcol=endchar.GetLength();
	plen=produce.GetSize();

	/*cout<<(LPCTSTR)endchar<<endl<<(LPCTSTR)unendchar<<endl;
	for(int i=0;i<plen;i++)
		cout<<(LPCTSTR)produce[i]<<endl;*/
}