production.h

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

/*************************************************************************

文件名：Production.h
简介：
文法产生式的左右部结点定义，及产生式相关操作的实现，
用于存储文法的产生式

**************************************************************************/
#define MAXLEN 256

static const char KeyWord[] = { '%', '<', '>', '$' };

#include "stdlib.h"
#include "string.h"

struct Lnode{				//产生式左结点
	int num;				//产生式序号
	//int flag;				//标志位：初值：0；成功：1；失败：2；
	char *name;				//结点符号名
	struct Lnode *next;		//下一产生式
	struct Rnode *right;	//产生式右部第一个符号
};

struct Rnode{				//产生式右结点
	char *name;				//结点符号名
	//struct Lnode *or;		//指向同符号名的左部结点
	struct Rnode *next;		//指向左部下一个符号
};

typedef struct Lnode ProductionSet;


void InsertRnode(struct Lnode *left, char *right)
{
	//接受一个符号，添加到产生式的右部
	struct Rnode *newRight;
	struct Rnode *pre, *nxt;

	//是空产生式
	newRight = (struct Rnode *)malloc(sizeof(struct Rnode));
	if(NULL == right)
	{
		newRight->name = (char *)malloc(1);
		newRight->name[0] = '\0';
		newRight->next = NULL;
		left->right = newRight;
	}
	else
	{
		newRight->name = (char *)malloc(strlen(right) + 1);
		strcpy(newRight->name, right);
		newRight->next = NULL;
		if(NULL == left->right)
		{
			left->right = newRight;
		}
		else
		{
			pre = nxt = left->right;
			while(nxt)
			{
				pre = nxt;
				nxt = nxt->next;
			}
			pre->next = newRight;
		}
	}
}

void InsertProduction(ProductionSet * Set, char *left, char *right)
{
	//接受一个右部串，添加产生式
	struct Lnode *newProduction, *tail = NULL;
	char temp[MAXLEN] = {'\0'};
	int i, len, j;

	if(NULL == (newProduction = (struct Lnode *)malloc(sizeof(struct Lnode))))
	{
		perror("error: Heap Overflow!\n");
		exit(1);
	}
	//读取左部串
	{
		//如果以'<'开头
		if(left[0] == '<')
		{
			for(i = 1, j = 0, len = strlen(left); (i < len) && (left[i] != '>');)
			{
				if(left[i] == '%')
				{
					temp[j++] = left[i + 1];
					i += 2;
				}
				else
				{
					temp[j++] = left[i];
					i++;
				}
			}
			if(left[i] != '>')
			{
				perror("error: wrong input!\n");
				exit(1);
			}
			temp[j] = '\0';
		}
		else
		{
			for(i = 0, j = 0, len = strlen(left); i < len;)
			{
				if(left[i] == '%')
				{
					temp[j++] = left[i + 1];
					i += 2;
				}
				else
				{
					temp[j++] = left[i];
					i++;
				}
			}
			temp[j] = '\0';
		}
	}
	newProduction->name = (char *)malloc((strlen(temp) + 1) * sizeof(char));
	strcpy(newProduction->name, temp);
	//注意：初始化右部
	newProduction->right = NULL;
	newProduction->next = NULL;
	newProduction->num = ++(Set->num);
	//添加到尾部
	{
		tail = Set;
		while(tail->next)
			tail = tail->next;
		tail->next = newProduction;
	}

	if(strcmp(right, "$") == 0)
	{
		//是空产生式
		InsertRnode(newProduction, NULL);
	}
	else
	{
		for(i = 0, len = strlen(right);	i < len;)
		{
			if(right[i] == '%')
			{
				//strncpy(temp, right + i + 1, 1);
				if((i + 1) >= len)
				{
					fprintf(stderr, "error: %s\nwrong input!\n", right);
					exit(1);
				}
				else
				{
					temp[0] = right[i + 1];
					temp[1] = '\0';
					InsertRnode(newProduction, temp);
					i += 2;
				}
			}
			else if(right[i] == '<')
			{
				for(i = i + 1, j = 0; right[i] && (right[i] != '>');)
				{
					if(right[i] == '%')
					{
						if((i + 1) >= len)
						{
							fprintf(stderr, "error: %s\nwrong input!\n", right);
							exit(1);
						}
						else
						{
							temp[j++] = right[i + 1];
							i += 2;
						}
					}
					else
					{
						temp[j++] = right[i];
						i++;
					}
				}
				if(right[i] != '>')
				{
					fprintf(stderr, "error: %s\nwrong input!\n", right);
					exit(1);
				}
				temp[j] = '\0';
				InsertRnode(newProduction, temp);
				i++;
			}
			else
			{
				temp[0] = right[i];
				temp[1] = '\0';
				InsertRnode(newProduction, temp);
				i++;
			}
		}
	}
}

//调用此函数来读产生式到产生式集合中
void InsertInit(ProductionSet * Set, char *left, char *right)
{
	//对有‘|’分割的各产生式分别处理
	int i, len, j = 0, k;
	int flag = 1;
	char temp[MAXLEN] = {'\0'};
	for(i = 0, len = strlen(right); i < len;)
	{
		if(right[i] == '|')
		{
			//判断'|'是否经过转义
			for(k = i - 1; k >= 0 && right[k] == '%'; k--)
				flag = !flag;
			if(flag)
			{
				temp[j] = '\0';
				InsertProduction(Set, left, temp);
				j = 0;
				memset(temp, 0, MAXLEN);
				i++;
			}
			else
			{
				temp[j++] = right[i];
				i++;
			}
		}
		else
		{
			temp[j++] = right[i];
			i++;
		}
	}
	temp[j] = '\0';

	if(strlen(temp) > 0)
		InsertProduction(Set, left, temp);
}

void ClearProductionSet(ProductionSet * Set)
{
	//清除所有产生式，释放内存
	struct Lnode *ln, *lntmp;
	struct Rnode *rn, *rntmp;
	ln = lntmp = Set->next;
	while(ln)
	{
		lntmp = ln;
		ln = ln->next;
		rn = rntmp = lntmp->right;
		while(rn)
		{
			rntmp = rn;
			rn = rn->next;
			if(NULL != rntmp->name)
				free(rntmp->name);
			free(rntmp);
			rntmp = NULL;
		}
		if(NULL != lntmp->name)
			free(lntmp->name);
		free(lntmp);
		lntmp = NULL;
	}
	Set->next = NULL;
}

void ClearLNode(struct Lnode *left)
{
	struct Rnode *rn = NULL, *rntmp = NULL;
	if(left == NULL)
		return;
	
	rn = rntmp = left->right;
	while(rn)
	{
		rntmp = rn;
		rn = rn->next;
		if(NULL != rntmp->name)
			free(rntmp->name);
		free(rntmp);
		rntmp = NULL;
	}
	if(NULL != left->name)
		free(left->name);
	free(left);
}

//通过一个现有产生式来添加产生式
void AddPro(ProductionSet *Set, struct Lnode *src)
{
	struct Lnode *newLeft = NULL, *tail = NULL;
	struct Rnode *right = NULL;
	newLeft = (struct Lnode *)malloc(sizeof(struct Lnode));
	newLeft->name = (char *)malloc(strlen(src->name) + 1);
	strcpy(newLeft->name, src->name);
	newLeft->num = ++(Set->num);
	//初始化右部，切记
	newLeft->right = NULL;
	newLeft->next = NULL;
	//添加到尾部
	{
		tail = Set;
		while(tail->next)
			tail = tail->next;
		tail->next = newLeft;
	}
	
	right = src->right;
	while(right)
	{
		InsertRnode(newLeft, right->name);
		right = right->next;
	}
}

void AddPro1(ProductionSet *srcSet, ProductionSet *Set, struct Lnode *lSrc, struct Lnode *rSrc)
{
	struct Lnode *newLeft = NULL, *tail = NULL, *ltmp = NULL;
	struct Rnode *right = NULL, *rtmpL = NULL, *rtmpR = NULL;
	int flag = 0;
	//先判断该产生式是否已经存在
	ltmp = srcSet->next;
	while(ltmp)
	{
		if(strcmp(ltmp->name, lSrc->name) == 0)
		{
			rtmpL = ltmp->right;
			rtmpR = rSrc->right;
			while(rtmpL && rtmpR)
			{
				if(strcmp(rtmpL->name, rtmpR->name) != 0)
					break;
				rtmpL = rtmpL->next;
				rtmpR = rtmpR->next;
			}
			if(rtmpL == NULL && NULL == rtmpR)
				return;	//已存在，不添加
		}
		ltmp = ltmp->next;
	}

	newLeft = (struct Lnode *)malloc(sizeof(struct Lnode));
	newLeft->name = (char *)malloc(strlen(lSrc->name) + 1);
	strcpy(newLeft->name, lSrc->name);
	newLeft->num = ++(Set->num);
	//初始化右部，切记
	newLeft->right = NULL;
	newLeft->next = NULL;
	//添加到尾部
	{
		tail = Set;
		while(tail->next)
			tail = tail->next;
		tail->next = newLeft;
	}
	
	right = rSrc->right;
	while(right)
	{
		InsertRnode(newLeft, right->name);
		right = right->next;
	}
}

//添加产生式S→ε
void AddNull(ProductionSet *Set, char *s)
{
	struct Lnode *left = NULL, *tail = NULL;
	struct Rnode *right;
	left = (struct Lnode *)malloc(sizeof(struct Lnode));
	right = (struct Rnode *)malloc(sizeof(struct Rnode));
	left->name = (char *)malloc(strlen(s) + 1);
	strcpy(left->name, s);
	right->name = (char *)malloc(1);
	right->name[0] = '\0';
	right->next = NULL;
	left->right = right;
	//下面这一句，一定不要忘，要养成初始化的好习惯
	//特别是用指针的时候
	left->next = NULL;
	//添加
	{
		tail = Set->next;
		while(tail->next)
			tail = tail->next;
		tail->next = left;
	}
}

//此函数又些多余，历史原因造成，不改了
void AddPro2(ProductionSet *srcSet, ProductionSet *Set, char *lSrc, struct Lnode *rSrc)
{
	struct Lnode *newLeft = NULL, *tail = NULL, *ltmp = NULL;
	struct Rnode *right = NULL, *rtmpL = NULL, *rtmpR = NULL;
	int flag = 0;
	//先判断该产生式是否已经存在
	ltmp = srcSet->next;
	while(ltmp)
	{
		if(strcmp(ltmp->name, lSrc) == 0)
		{
			rtmpL = ltmp->right;
			rtmpR = rSrc->right;
			while(rtmpL && rtmpR)
			{
				if(strcmp(rtmpL->name, rtmpR->name) != 0)
					break;
				rtmpL = rtmpL->next;
				rtmpR = rtmpR->next;
			}
			if(rtmpL == NULL && NULL == rtmpR)
				return;	//已存在，不添加
		}
		ltmp = ltmp->next;
	}

	newLeft = (struct Lnode *)malloc(sizeof(struct Lnode));
	newLeft->name = (char *)malloc(strlen(lSrc) + 1);
	strcpy(newLeft->name, lSrc);
	newLeft->num = ++(Set->num);
	//初始化右部，切记
	newLeft->right = NULL;
	newLeft->next = NULL;
	//添加到尾部
	{
		tail = Set;
		while(tail->next)
			tail = tail->next;
		tail->next = newLeft;
	}
	
	right = rSrc->right;
	while(right)
	{
		InsertRnode(newLeft, right->name);
		right = right->next;
	}
}