slr.cpp

实验SLR(1)分析表的构造,和大家分享一下.

#include "SLR.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <conio.h>


SLR::SLR() : Grams()
{
	slrchain=0;
}


int SLR::linksp(struct Stat *st, struct Sp *sp){
	struct Sp *psp=st->sp;
	struct Sp *psp_pre=psp;
	int i=1;

	while(psp){
		if(sp->gid == psp->gid){
			if(sp->dot == psp->dot){		//此状态已存在
				return 0;
			}else if(sp->dot < psp->dot){
				break;
			}
		}else if(sp->gid < psp->gid){
			break;
		}
		psp_pre=psp;
		psp=psp->next;
		i++;
	}

	if(psp==psp_pre){	//需修改首Sp
		sp->next=st->sp;
		st->sp=sp;
	}else{
		sp->next=psp;
		psp_pre->next=sp;
	}

	if(unendid(getright(sp->gid)[sp->dot])!=-1){
		i*=-1;
	}

	return i;
}


int SLR::closegrm(struct Stat *st){
	struct Sp *sp=st->sp;
	char c;
	int s=0, k=0;

	while(sp){
	//	if(!k){
			c=getright(sp->gid)[sp->dot];		//取出期待输入符
	//	}
		if(k||(unendid(c)!=-1)){		//为非终结符，需闭包
			k=0;
			struct Gram *pc=gchain;
			int i=0;
			while(pc){
				if(getleft(i)==c){
					struct Sp *newsp=(struct Sp*)malloc(sizeof(struct Sp));
					newsp->gid=i;
					newsp->dot=0;
					newsp->next=0;

					int j=linksp(st,newsp);
					if(!j){
						free(newsp);
					}else if((j<0)&&(j*-1-1<=s)){	//连接后新状态在前，需回到新状态继续检测
						sp=newsp;
						k=1;
						s=j*-1-1;
						break;
					}
				}
				pc=pc->next;
				i++;
			}
		}
		if(!k){
			sp=sp->next;
			s++;
		}
	}

	return s;
}


struct Stat* SLR::crestat(char c){
	struct Stat *st=(struct Stat*)malloc(sizeof(struct Stat));
	st->in=c;
	st->next=0;
	st->sp=0;
	st->slract=(int*)malloc(sizeof(int)*endc);
	st->slrgoto=(int*)malloc(sizeof(int)*unendc);
	for(int i=0; i<endc; i++){
		st->slract[i]=0;
	}
	for(i=0; i<unendc; i++){
		st->slrgoto[i]=0;
	}

	return st;
}


struct Stat* SLR::tostat(struct Stat* st){
	struct Sp *sp=st->sp;
	struct Stat *stmp=0;
	char c;

	while(sp){
		if(c=getright(sp->gid)[sp->dot]){		//未能归约
			
			struct Stat *smp=stmp;

			struct Sp *stp=(struct Sp*)malloc(sizeof(struct Sp));
			stp->dot=sp->dot+1;
			stp->gid=sp->gid;
			stp->next=0;

			while(smp){
				if(smp->in==c){	//找到已存在临时状态匹配
					struct Sp *ttp=smp->sp;
					while(ttp->next){
						ttp=ttp->next;
					}
					ttp->next=stp;
					c=0;
					break;
				}
				if(smp->next){
					smp=smp->next;
				}else{
					break;
				}
			}
			//找不到匹配临时状态，创建
			if(c){
				if(stmp){
					smp->next=crestat(c);
					smp=smp->next;
					smp->sp=stp;
				}else{
					stmp=crestat(c);
					stmp->sp=stp;
				}
			}
		}else{		//归约
			c=getleft(sp->gid);
			char* pf=getfollow(c);
			
			int u=0;
			for(;pf[u];u++){
				if(c!=*unends||(st->sp->dot!=1)){
					st->slract[endid(pf[u])]=(sp->gid+1)*-1;
				}
			}
		}
		sp=sp->next;
	}

	return stmp;
}


int SLR::chestat(struct Stat* st){
	struct Stat *tst=slrchain;

	int i=0, s=0;

	while(tst){
		if(tst->in==st->in){
			struct Sp *stp=st->sp;
			struct Sp *tstp=tst->sp;
			while(tstp){
				if(!stp){
					s=1;
					break;
				}
				if((stp->gid!=tstp->gid)||(stp->dot!=tstp->dot)){
					s=1;
					break;
				}
				tstp=tstp->next;
				stp=stp->next;
			}
			if(s){
				s=0;
			}else{
				return i;
			}
		}
		tst=tst->next;
		i++;
	}

	return i*-1;
}


int SLR::creatslr(){
	slrchain=crestat(0);
	struct Stat *st=slrchain;
	st->sp=(struct Sp*)malloc(sizeof(struct Sp));

	st->sp->gid=0;
	st->sp->dot=0;
	st->sp->next=0;

	closegrm(st);		//闭包

	do{
		//生成临时状态链并归约
		struct Stat *tsp=tostat(st);
		struct Stat *tmp=tsp;
		struct Stat *tmp_pre=tmp;
		int n=0;		//记录临时状态链保留个数

		
		while(tmp){
			closegrm(tmp);

			int i=chestat(tmp);		//得到临时状态序号和存在状态

			char c=tmp->in;
			if(i>=0){		//已存在，应删除
				//写slr表
				if(endid(c)!=-1){	//为终结符
					st->slract[endid(c)]=i+1;
				}else{
					st->slrgoto[unendid(c)]=i;
				}

				if(tmp_pre==tmp){
					tsp=tmp->next;
					free(tmp);
					tmp=tmp_pre=tsp;
				}else{
					tmp_pre->next=tmp->next;
					free(tmp);
					tmp=tmp_pre->next;
				}
			}else{		//新状态
				if(endid(c)!=-1){	//为终结符
					st->slract[endid(c)]=i*-1+n+1;
				}else{
					st->slrgoto[unendid(c)]=i*-1+n;
				}

				tmp_pre=tmp;
				tmp=tmp->next;
				
				n++;
			}
		}

		
		//连接临时状态链到根状态链
		tmp=slrchain;
		while(tmp->next){
			tmp=tmp->next;
		}

		tmp->next=tsp;

		st=st->next;
	}while(st);

	return 0;
}


int SLR::printslr(){
	int n=0;
	//char c;
	struct Stat *st=slrchain;

	printf("状态 ");
	while(ends[n]){
		printf("%c   ",ends[n]);
		n++;
	}
	n=0;
	while(unends[n]){
		printf("%c  ",unends[n]);
		n++;
	}
	n=0;

	printf("\n");
	while(st){
		printf("%-4d ",n);
		int i=0;
		while(ends[i]){
			if(st->slract[i]>0){
				printf("S%-2d ",st->slract[i]-1);
			}else if(st->slract[i]){
				printf("r%-2d ",st->slract[i]*-1-1);
			}else if((ends[i]=='#')&&(st->sp->gid==0)&&(st->sp->dot==1)){
				printf("acc ");
			}else{
				printf("    ");
			}
			i++;
		}
		i=0;
		
		while(unends[i]){
			if(st->slrgoto[i]){
				printf("%-2d ",st->slrgoto[i]);
			}else{
				printf("   ");
			}
			i++;
		}

		st=st->next;
		n++;
		printf("\n");
	}

	return n;
}


int SLR::anyslr(char *s){
	int statn=0;
	struct Stat *tstp=slrchain;

	while(tstp){
		statn++;
		tstp=tstp->next;
	}

	int *statstack=(int*)malloc(sizeof(int)*statn);
	char *symstack=(char*)malloc(statn+3);
	int statp=0;
	int symp=0;
	int sp=0;

	int n=1;

	//初始化栈
	statstack[statp]=0;
	symstack[symp]=*ends;
	printf("步骤 状态栈    符号栈    输入串    \n");
	do{
		//n++;
		printf("%-4d ",n);
		n++;
	
		//打印状态栈
		for(int k=0; k<=statp; k++){
			printf("%d.",statstack[k]);
		}

		//打印符号栈
		symstack[symp+1]=0;
		printf("     %s",symstack);

		//打印输入串
		printf("     %s",s+sp);

		//打印Action & Goto
		struct Stat *stpt=slrchain;
		for(k=0; k<statstack[statp]; k++){
			stpt=stpt->next;
		}

		int h,r;
		if((h=endid(s[sp]))!=-1){
			if((r=stpt->slract[h])>0){	//Action
				symstack[++symp]=s[sp++];
				statstack[++statp]=stpt->slract[h]-1;
				printf("     S%d\n",statstack[statp]);
			}else if(r){	//Action & Goto
				r=r*-1-1;
				printf("     r%d",r);

				symp-=strlen(getright(r));

				symstack[++symp]=getleft(r);

				stpt=slrchain;
				for(int k=0; k<statstack[statp-1]; k++){
					stpt=stpt->next;
				}

				statstack[statp]=stpt->slrgoto[unendid(symstack[symp])];
				if(statstack[statp]){
					printf("     %d\n",statstack[statp]);
				}else{
					printf("     Error\n");
					if(statstack){
						free(statstack);
					}
					if(symstack){
						free(symstack);
					}
					return -3;
				}
			}else{
				if((s[sp]=='#')&&(stpt->sp->gid==0)&&(stpt->sp->dot==1)){
					printf("     acc\n");
					if(statstack){
						free(statstack);
					}
					if(symstack){
						free(symstack);
					}
					return 0;
				}else{
					printf("     Error\n");
					if(statstack){
						free(statstack);
					}
					if(symstack){
						free(symstack);
					}
					return -1;
				}
			}
		}else{
			printf("     Error\n");
			if(statstack){
				free(statstack);
			}
			if(symstack){
				free(symstack);
			}
			return -2;
		}
	}while(1);
}

SLR::~SLR(){
	struct Stat *s;
	while(slrchain){
		struct Sp *p=slrchain->sp;
		struct Sp *tp;
		while(p){
			tp=p;
			p=p->next;
			free(tp);
		}

		if(slrchain->slract){
			free(slrchain->slract);
		}
		if(slrchain->slrgoto){
			free(slrchain->slrgoto);
		}

		s=slrchain;
		slrchain=slrchain->next;
		free(s);
	}
}