sfyxfx.cpp

编译原理中

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

#define NUM_MAX 127

/************************************************************************/
/* 用来写输出文件的指针                                                 */
/************************************************************************/
FILE	*optfp;

/************************************************************************/
/* FIRSTVT的布尔数组                                                    */
/************************************************************************/
bool	F[NUM_MAX][NUM_MAX] = {false};
bool	L[NUM_MAX][NUM_MAX] = {false};

/************************************************************************/
/* 优先表 1-低于(<) 2-等于(=) 3-高于(>)                                 */
/************************************************************************/
enum	{NUL,LOWER,EQUAL,HIGHER} PRIORITYTABLE[NUM_MAX][NUM_MAX] = {NUL};

/************************************************************************/
/* 产生式数组和计数                                                     */
/************************************************************************/
char	EXPRESSION[20][10] = {0};
int		EXP_SIZE = 0;

/************************************************************************/
/* 终结符数组和个数计数                                                 */
/************************************************************************/
char	VT[10] = {0};
int		VT_SIZE=0;

/************************************************************************/
/* 非终结符数组和个数计数                                               */
/************************************************************************/
char	VN[10] = {0};
int		VN_SIZE=0;

/************************************************************************/
/* 栈数据                                                               */
/************************************************************************/
char	STACK[NUM_MAX][2] = {0};
int		SP=0;

/************************************************************************/
/* 入栈                                                                 */
/************************************************************************/
void push(char P,char a)
{
	STACK[SP][0] = P;
	STACK[SP][1] = a;
	SP++;
}

/************************************************************************/
/* 出栈                                                                 */
/************************************************************************/
void pop(char *P,char *a)
{
	SP--;
	*P = STACK[SP][0];
	*a = STACK[SP][1];
}

/************************************************************************/
/* 判断栈是否为空                                                       */
/************************************************************************/
bool isStackEmpty()
{
	if (SP == 0) {
		return true;
	} else {
		return false;
	}
}

/************************************************************************/
/* 读取产生式到数组EXPRESSION[][]                                       */
/************************************************************************/
void loadExpression()
{
	FILE	*fp;
	char	ch;
	int		col;
	int		row;
	char	P;

	//打开文件
	fp=fopen("input1.txt","r");

	//无法打开文件
	if (!fp) {
		printf("Fatal error: Cannot open [input1.txt] for reading !\n");
		exit(0);
	}
	
	//初始化行列指针
	col = 0;
	row = 0;
	
	//从文件中读取产生式字符串
	while (!feof(fp)) {
		
		//从文件中读取一个字符
		ch = fgetc(fp);

		//如果是第一列则把字符存入P中,读取左部,同时跳过两个字符'->'
		if (col == 0) {
			P = ch;
			EXPRESSION[row][col] = ch;
			col++;
			fgetc(fp);
			fgetc(fp);
			continue;
		}

		//如果是回车则行加一列归零
		if (ch == '\n') {
			row++;
			col = 0;
			continue;
		}

		//如果是空格则跳过
		if (ch == ' ') {
			continue;
		}

		//如果是分隔符则把P写在下一行的第一个字符，行加一，列置一
		if (ch == '|') {
			row++;
			col = 1;
			EXPRESSION[row][0] = P;
			continue;
		}

		//将字符ch赋给产生式数组
		EXPRESSION[row][col] = ch; 

		//列指针后移
		col++;
	}
	//产生式行数
	EXP_SIZE = row;

	//显示读入的字符串数组
	for (row=0; row<EXP_SIZE; row++) {
		puts(EXPRESSION[row]);
	}

	//关闭文件
	fclose(fp);
}

/************************************************************************/
/* 对终结符VT和非终结符VN进行归类                                       */
/************************************************************************/
void sortV()
{
	char	*p;
	int		i;

	//查找非终结符并加到VN集合中
	for (i=0; i<EXP_SIZE; i++) {
		for (p=EXPRESSION[i]; *p!=0; p++) {
			
			//如果p指向的字符是大写字母(非终结符)
			//并且未加入到VN集合中,则把它加入到VN集合
			if (*p>='A' && *p <='Z' && !strchr(VN,*p)) {
				VN[VN_SIZE] = *p;
				VN_SIZE++;
			}

			//如果p指向的字符是其他字符(终结符)
			//并且未加入到VT集合中,则把它加入到VT集合
			if ((*p<'A'||*p>'Z') && !strchr(VT,*p)) {
				VT[VT_SIZE] = *p;
				VT_SIZE++;
			}
		}
	}

	//将#加入终结符集
	VT[VT_SIZE] = '#';
	VT_SIZE++;

	//输出VT和VN两个字符串
	puts("\nVT:");
	puts(VT);
	puts("\nVN:");
	puts(VN);
	puts("\n");
}

/************************************************************************/
/* 得到字符串中的第一个终结符                                          */
/************************************************************************/
char getFVT(char *str)
{
	char	*p;

	//用指针寻找str中的第一个终结符(*p属于VT)
	for (p=str; *p!=0; p++) {
		if (strchr(VT,*p)) {
			return *p;
		}
	}

	return 0;
}

/************************************************************************/
/* 得到字符串中的最后一个终结符                                         */
/************************************************************************/
char getLVT(char *str)
{
	char	*p;
	
	//从字符串str中的最后开始找第一个终结符
	for (p=str+strlen(str)-1; *p!=*str; p--) {
		if (strchr(VT,*p)) {
			return *p;
		}
	}
	
	return 0;
}

/************************************************************************/
/* 插入数据F                                                            */
/************************************************************************/
void insertF(char p,char a)
{
	//如果(p,a)不在FIRSTVT集合中则将其加入集合,并入栈.
	if (!F[p][a]) {
		F[p][a] = true;
		push(p,a);
	}
}

/************************************************************************/
/* 得到FIRSTVT                                                          */
/************************************************************************/
void getFIRSTVT()
{
	int		i;
	int		j;
	char	Q;	//临时存储非终结符
	char	a;	//临时存储终结符
	
	//初始化F[][]
	for (i=0; i<NUM_MAX; i++) {
		for (j=0; j<NUM_MAX; j++) {
			F[i][j] = false;
		}
	}
	
	//将所有的P->a...或P->Qa...的产生式加入集合
	for (i=0; i<EXP_SIZE; i++) {
		if (getFVT(EXPRESSION[i])) {
			insertF(EXPRESSION[i][0],getFVT(EXPRESSION[i]));
		}
	}
	
	while (!isStackEmpty()) {
		pop(&Q,&a);
		for (i=0; i<EXP_SIZE; i++) {
			//形如P->Q...的产生式
			if (Q == EXPRESSION[i][1]) {
				insertF(EXPRESSION[i][0],a);
			}
		}
	}
	
	//打印FIRSTVT
	puts("\nFIRSTVT:");
	for (i=0; i<NUM_MAX; i++) {
		for (j=0; j<NUM_MAX; j++) {
			if (strchr(VN,i) && strchr(VT,j) && F[i][j]==true) {
				printf("[%c,%c]\n",i,j);
			}
		}
	}
}

/************************************************************************/
/* 插入数据L                                                            */
/************************************************************************/
void insertL(char p,char a)
{
	//如果(p,a)不在LASTVT集合中则将其加入集合,并入栈.
	if (!L[p][a]) {
		L[p][a] = true;
		push(p,a);
	}
}

/************************************************************************/
/* 得到LASTVT                                                           */
/************************************************************************/
void getLASTVT()
{
	int		i;
	int		j;
	char	Q;	//临时存储非终结符
	char	a;	//临时存储终结符
	
	//初始化F[][]
	for (i=0; i<NUM_MAX; i++) {
		for (j=0; j<NUM_MAX; j++) {
			L[i][j] = false;
		}
	}
	
	//将所有的P->...a或P->...aQ的产生式加入集合
	for (i=0; i<EXP_SIZE; i++) {
		if (getLVT(EXPRESSION[i])) {
			insertL(EXPRESSION[i][0],getLVT(EXPRESSION[i]));
		}
	}
	
	while (!isStackEmpty()) {
		pop(&Q,&a);
		for (i=0; i<EXP_SIZE; i++) {
			//形如P->...Q的产生式
			j = strlen(EXPRESSION[i]) - 1;
			if (Q == EXPRESSION[i][j]) {
				insertL(EXPRESSION[i][0],a);
			}
		}
	}
	
	//打印LASTVT
	puts("\nLASTVT:");
	for (i=0; i<NUM_MAX; i++) {
		for (j=0; j<NUM_MAX; j++) {
			if (strchr(VN,i) && strchr(VT,j) && L[i][j]==true) {
				printf("[%c,%c]\n",i,j);
			}
		}
	}
}

/************************************************************************/
/* 构造优先表                                                           */
/************************************************************************/
void createPriorityTable()
{
	int	len;	//记录字符串长度
	int	i;
	int	j;
	int	k;

	for (i=0; i<EXP_SIZE; i++) {
		len = strlen(EXPRESSION[i]) - 1;
		for (j=1; j<len; j++) {

			//X[j],X[j+1]均为终结符
			if (strchr(VT,EXPRESSION[i][j]) && strchr(VT,EXPRESSION[i][j+1])) {
				PRIORITYTABLE[EXPRESSION[i][j]][EXPRESSION[i][j+1]] = EQUAL;
			}
			
			//X[j],X[j+2]为终结符,但X[j+1]为非终结符
			if (j<=len-1 && strchr(VT,EXPRESSION[i][j]) 
					     && strchr(VN,EXPRESSION[i][j+1]) 
					 	 && strchr(VT,EXPRESSION[i][j+2])) {
				PRIORITYTABLE[EXPRESSION[i][j]][EXPRESSION[i][j+2]] = EQUAL;
			}
			
			//X[j]为终结符,X[j+1]为非终结符
			if (strchr(VT,EXPRESSION[i][j]) && strchr(VN,EXPRESSION[i][j+1])) {
				for (k=0; k<VT_SIZE; k++) {
					if (F[EXPRESSION[i][j+1]][VT[k]] == true) {
						PRIORITYTABLE[EXPRESSION[i][j]][VT[k]] = LOWER;
					}
				}
			}

			//X[j]为非终结符,X[j+1]为终结符
			if (strchr(VN,EXPRESSION[i][j]) && strchr(VT,EXPRESSION[i][j+1])) {
				for (k=0; k<VT_SIZE; k++) {
					if (L[EXPRESSION[i][j]][VT[k]] == true) {
						PRIORITYTABLE[VT[k]][EXPRESSION[i][j+1]] = HIGHER;
					}
				}				
			}
		}
	}

	//得到'#'的优先级
	for (i=0; i<VT_SIZE; i++) {
			PRIORITYTABLE['#'][VT[i]] = LOWER;
			PRIORITYTABLE[VT[i]]['#'] = HIGHER;			
	}
	PRIORITYTABLE['#']['#'] = EQUAL;
	

	//显示优先表
	puts("\nPRIORITYTABLE:");
	for (i=0; i<NUM_MAX; i++) {
		for (j=0; j<NUM_MAX; j++) {
			if (PRIORITYTABLE[i][j] != NUL) {
				//打印到屏幕
				printf("[%c,%c,%d]\n",i,j,PRIORITYTABLE[i][j]);
				//输出到文件
				fprintf(optfp,"[%c,%c,%d]\n",i,j,PRIORITYTABLE[i][j]);
			}
		}
	}
}

/************************************************************************/
/* 归约函数                                                             */
/************************************************************************/
char GuiYue(char *str, int n)
{
	int		i;
	int		j;
	int		len;		//存储字符串长度
	char	str1[100];	//临时字符串1
	char	str2[100];	//临时字符串2

	//把匹配串中的非终结符转换为'N'
	strcpy(str1,str);
	for (i=0; i<n; i++) {
		if (strchr(VN,str1[i])) {
			str1[i] = 'N';
		}
	}

	for (i=0; i<EXP_SIZE; i++) {

		//把产生式中的终结符转换为'N'
		strcpy(str2,EXPRESSION[i]+1);
		len = strlen(str2);
		for (j=0; j<len; j++) {
			if (strchr(VN,str2[j])) {
				str2[j] = 'N';
			}
		}
		
		//进行匹配检查
		if (strncmp(str1,str2,n) == 0) {

			//打印出用到的产生式
			printf("%c->%-5s <=>  N->%-5s\n",EXPRESSION[i][0],EXPRESSION[i]+1,str2);
			
			//返回规约后的非终结符
			return EXPRESSION[i][0];
		}
	}
	return 0;
}

/************************************************************************/
/* 分析函数                                                             */
/************************************************************************/
void Scan()
{
	FILE	*fp;
	int		j;
	int		k;
	char	a;				//临时存储非终结符
	char	Q;				//临时存储非终结符
	char	N;				//用来记录归约后的字符
	char	S[100] = {0};	//模拟堆栈的数组
	
	printf("\nprocess:\n");

	//打开文件并检查是否有错误
	if (!(fp=fopen("input2.txt","r"))) {
		printf("Fatal error: Cannot open [input2.txt] for reading !\n");
		exit(0);
	}

	k = 1;
	S[k] = '#';
	do {

		//把下一个符号读到a中
		a = fgetc(fp);
		if (strchr(VT,S[k])) {
			j = k;
		} else {
			j = k - 1;
		}

		//只要S[j]>a就循环
		while (PRIORITYTABLE[S[j]][a] == HIGHER) {
			do {
				Q = S[j];
				if (strchr(VT,S[j-1])) {
					j = j - 1;
				} else {
					j = j - 2;
				}
			} while(!(PRIORITYTABLE[S[j]][Q] == LOWER));

			//把S[j+1]...S[k]规约为某个N
			N = GuiYue(&S[j+1],k-j);
			k = j + 1;
			S[k] = N;
		}

		//如果S[j]<a或者S[j]=a则把a入栈，否则出错
		if (PRIORITYTABLE[S[j]][a]==LOWER || PRIORITYTABLE[S[j]][a]==EQUAL) {
			k = k + 1;
			S[k] = a;
		} else {
			//输出文法不符，并退出
			printf("\nno\n");
			fprintf(optfp,"\nno\n");
			exit(0);			
		}
	} while(a != '#');
	
	//输出符合文法信息
	printf("\nyes\n");
	fprintf(optfp,"\nyes\n");
	
	//关闭文件
	fclose(fp);
}

/************************************************************************/
/* 主程序                                                               */
/************************************************************************/
void main()
{
	//以写的方式打开输出文件并检查是否有错误
	if (!(optfp=fopen("output.txt","w"))) {
		printf("Fatal error: Cannot open [output.txt] for writing !\n");
		exit(0);		
	}

	//读取产生式
	loadExpression();

	//对终结符VT和非终结符VN进行归类
	sortV();

	//得到FIRSTVT
	getFIRSTVT();

	//得到LASTVT
	getLASTVT();

	//构造优先表
	createPriorityTable();

	//分析函数
	Scan();

	//关闭输出文件
	fclose(optfp);
}