main.c

grammer 文法化简 消除单产生式 消除空产生式 消除无用产生式

						added = AddSym(&VT1, right->name);
					right = right->next;
				}
			}
			left = left->next;
		}
	}
	//第二步
	left = Productions.next;
	while(left)
	{
		flag = 1;
		if(IsInSet(&VN1, left->name) == 1)
		{
			right = left->right;
			while(right)
			{
				if(IsInSet(&VN1, right->name) == 0 && IsInSet(&VT1, right->name) == 0)
				{
					flag = 0;
					break;
				}
				right = right->next;
			}
			if(flag == 1)
				AddPro(&P1, left);
		}
		left = left->next;
	}

	//转移到系统链表集合
	{
		//删除原有的
		ClearProductionSet(&Productions);
		DestroySymbolSet(&NonTerminators);
		DestroySymbolSet(&Terminators);
		//转移
		Productions.num = P1.num;
		Productions.next = P1.next;
		NonTerminators.next = VN1.next;
		Terminators.next = VT1.next;
	}
}

//algorithm23,algorithm24用于消除ε-产生式
//算法2.3
void algorithm23()
{
	struct Lnode *left = NULL;
	struct Rnode *right = NULL;
	int flag = 0, added = 1;
	W1.next = NULL;
	W2.next = NULL;
	//第一步
	left = Productions.next;
	while(left)
	{
		right = left->right;
		//如果是空产生式
		if((right->next == NULL) && strcmp(right->name, "") == 0)
			AddSym(&W1, left->name);
		left = left->next;
	}
	//第二步
	added = 1;
	while(added)
	{
		added = 0;
		left = Productions.next;
		while(left)
		{
			flag = 1;
			right = left->right;
			while(right)
			{
				if(IsInSet(&W1, right->name) == 0)
				{
					flag = 0;
					break;
				}
				right = right->next;
			}
			if(flag == 1)
				added = AddSym(&W1, left->name);
			left = left->next;
		}
	}
	//algorithm23结束，等待算法2.4
}

//算法2.4
void algorithm24()
{
	ProductionSet P1;
	struct Symbol *sym = NULL;
	struct Lnode *left = NULL, *ltmp = NULL, *tmpNew = NULL;
	struct Rnode *right = NULL, *rtmp = NULL;
	int flag = 0, added = 1;
	P1.next = NULL;
	P1.num = 0;
	//第一步
	sym = NonTerminators.next;
	while(sym)
	{
		if(IsInSet(&W1, sym->name) == 0)
			AddSym(&W2, sym->name);
		sym = sym->next;
	}
	//第二步
	left = Productions.next;
	while(left)
	{
		tmpNew = (struct Lnode *)malloc(sizeof(struct Lnode));
		tmpNew->name = (char *)malloc(strlen(left->name) + 1);
		strcpy(tmpNew->name, left->name);
		tmpNew->next = NULL;
		tmpNew->right = NULL;

		forAlgo24(&P1, left, left->right, tmpNew);
		left = left->next;
	}

	//转移
	ClearProductionSet(&Productions);
	Productions.next = P1.next;
	Productions.num = P1.num;
}

//递归添加产生式
void forAlgo24(ProductionSet *Set, struct Lnode *left, struct Rnode *tail, struct Lnode *p)
{
	struct Lnode *ltmp = NULL, *new1 = NULL, *new2 = NULL;
	struct Rnode *rtmp = NULL, *rt1 = NULL, *rt2 = NULL, *tailTmp = NULL;;
	if(tail == NULL)
	{
		rtmp = p->right;
		if(strcmp(rtmp->name, "") == 0 && rtmp->next == NULL)
			return;
		else
			AddPro(Set, p);
	}
	else if(IsInSet(&W1, left->name) == 0)
	{
		//复制p
		new1 = (struct Lnode *)malloc(sizeof(struct Lnode));
		new1->name = (char *)malloc(strlen(p->name) + 1);
		strcpy(new1->name, p->name);
		new1->next = NULL;
		new1->right = NULL;
		rt1 = p->right;
		while(rt1)
		{
			rt2 = (struct Rnode *)malloc(sizeof(struct Rnode));
			rt2->name = (char *)malloc(strlen(rt1->name) + 1);
			strcpy(rt2->name, rt1->name);
			rt2->next = NULL;
			if(new1->right == NULL)
			{
				new1->right = rt2;
				tailTmp = new1->right;
			}
			else
			{
				tailTmp->next = rt2;
				tailTmp = tailTmp->next;
			}
			rt1 = rt1->next;
		}
		rt2 = (struct Rnode *)malloc(sizeof(struct Rnode));
		rt2->name = (char *)malloc(strlen(tail->name) + 1);
		strcpy(rt2->name, tail->name);
		rt2->next = NULL;

		if(tailTmp == NULL)
			new1->right = rt2;
		else
			tailTmp->next = rt2;
		forAlgo24(Set, left, tail->next, new1);
	}
	else
	{
		//复制p,1
		new1 = (struct Lnode *)malloc(sizeof(struct Lnode));
		new1->name = (char *)malloc(strlen(p->name) + 1);
		strcpy(new1->name, p->name);
		new1->next = NULL;
		new1->right = NULL;
		rt1 = p->right;
		while(rt1)
		{
			rt2 = (struct Rnode *)malloc(sizeof(struct Rnode));
			rt2->name = (char *)malloc(strlen(rt1->name) + 1);
			strcpy(rt2->name, rt1->name);
			rt2->next = NULL;
			if(new1->right == NULL)
			{
				new1->right = rt2;
				tailTmp = new1->right;
			}
			else
			{
				tailTmp->next = rt2;
				tailTmp = tailTmp->next;
			}
			rt1 = rt1->next;
		}
		rt2 = (struct Rnode *)malloc(sizeof(struct Rnode));
		rt2->name = (char *)malloc(strlen(tail->name) + 1);
		strcpy(rt2->name, tail->name);
		rt2->next = NULL;

		if(tailTmp == NULL)
			new1->right = rt2;
		else
			tailTmp->next = rt2;
		forAlgo24(Set, left, tail->next, new1);
		new1 = NULL;
		rt1 = rt2 = tailTmp = NULL;
		/////////////////////////////////////////////////
		//复制p,2
		new2 = (struct Lnode *)malloc(sizeof(struct Lnode));
		new2->name = (char *)malloc(strlen(p->name) + 1);
		strcpy(new2->name, p->name);
		new2->next = NULL;
		new2->right = NULL;
		rt1 = p->right;
		while(rt1)
		{
			rt2 = (struct Rnode *)malloc(sizeof(struct Rnode));
			rt2->name = (char *)malloc(strlen(rt1->name) + 1);
			strcpy(rt2->name, rt1->name);
			rt2->next = NULL;
			if(new2->right == NULL)
			{
				new1->right = rt2;
				tailTmp = new1->right;
			}
			else
			{
				tailTmp->next = rt2;
				tailTmp = tailTmp->next;
			}
			rt1 = rt1->next;
		}
		forAlgo24(Set, left, tail->next, new2);
	}
	ClearLNode(p);
}

//算法2.5
void algorithm25()
{
	struct Lnode *left = NULL;
	struct Rnode *right = NULL;
	int flag = 0, added = 1;
	char temp[MAXLEN] = {'\0'};
	memset(temp, 0, MAXLEN);
	
	//首先判断开始符号是否出现在产生式右部
	left = Productions.next;
	flag = 0;
	while(left && flag == 0)
	{
		right = left->right;
		while(right)
		{
			if(strcmp(Start, right->name) == 0)
			{
				flag = 1;
				break;
			}
			right = right->next;
		}
		left = left->next;
	}
	if(flag == 0)
	{
		algorithm24();
		//添加S→ε产生式
		AddNull(&Productions, Start);
	}
	else
	{
		//添加一个未曾出现过的非终结符
		strcpy(temp, Start);
		do{
			strcat(temp, "$");
		}while(IsInSet(&NonTerminators, temp) == 1);
		AddSym(&NonTerminators, temp);

		left = Productions.next;
		while(left)
		{
			if(strcmp(left->name, Start) == 0)
				AddPro2(&Productions, &Productions, temp, left);
			left = left->next;
		}
		if(Start)
			free(Start);
		Start = (char *)malloc(strlen(temp) + 1);
		strcpy(Start, temp);

		algorithm24();
		
		AddNull(&Productions, Start);
	}
}

//算法2.6
void algorithm26()
{
	ProductionSet P1;
	SymbolSet W;
	struct Lnode *left = NULL, *ltmp = NULL;
	struct Rnode *right = NULL, *rtmp = NULL;
	struct Symbol *sym = NULL;
	int flag = 0, added = 1;
	P1.next = NULL;
	P1.num = 0;
	W.next = NULL;

	left = Productions.next;
	while(left)
	{
		added = 1;
		while(added)
		{
			added = 0;
			added = AddSym(&W, left->name);
			ltmp = Productions.next;
			while(ltmp)
			{
				if(IsInSet(&W, ltmp->name) == 1)
				{
					rtmp = ltmp->right;
					if((IsInSet(&NonTerminators, rtmp->name) == 1) && (NULL == rtmp->next))
						added = AddSym(&W, rtmp->name);
				}
				ltmp = ltmp->next;		
			}
		}
		//第二步
		sym = W.next;
		while(sym)
		{
			ltmp = Productions.next;
			while(ltmp)
			{
				if(strcmp(sym->name, ltmp->name) == 0)
				{
					rtmp = ltmp->right;
					if(rtmp->next != NULL || IsInSet(&NonTerminators, rtmp->name) == 0)
						AddPro1(&P1, &P1, left, ltmp);
				}
				ltmp = ltmp->next;
			}
			sym = sym->next;
		}
		DestroySymbolSet(&W);
		left = left->next;
	}
	//转移
	ClearProductionSet(&Productions);
	DestroySymbolSet(&W);
	Productions.next = P1.next;
	Productions.num = P1.num;
}