slrgrammar.cpp

编译原理代码 包括正规式匹配LR文法分析语义分析

		{
			if (!IsInString(protemp,'e'))
			{
				temp[len++] = 'e';
				temp[len] = '\0';
			}
		}
	}
	len = strlen(temp);
	for (i=0;i<len;i++)
	{
		for (j=i+1;j<len;j++)
		{
			if (temp[i] == temp[j])
			{
				temp[j] = temp[len-1];
				temp[len-1] = '\0';
				len--;
			}
		}
	}
	return temp;
}
// 求出FOLLOW 集合
char * LRParse::Follow(char ch)
{
	int count=0,len=0;
	int i=0,j=0,k=0;
	bool flag = false;
	char *protemp = new char[20];
	char *temp = new char[20];
	strcpy(protemp,"\0");
	strcpy(temp,"\0");
	Production pro;
	if (ch == gra->GetstartState())
	{
		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;k<len;k++)
					{
						if (temp[k]=='e')
						{
							temp[k] = temp[len-1];
							temp[len-1] = '\0';
							len--;
							break;
						}
					}
					if (IsInString(First(protemp),'e')&&(pro.From!=ch))
					{
						strcat(temp,Follow(pro.From));
					}
					flag = false;
				}
			}
		}
	}
	len = strlen(temp);
	for (i=0;i<len-1;i++)
	{
		for (j=i+1;j<len;j++)
		{
			if (temp[i] == temp[j])
			{
				temp[j] = temp[len-1];
				temp[len-1] = '\0';
				len--;
			}
		}
	}
	return temp;
}
// 输出FIRST和Follow集合
void LRParse::OutPutFirstFollow()
{
	int i=0,len=0;
 	char temp[30];
	FirstFollow *ff = new FirstFollow[NumOfNonTeminal];
	strcpy(temp,"\0");
	// 求出FIRST和Follow集合
	for (i=0;i<NumOfNonTeminal;i++)
	{
		temp[len++] = NonTeminalSymbol[i];
		temp[len] = '\0';
		len = 0;
		ff[i].ch = NonTeminalSymbol[i];
		// 求出FIRST集合
	 	strcpy(ff[i].first,First(temp));
		// 求出Follow集合
		strcpy(ff[i].follow,Follow(NonTeminalSymbol[i]));
	}
	cout<<endl;
	// 输出FIRST 和 Follow集合
	cout<<"\n First集合：";
	for (i=0;i<NumOfNonTeminal;i++)
	{
		cout<<"\n First("<<ff[i].ch<<")："<<ff[i].first;
	}
	cout<<endl;
	cout<<"\n Follow集合：";
	for (i=0;i<NumOfNonTeminal;i++)
	{
		cout<<"\n Follow("<<ff[i].ch<<")："<<ff[i].follow;
	}
	cout<<endl;
	delete ff;
}
// 获取ch 在数组中的位置
int LRParse::GetPos(char * str,char ch)
{
	int len = strlen(str);
	for (int i=0;i<len;i++)
	{
		if (ch == str[i])
			break;
	}
	return i;
}
// 看是否是终结符
bool LRParse::IsTeminal(char ch)
{
	if (!isupper(ch))
	{
		return true;
	}
	else
	{
		return false;
	}
}
//构造分析表
void LRParse::FormParseTable()
{
	int i,j,k,pos=0;
	char ch,flag;
	// 用于测试
	char *follow = new char[20];
	Grammar gr,temp;
	Production pro;	
	// 消除左递归
	Grammar *g = gra;
	gra = ELRecrusion(g);

	NumOfItems = item->GetNumOfItems();
	pt = new ParseTable(InputSymbol,NonTeminalSymbol,NumOfItems);
	for (i=0;i<item->GetNumOfItems();i++)
	{
		gr = item->GetItem(i);
		for (j=0;j<gr.GetNumOfGra();j++)
		{
			pro = gr.GetProduction(j);
			pos = GetPos(pro.To,'.');
			// 移进动作
			if (pos < (int)strlen(pro.To)-1)
			{
				ch = GetNextOfDot(pro.To);
				temp = Goto(gr,ch);
				if (isupper(ch))
				{
					flag = 'N';
				}
				else
				{
					flag = 's';
				}
				if (!pt->Add(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 请按任意键继续......"<<endl;
	getch();
}
// 作出一个表达式在分析表下的动作
void LRParse::MadeMoves(char * str)
{
	int i,j,step=0;
	int itemCount=0;
	int len=0,len1=0;
	int stemp;
	bool flag = false;
	char stackTemp[128];
	int outtemp=0;
	char ip;
	TableElem act;
 	Production pro;
	stack<char> * stch = new stack<char>(0);
	stack<int> * ststate = new stack<int>(0);
	cout<<endl;
	cout<<"\n 下面是对"<<str<<"进行分析所做的移动：";
	cout<<"\n ━━━━━━━━━┯━━━━━━━━━┯━━━━━━━━━";
	cout<<"\n    STACK          │     输   入      │     输 出 ";
	cout<<"\n ━━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━";
	strcat(str,"$");
	len = strlen(str);
	len1 = 0;
	ststate->push(0);
	stackTemp[len1++] = '0';
	stackTemp[len1] = '\0';
	flag = false;
	step=0;
	i=0;
	itemCount = 0;
	while(true)
	{
		cout<<endl;
		cout<<" ("<<(step<10?" ":"")<<step<<") "<<stackTemp;
		for (j=0;j<13-(int)strlen(stackTemp);j++)
		{
			cout<<" ";
		}
		cout<<"│";
		for (j=0;j<18-len+i;j++)
		{
			cout<<" ";
		}
		for (j=i;j<len;j++)
		{
			cout<<str[j];
		}
		cout<<"│";
		ip = str[i];
 		stemp = ststate->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 "<<pro.From<<"→"<<pro.To;
			}
			else if (act.ch == 'A')
			{
				cout<<"accept";
				cout<<"\n ━━━━━━━━━┷━━━━━━━━━┷━━━━━━━━━";
				cout<<"\n 检测成功!";
				break;
			}
			else
			{
			 	Error();
				break;
			}
			step++;
		}
		else
		{
		 	Error();
			break;
		}
	}
	stch->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): "<<endl;
//		ch = getch();
//	}while(ch == 'y'||ch == 'Y');
//	cout<<"\n 按任意键退出....";
//	cout<<endl;
//	getch();
}

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

// 主函数
void main()
{
	char ch;
	do
	{
		// 输入表达式
        system("cls");
		LRParse lr;
		lr.Run();
		cout<<"\n 是否继续?(Y/N): "<<endl;
		ch = getch();
	}while(ch == 'y'||ch == 'Y');
	cout<<"\n 按任意键退出....";
	cout<<endl;
	getch();
}