winsuanfudoc.cpp

算符优先实验,可以输入文法

// WinsuanfuDoc.cpp : implementation of the CWinsuanfuDoc class
//

#include "stdafx.h"
#include "Winsuanfu.h"

#include "WinsuanfuDoc.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CWinsuanfuDoc

IMPLEMENT_DYNCREATE(CWinsuanfuDoc, CDocument)

BEGIN_MESSAGE_MAP(CWinsuanfuDoc, CDocument)
	//{{AFX_MSG_MAP(CWinsuanfuDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CWinsuanfuDoc construction/destruction

charstack s;

CWinsuanfuDoc::CWinsuanfuDoc()
{
	ClearDoc();
}

void CWinsuanfuDoc::ClearDoc()
{
	int i,j;

	memset(buffer, 0, sizeof(buffer));
	pnum = 0;
	Vn.Empty();
	Vt.Empty();
	Start.Empty();

	for(i=0; i<100; i++)	
		for(j=0; j<100; j++)
		{
			F[i][j]=false;
			L[i][j]=false;
			table[i][j]=0;
		}	

	for(i=0; i<100; i++)
	{
		p6[i].pleft=0;
		p6[i].pright.Empty();
	}
}

CWinsuanfuDoc::~CWinsuanfuDoc()
{
}

BOOL CWinsuanfuDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CWinsuanfuDoc serialization

void CWinsuanfuDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CWinsuanfuDoc diagnostics

#ifdef _DEBUG
void CWinsuanfuDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CWinsuanfuDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CWinsuanfuDoc commands
void CWinsuanfuDoc::fill_VnVtStart()
{
	Start += p6[0].pright[1];

	for(int i=0; i<pnum; i++)
	{
		if(Vn.Find(p6[i].pleft) == -1)
			Vn+=p6[i].pleft;
		for(int j=0; j<p6[i].pright.GetLength(); j++)
		{
			if(isupper(p6[i].pright[j]))
			{
				if(Vn.Find(p6[i].pright[j]) == -1)
					Vn+=p6[i].pright[j];
			}else
				if(Vt.Find(p6[i].pright[j]) == -1)
					Vt+=p6[i].pright[j];
		}
	}
}


int CWinsuanfuDoc::ConvertP(CString str)
{	
	int i=0;
	int retpos=0;
	int orpos=0;
	int arrowpos=0;
	CString s,temps1,temps2;

	if(str.Find('#') == -1)
	{
		str.TrimLeft();
		if(!isupper(str[0])) return -1;

		temps1.Empty();
		temps1+="$->#";
		temps1+=str[0];
		temps1+="#\r\n";
		
		str.Insert(0,temps1);				
		temps1.Empty();
	}

	s+=str;
	s+="\r\n";

	retpos = s.Find("\r\n");
	while(retpos!=-1) 
	{
		temps1=s.Left(retpos);
		
		s.Delete(0, retpos+2);
		retpos = s.Find("\r\n");

		if(temps1.IsEmpty()) continue;
	
		temps1.TrimLeft();
		arrowpos=temps1.Find("->");
		if(temps1.Left(arrowpos).GetLength()!=1)
		{
			MessageBox(NULL,"非上下文无关文法！","CWinsuanfuDoc::ConvertP",MB_ICONEXCLAMATION);
			return -1;
		}
		
		char pleft=temps1.Left(arrowpos)[0];	
		temps1.Delete(0, arrowpos+2);

		temps1+='|';
		orpos = temps1.Find('|');
		while(orpos != -1) 
		{
			temps2=temps1.Left(orpos);				
			if(temps2.IsEmpty()) continue;

			temps2.TrimLeft();
			temps2.TrimRight();
			p6[i].pleft=pleft;
			p6[i].pright=temps2;

			temps1.Delete(0, orpos+1);
			orpos = temps1.Find('|');
			i++;
		}//while '|'		
	
	}//while 0d 0a
	pnum = i;

	fill_VnVtStart();

	return pnum;
}


CString CWinsuanfuDoc::display_G()
{
	CString str;
	
	str += "Vn={" + Vn + "}\r\n";
	str += "Vt={" + Vt + "}\r\n";
	str += "S={" + Start + "}\r\n";

	for(int i=0; i<pnum; i++)
	{
		str += p6[i].pleft;
		str += " -> ";
		str += p6[i].pright;
		str += "\r\n";		
	}

	return str;
}

void CWinsuanfuDoc::InsertF(char p, char a)
{
	int p1=Vn.Find(p);
	int a1=Vt.Find(a);
	
	ASSERT(p1!=-1 && a1!=-1);

	if(!F[p1][a1])
	{
		F[p1][a1] = true;
		s.push(p,a);
	}
}

void CWinsuanfuDoc::InsertL(char p, char a)
{
	int p1=Vn.Find(p);
	int a1=Vt.Find(a);
	
	ASSERT(p1!=-1 && a1!=-1);

	if(!L[p1][a1])
	{
		L[p1][a1] = true;
		s.push(p,a);
	}
}

void CWinsuanfuDoc::FirstVt()
{
	char a0,a1;
	int row = Vn.GetLength();
	int col = Vt.GetLength();

	for(int i=0; i<row; i++)
		for(int j=0; j<col; j++)
			F[i][j] = false;

	for(i=0; i<pnum; i++)
	{
		a0=p6[i].pright[0];
		if(Vt.Find(a0) != -1)
		{
			InsertF(p6[i].pleft, a0);
			continue;
		}
		
		if(p6[i].pright.GetLength() <= 1) continue;

		a1=p6[i].pright[1];
		if(Vn.Find(a0) != -1 && Vt.Find(a1) != -1)
			InsertF(p6[i].pleft, a1);
	}

	while(!s.empty())
	{
		char q, a;		
		s.pop(q, a);
		for(i=0; i<pnum; i++)
			if(p6[i].pright[0]  == q)
				InsertF(p6[i].pleft, a);

	}

}

void CWinsuanfuDoc::LastVt()
{
	char a0,a1;
	int row = Vn.GetLength();
	int col = Vt.GetLength();

	for(int i=0; i<row; i++)
		for(int j=0; j<col; j++)
			L[i][j] = false;

	for(i=0; i<pnum; i++)
	{
		a0=p6[i].pright.Right(1)[0];
		if(Vt.Find(a0) != -1)
		{
			InsertL(p6[i].pleft, a0);
			continue;
		}
		
		if(p6[i].pright.GetLength() <= 1) continue;

		a1=p6[i].pright.Right(2)[0];
		if(Vn.Find(a0) != -1 && Vt.Find(a1) != -1)
			InsertL(p6[i].pleft, a1);
	}

	while(!s.empty())
	{
		char q, a;		
		s.pop(q, a);
		for(i=0; i<pnum; i++)
			if(p6[i].pright.Right(1)[0]  == q)
				InsertL(p6[i].pleft, a);

	}
}


void CWinsuanfuDoc::createtable(CString str)
{
	ClearDoc();
	
	int findspace = str.Find(' ');
	while(findspace!=-1)
	{
		str.Delete(findspace,1);
		findspace = str.Find(' ');
	}

	if(ConvertP(str) == -1) return;
	FirstVt();
	LastVt();
	
	int vtnum = Vt.GetLength();
	
	for(int j=0; j<pnum; j++)
	{
		for(int i=0; i<p6[j].pright.GetLength()-1; i++)
		{
			char xi = p6[j].pright[i];
			char xi1 = p6[j].pright[i+1];
			int pxi = Vt.Find(xi);
			int pxi1 = Vt.Find(xi1);

			if(pxi != -1 && pxi1 != -1) 
			{
				if(table[pxi][pxi1] == 0)
					table[pxi][pxi1] = '=';
				else
				{
					MessageBox(NULL, "不是算符优先文法", NULL, MB_ICONEXCLAMATION);
					return;
				}
				continue;
			}

			if(i+2 < p6[j].pright.GetLength())
			{
				char xi2 = p6[j].pright[i+2];
				int pxi2 = Vt.Find(xi2);

				if(pxi != -1 && pxi1 == -1 && pxi2 != -1)
				{
					if(table[pxi][pxi2] == 0)
						table[pxi][pxi2] = '=';
					else
					{
						MessageBox(NULL, "不是算符优先文法", NULL, MB_ICONEXCLAMATION);
						return;
					}
				}
			}

			if(pxi != -1 && pxi1 == -1)
			{
				pxi1 = Vn.Find(xi1);
				ASSERT(pxi1 != -1);
				for(int k=0; k<vtnum; k++)
					if(F[pxi1][k]) 
					{
						if(table[pxi][k] == 0)
							table[pxi][k] = '<';
						else
						{
							MessageBox(NULL, "不是算符优先文法", NULL, MB_ICONEXCLAMATION);
							return;
						}
					}
				continue;
			}
			
			if(pxi == -1 && pxi1 != -1)
			{
				pxi = Vn.Find(xi);
				ASSERT(pxi != -1);
				for(int k=0; k<vtnum; k++)
					if(L[pxi][k])
					{
						if(table[k][pxi1] == 0)
							table[k][pxi1] = '>';
						else
						{
							MessageBox(NULL, "不是算符优先文法", NULL, MB_ICONEXCLAMATION);
							return;
						}
					}
			}
		} 
	}
}

CString CWinsuanfuDoc::display_firstvt()
{	
	char p, a;
	CString str;

	int row = Vn.GetLength();
	int col = Vt.GetLength();

	for(int i=0; i<row; i++)
	{
		p = Vn[i];
		str += "FIRSTVT(";
		str +=  p;
		str += ") = {";
		for(int j=0; j<col; j++)
			if (F[i][j])
			{
				a = Vt[j];
				str += a;
				str += " ";
			}
		str+= "}\r\n";
	}
	return str;
}

CString CWinsuanfuDoc::display_lastvt()
{
	char p, a;
	CString str;

	int row = Vn.GetLength();
	int col = Vt.GetLength();

	for(int i=0; i<row; i++)
	{
		p = Vn[i];
		str += "LASTVT(";
		str += p;
		str += ") = {";
		for(int j=0; j<col; j++)
			if (L[i][j])
			{
				a = Vt[j];
				str += a;
				str += " ";
			}
		str += "}\r\n";
	}
	
	return str;
}

CString CWinsuanfuDoc::display_table()
{
	CString str;

	str+="文法 \r\n";
	str+=display_G();

	str+="\r\nFIRSTVT和LASTVT \r\n";
	str+=display_firstvt();
	str+=display_lastvt();

	int row = Vt.GetLength();
	int col = Vt.GetLength();

	str += "\r\n算符优先表\r\n";
	for(int i=0; i<=col; i++)
		str += "----+";
	str+="\r\n";

	str+="    |";
	
	for(i=0; i<col; i++)
	{
		str += Vt[i];
		str += "   |";
	}
	str+="\r\n";

	for(i=0; i<=col; i++)
		str+="----+";
	str+="\r\n";
	
	for(i=0; i<row; i++)
	{
		str += Vt[i];
		str += "   |";
		for(int j=0; j<col; j++)
		{
			str+=table[i][j]?table[i][j]:' ';
			str+="   |";
		}
		str += "\r\n";
		for(j=0; j<=col; j++)
			str += "----+";
		str+="\r\n";
	}
	return str;
	
}


int CWinsuanfuDoc::mymatch(CString str)
{
	int ret=-1;
	
	//首先找出最匹配的产生式，即终结符全部匹配
	for(int i=0; i<pnum; i++)
	{
		//长度匹配
		if(p6[i].pright.GetLength() != str.GetLength()) continue;

		for(int j=0; j<str.GetLength(); j++)
		{
			if(str[j] == p6[i].pright[j]) continue;

			int sj=Vt.Find(str[j]);				//字符串
			int pj=Vt.Find(p6[i].pright[j]);	//产生式

			if((sj==-1 && pj!=-1) || 
				(sj!=-1 && pj==-1)) break;		//一个是终结符一个是非终结符
			if(sj != -1 && pj != -1) break;		//终结符不匹配
		}

		if(j>=str.GetLength()) break;
	}
	
	if(i >= pnum) return -1;

	//然后看str能否归约到这个产生式
	int matchpos = i;
	int count =0;
	while(p6[matchpos].pright.Compare(str)!=0)
	{
		if(count++ > pnum) return -1;

		for(int j=0; j<str.GetLength(); j++)
		{
			if(str[j] == p6[matchpos].pright[j]) continue;

			for(i=0; i<pnum; i++)
			{
				if(p6[i].pright.GetLength() == 1 &&
					p6[i].pright[0] == str[j])
				{
					str.Delete(j);
					str.Insert(j, p6[i].pleft);	
					break;
				}
			}
			if(i < pnum) break;
		}
	}

	
	return matchpos;
}

CString CWinsuanfuDoc::analyzer(CString str)
{
	if(str.Find('#')==-1) str+='#';

	int row=0;
	int i=0,k=0,j=0;
	int pa,pq,pj;
	char a,q;
	CString s;
	CString endstr;
	CString retstr;
	CString tmpstr;

	retstr = "步骤		栈		输入串		动作	原因\r\n";
	retstr +="-------------------------------------------------------------\r\n";

	s += '#';
	endstr += '#';
	endstr += Start;
	
	while(1)
	{
		tmpstr.Empty();
		tmpstr.Format("%d\t%10s%20s", row, s, str.Right(str.GetLength()-i));
		retstr+=tmpstr;

		row++;
		a=str[i];
		if(a == '#')
		{
			if(s.Compare(endstr) == 0)
				break;
			
			if(s.GetLength() == 2)
			{
				int r=mymatch(s.Right(1));
				int count=0;
				while(p6[r].pleft != Start[0] && count++ < pnum)				
					r=mymatch(s.Right(1));	
				
				if(p6[r].pleft != Start[0])
				{
					MessageBox(NULL, "error1", "analysis", MB_ICONEXCLAMATION);
					break;
				}

				s.Delete(1);
				s.Insert(1, Start);

				tmpstr.Empty();
				tmpstr.Format("%14s  LastVn\r\n","归约");
				retstr += tmpstr;

				continue;
			}
		}
		

		if(Vt.Find(s[k]) != -1)
			j=k;
		else
			j=k-1;

		if(j<0)
		{
			MessageBox(NULL, "error2", "analysis", MB_ICONEXCLAMATION);
					break;
		}
		
		pa=Vt.Find(a);
		pj=Vt.Find(s[j]);
		ASSERT(pa!=-1 && pj!=-1);
		if(table[pj][pa] == '>')
		{
			tmpstr.Empty();
			tmpstr.Format("%14s     %c%c%c\r\n","归约",Vt[pj],table[pj][pa],Vt[pa]);
			retstr += tmpstr;

			do
			{
				q=s[j];
				pq=Vt.Find(q);

				if(Vt.Find(s[j-1])!=-1) j-=1;
				else j-=2;			

				pj=Vt.Find(s[j]);
				ASSERT(pj != -1 && pq != -1);				
			}
			while(table[pj][pq] == '>' || table[pj][pq] == '=');

			//归约
			for(int len=0; len<pnum; len++)
			{
				if(p6[len].pright.Compare(s.Right(s.GetLength()-j-1)) == 0)
					break;
			}
			
			if(len >= pnum)
			{				
				len = mymatch(s.Right(s.GetLength()-j-1));
				if(len == -1)
				{
					MessageBox(NULL, "error3", "analysis", MB_ICONEXCLAMATION);
					break;
				}				
			}

			k=j+1;			
			s.Delete(k, s.GetLength()-k);
			s+=p6[len].pleft;
			continue;
		}

		if(table[pj][pa] == '<' || table[pj][pa] == '=')
		{			
			tmpstr.Empty();
			tmpstr.Format("%14s     %c%c%c\r\n","移进",Vt[pj],table[pj][pa],Vt[pa]);
			retstr += tmpstr;

			k++;
			s += a;
		}
		if(table[pj][pa] == 0)
		{
			tmpstr.Empty();
			tmpstr.Format("error:%c和%c没有优先关系\r\n",Vt[pj],Vt[pa]);

			MessageBox(NULL, tmpstr, "analysis", MB_ICONEXCLAMATION);
					break;
		}
		i++;
	}
	
	retstr += "\r\n";

	return retstr;
}