grammar.cpp

这是一个关于LR法分析语句的小程序,大家先看看吧,有什么问题我会及时改正

#include "stdafx.h"
#include "Grammar.h"
#include <cassert>
#include <iostream>
using namespace std;

Grammar::Grammar()
{
	cStart = 0;
	P.clear();
	nVn = 0;
	nVt = 0;
	nP = 0;
	nC = 0;
	GoSet.clear();
	pTable = 0;
	iLegal = 0;

}
Grammar::~Grammar()
{
	if (pTable !=0)
		delete []pTable;
}
Grammar::Grammar(const Grammar & g)
{
	if (&g == this)
		return;
	CopyGrammar(g);	
}
const Grammar Grammar::operator = (const Grammar & g)
{
	if (&g != this)
		CopyGrammar(g);
	return *this;
}
void Grammar::CopyGrammar(const Grammar & g)
{
	Vt = g.Vt;
	Vn = g.Vn;
	cStart = g.cStart;
	P = g.P;
	C = g.C;
	GoSet = g.GoSet;
	nVt = g.nVt;
	nVn = g.nVn;
	nP = g.nP;
	nC = g.nC;
	iLegal = g.iLegal;
	if (g.pTable != 0)
	{
		pTable = new Pair[C.size() * (nVt + 1 + nVn)];
		for( int i = 0; i < C.size() * (nVt + 1 + nVn); i++ )
			pTable[i] = g.pTable[i];
	}
}

void Grammar::SetVt(string vt)
{
	for(unsigned int i = 0; i < vt.length(); i ++)
		Vt.Insert(vt[i]);
	nVt = Vt.Size();	
}

void Grammar::SetVn(string vn)
{
	for(unsigned int i = 0; i < vn.length(); i ++)
		Vn.Insert(vn[i]);
	nVn = Vn.Size();
}

void Grammar::SetStart(char start)
{
	if (Vn.Find(start))
		cStart = start;
}

void Grammar::AddPrecept(string p)
{
	string strLeft, strRight;
	char cTemp;
	int iPos = 0;
	for(unsigned int i = 0; i < p.length(); i ++)
	{
		cTemp = p[i];		
		if (cTemp == '-')
		{
			iPos = i;
			break;
		}
		strLeft += cTemp;
		
	}
	cTemp = p.at(++iPos);
	for(i = iPos + 1; i < p.length(); i ++)
	{
		cTemp = p[i];
		strRight += cTemp;
	}
	Precept precept(strLeft,strRight);
	P.push_back(precept);
	nP = (int) P.size();
}

bool Grammar::IsGrammarLegal()
{
	bool flag = false;
	if (!Vn.Find(cStart))
		return false;
	if (P.empty())
		return false;
	for(int i = 0; i < Vn.Size(); i ++)
	{
		if(Vt.Find(Vn.GetAt(i)))
			return false;
	}
	for(i = 0; i < Vt.Size(); i ++)
	{
		if(Vn.Find(Vt.GetAt(i)))
			return false;
	}
	for(i = 0; i < P.size(); i ++)
	{
		string strTest;
		strTest = P[i].GetLeft();
		for(unsigned int j = 0; j < strTest.length(); j ++)
		{
			if ((!Vn.Find(strTest[j]))&&(!Vt.Find(strTest[j])))
				return false;
			if ((j==0)&&(strTest[j] == cStart))
				flag = true;
		}
		strTest = P[i].GetRight();
		for(j = 0; j < strTest.length(); j ++)
		{
			if ((!Vn.Find(strTest[j]))&&(!Vt.Find(strTest[j])))
				return false;
		}
	}
	return flag;
}

bool Grammar::IsInVn(char cChar)
{
	return Vn.Find(cChar);
}

bool Grammar::IsInVt(char cChar)
{
	return Vt.Find(cChar);
}

char Grammar::GetStart()
{
	return cStart;
}

void Grammar::GenerateLR0Table()
{
	EnlargeGrammar();
	MakeProjects();
	if (IsLegalLR0Grammar())
		GenerateTable();
}


void Grammar::EnlargeGrammar()
{
	string strRight;
	strRight = cStart;
	P.insert(P.begin(), Precept("$", strRight));
	Vn.Add('$');
	nP++;
}

void Grammar::MakeProjects()
{
	ProjectSet ps = GetClosure(Pair(0, 0));
	AddProject(ps);
	assert(nC == C.size());
	int iPos = 0;
	while (iPos < nC)
	{
		ps = C[iPos];
		for (int i = 0; i < ps.Size(); i++)
		{
			Precept p = GetProject(ps.GetAt(i));
			string strRight = p.GetRight();
			assert(strRight[ps.GetAt(i).two] == '.');
			if (ps.GetAt(i).two < strRight.length() - 1)
			{
				ProjectSet tempSet = MakeGoSet(iPos, strRight[ps.GetAt(i).two + 1]);
				GoData gd;
				gd.iFrom = iPos;
				gd.cChar = strRight[ps.GetAt(i).two + 1];
				if(AddProject(tempSet))
				{
					gd.iTo = nC - 1;
				}
				else
				{
					int j;
					for (j = 0; j < nC; j++)
						if (C[j] == tempSet)
							break;
					assert(j != nC);
					gd.iTo = j;
				}
				GoSet.push_back(gd);
			}
		}
		iPos++;
	}
	for (int i = 0; i < nC; i++)
	{
		ProjectSet ps = C[i];
		int iP = 0;
		int iR = 0;
		for (int j = 0; j < ps.Size(); j++)
		{
			Pair p = ps.GetAt(j);
			string strRight = P[p.one].GetRight();
			if (p.two == strRight.size())
			{
				if (strRight.at(p.two - 1) != cStart)
					iR++;
			}
			else
			{
				if (p.one > 0)
					if (Vt.Find(strRight[p.one - 1]))
						iP++;
			}
		}
		assert(iLegal == 0);
		if (((iP != 0) && (iR !=0 )) || (iR >= 2))
		{
			iLegal = 2;
			break;
		}
	}
	if (iLegal == 0)
		iLegal = 1;
}

void Grammar::GenerateTable()
{
	bool bLegal = true;
	pTable = new Pair[C.size() * (nVt + 1 + nVn)];
	int i;
	for (i = 0; i < C.size() * (nVt + 1 + nVn); i++ )
		pTable[i] = Pair(0, 0);
	assert (nC == C.size());
	for( i = 0; i < nC; i++ )
	{
		ProjectSet ps = C[i];
		for( int j = 0; j < ps.Size(); j++)
		{
			Pair p = ps.GetAt(j);
			string strRight = P[p.one].GetRight();
			if (p.two < strRight.length())
			{
				if (Vt.Find(strRight[p.two]))
				{
					int t = GetGoSet(i, strRight[p.two]);
					assert (t != -1);
					bLegal &= FillTable(i, strRight[p.two], Pair('S', t));
				}
				else
				{
					if (Vn.Find(strRight[p.two]))
					{
						int t;
						t =	GetGoSet(i, strRight[p.two]);
						assert (t != -1);
						bLegal &= FillTable(i, strRight[p.two], Pair(t,0));
					}
					else
					{
						assert(false);
					}
				}
			}
			else
			{
				if (p == Pair(0, 1))
				{
					bLegal &= FillTable(i, '#', Pair('a', 0));
				}
				else
				{
					for( int x = 0; x < nVt + 1; x++ )
					{
						bLegal &= FillTable(i, ((x != nVt)?Vt.GetAt(x):'#'), Pair('R', p.one));
					}
				}
			}
		}
	}
	assert(bLegal);
}

Precept Grammar::GetProject(const Pair & pair1)
{
	Precept temp;
	if (pair1.one >= nP)
		return temp;
	string strRight = P[pair1.one].GetRight();
	if (strRight.length() < pair1.two)
		return temp;
	return Precept(P[pair1.one].GetLeft(), strRight.substr(0, pair1.two) + "." + strRight.substr(pair1.two));
}

ProjectSet Grammar::GetClosure(const Pair & pair1)
{
	int iNum = pair1.one;
	int iPos = pair1.two;
	ProjectSet temp;
	temp.Insert(Pair(iNum, iPos));
	int iCount = 0;
	while (iCount < temp.Size())
	{
		iNum = temp.GetAt(iCount).one;
		iPos = temp.GetAt(iCount).two;
		string strRight = P[iNum].GetRight();
		if (iPos < strRight.length())
		{
			if (Vn.Find(strRight[iPos]))
			{
				for (int j = 0; j < nP; j++)
				{
					if (P[j].GetLeft()[0] == strRight[iPos])
						temp.Insert(Pair(j,0));
				}
			}
		}
		iCount++;
	}
	return temp;
}

ProjectSet Grammar::MakeGoSet(int iI, char cChar)
{
	ProjectSet rtn;
	ProjectSet ps = C[iI];
	for (int i = 0; i < ps.Size(); i++)
	{
		Pair p = ps.GetAt(i);
		string strRight = P[p.one].GetRight();
		if (p.two < strRight.length())
		{
			if(strRight[p.two] == cChar)
			{
				rtn.Add(GetClosure(Pair(p.one, p.two + 1)));
			}
		}
	}
	return rtn;
}
int Grammar::GetGoSet(int iI, char cChar)
{