main.c

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

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

功能简介：
从文件读入文法，实现文法的内部存储，及文法的
ε-产生式，单产生式，无用产生式的化简
输入：
输入的文法格式见设计报告

******************************************/
#include "stdio.h"
#include "string.h"
#include "common.h"

#include "Production.h"
#include "SymbolSet.h"

ProductionSet Productions;			//存储所有产生式
SymbolSet Terminators;				//存储所有终结符
SymbolSet NonTerminators;			//存储所有非终结符
char *Start;						//文法开始符号

SymbolSet W1, W2;					//算法2.3的结果，非终结符的互补子集

char sourceFile[FILENAME_LENGTH];
char outFile[FILENAME_LENGTH];
FILE *in = (FILE *) 0, *out = (FILE *) 0;

void algorithm21();
void algorithm22();
void algorithm23();
void algorithm24();
void forAlgo24(ProductionSet *Set, struct Lnode *left, struct Rnode *tail, struct Lnode *p);
void algorithm25();
void algorithm26();

void Init()
{
	Productions.next = NULL;
	Productions.num = 0;
	Terminators.next = NULL;
	NonTerminators.next = NULL;
	W1.next = NULL;
	W2.next = NULL;
}

void readInGrammer(FILE * in)
{
	char temp[MAXLEN] = {'\0'}, lTemp[MAXLEN] = {'\0'}, rTemp[MAXLEN] = {'\0'};
	int i = 0, j = 0;

	while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") == 0);
	if(feof(in))
		return;
	if(temp[strlen(temp) - 1] == '\n')
		temp[strlen(temp) - 1] = '\0';
	Start = (char *)malloc(strlen(temp) + 1);
	strcpy(Start, temp);
	memset(temp, 0, MAXLEN);
	while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") == 0);
	if(feof(in))
		return;
	
	//读非终结符
	do{
		if(temp[strlen(temp) - 1] == '\n')
			temp[strlen(temp) - 1] = '\0';
		InsertSymbol(&NonTerminators, temp);
		memset(temp, 0, MAXLEN);
	}while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") != 0);
	
	while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") == 0);
	if(feof(in))
		return;

	//读终结符
	do{
		if(temp[strlen(temp) - 1] == '\n')
			temp[strlen(temp) - 1] = '\0';
		InsertSymbol(&Terminators, temp);
		memset(temp, 0, MAXLEN);
	}while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") != 0);
	while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") == 0);
	if(feof(in))
		return;

	//读产生式
	do{
		if(temp[strlen(temp) - 1] == '\n')
			temp[strlen(temp) - 1] = '\0';
		for(i = 0, j = 0; temp[i] && temp[i] != ' ';i++, j++)
			lTemp[j] = temp[i];
		lTemp[j] = '\0';
		while(temp[i] && temp[i] == ' ')
			i++;
		for(j = 0; temp[i]; i++, j++)
			rTemp[j] = temp[i];
		rTemp[j] = '\0';
		InsertInit(&Productions, lTemp, rTemp);
		memset(temp, 0, MAXLEN);
	}while(!feof(in) && fgets(temp, MAXLEN, in) && strcmp(temp, "\n") != 0);
}

void outputGrammer(FILE *out)
{
	struct Symbol *sym = NULL;
	struct Lnode *left = NULL;
	struct Rnode *right = NULL;

	fprintf(out, "%s\n", Start);
	fprintf(out, "\n");
	fflush(out);
	//输出非终结符
	sym = NonTerminators.next;
	while(sym)
	{
		if(strlen(sym->name) > 1)
			fprintf(out, "<%s>\n", sym->name);
		else
			fprintf(out, "%s\n", sym->name);
		sym = sym->next;
	}
	fprintf(out, "\n");
	fflush(out);
	//输出终结符
	sym = Terminators.next;
	while(sym)
	{
		if(strlen(sym->name) > 1)
			fprintf(out, "<%s>\n", sym->name);
		else
			fprintf(out, "%s\n", sym->name);
		sym = sym->next;
	}
	fprintf(out, "\n");
	fflush(out);

	//输出产生式
	left = Productions.next;
	while(left)
	{
		fprintf(out, "%s->", left->name);
		right = left->right;
		while(right)
		{
			//空产生式
			if(strcmp(right->name, "") == 0)
				fprintf(out, "$");
			else if(strlen(right->name) > 1)
				fprintf(out, "<%s>", right->name);
			else
				fprintf(out, "%s", right->name);
			right = right->next;
		}
		fprintf(out, "\n");
		left = left->next;
	}
	fflush(out);

}

int main(int argc, char ** argv)
{
	Init();
	if(argc > 1)
	{
		char *cp;
		strcpy(sourceFile, argv[1]);
		if(argc == 2)
		{
			strcpy(outFile, sourceFile);
			cp = &outFile[strlen(outFile)] - 1;
			while((cp >= outFile) && (*cp != '.') && (*cp != '\\'))
				cp--;
			if(*cp == '.')
				*cp = 0;
			strcat(outFile, ".out.txt");
		}
		else
			strcpy(outFile, argv[2]);
	}
#ifndef _DEBUG
	else
	{
		fprintf(stderr, "Usage: %s sourceFile outFile\n", argv[0]);
		exit(1);
	}
#else
	else
	{
		strcpy(sourceFile, "grammer.txt");
		strcpy(outFile, "grammer.out.txt");
	}
#endif
	in = fopen(sourceFile, "r");
	if(NULL == in)
	{
		fprintf(stderr, "%s open fail!\n", sourceFile);
		exit(1);
	}
	readInGrammer(in);
	if(NULL != in)
		fclose(in);

	algorithm25();
	out = fopen("消除空产生式.txt", "w");
	outputGrammer(out);
	fclose(out);
	
	algorithm26();
	out = fopen("消除单产生式.txt", "w");
	outputGrammer(out);
	fclose(out);
	
	algorithm21();
	algorithm22();
	out = fopen("消除无用产生式.txt", "w");
	outputGrammer(out);
	fclose(out);
	if(NULL != out)
		fclose(out);
	//销毁链表
	free(Start);
	ClearProductionSet(&Productions);
	DestroySymbolSet(&NonTerminators);
	DestroySymbolSet(&Terminators);
	DestroySymbolSet(&W1);
	DestroySymbolSet(&W2);

	//system("edit grammer.out.txt");
	return 0;
}

//algorithm21, algorithm22用于消除无用产生式
//算法2.1
void algorithm21()
{
	SymbolSet VN1;
	ProductionSet P1;
	struct Lnode *left = NULL;
	struct Rnode *right = NULL;
	int flag = 0, added = 1;
	VN1.next = NULL;
	P1.next = NULL;
	P1.num = 0;
	
	//第一步
	left = Productions.next;
	while(left)
	{
		flag = 1;
		right = left->right;
		while(right)
		{
			if(strcmp(right->name, "") == 0)
				break;
			if(IsInSet(&Terminators, right->name) == 0)
			{
				flag = 0;
				break;
			}
			right = right->next;
		}
		if(flag == 1)
		{
			//如果原来不存在则添加
			if(IsInSet(&VN1, left->name) == 0)
				AddSym(&VN1, left->name);
		}
		left = left->next;
	}
	//第二步
	added = 1;
	while(added)
	{
		added = 0;
		left = Productions.next;
		while(left)
		{
			flag = 1;
			right = left->right;
			while(right)
			{
				if(strcmp(right->name, "") == 0)
					break;
				if((IsInSet(&Terminators, right->name) == 0) && ( IsInSet(&VN1, right->name) == 0))
				{
					flag = 0;
					break;
				}
				right = right->next;
			}
			if(flag == 1)
			{
				//如果原来不存在则添加
				if(IsInSet(&VN1, left->name) == 0)
				{
					AddSym(&VN1, left->name);
					added = 1;
				}
			}
			left = left->next;
		}
	}
	//第三步
	left = Productions.next;
	while(left)
	{
		flag = 1;
		right = left->right;
		while(right)
		{
			if(strcmp(right->name, "") == 0)
				break;
			if((IsInSet(&Terminators, right->name) == 0) &&( IsInSet(&VN1, right->name) == 0))
			{
				flag = 0;
				break;
			}
			right = right->next;
		}
		if(flag == 1)
			AddPro(&P1, left);
		left = left->next;
	}
	//转移到系统链表集合
	{
		//删除原有的
		ClearProductionSet(&Productions);
		DestroySymbolSet(&NonTerminators);
		//转移
		Productions.num = P1.num;
		Productions.next = P1.next;
		NonTerminators.next = VN1.next;
	}
}

//算法2.2
void algorithm22()
{
	SymbolSet VN1, VT1;
	ProductionSet P1;
	struct Lnode *left = NULL;
	struct Rnode *right = NULL;
	int flag = 0, added = 1;
	VN1.next = NULL;
	VT1.next = NULL;
	P1.next = NULL;
	P1.num = 0;

	//开始符号放入VN1
	AddSym(&VN1, Start);
	//第一步
	added = 1;
	while(added)
	{
		added = 0;
		left = Productions.next;
		while(left)
		{
			if(IsInSet(&VN1, left->name) == 1)
			{
				right = left->right;
				while(right)
				{
					if(IsInSet(&NonTerminators, right->name) == 1)
						added = AddSym(&VN1, right->name);
					else if(IsInSet(&Terminators, right->name) == 1 || strcmp(right->name, "") == 0)