grammar.cpp

ll(1)文法,我们编译原理的课程设计实验报告,非常 好,得 A 的

	bool flag;
	do
	{
		flag = false;
		string strLeft, strRight;
		for(int i = 0; i< nP; i ++)
		{
			strLeft = P[i].GetLeft();
			strRight = P[i].GetRight();
			int iPos = Vn.FindPos(strLeft[0]);
			if (Vn.Find(strLeft[0]))
			{
				if ((strRight == "@")||(Vt.Find(strRight[0])))
					flag |= FirstSet[iPos].Insert(strRight[0]);
				else
				{
					unsigned int j = 0;
					do
					{
						char cChar = strRight[j];
						if (Vn.Find(cChar))
						{
							flag |= (FirstSet[iPos].Add((GetFirstSet(cChar) - Set('@'))) != 0);
							if (!CanReachEmpty(cChar))
								break;
						}
						j ++;
					}while(j < strRight.length());
					if (j == strRight.length())
						flag |= FirstSet[iPos].Insert('@');
				}
			}
		}
	}while(flag);
}

void Grammar::CalculateFollowSet()
{
	if(pCanEmptyTable == 0)
		MakeCanReachEmptyTable();
	for(int i = 0; i < nVn; i ++)
	{
		Set tempSet;
		FollowSet.push_back(tempSet);
	}
	FollowSet[Vn.FindPos(cStart)].Insert('#');
	bool flag = false;
	do
	{
		flag = false;
		for(int i = 0; i < nP; i ++)
		{
			string strLeft, strRight;
			strLeft = P[i].GetLeft();
			strRight = P[i].GetRight();

			for ( unsigned int j = 0; j < strRight.length() - 1; j++)
			{
				char cChar = strRight[j];
				if (Vn.Find(cChar))
				{
					string temp;
					for(unsigned int k = j + 1; k < strRight.length(); k++)
						//temp.push_back(strRight[k]);
						temp += strRight[k];
					Set firstset = GetFirstSet(temp);
					flag |= (FollowSet[Vn.FindPos(cChar)].Add(firstset - Set('@')) != 0);
					if (CanReachEmpty(temp))
					{
						flag |= (FollowSet[Vn.FindPos(cChar)].Add(GetFollowSet(strLeft[0])) != 0);
					}
				}
			}
			if (Vn.Find(strRight[strRight.length() -1]))
				flag |= (FollowSet[Vn.FindPos(strRight[strRight.length() -1])].Add(GetFollowSet(strLeft[0])) != 0);
		}
	}while(flag);
}

void Grammar::CalculateSelectSet()
{
	for(int i = 0; i < nP; i ++)
	{
		Set selectSet;
		selectSet = GetFirstSet(P[i].GetRight());
		if (CanReachEmpty(P[i].GetRight()))
			selectSet.Add(GetFollowSet(P[i].GetLeft()[0]));
		SelectSet.push_back(selectSet);
	}
}

bool Grammar::IsLegalLL1Grammar()
{
	if (iIsLL1 == 1)
		return true;
	if (iIsLL1 == 2)
		return false;
	bool * pDeleteFlag = new bool[nP];
	for(int i = 0; i < nP; i ++)
		pDeleteFlag[i] = false;
	for(i = 0; i < nP; i ++)
	{
		if (pDeleteFlag[i])
			continue;
		string strLeft = P[i].GetLeft();
		Set set = SelectSet[i];
		Set setb;
		for(int j = i + 1; j < nP; j ++)
		{
			if (pDeleteFlag[i])
				continue;
			if (P[j].GetLeft() == strLeft)
			{
				setb = SelectSet[j];
				if (set.Add(setb) != setb.Size())
				{
					iIsLL1 = 2;
					return false;
				}
			}
		}
	}
	delete [] pDeleteFlag;
	iIsLL1 = 1;
	return true;
}



bool Grammar::CanReachEmpty(string str)
{
	bool flag = true;
	if (str != "@")
	{
		for (unsigned int i = 0; i < str.length(); i++)
		{
			int iPos = Vn.FindPos(str[i]);
			if (iPos != -1)
			{
				if (pCanEmptyTable[iPos] == CANFALSE)
				{
					flag = false;
					break;
				}
			}
			else
			{
				flag = false;
				break;
			}
		}
	}
	return flag;
}

bool Grammar::CanReachEmpty(char cChar)
{
	int iPos;
	if((iPos = Vn.FindPos(cChar)) != -1)
	{
		if(pCanEmptyTable[iPos] == CANTRUE)
			return true;
		else
			return false;
	}
	else
		return false;
		
}

Set Grammar::GetFirstSet(char cChar)
{
	if(Vt.Find(cChar) || (cChar == '@'))
	{
		Set set;
		set.Insert(cChar);
		return set;
	}
	else
	{
		return FirstSet[Vn.FindPos(cChar)];	
	}
}

Set Grammar::GetFirstSet(string str)
{
	Set firstset;
	if ((Vt.Find(str[0]))||(str == "@"))
	{
		firstset.Insert(str[0]);
	}
	else
	{
		unsigned int i;
		for (i = 0; i < str.length(); i++)
		{
			char cChar = str[i];
			if (Vn.Find(cChar))
			{
				firstset.Add(GetFirstSet(cChar) - Set('@'));
				if (!CanReachEmpty(cChar))
					break;
			}
			else
			{
				firstset.Insert(cChar);
				break;
			}
				
		}
		if (i == str.length())
			firstset.Insert('@');
	}
	return firstset;
}

Set Grammar::GetFollowSet(char cChar)
{
	int iPos;
	if ((iPos = Vn.FindPos(cChar)) != -1)
		return FollowSet[iPos];
	else
		return Set();
}

void Grammar::MakePredictTable()
{
	Set Select;
	pPredictTable = new int [nVn*(nVt+1)];
	for(int i = 0; i < nVn*(nVt+1); i++)
		pPredictTable[i] = -1;
	for(i = 0; i < nP; i++)
	{
		Select = SelectSet[i];
		for(int j = 0; j < Select.Size(); j++)
		{
			if (Select.GetAt(j) != '@')
				pPredictTable[Vn.FindPos(P[i].GetLeft()[0])*(nVt+1)+((Select.GetAt(j) == '#')?(nVt):(Vt.FindPos(Select.GetAt(j))))] = i;
		}
	}
}

void Grammar::Output(char * pFilename)
{
	if (pFilename == 0)
		return;
	CStdioFile OutFile;
	OutFile.Open(pFilename, CFile::modeCreate | CFile::modeWrite);
	CString t;
	OutFile.WriteString("[Terminator]\n");
	for(int i = 0; i < nVt; i++)
	{
		t.Format("%c\n", Vt.GetAt(i));
		OutFile.WriteString(t);
		
	}
	OutFile.WriteString("\n[NonTerminator]\n");
	for(i = 0; i < nVn; i++)
	{
		t.Format("%c\n", Vn.GetAt(i));
		OutFile.WriteString(t);
	}
	OutFile.WriteString("\n[Starter]\n");
	t.Format("%c", cStart);
	t += "\n\n[Precept]\n";
	OutFile.WriteString(t);
	for(i = 0; i < nP; i++)
	{
		t.Format("%s->%s\n", P[i].GetLeft().c_str(), P[i].GetRight().c_str());
		OutFile.WriteString(t);
	}
	OutFile.WriteString("\n[CanReachEmptySet]\n");
	for(i = 0; i < nVn; i ++)
	{
		if(CanReachEmpty(Vn.GetAt(i)))
		{
			t.Format("%c\n", Vn.GetAt(i));
			OutFile.WriteString(t);
		}
	}
	OutFile.WriteString("\n[FirstSet]\n");
	for(i = 0; i < nVn; i ++)
	{
		t.Format("%c = ",Vn.GetAt(i));
		for(int j = 0; j < FirstSet[i].Size() - 1; j ++)
		{
			//t.AppendChar(FirstSet[i].GetAt(j));
			t += FirstSet[i].GetAt(j);
			t += ", ";
		}
		//t.AppendChar(FirstSet[i].GetAt(FirstSet[i].Size()-1));
		t += FirstSet[i].GetAt(FirstSet[i].Size()-1);
		t += " \n";
		OutFile.WriteString(t);
	}
	OutFile.WriteString("\n[FollowSet]\n");
	for(i = 0; i < nVn; i ++)
	{
		t.Format("%c = ",Vn.GetAt(i));
		for(int j = 0; j < FollowSet[i].Size() - 1; j ++)
		{
			//t.AppendChar(FollowSet[i].GetAt(j));
			t += FollowSet[i].GetAt(j);
			t += ", ";
		}
		//t.AppendChar(FollowSet[i].GetAt(FollowSet[i].Size()-1));
		t += FollowSet[i].GetAt(FollowSet[i].Size()-1);
		t += " \n";
		OutFile.WriteString(t);
	}
	OutFile.WriteString("\n[SelectSet]\n");
	for(i = 0; i < nP; i ++)
	{
		t.Format("%s->%s = ",P[i].GetLeft().c_str(),P[i].GetRight().c_str());
		for(int j = 0; j < SelectSet[i].Size() - 1; j ++)
		{
			//t.AppendChar(SelectSet[i].GetAt(j));
			t += SelectSet[i].GetAt(j);
			t += ", ";
		}
		//t.AppendChar(SelectSet[i].GetAt(SelectSet[i].Size()-1));
		t += SelectSet[i].GetAt(SelectSet[i].Size()-1);
		t += " \n";
		OutFile.WriteString(t);
	}
	OutFile.WriteString("\n");
	if(IsLegalLL1Grammar())
	{
		OutFile.WriteString("[PredictTable]\n");
		for(int x = 0; x < nVn; x ++)
		{
			for(int y = 0; y < nVt + 1; y ++)
			{
				if (pPredictTable[x*(nVt+1)+y] != -1)
				{
					t.Format("%c, %c = %s\n", Vn.GetAt(x), ((y != nVt)?Vt.GetAt(y):'#'), P[pPredictTable[x*(nVt+1)+y]].GetRight().c_str());
					OutFile.WriteString(t);
				}
			}

		}
	}
	OutFile.Close();
}

Grammar::Grammar(const Grammar & g)
{
	if (&g == this)
		return;
	Vt = g.Vt;
	Vn = g.Vn;
	cStart = g.cStart;
	P = g.P;
	FirstSet = g.FirstSet;
	FollowSet = g.FollowSet;
	SelectSet = g.SelectSet;
	nVt = g.nVt;
	nVn = g.nVn;
	nP = g.nP;
	if (g.pCanEmptyTable !=0)
	{
		pCanEmptyTable = new CanEmpty[nVn];
		for (int i = 0; i < nVn; i ++)
			pCanEmptyTable[i] = g.pCanEmptyTable[i];
	}
	if(g.pPredictTable != 0)
	{
		pPredictTable = new int[nVn * (nVt + 1)];
		for (int i = 0; i < nVn * (nVt + 1); i ++)
			pPredictTable[i] = g.pPredictTable[i];
	}
}

const Grammar Grammar::operator = (const Grammar & g)
{
	if (&g == this)
		return * this;
	Vt = g.Vt;
	Vn = g.Vn;
	cStart = g.cStart;
	P = g.P;
	FirstSet = g.FirstSet;
	FollowSet = g.FollowSet;
	SelectSet = g.SelectSet;
	nVt = g.nVt;
	nVn = g.nVn;
	nP = g.nP;
	if (g.pCanEmptyTable !=0)
	{
		pCanEmptyTable = new CanEmpty[nVn];
		for (int i = 0; i < nVn; i ++)
			pCanEmptyTable[i] = g.pCanEmptyTable[i];
	}
	if(g.pPredictTable != 0)
	{
		pPredictTable = new int[nVn * (nVt + 1)];
		for (int i = 0; i < nVn * (nVt + 1); i ++)
			pPredictTable[i] = g.pPredictTable[i];
	}
	return *this;
}

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

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

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

Precept Grammar::GetToDo(char vn, char vt)
{
	int i;
	if ((i = pPredictTable[Vn.FindPos(vn) * (nVt + 1) + ((vt == '#')?nVt:Vt.FindPos(vt))]) != -1)
		return P[i];
	else
	{
		return Precept("","");
	}
}