📄 grammar.cpp
字号:
#include "stdafx.h"
#include "Grammar.h"
#include "Set.h"
Grammar::Grammar(void)
{
cStart = '\0';
P.clear();
nVn = 0;
nVt = 0;
nP = 0;
pCanEmptyTable = 0;
pPredictTable = 0;
iIsLL1 = 0;
}
Grammar::~Grammar(void)
{
if (pCanEmptyTable != 0)
delete [] pCanEmptyTable;
if (pPredictTable != 0)
delete [] pPredictTable;
}
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)
{
if (p == "#")
return;
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.push_back(cTemp);
strLeft += cTemp;
}
cTemp = p.at(++iPos);
for(i = iPos + 1; i < p.length(); i ++)
{
cTemp = p[i];
//strRight.push_back(cTemp);
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]))&&(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]))&&(strTest[j]!='@'))
return false;
}
}
return flag;
}
void Grammar::GeneratePredictTable()
{
MakeCanReachEmptyTable();
CalculateFirstSet();
CalculateFollowSet();
CalculateSelectSet();
if(IsLegalLL1Grammar())
{
MakePredictTable();
}
}
string Grammar::OutputHTML()
{
char szTempPath[MAX_PATH];
char szTempName[MAX_PATH];
::GetTempPath(100,szTempPath);
::GetTempFileName(szTempPath,"LL1",0,szTempName);
CStdioFile out;
CString temp;
out.Open(szTempName, CFile::modeCreate | CFile::modeWrite);
out.WriteString("<html>\n");
out.WriteString("<head>\n");
out.WriteString("<title>Untitled Document</title>\n");
out.WriteString("<meta http-equiv=\"Content-Type\" content=\"text/html; charset=gb2312\">\n");
out.WriteString("</head>\n");
out.WriteString("<body bgcolor=\"#FFFFFF\" text=\"#000000\">\n");
out.WriteString("<p>下面是你输入的文法G：<br>\n");
temp = "非终结符号集合为：{ ";
for(int i = 0; i < nVn -1; i++)
{
//temp.AppendChar(Vn.GetAt(i));
temp += Vn.GetAt(i);
temp += ", ";
}
//temp.AppendChar(Vn.GetAt(nVn-1));
temp += Vn.GetAt(nVn-1);
temp += " }<br>\n";
out.WriteString(temp);
temp = "终结符符号集合为：{ ";
for(i = 0; i < nVt -1; i++)
{
//temp.AppendChar(Vt.GetAt(i));
temp += Vt.GetAt(i);
temp += ", ";
}
//temp.AppendChar(Vt.GetAt(nVt-1));
temp += Vt.GetAt(nVt-1);
temp += " }<br>\n";
out.WriteString(temp);
temp = "G[";
//temp.AppendChar(cStart);
temp += cStart;
temp += "]:<br>\n";
out.WriteString(temp);
for(i = 0; i < nP; i ++)
{
out.WriteString(P[i].GetLeft().c_str());
out.WriteString("->");
out.WriteString(P[i].GetRight().c_str());
out.WriteString("<br>\n");
}
out.WriteString("<br>可以推出空串的非终结符集合为：{ ");
temp = "";
for(i = 0; i < nVn; i ++)
{
if(CanReachEmpty(Vn.GetAt(i)))
{
CString t;
t.Format("%c, ", Vn.GetAt(i));
temp += t;
}
}
if (temp.GetLength() !=0)
{
temp = temp.Left(temp.GetLength()-2);
}
temp += " }<BR>\n";
out.WriteString(temp);
out.WriteString("<br>非终结符号的FIRST集合：<br>\n");
for(i = 0; i < nVn; i ++)
{
out.WriteString("FIRST(");
temp = "";
//temp.AppendChar(Vn.GetAt(i));
temp += Vn.GetAt(i);
temp += ") = { ";
for(int j = 0; j < FirstSet[i].Size() - 1; j ++)
{
//temp.AppendChar(FirstSet[i].GetAt(j));
temp += FirstSet[i].GetAt(j);
temp += ", ";
}
//temp.AppendChar(FirstSet[i].GetAt(FirstSet[i].Size()-1));
temp += FirstSet[i].GetAt(FirstSet[i].Size()-1);
temp += " }<br>\n";
out.WriteString(temp);
}
out.WriteString("<br>非终结符号的FOLLOW集合：<br>\n");
for(i = 0; i < nVn; i ++)
{
out.WriteString("FOLLOW(");
temp = "";
//temp.AppendChar(Vn.GetAt(i));
temp += Vn.GetAt(i);
temp += ") = { ";
for(int j = 0; j < FollowSet[i].Size() - 1; j ++)
{
//temp.AppendChar(FollowSet[i].GetAt(j));
temp += FollowSet[i].GetAt(j);
temp += ", ";
}
//temp.AppendChar(FollowSet[i].GetAt(FollowSet[i].Size()-1));
temp += FollowSet[i].GetAt(FollowSet[i].Size()-1);
temp += " }<br>\n";
out.WriteString(temp);
}
out.WriteString("<br>各产生式的SELECT集合：<br>\n");
unsigned int iMaxLength = 0;
for(i = 0; i < nP; i ++)
{
iMaxLength = (iMaxLength >= P[i].GetRight().length())?iMaxLength:(P[i].GetRight().length());
out.WriteString("SELECT(");
out.WriteString(P[i].GetLeft().c_str());
out.WriteString("->");
out.WriteString(P[i].GetRight().c_str());
temp = ") = { ";
for(int j = 0; j < SelectSet[i].Size() - 1; j ++)
{
//temp.AppendChar(SelectSet[i].GetAt(j));
temp += SelectSet[i].GetAt(j);
temp += ", ";
}
//temp.AppendChar(SelectSet[i].GetAt(SelectSet[i].Size()-1));
temp += SelectSet[i].GetAt(SelectSet[i].Size()-1);
temp += " }<br>\n";
out.WriteString(temp);
}
if(IsLegalLL1Grammar())
{
out.WriteString("<br><b>输入的文法是一个LL(1)文法。</b><br>");
iMaxLength ++;
iMaxLength *= 12;
out.WriteString("下面是生成的预测分析表：<BR>\n");
out.WriteString("<table border=\"1\" cellpadding=\"0\" cellspacing=\"0\" style=\"border-collapse: collapse\" bordercolor=\"#111111\">\n");
out.WriteString("<tr>\n");
out.WriteString("<td nowrap width=\"25\"> </td>\n");
for(int i = 0; i < nVt; i ++)
{
temp.Format("<td nowrap width=\"25\"> %c</td>\n", Vt.GetAt(i));
out.WriteString(temp);
}
temp.Format("<td nowrap width=\"%u\"> #</td>\n", iMaxLength);
out.WriteString(temp);
out.WriteString("</tr>\n");
for(int x = 0; x < nVn; x ++)
{
out.WriteString("<tr>\n");
temp.Format("<td nowrap width=\"25\"> %c</td>\n", Vn.GetAt(x));
out.WriteString(temp);
for(int y = 0; y < nVt + 1; y ++)
{
temp.Format("<td nowrap width=\"%u\"> %s</td>\n", iMaxLength, ((pPredictTable[x*(nVt+1)+y] == -1)?" ":P[pPredictTable[x*(nVt+1)+y]].GetRight().c_str()));
out.WriteString(temp);
}
out.WriteString("</tr>\n");
}
out.WriteString("</table>\n");
}
else
{
out.WriteString("<br><font color= \"#ff0000\"<b>输入的文法不是LL(1)文法，不能生成预测分析表<b></font><br>\n");
}
out.WriteString("</body>\n");
out.WriteString("</html>");
out.Close();
return szTempName;
}
void Grammar::MakeCanReachEmptyTable()
{
if (pCanEmptyTable != 0)
delete [] pCanEmptyTable;
pCanEmptyTable = new CanEmpty[nVn];
for(int i = 0; i < nVn; i ++)
pCanEmptyTable[i] = UNDEFINED;
bool * pDeleteFlag = new bool[nP];
for (i = 0; i< nP; i ++)
pDeleteFlag[i] = false;
for (i = 0; i < nP; i ++)
{
if(pDeleteFlag[i])
continue;
string pl, pr;
pl = P[i].GetLeft();
pr = P[i].GetRight();
if (pr == "@")
{
pCanEmptyTable[Vn.FindPos(pl[0])] = CANTRUE;
pDeleteFlag[i] = true;
for (int j = 0; j < nP; j ++)
{
if (pDeleteFlag[j])
continue;
if (P[j].GetLeft() == pl)
pDeleteFlag[j] = true;
}
continue;
}
for(unsigned int j = 0; j < pr.length(); j ++)
{
if(Vt.Find(pr[j]))
{
pDeleteFlag[i] = true;
bool bDeleteFlag = true;
for (int k = 0; k < nP; k ++)
{
if (!pDeleteFlag[k])
{
if (P[k].GetLeft() == pl)
{
bDeleteFlag = false;
break;
}
}
}
if (bDeleteFlag)
{
pCanEmptyTable[Vn.FindPos(pl[0])] = CANFALSE;
}
break;
}
}
}
bool bRepeat;
do
{
bRepeat = false;
for(int i = 0; i < nP; i ++)
{
if (pDeleteFlag[i])
continue;
string pl, pr;
pl = P[i].GetLeft();
pr = P[i].GetRight();
Set set;
for(unsigned int j = 0; j < pr.length(); j ++)
set.Insert(pr[j]);
for(j = 0; j < pr.length(); j ++)
{
char cN = pr[j];
int k;
if(Vn.Find(cN))
{
bool bDelete;
switch(pCanEmptyTable[Vn.FindPos(cN)])
{
case CANTRUE:
set.Delete(cN);
if(set.IsEmpty())
{
pCanEmptyTable[Vn.FindPos(pl[0])] = CANTRUE;
bRepeat = true;
for (int k = 0; k < nP; k ++)
{
if (pDeleteFlag[k])
continue;
if (P[k].GetLeft() == pl)
pDeleteFlag[k] = true;
}
}
break;
case CANFALSE:
pDeleteFlag[i] = true;
bDelete = true;
for (k = 0; k < nP; k ++)
{
if (!pDeleteFlag[k])
{
if (P[k].GetLeft() == pl)
{
bDelete = false;
break;
}
}
}
if (bDelete)
{
pCanEmptyTable[Vn.FindPos(pl[0])] = CANFALSE;
bRepeat = true;
}
break;
case UNDEFINED:
break;
}
}
}
}
}while(bRepeat);
delete [] pDeleteFlag;
}
void Grammar::CalculateFirstSet()
{
if(pCanEmptyTable == 0)
MakeCanReachEmptyTable();
for(int i = 0; i < nVn; i ++)
{
Set tempSet;
FirstSet.push_back(tempSet);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -