compile3.cpp

LR分析法对表达式文法进行自底向上语法分析的算法 个个作业仅供参考

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<iomanip>
static int line=1;
bool end=1;
#define MAXLONG 20
void ACTION(char *chars);
void Print();
struct Sentence{//句型结构体
				char head;//句型开始字符
				int ch_le;//该句型右部的长度
				};
Sentence r[7]={{'S',1/*"S→E"*/},{'E',3/*"E→E+T"*/},{'E',1/*"E→T"*/},{'T',3/*"T→T*F"*/},
			   {'T',1/*"T→F"*/},{'F',3/*"F→(E)"*/},{'F',1/*"F→i"*/}};//句子变量表							
struct Table{//定义一个结构体
			int  state;//状态变量
			char V;//终结符或非终结符
			char Ne_act[4];//下一个状态
			};
Table SLR[45]= {{0,'i',"S5"},{0,'(',"S4"},{0,'E',"1"},{0,'T',"2"},{0,'F',"3"},
				{1,'+',"S6"},{1,'#',"acc"},
				{2,'+',"r2"},{2,'*',"S7"},{2,')',"r2"},{2,'#',"r2"},
				{3,'+',"r4"},{3,'*',"r4"},{3,')',"r4"},{3,'#',"r4"},
				{4,'i',"S5"},{4,'(',"S4"},{4,'E',"8"},{4,'T',"2"},{4,'F',"3"},
				{5,'+',"r6"},{5,'*',"r6"},{5,')',"r6"},{5,'#',"r6"},
				{6,'i',"S5"},{6,'(',"S4"},{6,'T',"9"},{6,'F',"3"},
				{7,'i',"S5"},{7,'(',"S4"},{7,'F',"10"},
				{8,'+',"S6"},{8,')',"S11"},
		 		{9,'+',"r1"},{9,'*',"S7"},{9,')',"r1"},{9,'#',"r1"},
				{10,'+',"r3"},{10,'*',"r3"},{10,')',"r3"},{10,'#',"r3"},
				{11,'+',"r5"},{11,'*',"r5"},{11,')',"r5"},{11,'#',"r5"}};
class STACK_I{//定义一个字符栈类		
			private:
				int   top;//栈顶指针
				int  bottom;//栈底指针				
				int stack[MAXLONG];//栈长
			public:
				STACK_I()//栈初始化，构造函数
				{top=0;bottom=0;}
				~STACK_I(){}//析构函数
				void PUSH_STACK(int num)//进栈操作
				{
					if((top-bottom)>=MAXLONG-1)//判断是否栈空
						cout<<"The STACK if full!"<<endl;
					else//入栈
					{
						stack[top]=num;
						top=top+1;
					}
				}
				void POP_STACK()//出栈顶元素
				{
					if((top-bottom)==0)//判断栈空
						cout<<"The STACK is empty!"<<endl;
					else
						{
						    top=top-1;
							stack[top]=0;
						}
				}
				void PRINT()//从左向右输出栈元素----用在分析栈
				{
					for(int j=0;j<top;j++)					
					{
						if(stack[j]>9)
						 cout<<'('<<stack[j]<<')';
					    else
					      cout<<stack[j];
					}
				}
				int GET_TOP(int n=1)//得到栈顶元素
				{
					if(n==1)
						return stack[top-1];
					else
						return stack[top-n];
				}			
			};
class STACK_C{//定义一个字符栈类		
			private:
				int   top;//栈顶指针
				int  bottom;//栈底指针				
				char stack[MAXLONG];//栈长
			public:
				STACK_C()//栈初始化，构造函数
				{top=0;bottom=0;}
				~STACK_C(){}//析构函数
				void PUSH_STACK(char const character)//进栈操作
				{
					if((top-bottom)>=MAXLONG-1)//判断是否栈空
						cout<<"The STACK if full!"<<endl;
					else//入栈
					{
						stack[top]=character;
						top=top+1;
					}
				}
				void PUSH_STACK(char const *chars)//进栈操作
				{
					int length;//字符串长临时变量
					length=strlen(chars);							
					for(int i=length-1;i>=0;i--)//字符串反向进栈
						{
						  char temp=chars[i];
						  PUSH_STACK(temp);
						}
				}
				void POP_STACK()//出栈顶元素
				{
					if((top-bottom)==0)//判断栈空
						cout<<"The STACK is empty!"<<endl;
					else
						{	stack[top-1]='\0';
						    top=top-1;
							
						}
				}
				void L_PUTOUT_STACK()//从左向右输出栈元素----用在分析栈
				{
					cout<<stack;
				}							
				void R_PUTOUT_STACK()//从右向左输出栈元素----用在剩余输入栈
				{
					for(int j=top-1;j>=0;j--)			
					cout<<stack[j];
				}
				char GET_TOP()//得到栈顶元素
				{
				  return stack[top-1];
				}			
			};
STACK_I State_Stack;//状态栈
STACK_C Ch_Stack;//符号栈
STACK_C In_Stack;//输入串栈
int tem_state;//存放状态变量的临时变量
char in_put;//存放输入符号的临时变量
char Across[4];//临时存放表的交叉信息
int GOTO;//转向的下一个变量
void main()
{
	char Input[15]="(i+i)*i#";//将要验证的输入串+i
	cout<<"步骤"<<'\t'<<"状态栈"<<'\t'<<'\t'<<"符号栈"<<'\t'<<'\t'
		<<"输入串"<<'\t'<<'\t'<<"ACTION"<<'\t'<<"GOTO"<<endl;
	In_Stack.PUSH_STACK(Input);//输入符号入栈
	State_Stack.PUSH_STACK(0);//状态栈进初始状态
	Ch_Stack.PUSH_STACK('#');//符号栈进初始符号符号进栈
do{
	int i=0;//临时计数变量
	tem_state=State_Stack.GET_TOP();//临时状态变量赋值
	in_put=In_Stack.GET_TOP();//临时输入串赋值
	//cout<<tem_state<<in_put<<endl;
	for(;i<45;i++)
	  {	
		if(SLR[i].state==tem_state&&SLR[i].V==in_put)
		  {
			strcpy(Across,SLR[i].Ne_act);
			break;
		  }
	  }
	if(i>=45)
	  {//不能向下推导句子错误
		cout<<"The sentence is wrong!"<<endl;
		end=1;
		break;
	  }
	ACTION(Across);

}while(end);
}
void ACTION(char *ch_s)
{ 
  int sta;//临时存放状态
  int j=0;//临时计数变量
  int count;//归约串的个数
  if(ch_s[0]=='S')//当状态为S1或S2--
    {
	  Print();//输出信息
	  sta=atoi(ch_s+1);//状态变量赋值
	  State_Stack.PUSH_STACK(sta);//状态变量入栈
	  Ch_Stack.PUSH_STACK(in_put);//输入串中的变量入符号栈
	  In_Stack.POP_STACK();//输入串出栈
    }
  else if(ch_s[0]=='r')
	{	  
	  sta=atoi(ch_s+1);//第几个Sentence
	  count=r[sta].ch_le;//句子长度
	  tem_state=State_Stack.GET_TOP(count+1);//新的状态
	  in_put=r[sta].head;
	  for(;j<45;j++)
		{	
		  if(SLR[j].state==tem_state&&SLR[j].V==in_put)
			{
				tem_state=atoi(SLR[j].Ne_act);
				GOTO=tem_state;
				break;
			}
		}
	  if(j==45)
	  {//不能向下推导句子错误
		cout<<"The sentence is wrong!"<<endl;
		end=1;
	  }
	  Print();
	  for(int i=0;i<count;i++)//状态栈出栈次数
		State_Stack.POP_STACK();
	  State_Stack.PUSH_STACK(tem_state);//新状态入栈
	  for(int j=0;j<count;j++)//状态栈出栈次数
	  Ch_Stack.POP_STACK();
	  Ch_Stack.PUSH_STACK(in_put);//Sentence开始符号入栈
	  
	}

  else//为可以接受的串标志结束
	{
	  Print();
	  end=0;
	}

}

void Print()//输出函数
{
	cout<<line<<'\t';//步骤数
	State_Stack.PRINT();//状态栈输出	
	cout<<'\t'<<'\t';
	Ch_Stack.L_PUTOUT_STACK();//符号栈输出
	cout<<'\t'<<'\t';
	In_Stack.R_PUTOUT_STACK();//输入栈输出
	cout<<'\t'<<'\t';
	cout<<Across<<'\t';//ACTION输出'\t'<<
	if(Across[0]=='r')//GOTO输出
		cout<<GOTO<<endl;
	else 
		cout<<endl;
	line++;//行数
}