#include
#include

using?namespace?std;
#define?max?100

typedef?struct?Chomsky?????//定義一個產(chǎn)生式結(jié)構(gòu)體
{
???string?left;?//定義產(chǎn)生式的左部
???string?right;?//定義產(chǎn)生式的右部
}Chomsky;

int?n;//產(chǎn)生式總數(shù)
string?strings;//存儲產(chǎn)生式
string?noend;//存放文法中的非終結(jié)符
string?empty;//存放可以推出空的非終結(jié)符
string?first[max];//存放非終結(jié)符的first集
string?follow[max];//存放非終結(jié)符的follow集
string?select[max];//存放產(chǎn)生式的select集

void?apart（Chomsky?*pint?i）?//分開產(chǎn)生式左右部，i代表產(chǎn)生式的編號
{
	int?j;
????for（j=0;j		if（strings[j]==‘-‘）
		{
			p[i].left=strings.substr（0j）;//從0開始的j長度的子串，即0~j-1
			p[i].right=strings.substr（j+1strings.length（）-j）;//從j+1開始的后面子串
		}
}

/*string?is_empty（Chomsky?*p）//判斷某非終結(jié)符能否直接推出空，空用#代替
{
	//如果可以，返回1
	//不可以，返回0
	int?i;
	string?s;
	for（i=0;i	{
		if?（p[i].right[0]=“#“&&p[i].right.length（）==1）//直接推出空的
		{
			empty=empty+p[i].left;
		}

	}
	s=empty;
	return?s;//s存放能直接推出空的非終結(jié)符

}
string?isempty（Chomsky?*p）//可以間接推出空的非終結(jié)符
{
	int?ij;
	string?s1;
	for（i=0;i	{
		if（is_empty（p）.find（p[i].left）>=0）//若此非終結(jié)符已經(jīng)存在直接推出空那里，在此無需重復(fù)計算
		{
		}
		else
		{
			for（j=0;j<（int）p[i].right.length（）;j++）
			{
				if（is_empty（p）.find（p[i].right.[j]）<0）
				{
				}
			}
			if（j==（int）p[i].right.length（））//如果右部所有符號都在直接推出空那里，則此左部也可以推出空
			{
				s1=s1+p[i].left[0];

			}
		}
		

	}

}*/
void?search（Chomsky?*pint?n）//提取產(chǎn)生式中的非終結(jié)符
{
	int?ij;
	for（i=0;i	{
		if（!（noend.find（p[i].left[0]）>=0&&noend.find（p[i].left[0]）			noend=noend+p[i].left;
		for（j=0;j		{
			if（‘A‘<=p[i].right[j]&&p[i].right[j]<=‘Z‘）
			{
				if（noend.find（p[i].right[j]）>=0&&noend.find（p[i].right[j]）					break;
				else
					noend=noend+p[i].right.substr（j1）;
			}
		}
	}
}


void?First（Chomsky?*pint?nchar?mint?mm）//求文法中非終結(jié)符的First集
{
	int?length=noend.length（）;
	string?f;
	int?ijxy;
	int?flag=0;
	for（i=0;i	{
		if（m==p[i].left[0]）
		{
			if（‘a(chǎn)‘<=p[i].right[0]&&‘z‘>=p[i].right[0]）
				?first[mm]=first[mm]+p[i].right.substr（01）;
			if（p[i].right[0]==‘#‘）
				?first[mm]=first[mm]+p[i].right.substr（01）;
			if（‘A‘<=p[i].right[0]&&‘Z‘>=p[i].right[0]）
			{
				for（j=0;j				{
					if（‘A‘<=p[i].right[j]&&p[i].right[j]<=‘Z‘）flag++;
				}
				if（flag==j）//產(chǎn)生式的右部均為非終結(jié)符
				{
					flag=0;
					for（j=0;j					{
						for（x=0;x							if（p[i].right[j]==p[x].left[0]&&p[x].right[0]==‘#‘）
							{
								flag++;
								break;
							}
					}
					if（flag==j）//產(chǎn)生式右部的全部非終結(jié)符均能推出空
					{
						for（j=0;j						{
							for（x=0;x							{
								if（p[i].right[j]==noend[x]）break;
							}
							y=x;
							if（first[y]==““）First（pnp[i].right[j]x）;
????????????????????????????f=first[y];
							for（x=0;x							{
								if（f[x]==‘#‘）
									{
										if（x==f.length（）-1）f=f.substr（0x）;
										els

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????7068??2014-06-04?17:16??7.cpp
?????文件???????80384??2015-12-13?20:43??編譯原理實(shí)驗七：LL（1）文法的判斷?.doc