exp_3.cpp

1、输入串应是词法分析的输出二元式序列

#include<stdio.h>
#include<malloc.h>
#include<string.h>
/*

0:E
1:R(E')
2:T
3:P(T')
4:F
5:A
6:M

0:i
1:+
2:-
3:*
4:/
5:(
6:)
7:#

1:E->TR
2:R->ATR
3:R->ε
4:T->FP
5:P->MFP
6:P->ε
7:F->(E)
8:F->i
9:A->+
10:A->-
11:M->*
12:M->/

*/

///////////////////////////////////////////----------------------------------------------

struct stack
{
	int class_value;
	char value[32];
	struct stack *next;
}*analyse_stack,*putin_stack;//分析栈指针


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

int analyse_table[8][8]={
	{1,0,0,0,0,1,0,0},
	{0,2,2,0,0,0,3,3},
	{4,0,0,0,0,4,0,0},
	{0,6,6,5,5,0,6,6},
	{8,0,0,0,0,7,0,0},
	{0,9,10,0,0,0,0,0},
	{0,0,0,11,12,0,0,0}	};
char filename[40];
FILE *fp;

///////////////////////////////////////////·······················

void init();
bool push_stack(int class_value,char c,struct stack *&sp);
struct stack *pop_stack(struct stack *&sp);
int get_analyse();												//获得分析栈栈顶的符号代码
int get_putin();												//获得输入栈栈顶符号的代码
int drive_function(int analyse,int putin);						//控制程序
void output_stack(struct stack *sp);							//打印栈内字符

///////////////////////////////////////////%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void init()
{
	struct stack *sp;
	int i=0;
	char c;
	sp=(struct stack*)malloc(1*sizeof(struct stack));
	putin_stack=sp;
	
	printf("输入文件名:\n");
	scanf("%s",&filename);
	fp=fopen(filename,"r");
	while(c=getc(fp)!='.')						//从文件中读取信息
	//while(!feof(fp))
	{
	sp->next=(struct stack*)malloc(1*sizeof(struct stack));
	sp=sp->next;							//(
	sp->class_value=getc(fp);
	getc(fp);								//,
//	i=0;
//	while((sp->value[i]=getc(fp))!=')')
//		i++;
	sp->value[0]=getc(fp);
	sp->value[1]='\0';
	sp->next=NULL;
	getc(fp);
	}
	
	sp->next=(struct stack*)malloc(1*sizeof(struct stack));
	sp=sp->next;
	sp->class_value=2;
	sp->value[0]='#';
	sp->value[1]='\0';						//将#压入输入栈
	sp->next=NULL;
	sp=putin_stack;
	putin_stack=putin_stack->next;//初始化输入栈
	free(sp);

	sp=(struct stack*)malloc(1*sizeof(struct stack));
	sp->class_value='2';
	sp->value[0]='#';
	sp->value[1]='\0';						//将#压入输入栈
	sp->next=NULL;
	analyse_stack=sp;
	sp=(struct stack*)malloc(1*sizeof(struct stack));
	sp->class_value='5';
	sp->value[0]='E';						//将开始符号E压入输入栈
	sp->value[1]='\0';	
	sp->next=analyse_stack;	
	analyse_stack=sp;						//初始化分析栈
}

bool push_stack(int class_value,char c,struct stack *&sp)
{
	struct stack *l_sp;
	if((l_sp=(struct stack*)malloc(1*sizeof(struct stack)))==NULL) return 0;
	l_sp->next=sp;
	sp=l_sp;
	sp->class_value=class_value;
	sp->value[0]=c;
	if(c=='(') sp->value[0]=')';			//为什么进行这个转换？
	if(c==')') sp->value[0]='(';			//	(,)在堆栈结构中互换位置
	sp->value[1]='\0';
	return 1;
}

struct stack *pop_stack(struct stack *&sp)
{
	struct stack *l_sp;
	l_sp=sp->next;
	free(sp);
	sp=l_sp;
	return(l_sp);
}

int get_analyse()
{
	char c=analyse_stack->value[0];
	if(analyse_stack->class_value!='5')
		return -1;
	else
	switch(c)
	{
	case 'E':return 0;
	case 'R':return 1;
	case 'T':return 2;
	case 'P':return 3;
	case 'F':return 4;
	case 'A':return 5;
	case 'M':return 6;
	}
}

int get_putin()
{
	char c=putin_stack->value[0];
	switch(c)
	{
	case 'i':return 0;
	case '+':return 1;
	case '-':return 2;
	case '*':return 3;
	case '/':return 4;
	case '(':return 5;
	case ')':return 6;
	case '#':return 7;
	}
}

int drive_function(int analyse,int putin)
{
	if(analyse_stack->class_value!='5')
	{
		if(analyse_stack->value[0]!=putin_stack->value[0])
		return 1;
		else
		{
			pop_stack(analyse_stack);
			pop_stack(putin_stack);
			printf("\n");
			return 0;
		}
	}
	else
	switch(analyse_table[analyse][putin])
	{
		case 0:return 1;
		case 1:
			pop_stack(analyse_stack);
			push_stack('5','R',analyse_stack);
			push_stack('5','T',analyse_stack);
			printf("E->TR\n");
			return 0;
		case 2:
			pop_stack(analyse_stack);
			push_stack('5','R',analyse_stack);
			push_stack('5','T',analyse_stack);
			push_stack('5','A',analyse_stack);
			printf("R->ATR\n");
			return 0;
		case 3:pop_stack(analyse_stack);
			printf("R->ε\n");
			return 0;
		case 4:
			pop_stack(analyse_stack);
			push_stack('5','P',analyse_stack);
			push_stack('5','F',analyse_stack);
			printf("T->FP\n");
			return 0;
		case 5:
			pop_stack(analyse_stack);
			push_stack('5','P',analyse_stack);
			push_stack('5','F',analyse_stack);
			push_stack('5','M',analyse_stack);
			printf("P->MFP\n");
			return 0;
		case 6:pop_stack(analyse_stack);
			printf("P->ε\n");
			return 0;
		case 7:pop_stack(analyse_stack);
			push_stack('2','(',analyse_stack);
			push_stack('5','E',analyse_stack);
			push_stack('2',')',analyse_stack);
			printf("F->(E)\n");
			return 0;
		case 8:pop_stack(analyse_stack);
			push_stack('3','i',analyse_stack);
			printf("F->i\n");
			return 0;
		case 9:pop_stack(analyse_stack);
			push_stack(2,'+',analyse_stack);
			printf("A->+\n");
			return 0;
		case 10:pop_stack(analyse_stack);
			push_stack('2','-',analyse_stack);
			printf("A->-\n");
			return 0;
		case 11:pop_stack(analyse_stack);
			push_stack('2','*',analyse_stack);
			printf("M->*\n");
			return 0;
		case 12:pop_stack(analyse_stack);
			push_stack('2','/',analyse_stack);
			printf("M->/\n");
			return 0;
		default:return 1;
	}
}

void output_stack(struct stack *sp)
{
	struct stack *l_sp=sp;
	while(l_sp!=NULL)
	{
		printf("%c",l_sp->value[0]);
		l_sp=l_sp->next;
	}
}

int main()
{
	int cc=1;
	init();
	printf("输入栈读取文件结果:\n");
	output_stack(putin_stack);
	printf("\n");
	printf("符号串匹配:\n");
	while(analyse_stack->value[0]!='#')
	{
		printf("%d\t",cc++);
		output_stack(analyse_stack);
		printf("\t");
		output_stack(putin_stack);
		printf("\t");
		if(drive_function(get_analyse(),get_putin())==1)
		{printf("\n符号串不符合语法规则！\n");return 1;}
	}
	printf("符号串匹配成功！\n");
	return 0;
}