#include
#include
using?namespace?std;

#define?max?50
int?NONE=1;
string?stringsnoendend;//非終結符與終結符存儲
int?n;//產生式總數

struct?Chomsky
{
	string?left;
	string?right;?
};?

void?apart（Chomsky?*pint?i）?//分開產生式左右部
{
	int?j;
????for（j=0;j		if（strings[j]==‘-‘）
		{
			p[i].left=strings.substr（0j）;
			p[i].right=strings.substr（j+1strings.length（）-j）;
		}
}
void?VNVT（Chomsky?*p）//求VN和VT
{
	int?ij;
	for（i=0;i	{
		for（j=0;j<（int）p[i].left.length（）;j++）?
		{
			if（（p[i].left[j]>=‘A‘&&p[i].left[j]<=‘Z‘））//非終結符判斷
			{
				if（noend.find（p[i].left[j]）>100）
					noend+=p[i].left[j];?
			}
			else
			{
				if（end.find（p[i].left[j]）>100）
					end+=p[i].left[j];
			}
		}
		for（j=0;j<（int）p[i].right.length（）;j++）?
		{
			if（!（p[i].right[j]>=‘A‘&&p[i].right[j]<=‘Z‘））//終結符判斷
			{
				if（end.find（p[i].right[j]）>100）
					end+=p[i].right[j];
			}
			else?
			{
				if（noend.find（p[i].right[j]）>100）
					noend+=p[i].right[j];
		}
		}
	}
}

int?zero（Chomsky?*p）//0型文法
{
	int?flag（0）count（0）;
????int?ij;
????for（i=0;i	{
		for（j=0;j<（int）p[i].left.length（）;j++）
		{
			if（p[i].left[j]>=‘A‘&&p[i].left[j]<=‘Z‘）?//有否非終結符
				flag++;
		}
		if（flag>0）
		{
			flag=0;
			count++;
		}
		else?
			break;?//左部沒有非終結符，結束
	}
	if（count==n）?
		return?1;?//屬于0型文法
	else
	{
		cout<		NONE=0;
		return?0;
	}
}


int?one（Chomsky?*p）//1型文法
{
	int?flag（0）;
????int?i;
????if（zero（p））
	{
		for（i=0;i		{
			if（p[i].right.length（）			{
				flag++;
				break;
			}
		}
	}
	else
		flag--;
	if（flag>0）
	{
		cout<????????return?0;???//不屬于1型文法
	}
	else?
		if（flag==0）
			return?1;?//屬于1型文法
		else
			return?0;
}


int?two（Chomsky?*p）//2型文法
{
	int?flag（0）;
????int?i;
????if（one（p））
	{
		for（i=0;i			if（（p[i].left.length（）!=1）||!（p[i].left[0]>=‘A‘&&p[i].left[0]<=‘Z‘））?//左部不屬于一個字符或不屬于非終結符
			{
				flag++;
				break;
			}
	}
	else
??????flag--;
	if（flag>0）
	{
		cout<????????return?0;???//不屬于2型文法
	}
	else?
		if（flag==0）
		{
			return?1;?//屬于2型文法
		}
		else
			return?0;
}


int?three（Chomsky?*p）//3型文法
{
int?flag=0;
int?i;
if（two（p））???
{
???for（i=0;i????if（!（p[i].right.length（）==1||p[i].right.length（）==2）||（p[i].right[0]>=‘A‘&&p[i].right[0]<=‘Z‘））?//右部字符個數不是1或2，或首字符是非終結符
????{
?????flag++;
?????break;
????}
????else?
?????if（（p[i].right.length（）==2）&&!（p[i].right[1]>=‘A‘&&p[i].right[1]<=‘Z‘））?//第二個字符不是非終結符
??????{
???????flag++;
???????break;
??????}
}
else
???flag--;
if（flag>0）
{
???cout<<“此文法屬于2型文法，即上下文無關文法。“<???i=n;
???return?0;
}
else?
???if（flag==0）
???{
????cout<<“此文法屬于3型文法，即正規文法。“<????return?1;
???}
???else
????return?0;?
}

void?change（Chomsky?*p）//正規文法到正規式的轉換函數
{
	int?ijmflag;???//合并產生式
	for?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????6703??2014-05-07?17:19??3.cpp
?????文件??????324608??2015-12-13?20:44??編譯原理實驗三：正規文法到正規式的轉換.doc