lr分析法的实现.cpp

lr分析法分析表达式

#include<stdio.h>
#include<ctype.h>
#define n 5
int A[10]={0};
int a=0;
int flag=1;
void E();
void change()
{
	int i=0,j;
	char B[20];
    printf("请输入一个关于标识符与整数的算术表达式（不包括减法、除法运算）！");
	do
	{
	 	scanf("%c",&B[i++]);
	}while(B[i-1]!='#');
	i=0;j=0;
	do
	{  
	   if(isdigit(B[i]))
	   {
		   while(isdigit(B[i])||B[i]=='.')
		   { 
			   i++;
		   };
		   A[j++]=n;
	       //  printf("asfdhgj");
	   }
	   if(ischar(B[i]))
	   {
		   while(isalpha(B[i])||isdigit(B[i]))
		   {
			   i++;
		   }
		   A[j++]=n;
	   }
	   else
	   {
		   switch(B[i++])
		   {
		   case '+':  A[j++]=0;break;
		   case '*':  A[j++]=1;break;
		   case '(':  A[j++]=2;break;		
		   case ')':  A[j++]=3;break;
		   }
	   }
   }while(B[i-1]!='#');
//   i=0;
//   for(i=0;i<=5;i++)
//	   printf("%d",A[i]);
}

int read( )
{
	static int i;
    return A[i++];
}

void F( )
{
	if(a==n) a=read();
	else
		if(a==5)
		{
			a=read();
			E( );
			if(a==6) a=read();
			else 
			{	
				flag=0; 
				printf("缺少一个右括号\n");
			}
		}
		else 
		{	
			flag=0;
			printf("在%d前面缺少一个运算量\n",a);
		}
}

void T_2( )
{
	if(a==1||a==2)
	{
		a=read();
		F( );
		T_2( );
	}
	/*
	else if(a==2)
	{
		a=read( );
		F( );
		T_2( );
	}
	*/
}
void T( )
{
	F( );
	T_2( );
}
void E_2( )
{
	if (a==3||a==4) 
	{ a=read();
	  T( );
	  E_2( );
	}
	/*
	else if(a==4)
	{
		a=read();
		T( );
		E_2( );
	}
	*/
}
void E( )
{
	T( );
//	exit(0);
	E_2( );
}
typedef struct node 
{ 
	int data; 
	struct node *next; 
} LinkStack; 

void InitLinkStack(int &s) 
{ 
	s=NULL; 
} 
 
int IsEmptyLinkStack(int &s) 
{ 
	if(s==NULL) 
		return 1; 
	else 
		return 0; 
} 

void Push(LinkStack &s ,int x) 
{ 
	LinkStack *p; 
	p=malloc(sizeof(LinkStack)); /*生成新结点*s */ 
	p->data=x; 
	p->next=s; 
	s=p; 
} 
//出栈 删除链栈top的栈顶结点 
int Pop(LinkStack &s, int &x) 
{ 
	LinkStack *p; 
	if(s==NULL) return 0; 
	x = s->data; /*将栈顶数据存入*x */ 
	p = s; /*保存栈顶结点地址*/ 
	s = s->next; /*删除原栈顶结点*/ 
	free (p); /*释放原栈顶结点*/ 
	return 1; /*返回新栈顶指针*/ 
} 

int GetTop (LinkStack &s, int &x) 
{ 
	if(s==NULL) return 0; 
	x = s->data; /*将栈顶数据存入x */ 
	return 1; /*返回新栈顶指针*/ 
}
LinkStack s1,s2;//s1是状态栈，s2是符号栈

int LR[10][7]={{-1,-1,2,-1,3,-1,1},{4,5,-1,-1,-1,0,-1},{-1,-1,2,-1,3,-1,6},
{104,104,-1,104,-1,104,-1},{-1,-1,2,-1,3,-1,7},{-1,-1,2,-1,3,-1,8},
{4,5,-1,9,-1,-1,-1},{101,5,-1,101,-1,101,-1},{102,102,-1,102,-1,102,-1},
{103,103,-1,103,-1,103,-1}};



{
	int sym;
	bool acc;
	push(s1,0);
	push(s2,#);
	printf("请输入一个关于标识符与整数的算术表达式（不包括减法、除法运算）！");
	sym=read();
    acc=false;
	while(!acc)
	{
		t=gettop(s1);
		根据t sym查lr分析表得t;
		if(t==-1)  error();
		if(t==-2)  acc=ture;
		if(0<t<100)
		{
			push(s2,sym);
			push(s1,t);
			sym-读入下一个单词;
		}
		if(t>100)
		{
			switch(t)
			{
			case 101
			case 102
			case 102:
			{
				pop(s2)3次
				push(s2,E)
				pop(s1)3次;
				t=gettop(s1);
				根据s E查lr表得x;
				push(s1,x);
			}
			case 104:
				{
					pop(s2);
					push(s2,E);
					pop(s1);
					t=gettop(s1);
					根据t E查表得x;
					push(s1,x);
				}
			}
		}
void main( )
{
change( );
a=read();	
E( );
if(flag)
printf("成功!");
else printf("失败");
}