slr分析.cpp

slr分析

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//#include"biao1.h"
#include"biao2.h"

FILE *fp; //二元式文件

struct linkstate
{
	int value;
	linkstate *next;
};  ///构造状态栈
linkstate *stop,*sbase;//////全局变量
struct linkchar
{
	char token[10];
	linkchar *next; 
};  ////构造符号栈
linkchar *ctop, *cbase;
void initstack(); ////初始化栈
int next_token();/////取下一记号
int search_vn(char ch[]);/////查找非终结符
int search_vt(char ch[]);/////查找终结符
void SLR();   //////自下而上分析
int gettop();//////取栈顶元素
void printlink();
void pop();
void push_char(char ch[]);
void push_state(int);
////////////////////////////////////////////////////////////////////
void main()
{
	char fname[10];
	printf("请输入二元式文件名:");
	scanf("%s",fname);
	fp=fopen(fname,"r");
	if(fp==NULL) {printf("文件打不开.\n");    exit(0);}
	printf("语法分析过程如下:\n\n");
	initstack();
	SLR();
}
////////////////////////////////////////////////////////////////////
void initstack()
{    //预测分析栈初始化函数,使用不带头结点的单链表作为栈的存储结构                                              
	sbase=new linkstate;
	sbase->value=0;
	sbase->next=NULL;
	stop=sbase;

	cbase=new linkchar;
	strcpy(cbase->token,"");
	cbase->next=NULL;
	ctop=cbase;
}
void SLR()
{
	int row; /////行标号
	int column;////列表号
	int gcolumn;////gotobiao的列表号

	printf("栈			输入		操作\n");
	printf("_________________________________________________________________________\n");

	column=next_token();///////取下一记号
	row=gettop();
	while(action[row][column]!=1)
	{		
		int state;
		state=action[row][column];
		if(state>100&&state<200)/////////移进
		{		
			printlink();
			push_state(state%100);/////状态入栈
			push_char(vt[column]);/////符号入栈
			cout<<'\t'<<'\t'<<'\t'<<vt[column]<<'\t'<<'\t'<<'\t'<<"移进"<<endl;
			column=next_token();///////读下一个字符
		}
		else if(state>200&&state<300)///////归约
		{
			printlink();
			int j=strlen(fa2[state%100]);/////////产生式右部的长度
			if(strcmp("id",fa2[state%100])==0)
				pop();
			else
			{
				for(int i=0;i<j;i++)//////弹出j个字符和j个状态
					pop();
			}
			int ss=gettop();////弹出后栈顶的状态号
			push_char(fa1[state%100]);/////////将产生式的左部入栈
			gcolumn=search_vn(fa1[state%100]);
			push_state(gotobiao[ss][gcolumn]);
			cout<<"\t"<<"\t"<<'\t'<<vt[column]<<"\t"<<"\t"<<'\t'<<"按产生式 "<<fa1[state%100]<<"->"<<fa2[state%100]<<" 归约"<<endl;
		} 
		row=gettop();
		 if(action[row][column]==-1)/////////分析失败
		{
			 if(strcmp("$",vt[column])==0)/////////////如果是最后一个元素，输出分析失败
			 {
				printlink();
				cout<<'\t'<<'\t'<<'\t'<<vt[column]<<'\t'<<'\t'<<'\t'<<"分析失败!"<<endl;
				break;
			 }
			 else//////////如果不是最后一个元素，跳过
			 {
				printlink();//////
				cout<<'\t'<<'\t'<<'\t'<<vt[column]<<'\t'<<'\t'<<'\t'<<"出错!!!!!!!跳过"<<endl;
				column=next_token();
			 }
		}
	}
	if(action[row][column]==1)/////////接受
		{
			printlink();////
			cout<<'\t'<<'\t'<<'\t'<<vt[column]<<'\t'<<'\t'<<'\t'<<"接受!"<<endl;
		}
}
void pop()/////出栈操作，
{	
	linkstate *shead;////状态出栈
	shead=sbase;
	while(shead->next!=stop)/////如果shead不是倒数第2个节点，指针下移
		shead=shead->next;
	shead->next=NULL;
	free(stop);///////////释放节点
	stop=shead;
//	cout<<"stop="<<stop<<endl;

	linkchar *chead;////////字符出栈
	chead=cbase;
	while(chead->next!=ctop)/////如果shead不是倒数第2个节点，指针下移
		chead=chead->next;
	chead->next=NULL;
	free(ctop);///////释放节点
	ctop=chead;
}
void push_char(char ch[])/////将符号入栈，在节点后边插入
{
	linkchar *head=new linkchar;
	ctop->next=head;
	strcpy(head->token,ch);
	head->next=NULL;
	ctop=head;
//	cout<<"ch[]="<<ch<<endl;
}
void push_state(int m)///////////////将状态入栈
{
	linkstate *head=new linkstate;
	stop->next=head;
	head->value=m;
	head->next=NULL;
	stop=head;
//	cout<<"m="<<m<<endl;
}
int next_token()////////////////取下一个记号，并返回终结符在数组中所在位置的下标
{
	int i;/////////终结符在数组中所在位置的下标
	char ch[10]="";
	int len=1;/////字符数组中字符串的长度
	ch[0]=fgetc(fp);
	ch[1]='\0';
	while((i=search_vt(ch))==-1)////////没有找到，继续读下一个字符
	{
		ch[len]=fgetc(fp);
		len++;
		ch[len]='\0';
	}
//	cout<<"ch[len]="<<ch<<endl;
//	cout<<"next_token()"<<i<<endl;
	return i;
}
int search_vt(char ch[])/////////////查找终结符
{
//	cout<<" search_vt(char ch[])="<<ch<<endl;
	int i;
	for(i=len_vt-1;i>=0&&strcmp(ch,vt[i])!=0;i--);
//	cout<<"search_vt(char ch[])i="<<i<<endl;
	return i;
}
int search_vn(char ch[])/////查找非终结符，并返回非终结符的下标
{
	int i;
	for(i=len_vn-1;i>=0&&strcmp(ch,vn[i])!=0;i--);
	return i;
}
int gettop()/////////////////取状态栈的栈顶元素
{
	return stop->value;
}
void printlink()
{
	linkstate *sp=new linkstate;
	linkchar *cp=new linkchar;
	sp=sbase;
	cp=cbase;
	while(cp!=NULL||sp!=NULL)
	{
		cout<<cp->token<<sp->value;
		sp=sp->next;
		cp=cp->next;
	}		
}