exp_4.cpp

1、构造该算符优先文法的优先关系矩阵或优先函数； 2、输入串应是词法分析的输出二元式序列

#include<stdio.h>
#define MAX_STACK 100

char stack[MAX_STACK],input[MAX_STACK];

int priority_matrix[8][8]=				//优先矩阵
{//			  (  i  *  /  +  -  )  #		
/* ( */	    { 0, 0, 0, 0, 0, 0, 1,-1},
/* i */	    {-1,-1, 2, 2, 2, 2, 2, 2},
/* * */		{ 0, 0, 2, 2, 2, 2, 2, 2},
/* / */		{ 0, 0, 2, 2, 2, 2, 2, 2},
/* + */		{ 0, 0, 0, 0, 2, 2, 2, 2},
/* - */		{ 0, 0, 0, 0, 2, 2, 2, 2},
/* ) */		{-1,-1, 2, 2, 2, 2, 2, 2},
/* # */		{ 0, 0, 0, 0, 0, 0,-1,-2}
};

void init();							//初始化函数
int char_num(char c);
bool Larger(char c1,char c2);				
bool Equal(char c1,char c2);
bool Smaller(char c1,char c2);
char Merger(int s,int e,int l);			//归约函数
bool Vt(char c);						//判断是否为终结符
bool parser ();							//算符分析算法
void stack_printf(int k);				//打印栈内容
char filename[40];						//文件名数组

void init()
{
	FILE *fp;
	char c;
	int i=0;

	printf("输入文件名:\n");
	scanf("%s",&filename);
	fp=fopen(filename,"r");

	c=fgetc(fp);
	//while(!feof(fp))
	while(c!='.')
	{
		fseek(fp,2*sizeof(char),1);
		input[i++]=fgetc(fp);
		fgetc(fp);
		c=fgetc(fp);
	}
	input[i]='#';

	fclose(fp);
	printf("          归约前堆栈        归约公式\t归约后堆栈\n");
}

int char_num(char c)
{
	switch(c)
	{
	case '(':return 0;break;
	case 'i':return 1;break;
	case '*':return 2;break;
	case '/':return 3;break;
	case '+':return 4;break;
	case '-':return 5;break;
	case ')':return 6;break;
	case '#':return 7;break;
	default:return -1;
	}
}

bool Larger(char c1,char c2)
{
	if(priority_matrix[char_num(c1)][char_num(c2)]==2)
		return true;
	else return false; 
}

bool Equal(char c1,char c2)
{
	if(priority_matrix[char_num(c1)][char_num(c2)]==1)
		return true;
	else return false; 
}

bool Smaller(char c1,char c2)
{
	if(priority_matrix[char_num(c1)][char_num(c2)]==0)
		return true;
	else return false; 
}

char Merger(int s,int e,int l)
{
	switch(stack[s])
	{
	case 'E':if((stack[s+1]=='+')&&(stack[s+2]=='T')) {printf("E+T->E\t");return 'E';}
		else if((stack[s+1]=='-')&&(stack[s+2]=='T')) {printf("E-T->E\t");return 'E';}
		else return('?');
	case 'T':if(l==1) {printf("T->E\t");return 'E';}
		else if((stack[s+1]=='*')&&(l==3)&&(!Vt(stack[s+2]))) {printf("%c*%c->T\t",stack[s],stack[s+2]);return 'T';}
		else if((stack[s+1]=='/')&&(l==3)&&(!Vt(stack[s+2])))  {printf("%c/%c->T\t",stack[s],stack[s+2]);return 'T';}
		else if((stack[s+1]=='+')&&(l==3)&&(!Vt(stack[s+2])))  {printf("%c+%c->E\t",stack[s],stack[s+2]);return 'E';}
		else if((stack[s+1]=='-')&&(l==3)&&(!Vt(stack[s+2])))  {printf("%c-%c->E\t",stack[s],stack[s+2]);return 'E';}
		else return('?');
	case 'F':if(l==1) {printf("F->T\t");return 'T';}
		else if((stack[s+1]=='*')&&(l==3)&&(!Vt(stack[s+2]))) {printf("%c*%c->T\t",stack[s],stack[s+2]);return 'T';}
		else if((stack[s+1]=='/')&&(l==3)&&(!Vt(stack[s+2]))) {printf("%c/%c->T\t",stack[s],stack[s+2]);return 'T';}
		else if((stack[s+1]=='+')&&(l==3)&&(!Vt(stack[s+2]))) {printf("%c+%c->E\t",stack[s],stack[s+2]);return 'E';}
		else if((stack[s+1]=='-')&&(l==3)&&(!Vt(stack[s+2]))) {printf("%c-%c->E\t",stack[s],stack[s+2]);return 'E';}
		else return('?');
	case '(':if((l==3)&&(stack[s+1]=='E')&&(stack[s+2]==')')) {printf("(E)->F\t");return 'F';}
		else return('?');
	case 'i':if(l==1) {printf("i->F\t");return 'F';}
		else return('?');
	default: return '?';
	}
}

bool Vt(char c)
{
	if((c=='(')||(c==')')||(c=='+')||(c=='-')||(c=='*')||(c=='/')||(c=='#')||(c=='i'))
		return true;
	else return false;
}

bool parser ()
{
	int i,k;
	char r,NewVn;

	i=0;
	k=0;

	stack[0]='#';

	do
	{
		int j;
		r=input[i++];
		if (Vt(stack[k]))j=k; else j=k-1;
		while (Larger(stack[j],r))
		{
			stack_printf(k);
			char q;
			do
			{
				q=stack[j];
				if (Vt(stack[j-1])) 
					j--;
				else 
					j-=2;
			}while(!Smaller(stack[j],q));
			NewVn=Merger(j+1,k,k-j);
			if(NewVn=='?') return false;
			k=j+1;
			stack[k]=NewVn;
			stack_printf(k);
			printf("\n");
		}
		if ((Smaller(stack[j],r))|| Equal(stack [j],r))
		{			
			stack[++k]=r;
		}
		else if(priority_matrix[char_num(stack[j])][char_num(r)]==-2)
			return true;
		else
		{
			printf("%c-%c无效字符!!!\n",stack[j],r);
			return false;
		}
	} while (r!='#');

	return true;
}

void stack_printf(int k)
{
	for(int i=0;i<=k;i++)
		printf("%c ",stack[i]);
	for(k=0;k<=15-i;k++)
	printf("  ");
}


void main()
{
	init();
	if(!parser())
		printf("匹配失败！！！\n");
	else if(stack[1]=='E')
		printf("匹配成功！！！\n");
}