program4.cpp

根据所给文法的算术优先矩阵对算数表达式进行算符优先分析

// program4.cpp : Defines the entry point for the console application.
//
/* 程序名称：算符优先分析程序 */
/*
G[E]:
    E→E+T∣E-T∣    
    T→T*F∣T/F∣F
    F→(E)∣i

各算符对应的下标如下:
0  1  2  3  4  5  6  7
+  -  *  /  (  )  i  #
该算符优先分析的优先关系矩阵用二维数组表示为：
int table[8][8]={
	{ 1, 1,-1,-1,-1, 1,-1, 1},  
	{ 1, 1,-1,-1,-1, 1,-1, 1},  
	{ 1, 1, 1, 1,-1, 1,-1, 1},  
	{ 1, 1, 1, 1,-1, 1,-1, 1},  
	{-1,-1,-1,-1,-1,-1,-1, 0},  
	{ 1, 1, 1, 1, 0, 1, 0, 1},  
	{ 1, 1, 1, 1, 0, 1, 0, 1},  
	{-1,-1,-1,-1,-1, 0,-1,-1}
};  
*/
#include "stdafx.h"
#include "stdio.h"  
#include "malloc.h"  

char token[100],in[200];
int n=0;
int i=0;
int flag;
FILE *fp;

void turn()
{
	char ch;
	ch =fgetc(fp);
	while(ch != EOF)
	{
		switch(ch)
		{
		case'\n':break;
		case' ':break;
		case'\0':break;
		default:in[i]=ch;i++;break;
		}
		ch =fgetc(fp);
	}
	in[i]='\0';
	printf("____________输入串为___________\n");
	printf("            ");
	for(i=0;in[i]!='\0';i++)
	{
		if((in[i]=='2' )&& (in[i+1]=='9'))  flag=i+5;
	}
	for(i=flag;in[i]!=';';i++)
	{
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='1'))  {token[n]='+';n++;}
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='2'))  {token[n]='-';n++;}
        if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='3'))  {token[n]='*';n++;}
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='5'))  {token[n]='(';n++;}
		if((in[i]=='[')&&(in[i+1]=='2')&&(in[i+2]=='6'))  {token[n]=')';n++;}
        if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='0'))  {token[n]='/';n++;}
        if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='7'))  {token[n]='i';n++;}
		if((in[i]=='[')&&(in[i+1]=='3')&&(in[i+2]=='8'))  {token[n]='i';n++;}
	}
 	token[n]='#';
    for(i=0;i<=n;i++)
	{
		printf("%c",token[i]);
	}
	printf("\n");
	printf("_______________________________\n");
//	printf("\n");
}
/*****************************************************************************/

struct Lchar
{ 
	char char_ch; 
	struct Lchar *next;
}LLchar,*p,*h,*temp,*top,*base;

int table[8][8]={
	{ 1, 1,-1,-1,-1, 1,-1, 1},  
	{ 1, 1,-1,-1,-1, 1,-1, 1},  
	{ 1, 1, 1, 1,-1, 1,-1, 1},  
	{ 1, 1, 1, 1,-1, 1,-1, 1},  
	{-1,-1,-1,-1,-1,-1,-1, 0},  
	{ 1, 1, 1, 1, 0, 1, 0, 1},  
	{ 1, 1, 1, 1, 0, 1, 0, 1},  
	{-1,-1,-1,-1,-1, 0,-1,-1}
};  

char curchar;  
char curcmp;  
int right; 
int j;  
int k;//比较字符在栈的位置

void push(char pchar)//模拟进栈，链表尾部为栈底元素
{  
	temp=(Lchar*)malloc(sizeof(LLchar));  
	temp->char_ch=pchar;  
	temp->next=top;  
	top=temp;  
}  

void pop()//模拟出栈
{  
	if(top->char_ch!='#')  
		top=top->next;  
}  

int changchartoint(char ch)//将字符转为数字，以得到算符优先值  
{  
	int t;  
	switch(ch)  
	{  
	case '+':t=0;break;  
	case '-':t=1;break;  
	case '*':t=2;break;  
	case '/':t=3;break;  
	case '(':t=4;break;  
	case ')':t=5;break;  
	case 'i':t=6;break;  
	case '#':t=7;  
	}  
	return t;  
}  

void dosome()  
{  
	k=1;  
	for(;;)  
	{  
		curchar=h->char_ch;  
		temp=top;
		for(;;)  
		{  
			if(temp->char_ch=='N')  
			{  
				temp=temp->next;  
				k++;  
			}  
			else  
			{  
				curcmp=temp->char_ch;
				break;  
			}  
		} 
		printf("\n");
		temp=top;  
	    n=0;
		for(;;)//打印分析栈中字符
		{  
			in[n]=temp->char_ch;n++;
			if(temp->char_ch=='#')  
				break;  
			else  
				temp=temp->next;  
		}  
		for(i=n-1;i>=0;i--)
		{
			printf("%c",in[i]);
		}
		printf("\t");  
		temp=h;  
		for(;;)//打印输入串中剩余字符 
		{  
			printf("%c",temp->char_ch);  

			if(temp->char_ch=='#')  
				break;  
			else  
				temp=temp->next;  
		}  
		i=changchartoint(curcmp);  
		j=changchartoint(curchar);  
		if(table[i][j]==0)//算符优先关系为空,即对应数组元素为0
		{  
     		printf("\n%c\t%c\tERROR!\n----算符优先关系为空",curcmp,curchar);  
			right=0;  
			break;  
		}  
		else//算符优先关系不为空
		{  
			if(table[i][j]<0)//算符优先值为-1，准备移进
			{  
				if(curchar=='#')//剩余字符串为空
				{  
					if(k==2)//当前比较字符在栈的位置为两个元素  
						break;  
					else
					{  
 						printf("\n%c\t%c\tERROR!\n----未规约到N",curcmp,curchar);  
						right=0;  
						break;  
					}  
				}  
				push(curchar);  
				k=1;  
				curcmp=curchar;  
				h=h->next;  
			}  
			else//算符优先值为1，归约  
			{  
				if(curcmp=='i')//当前比较为i,出栈一次  
					pop();  
				else					
				{
					if(top->char_ch!='N'&&curchar=='#')
					{
						printf("\n%c\t%c\tERROR!\n----未规约到N",curcmp,curchar);  
						right=0;  
						break;
					}
					pop();  
					pop();  
					pop();  
				}  
				push('N');//归约到N
				k=1;  
			}  
		}  
	}  
}  

void scanner()
{
	char ch;  
	right=1;  
	base=(Lchar*)malloc(sizeof(LLchar));  
	base->next=NULL;  
	base->char_ch='#';  
	top=base;  
	h=(Lchar*)malloc(sizeof(LLchar));  
	h->next=NULL;
	p=h;
	for(i=0;i<=n;i++)
	{
		ch=token[i];
        if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
		{
			temp=(struct Lchar *)malloc(sizeof(Lchar));
            temp->next=NULL;
            temp->char_ch=ch;
            h->next=temp;
            h=h->next;
		}
		else
		{
			temp=p->next;
			printf("输入串错误!\n");
		}
	}
	p=p->next;
	h=p;
	dosome();
	if(right)   printf("\n此输入串是该文法定义的算术表达式!\n\n");
	else	printf("\n此输入串不是该文法定义的算术表达式!\n\n");
}

int main(int argc, char* argv[])
{
	fp=fopen("test.txt", "r");
	turn();
	scanner();
	return 0;
}