www.pudn.com > SLRGrammar.rar > SLRGrammar.cpp
/***********************************************************
Copyright (c) 2004, RM.RYT. All rights reserved.
Developed in Microsoft Visual C++ 6.0 Enterprise Edition.
***********************************************************/
#include
#include
#include
#include
#include
#include
/////////////////////////////////////////////////
//定义结点类
template class link
{
public:
link* next;
Elem element;
int sign;
link(const Elem& elementValue,link* nextValue = NULL)
{
element = elementValue;
next = nextValue;
sign = -1;
}
link(link* nextValue = NUll)
{
next = nextValue;
sign = -1;
}
};
/////////////////////////////////////////////////
//定义堆栈类
template class stack
{
private:
link *top;
int size;
public:
stack(int sz = DefaultSize)
{
top = NULL;
size = 0;
}
~stack(){ clear(); }
void clear()
{
while(top!=NULL)
{
link* temp = top;
top = top->next;
size = 0;
delete temp;
}
}
//入栈函数
bool push(const Elem& item)
{
top = new link(item,top);
size++;
return true;
}
//出栈函数
Elem pop()
{
Elem item;
if (size == 0)
return false;
item = top->element;
link* temp = top->next;
delete top;
top = temp;
size--;
return item;
}
//获取栈顶元素的值
Elem GetTop() const
{
Elem item;
if(size == 0)
return false;
item = top->element;
return item;
}
//获取堆栈的深度
int length() const
{ return size; }
//判断栈是否为空
bool IsEmpty() const
{ return top == NULL; }
//获取标志位
int GetSign() const
{ return top->sign; }
//设置标志位
void SetSign(int s)
{ top->sign = s; }
};
//////////////////////////////////
//定义产生式的数据结构
class Production
{
public:
char From;
char To[20];
};
//////////////////////////////////
//定义输入文法数据结构
class Grammar
{
private:
char startState;
Production pro[30];
int NumOfGra;
public:
Grammar()
{
NumOfGra = 0;
}
~Grammar()
{
}
//定义重载运算符 ==
bool operator == (Grammar g)
{
if (g.NumOfGra == NumOfGra)
{
bool flag=true;
Production p;
for (int i=0;ipos;i--)
{
pro[i] = pro[i-1];
}
pro[pos].From = fr;
strcpy(pro[pos].To,temp);
NumOfGra++;
return true;
}
//设置和获取开始状态
bool SetStartState(char ch)
{
startState = ch;
return true;
}
//获取文法开始状态
char GetstartState()
{
return startState;
}
//获取开始的产生式
Production GetStartProduction()
{
for (int i=0;ipos;i--)
{
gr[i] = gr[i-1];
}
gr[pos] = g;
NumOfItems++;
return true;
}
//删除一个项目集
bool Delete(Grammar g)
{
for (int i=0;i>NumOfGrammar;
cout<<"\n 请输入你的文法\n （如S→DE|a|e 终结符用小写，非终结符用大写）"<>rPro;
len = strlen(rPro);
// 把文法分开保存在文法段中
k = 0;
if (i == 0)
{
gra->SetStartState(lPro);
}
for (j=0;jInsert(lPro,temp);
k = 0;
strcpy(temp,"\0");
}
else if (j == len-1)
{
temp[k++] = rPro[j];
temp[k] = '\0';
gra->Insert(lPro,temp);
k = 0;
strcpy(temp,"\0");
}
else
{
temp[k++] = rPro[j];
temp[k] = '\0';
}
}
// 获取终结符的数目
for (j=0;jGetstartState();
rstr[1] = '\0';
gra->Insert(0,'G',rstr);
gra->SetStartState('G');
NonTeminalSymbol[NumOfNonTeminal] = '\0';
cout<<"\n 你输入的文法是：";
Production pro;
for (i=0;iGetNumOfGra()-1;i++)
{
pro = gra->GetProduction(i);
for (j=i+1;jGetNumOfGra();j++)
{
Production prod= gra->GetProduction(j);
if ((pro.From == prod.From)&&(strcmp(pro.To,prod.To)==0))
{
gra->Delete(j);
break;
}
}
}
for (i=0;iGetNumOfGra();i++)
{
pro = gra->GetProduction(i);
cout<<"\n "<GetNumOfGra();i++)
{
pro = g->GetProduction(i);
if (IsInString(tempNon,'Q'))
{
ch = (char)('Q'+1);
}
if (pro.From == pro.To[0])
{
p = g->GetProduction(g->GetProDuctionOF(pro.From));
strcpy(temp,p.To);
tempNon[NumOfNonTeminal] = ch;
tempNon[NumOfNonTeminal+1] = '\0';
temp[strlen(pro.To)] = ch;
temp[strlen(pro.To)+1] = '\0';
gr->Delete(i);
gr->Insert(i,ch,temp);
gr->Insert(ch,"e");
for (int i=1;i<(int)strlen(pro.To);i++)
{
temp[i-1] = pro.To[i];
}
temp[i-1] = ch;
gr->Insert(ch,temp);
}
}
return gr;
}
// 把.插入到第a个位置
char * LRParse::InsertIndexOf(char *str, int a)
{
int i=0;
char *temp = new char[20];
for (i=0;iInsert(pro.From,InsertIndexOf(pro.To,i));
}
}
// 扩展文法
void LRParse::ExGrammar()
{
int i=0,j=0;
Production pro;
egra->SetStartState(gra->GetstartState());
for (i=0;iGetNumOfGra();i++)
{
pro = gra->GetProduction(i);
AddDot(pro);
}
cout<<"\n 扩展后的文法如下：";
for (i=0;iGetNumOfGra();i++)
{
pro = egra->GetProduction(i);
cout<<"\n "<<(i+1<10?" ":"")<GetNumOfGra();j++)
{
p2 = egra->GetProduction(j);
if (p2.From == GetNextOfDot(p1.To)&&(GetPos(p2.To,'.') == 0))
{
if (!gr.IsIn(p2))
gr.Insert(p2.From,p2.To);
}
}
}
return gr;
}
// 移动函数
Production LRParse::Shift(Production pro)
{
Production p;
p.From = pro.From;
strcpy(p.To,pro.To);
int i = GetPos(pro.To,'.');
p.To[i] = pro.To[i+1];
p.To[i+1] = pro.To[i];//即'.'
return p;
}
// goto函数处理
Grammar LRParse::Goto(Grammar g, char ch)
{
Grammar gr;
Production p,temp;
for (int i=0;iGetStartProduction();
temp.Insert(p.From,p.To);
temp = E_cloure(temp);
item->Insert(temp);
for (i=0;iGetNumOfItems();i++)
{
temp = item->GetItem(i);
for (j=0;j<(int)strlen(Symbol);j++)
{
gtemp = Goto(temp,Symbol[j]);
if ((!gtemp.IsEmpty())&&(!item->IsIn(gtemp)))
{
item->Insert(gtemp);
}
}
}
}
// 项目集的输出
void LRParse::OutputItems()
{
int i,j;
Grammar temp;
Production p;
cout<<"\n 构造的项目集如下：";
for (i=0;iGetNumOfItems();i++)
{
temp = item->GetItem(i);
cout<<"\n I"<< i <<"：";
for (j=0;jGetNumOfGra());j++)
{
pro = gra->GetProduction(j);
if (ch[0] == pro.From)
{
if (strcmp(pro.To,"e")==0)
{
temp[len++] = 'e';
temp[len] = '\0';
break;
}
else
{
count = strlen(pro.To);
for (k=0;kGetstartState())
{
temp[len++] = '$';
temp[len] = '\0';
}
for (j=0;j<(gra->GetNumOfGra());j++)
{
pro = gra->GetProduction(j);
if (IsInString(pro.To,ch))
{
flag = false;
for (j=0;pro.To[j]!='\0';j++)
{
if (ch == pro.To[j])
{
flag = true;
}
if (flag)
{
count = 0;
for (k=j+1;k<(int)strlen(pro.To);k++)
{
protemp[count++] = pro.To[k];
}
protemp[count] = '\0';
if (strlen(protemp)==0)
{
temp[len++] = 'e';
temp[len] = '\0';
}
strcat(temp,First(protemp));
len = strlen(temp);
for (k=0;kGetNumOfItems();
pt = new ParseTable(InputSymbol,NonTeminalSymbol,NumOfItems);
for (i=0;iGetNumOfItems();i++)
{
gr = item->GetItem(i);
for (j=0;jAdd(i,ch,flag,item->GetPos(temp)))
{
cout<<"\n 语法有冲突，你输入的文法不是SLR文法!";
Error();
}
}
// 归约动作
else
{
if (pro.From == item->GetStartProduction().From&&(strcmp(pro.To,Shift(item->GetStartProduction()).To) == 0))
{
if (!pt->Add(i,'$','A',0))
{
cout<<"\n 语法有冲突，你输入的文法不是SLR文法!";
Error();
}
}
else
{
// 用于测试
follow = Follow(pro.From);
Production p;
p.From = pro.From;
for (int d=0;d<(int)strlen(pro.To)-1;d++)
{
p.To[d] = pro.To[d];
}
p.To[d] = '\0';
for (k=0;k<(int)strlen(follow);k++)
{
if (!pt->Add(i,follow[k],'r',gra->GetPos(p)))
{
cout<<"\n 语法有冲突，你输入的文法不是SLR文法!";
Error();
}
}
}
}
}
}
// 还原文法
gra = g;
}
// 字符转化为数字(数字小于10)
int LRParse::GetCharDigit(char a)
{
switch(a)
{
case '0':
return 0;
break;
case '1':
return 1;
break;
case '2':
return 2;
break;
case '3':
return 3;
break;
case '4':
return 4;
break;
case '5':
return 5;
break;
case '6':
return 6;
break;
case '7':
return 7;
break;
case '8':
return 8;
break;
case '9':
return 9;
break;
default:
return -1;
break;
}
}
//字符转化为数字
int LRParse::ToDigit(char * a)
{
int temp=-1;
if (strlen(a)<=1)
{
temp = GetCharDigit(a[0]);
}
else if (strlen(a)==2)
{
temp = 10*GetCharDigit(a[0]) + GetDigitChar(a[1]);
}
else
{
temp = 100*GetCharDigit(a[0]) + 10*GetDigitChar(a[1])+ GetDigitChar(a[2]);
}
return temp;
}
// 数字转化为字符(数字小于10)
char LRParse::GetDigitChar(int a)
{
switch(a)
{
case 0:
return '0';
break;
case 1:
return '1';
break;
case 2:
return '2';
break;
case 3:
return '3';
break;
case 4:
return '4';
break;
case 5:
return '5';
break;
case 6:
return '6';
break;
case 7:
return '7';
break;
case 8:
return '8';
break;
case 9:
return '9';
break;
default:
return '0';
break;
}
}
// 数字转化为字符
char *LRParse::ToChar(int a)
{
char *temp = new char[4];
if (a<10)
{
temp[0] = GetDigitChar(a);
temp[1] = '\0';
}
else if (a<100)
{
temp[0] = GetDigitChar((int)(a/10));
temp[1] = GetDigitChar(a%10);
temp[2] = '\0';
}
else
{
temp[0] = GetDigitChar((int)(a/100));
temp[1] = GetDigitChar((int)((a%100)/10));
temp[2] = GetDigitChar(a%10);
temp[3] = '\0';
}
return temp;
}
// 出错处理函数
void LRParse::Error()
{
cout<<"\n ━━━━━━━━━┷━━━━━━━━━┷━━━━━━━━━";
cout<<"\n 检测出现错误! 你输入的字符串不是SLR文法。";
cout<<"\n 请按任意键继续......"< * stch = new stack(0);
stack * ststate = new stack(0);
cout<push(0);
stackTemp[len1++] = '0';
stackTemp[len1] = '\0';
flag = false;
step=0;
i=0;
itemCount = 0;
while(true)
{
cout<GetTop();
act = pt->GetAction(itemCount,ip);
if (act.ch != '\0')
{
if (act.ch == 's')
{
stch->push(ip);
ststate->push(act.state);
stackTemp[len1++] = ip;
stackTemp[len1] = '\0';
if (act.state >= 10)
{
strcat(stackTemp,ToChar(act.state));
len1 = strlen(stackTemp);
}
else
{
stackTemp[len1++] = GetDigitChar(act.state);
}
stackTemp[len1] = '\0';
itemCount = act.state;
i++;
cout<<"Shift ";
}
else if (act.ch == 'r')
{
pro = gra->GetProduction(act.state);
for (j=0;j<(int)strlen(pro.To);j++)
{
if (ststate->pop()<10)
{
stackTemp[--len1] = '\0';
}
else if (ststate->pop()<100)
{
stackTemp[--len1] = '\0';
stackTemp[--len1] = '\0';
}
else
{
stackTemp[--len1] = '\0';
stackTemp[--len1] = '\0';
stackTemp[--len1] = '\0';
}
stch->pop();
stackTemp[--len1] = '\0';
}
int s = ststate->GetTop();
stch->push(pro.From);
stackTemp[len1++] = pro.From;
stackTemp[len1] = '\0';
int gotos = pt->GetGoto(s,pro.From);
if (gotos != -1)
{
itemCount = gotos;
ststate->push(gotos);
}
else
{
Error();
break;
}
strcat(stackTemp,ToChar(gotos));
len1 = strlen(stackTemp);
cout<<"Reduce by "<clear();
ststate->clear();
}
// 输出分析表
void LRParse::OutputParseTable()
{
pt->OutPut();
}
// 执行主流程序
void LRParse::Run()
{
char ch;
char Sentence[20];
// 输入文法
GetGrammar();
// 输出FIRST 和 Follow集合
OutPutFirstFollow();
// 构造扩展文法
ExGrammar();
// 构造项目集族
FormItems(egra);
// 输出项目集族
OutputItems();
// 构造分析表
FormParseTable();
// 输出分析表
OutputParseTable();
// 作出一个表达式在分析表下的动作do
do
{
//输入表达式
cout<<"\n\n 请你输入你要验证的字符串：";
cin >>Sentence;
MadeMoves(Sentence);
cout<<"\n 是否继续?(Y/N): "<