symbolset.h

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

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

文件名：SymbolSet.h
简介：
符号集合的定义与各种操作的实现，用于存储存储终结符和非终结符序列

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

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

struct Symbol{				//符号集合，用于存储终结符和非终结符序列
	char *name;				//符号名
	struct Symbol *next;	//下一个符号
};
typedef struct Symbol SymbolSet;

int IsInSet(SymbolSet * Set, char * SymbolStr)
{
	//判断一个符号是否在集合中，是返回1，否则返回0
	struct Symbol * sym = Set->next;
	if(SymbolStr == NULL)
		return 0;
	while(NULL != sym)
	{
		if(strcmp(sym->name, SymbolStr) == 0)
			return 1;
		sym = sym->next;
	}
	return 0;
}

void InsertSymbol(SymbolSet * Set, char * SymbolStr)
{
	//添加一个符号到集合中
	char temp[MAXLEN] = {'\0'};
	int i, j, len;
	
	struct Symbol * newSymbol, *tail = NULL;
	//从输入串中读取符号
	{
		//如果以'<'开头
		if(SymbolStr[0] == '<')
		{
			for(i = 1, j = 0, len = strlen(SymbolStr); (i < len) && (SymbolStr[i] != '>');)
			{
				if(SymbolStr[i] == '%')
				{
					if((i + 1) >= len)
					{
						fprintf(stderr, "error: %s\nwrong input!\n", SymbolStr);
						exit(1);
					}
					else
					{
						temp[j++] = SymbolStr[i + 1];
						i += 2;
					}
				}
				else
				{
					temp[j++] = SymbolStr[i];
					i++;
				}
			}
			if(SymbolStr[i] != '>')
			{
				perror("error: wrong input!\n");
				exit(1);
			}
			temp[j] = '\0';
		}
		else
		{
			for(i = 0, j = 0, len = strlen(SymbolStr); i < len;)
			{
				if(SymbolStr[i] == '%')
				{
					if((i + 1) >= len)
					{
						fprintf(stderr, "error: %s\nwrong input!\n", SymbolStr);
						exit(1);
					}
					else
					{
						temp[j++] = SymbolStr[i + 1];
						i += 2;
					}
				}
				else
				{
					temp[j++] = SymbolStr[i];
					i++;
				}
			}
			temp[j] = '\0';
		}
	}
	//判断是否已经存在，保证唯一性
	if(IsInSet(Set, SymbolStr) == 1)
		return;

	if(NULL == (newSymbol = (struct Symbol *)malloc(sizeof(struct Symbol))))
	{
		perror("error: Heap Overflow!\n");
		exit(1);
	}
	newSymbol->name = (char *)malloc((strlen(temp) + 1) * sizeof(char));
	strcpy(newSymbol->name, temp);
	newSymbol->next = NULL;
	//添加到尾部
	{
		tail = Set;
		while(tail->next)
			tail = tail->next;
		tail->next = newSymbol;
	}
	
}

void DestroySymbolSet(SymbolSet *Set)
{
	//清除集合，释放内存
	struct Symbol *sym, *temp;
	sym = temp = Set->next;
	while(NULL != sym)
	{
		temp = sym;
		sym = sym->next;
		if(NULL != temp->name)
			free(temp->name);
		free(temp);
		temp = NULL;
	}
	Set->next = NULL;
}

int AddSym(SymbolSet *Set, char *SymbolStr)
{
	struct Symbol * newSymbol, *tail = NULL;
	//判断是否已经存在，保证唯一性
	if(IsInSet(Set, SymbolStr) == 1)
		return 0;
	if(NULL == (newSymbol = (struct Symbol *)malloc(sizeof(struct Symbol))))
	{
		perror("error: Heap Overflow!\n");
		exit(1);
	}
	newSymbol->name = (char *)malloc((strlen(SymbolStr) + 1) * sizeof(char));
	strcpy(newSymbol->name, SymbolStr);
	newSymbol->next = NULL;
	//添加到尾部
	{
		tail = Set;
		while(tail->next)
			tail = tail->next;
		tail->next = newSymbol;
	}
	return 1;
}