slrgrammar.cpp

编译原理部分代码

		cout<<"\n ━━━┯";
		for (i=0;i<col_t;i++)
		{
			cout<<"━━━━";
		}
		cout<<"┯";
		for (i=0;i<col_n;i++)
		{
			cout<<"━━━━";
		}
		cout<<"\n       │";
		for (i=0;i<col_t-1;i++)
		{
			cout<<"\t";
			if (i == (int)(col_t/2-1))
				cout<<"action  ";
		}
		cout<<" │          goto";
		cout<<"\n       ┝";		
		for (i=0;i<col_t;i++)
		{
			cout<<"━━━━";
		}
		cout<<"┿";
		for (i=0;i<col_n;i++)
		{
			cout<<"━━━━";
		}
		cout<<"\n   状态│";
		for (i=0;i<col_t;i++)
		{
			cout<<"  "<<InputSymbol[i]<<" \t";
		}
		cout<<" │";
		for (i=0;i<col_n;i++)
		{
			cout<<"  "<<NonTerminal[i]<<" \t";
		}
		cout<<"\n ━━━┿";		
		for (i=0;i<col_t;i++)
		{
			cout<<"━━━━";
		}
		cout<<"┿";
		for (i=0;i<col_n;i++)
		{
			cout<<"━━━━";
		}
		for (i=0;i<row;i++)
		{
			cout<<"\n   "<<(i<10?" ":"")<<i<<"  │";
			//action部分
			for (j=0;j<col_t;j++)
			{
				if (!IsEmpty(i,InputSymbol[j]))
				{
					cout<<"  "<<action[i][j].ch<<action[i][j].state<<"\t";
				}
				else
				{
					cout<<"  --\t";
				}
			}
			//goto部分
			cout<<" │";
			for (j=0;j<col_n;j++)
			{
				if (!IsEmpty(i,NonTerminal[j]))
				{
					cout<<"  "<<goTo[i][j]<<"\t";
				}
				else
				{
					cout<<"  --\t";
				}
			}
		}
		cout<<"\n ━━━┷";		
		for (i=0;i<col_t;i++)
		{
			cout<<"━━━━";
		}
		cout<<"┷";
		for (i=0;i<col_n;i++)
		{
			cout<<"━━━━";
		}
	}
};

/////////////////////////////////////////////////

//定义保存first，Follow的类
class FirstFollow
{
public:
	char ch;
	char first[10];
	char follow[10];
};

/////////////////////////////////////////////////

// 建立文法分析表类
class LRParse
{
private:
	Item * item;
	Grammar * egra;
	Grammar * gra;
	ParseTable * pt;
	char InputSymbol[20];
	char NonTeminalSymbol[20];
	char Symbol[40];
	int NumOfTeminal;
	int NumOfNonTeminal;
	int NumOfGrammar;
	int NumOfItems;
	char * First(char *ch);
	char * Follow(char ch);	
	bool IsTeminal(char ch);
	char GetDigitChar(int a);
	int GetCharDigit(char a);
	int ToDigit(char * a);
	char *ToChar(int a);
	void Error();
public:
	void OutPutFirstFollow();
	void OutputItems();
	char GetNextOfDot(char *str);
	char * InsertIndexOf(char *str,int i);
	Production Shift(Production pro);
	Grammar Goto(Grammar g,char ch);
	void FormItems(Grammar *g);
	Grammar E_cloure(Grammar g);
	void ExGrammar();
	void AddDot(Production str);
	LRParse();
	~LRParse();
	void GetGrammar();
	void FormParseTable();
	void OutputParseTable();
	void MadeMoves(char * pt);
	void Run();
	bool IsInString(char *st,char ch);
	int GetPos(char *str,char ch);
	//消除左递归
	Grammar *ELRecrusion(Grammar *g);
};
// 构造函数
LRParse::LRParse()
{
	NumOfItems = 0;
	NumOfTeminal = 0;
	NumOfNonTeminal = 0;
	NumOfGrammar = 0;
	gra = new Grammar();
	egra = new Grammar();
	item = new Item();
}
// 析构函数
LRParse::~LRParse()
{
	delete gra;	
	delete egra;
	delete item;
}
// 获取输入文法
void LRParse::GetGrammar()
{
	int i = 0,j = 0,k = 0;
	int len = 0;
	char lPro;
	char rPro[30];
	char rstr[2];
	cout<<"\n 请你输入文法的条数：";
	cin >>NumOfGrammar;
	cout<<"\n 请输入你的文法\n （如S→DE|a|e 终结符用小写，非终结符用大写）"<<endl;
	NonTeminalSymbol[NumOfNonTeminal++] = 'G';
	for (i=0;i<NumOfGrammar;i++)
	{
		char temp[20];
		cout<<" "<<i+1<<": ";
		lPro = getch();
		if (islower(lPro))
		{
			lPro = toupper(lPro);
		}
		NonTeminalSymbol[NumOfNonTeminal++] = lPro;
		cout<<lPro<<"→";
		cin >>rPro;
		len = strlen(rPro);
		// 把文法分开保存在文法段中
		k = 0;
		if (i == 0)
		{
			gra->SetStartState(lPro);
		}
	 	for (j=0;j<len;j++)
		{
			if (rPro[j] == '|')
			{
				gra->Insert(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;j<len;j++)
		{
			if (!isupper(rPro[j])&&rPro[j]!='|'&&rPro[j]!='e')
			{
				for(k=0;k<NumOfTeminal;k++)
				{
					if (rPro[j] == InputSymbol[k])
						break;
				}
				if (k == NumOfTeminal)
					InputSymbol[NumOfTeminal++] = rPro[j];
			}
		}
	}
	rstr[0] = gra->GetstartState();
	rstr[1] = '\0';
	gra->Insert(0,'G',rstr);
	gra->SetStartState('G');
	NonTeminalSymbol[NumOfNonTeminal] = '\0';
	cout<<"\n 你输入的文法是：";
	Production pro;
	for (i=0;i<gra->GetNumOfGra()-1;i++)
	{
		pro = gra->GetProduction(i);
		for (j=i+1;j<gra->GetNumOfGra();j++)
		{
			Production prod= gra->GetProduction(j);
			if ((pro.From == prod.From)&&(strcmp(pro.To,prod.To)==0))
			{
				gra->Delete(j);
				break;
			}
		}
	}
	for (i=0;i<gra->GetNumOfGra();i++)
	{
		pro = gra->GetProduction(i);
		cout<<"\n "<<i+1<<": "<<pro.From<<"→"<<pro.To;
	}
	cout<<"\n 非终结符是：";
	for (i=0;i<NumOfNonTeminal;i++)
	{
		cout<<NonTeminalSymbol[i]<<"  ";
	}
	cout<<"\n 终结符的：";
	for (i=0;i<NumOfTeminal;i++)
	{
		cout<<InputSymbol[i]<<"  ";
	}
	InputSymbol[NumOfTeminal++] = '$';
	InputSymbol[NumOfTeminal] = '\0';
	cout<<endl;
	strcpy(Symbol,NonTeminalSymbol);
	strcat(Symbol,InputSymbol);
}
// 消除左递归
Grammar *LRParse::ELRecrusion(Grammar *g)
{
	Grammar *gr;
	char ch = 'Q';
	gr = g;
	char temp[20],tempNon[20];
	Production pro,p;
	strcpy(tempNon,NonTeminalSymbol);
	for(int i=0;i<g->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;i<a;i++)
	{
		temp[i] = str[i];
	}
	temp[a] = '.';
	for (i=a;i<(int)strlen(str);i++)
	{
		temp[i+1] = str[i];
	}
	temp[i+1] = '\0';
	return temp;
}
// 向文法中加点
void LRParse::AddDot(Production pro)
{
	int i=0;
	for (i=0;i<=(int)strlen(pro.To);i++)
	{
		egra->Insert(pro.From,InsertIndexOf(pro.To,i));
	}
}
// 扩展文法
void LRParse::ExGrammar()
{
	int i=0,j=0;
	Production pro;
	egra->SetStartState(gra->GetstartState());
	for (i=0;i<gra->GetNumOfGra();i++)
	{
		pro = gra->GetProduction(i);
		AddDot(pro);
	}
	cout<<"\n 扩展后的文法如下：";
	for (i=0;i<egra->GetNumOfGra();i++)
	{
		pro = egra->GetProduction(i);
		cout<<"\n "<<(i+1<10?" ":"")<<i+1<<"：";
		cout<<pro.From<<"→"<<pro.To;
	}
	cout<<endl;
}
// 获取“.”的下一个字符
char LRParse::GetNextOfDot(char *str)
{
	for (int i=0;i<(int)strlen(str);i++)
	{
		if (str[i] == '.')
		{
			break;
		}
	}
	return str[i+1];
}
// 求E-cloure函数
Grammar LRParse::E_cloure(Grammar g)
{
	Grammar gr;
	Production p1,p2;
	gr = g;
 	for (int i=0;i<gr.GetNumOfGra();i++)
	{
		p1 = gr.GetProduction(i);
		for (int j=0;j<egra->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;i<g.GetNumOfGra();i++)
	{
		p = g.GetProduction(i);
		if (GetNextOfDot(p.To) == ch)
		{
			temp = Shift(p);
			gr.Insert(temp.From,temp.To);
		}
	}
	return E_cloure(gr);
}
// 项目集的构造
void LRParse::FormItems(Grammar *g)
{
	int i,j;
	Grammar temp,gtemp;
	Production p;
	p = g->GetStartProduction();
	temp.Insert(p.From,p.To);
	temp = E_cloure(temp);
	item->Insert(temp);
	for (i=0;i<item->GetNumOfItems();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;i<item->GetNumOfItems();i++)
	{
		temp = item->GetItem(i);
		cout<<"\n I"<< i <<"：";
		for (j=0;j<temp.GetNumOfGra();j++)
		{
			if (j != 0)
				cout<<"\n     ";
			p = temp.GetProduction(j);
			cout<< j+1 <<"："<<p.From<<"→"<<p.To;
		}
		cout<<endl;
	}		
}
// 判断字符ch是否在string st中
bool LRParse::IsInString(char *st,char ch)
{
	int len = strlen(st);
	for (int i=0;i<len;i++)
	{
		if (st[i] == ch)
		{
			return true;
		}
	}
	if (i == len)
	{
		return false;
	}
	return true;
}
// 求出FIRST 集合
char * LRParse::First(char *ch)
{
	int count=0,len=0;
	int i=0,j=0,k=0;
	char *protemp = new char[20];
	char *temp = new char[20];
	strcpy(protemp,"\0");
	strcpy(temp,"\0");
	Production pro;
	if (strlen(ch) == 1)
	{
		if (isupper(ch[0]))
		{
			for (j=0;j<(gra->GetNumOfGra());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;k<count;k++)
						{
							protemp[0] = pro.To[k];
							protemp[1] = '\0';
							strcpy(protemp,First(protemp));
							for (i=0;protemp[i]!='\0';i++)
							{
								if (!IsInString(temp,protemp[i]))
								{
									temp[len++] = protemp[i];
									temp[len] = '\0';
								}						
							}
							if (!IsInString(temp, 'e'))
							{
								break;
							}
						}	
						if (k==count)
						{
							if (!IsInString(protemp,'e'))
							{
								temp[len++] = 'e';
								temp[len] = '\0';
							}
						}
					}
				}
			}
		}
		else
		{
			temp[len++] = ch[0];
			temp[len] = '\0';
		}
	}
	else
	{
		count = strlen(ch);
		for (i=0;i<count;i++)
		{
			protemp[0] = ch[i];
			protemp[1] = '\0';
			strcpy(protemp,First(protemp));
			for (i=0;protemp[i]!='\0';i++)
			{
				if (!IsInString(temp,protemp[i]))
				{
					temp[len++] = protemp[i];
					temp[len] = '\0';
				}						
			}
			if (!IsInString(temp, 'e'))
			{
				break;
			}
		}