软件学院编译原理第二次上机求first和follow集

第三次上机作业 1. 编写First和Follow函数，实现其求解过程。 （1）FIRST集合计算方法： ① 若Xa..， 则将终结符ａ加入FIRST(X)中； ② 若X，则将加入FIRST(X)中； ③ 若XY…，且Y属于非终结符，则将FIRST(Y)\{}加入到FIRST(X)中；（注：“\”表示除去元素，即FIRST(Y)中的非元素加入到FIRST(X)中。以下同理。） ④ 若XY1Y2..YK,且Y1,Y2,..Yi-1都是非终结符，且Y1,Y2,..Yi-1的FIRST集合中均包含，则将FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特别地，若Y1~YK均有产生式，则将加到FIRST(X)中。 （2）FOLLOW集合计算方法： ① 对文法开始符号S，置$于FOLLOW(S)中。 ② 若有AB，则将FIRST()\{} 加入FOLLOW(B)中。 （此处 可以为空） ③ 若A B 或A B ,且  * （即 属于FIRST()），则将 FOLLOW(A)加入FOLLOW(B)中（此处 可以为空）。 2. 测试文法： A->BCDE B->aBA|ε C->F|ε D->b|c|ε E->e|ε F->d|ε

#include
#include
#include
#include
using namespace std;
#define MAX 50
int NONE[MAX] = { 0 };
string strings;       //产生式
string Vn;           //非终结符
string Vt;           //终结符
string first[MAX];  //存放每个终结符的first集
string First[MAX];  //存放每个非终结符的first集
string Follow[MAX]; //存放每个非终结符的follow集
int N;               //产生式个数
struct STR
{
	string left;
	string right;
};

void rec（STR *p）                 //识别Vn和Vt
{
	int i j;
	for （i = 0;i < N;i++）                                              //第i个产生式
	{
		for （j = 0;j < （int）p[i].left.length（）;j++）//左侧
		{
			if （（p[i].left[j] >= ‘A‘&&p[i].left[j] <= ‘Z‘））                //左侧第j个字母是大写
			{
				if （Vn.find（p[i].left[j]）>100）                             //Vn里没找到返回很大的值
					Vn += p[i].left[j];
			}
			else
			{
				if （Vt.find（p[i].left[j]）>100）                           //小写字母放Vt
					Vt += 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 （Vt.find（p[i].right[j]）>100）
					Vt += p[i].right[j];
			}
			else
			{
				if （Vn.find（p[i].right[j]） > 100）
					Vn += p[i].right[j];
			}
		}
	}
}
void getlr（STR *p int i）                                             //将产生式的左右部分别放入left，right
{
	int j;
	for （j = 0;j	{ if （strings[j] == ‘-‘&&strings[j + 1] == ‘>‘）
	{ p[i].left = strings.substr（0 j）;
	  p[i].right = strings.substr（j + 2 strings.length（） - j）;
	}
	}
}

string Letter_First（STR *p char ch）
{
	int t;
	if （!（Vt.find（ch）>100））                        //在Vt里，first就是自身
	{
		first[Vt.find（ch）] = ch;
		return first[Vt.find（ch） - 1];
	}
	if （!（Vn.find（ch） > 100））                      //在Vn中的第i个
	{
		for （int i = 0;i < N;i++）                //第i个产生式
		{
			if （p[i].left[0] == ch）             //左侧字符是ch
			{
				if （!（Vt.find（p[i].right[0]）>100））
				{
					if （First[Vn.find（ch）].find（p[i].right[0]） > 100）     //右侧第一个字符是Vt，加入Vni的first集合中
					{
						First[Vn.find（ch）] += p[i].right[0];
					}
				}
				if （p[i].right[0] == ‘#‘）
				{
					if （First[Vn.find（ch）].find（‘#‘） > 100）           //右侧第一个字符是空，加入Vni的first集合中
					{
						First[Vn.find（ch）] += ‘#‘;
					}
				}
				if （!（Vn.find（p[i].right[0]） > 100））                //右侧第一个字母是Vn
				{
					if （p[i].right.length（） == 1）                      //只有一个字母
					{
						string ff;
						ff = Letter_First（p p[i].right[0]）;                        //把右侧字母的first集合加入到左侧字母中
						for （int k = 0;k < ff.length（）;k++）
						{
							if （First[Vn.find（ch）].find（ff[k]）>100）
							{
								First[Vn.find（ch）] += ff[k];
							}
						}
					}
					else                                               //多个字母都是Vn
					{
						for （int j = 0;j < p[i].right.length（）;j++）
						{

								string TT;
								TT = Letter_First（p p[i].right[j]）;
								if （!（TT.find（‘#‘）>100） && （j + 1） < p[i].right.length（））             /