lr(1).cpp

一个很好的用java编写的用来判断一个文法是否是LR(1)文法及其分析器的构造

#pragma warning(disable:4786)
#pragma warning(disable:4503)
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
using namespace std;

#define MAX 20
#define MAXSIZE 100
 
typedef struct product
{
	string s;
	int pcode;
	string front;
	char go;
	int point_pos;
}Item_container;

typedef set<string>Item;

typedef struct chuan//定义一个堆串
{
     char *ch;
     int length;
  }l,*pl;

struct Vn/*产生式结构*/
{
int tag;//每个非终结符的产生式个数
int info;//标记能否推出空
char ch;//标记非终结符
  pl p;
}pv[20],pv2[20],*pv1,*pv4;

struct set2//定义SELECT集
{
	int n;//非终结符的下标
	int len;//产生式的长度
	char NVT[10];//存放产生式的右部
}select[20],*ss;

typedef struct node/*first和follow集合结构*/
{
	int lable;/*表明是否是非终结符*/
	int f;/*表明是first还是 follow集*/
	union{
		int key;//终结符的下标
		char ch;//终结符的字符
	}val;
	struct node *next;
}*sq,sql;

typedef struct{
	int t,v;
}info;

typedef struct{/*定义栈结构，递归用*/
             info data[MAX];
             int top;
            }seqstack,*pseqstack;

typedef struct{/*定义栈结构，递归用*/
             char tittle[MAXSIZE];
             int top;
            }sign,*psign;

static int visited[20];//标记数组
static int y;

pseqstack  Init_seqstack(void)//定义一个符号栈
{
	pseqstack s;
  s=(pseqstack)malloc(sizeof(seqstack));
    if(s)
      s->top=-1;
   return s;
}

int push_seqstack(pseqstack s,info temp)
{
	if(s->top==MAX-1)
       return 0;
    else
	{ s->top++;
      s->data[s->top].t=temp.t;
	  s->data[s->top].v=temp.v;
      return 1;
	}
}

void pop_seqstack(pseqstack s,info *temp)
{
	if(s->top==-1)
		printf("栈空，不出栈\n");
	else
	{   temp->t=s->data[s->top].t;
		temp->v=s->data[s->top].v;
	   s->top--;
	}
}

int empty(pseqstack s)
{
	if(s->top==-1)
		return 1;
	else
		return 0;
}

void init(pl s)/*初始化串*/
{ 
	s->ch=NULL;
	s->length=0;
	
}

int strassign(pl s, char *r)/*串赋值操作*/
{    int i,n;
     if(s->ch)
     free(s->ch);/*printf("%s\n",r);gggghghgh*/
     for(i=0,n=0;r[n]!='\0';++i,++n);
 if(!i)
   { 
     s->ch=NULL;
     s->length =0;
   }
  else
     {
        if(!(s->ch=(char *)malloc(i * sizeof(char))))
        exit (0);	
		for(i=0;i<n;i++)
		s->ch[i]=r[i];
		s->ch[i]='\0';
		    s->length=n;
			
     }
    return 1;
}

int strlength(sql *s)/*求串长*/
{
	int i=0;
	sql *p=s->next;
	while(p!=NULL)
	{
		i++;
		p=p->next;
	}
	return i;

}


int clearstring (pl s)
{   
      if(s->ch!=NULL)
      {
		/*free(s->ch);清空串*/
		s->ch=NULL;
	  }
        s->length=0;
         return s->length;
}

int strinsert(pl s, int w, pl t)/*串插入*/
{
	int i;
  if(w<0||w>s->length+1) 
  return 0;
  if(t->length)
  {
	  if(!(s->ch=(char *)realloc(s->ch,(s->length+t->length)*sizeof(char))))
      exit(0);
      for(i=s->length-1;i>=w-1;--i)
      s->ch[i+t->length]=s->ch[i];
	  for(i=0;i<t->length;i++)
	  	s->ch[w+i]=t->ch[i];
	  s->ch[w+i]='\0';
       s->length+=t->length;
  }
  return 1;
}



int strindex(pl s1,pl s2,int n)/*串定位*/
{ 
	int i=n,j=0;
	if(s1->length<s2->length)
	{
       return -1;
	   }
	else
         while(i<s1->length&&j<s2->length)
		 {
			 if(s1->ch[i]==s2->ch[j])
			{
			   i++;
               j++;
			}
		    else
			{
			  i=i-j+1;
		     j=0;
			}
		 }
		    if(j>=s2->length)
			  return i-s2->length;
		    else 
			  return -1;
}

int delestr(pl s,int i,int j)//删除集合中重复的元素
{
	int k=s->length,n=j,c=i;
	if(i<0||i>s->length||i+j>s->length+1)
		return 0;
      for(n;n<k;n++)
      s->ch[c++]=s->ch[n];
	  s->ch[c]='\0';
	  s->length=k-j-i;
	  return 1;
}

void Check_kong(int c,int h,char s2[],char vn1[])//判断能否产生空串
{
	int m=h,i,pos,k,f,a,j;
	pl s1;
	s1=(pl)malloc(sizeof(l));
    init(s1);
	strassign(s1,s2);					
 for(i=0;i<c;i++)
	while(m>0)
	{ 
		for(i=0;i<c;i++)
		{ 	pos=0;	f=0;
		      if(pv1[i].tag||pv1[i].info==-1)
			  {
			     if(pv1[i].tag>1)
				 {      
					k=strindex(pv1[i].p,s1,pos);

					for(j=pos;j<k;j++)
					{	
						if(!memchr(vn1,pv1[i].p->ch[j],c))
                    {
						    f=1;
						  continue;
						}
					}
				 }
				else
				{
					for(j=0;j<pv1[i].p->length;j++)
					{
						if(!memchr(vn1,pv1[i].p->ch[j],c))
						{	
							 f=1;
							 continue;
						}
					}
			  }
			  

						if(f==1)
						{
							if(j==k||j==pv1[i].p->length)
									j=j-1;
                             
						     if(pv1[i].p->ch[j]=='@')
							 {
								pv1[i].info=1;
						        clearstring(pv1[i].p);
						        m=m-pv1[i].tag;
						        pv1[i].tag=0;							  
							 }
						     
							 else if(pv1[i].p->length==j+1)
							 {
								pv1[i].tag--;
								clearstring(pv1[i].p);	
								  m--;    
								pv1[i].info=0;		
							 }
							 
							  else
							  {
								  pv1[i].tag--;	
								    m--;    
						          h=delestr(pv1[i].p,pos,k+2); 
							  }
						}
						
				
							if(f==0)
							{
								if(j==k||j==pv1[i].p->length)
								
									j=j-1;
								
								for(a=0;a<c&&pv1[a].ch!=pv1[i].p->ch[j];a++);
							
								if(pv1[a].info==1)
								{
									if(pv1[i].p->length==j+1)
									    pv1[i].p->ch[j]='\0';
									else 
										delestr(pv1[i].p,j,j+1);
																
									if(pv1[i].p->ch[0]=='-'&&pv1[i].p->ch[1]=='>')
									{
										clearstring(pv1[i].p);
										m=m-pv[i].tag;
										pv1[i].tag=0;
										pv[i].info=1;
									}
							    	
									else if(pv1[i].p->ch[0]=='\0')
									{
									  pv1[i].p->ch=NULL;
									  pv1[i].p->length=0;
									  m=m-1;
									  pv1[i].tag--;
									}
									
									if(pv1[i].p->ch==NULL)
									{
										pv1[i].info=1;	
									}
								}	
									if(pv1[a].info==0)
									{
										m=m-1;
										pv1[i].tag--;
										delestr(pv1[i].p,pos,k+2);
									}
							}
				}
		}
	}
}

void project_set(char vn1[],int c,struct set2 select[],string ft[])
{
	queue<Item_container>qu;//队列
	Item product_Item;//小集合容器
	set<Item>Item_set;//大集合
	vector<Item_container>pi;
	vector<string>vt;

	int i,j,k,n;
	string str,str1;

	Item_container product1,product2,product3;
	product1.s=".S";
	product1.pcode=0;
	product1.front='#';
	product1.go='S';
	product1.point_pos=0;
	product_Item.insert (product1.s+','+product1.front);
	qu.push(product1);
	
	while(!qu.empty())
	{
		product2=qu.front();
		qu.pop();
      if(memchr(vn1,product2.s[product2.point_pos+1],c))
	  {
		      k=0;
        for(i=0,n=0;product2.s[product2.point_pos+1]!=vn1[i];n+=pv2[i].tag,i++);
		 k=pv2[i].tag;
		 for(j=0;j<k;j++)
		 {
		     str=select[n++].NVT;
			 str.insert(0,'.');
			 product1.s=str;
			if(product2.s[product2.point_pos+2]=='\0')
			     product1.front=product2.front;
			 else  
				 if(!memchr(vn1,product2.s[product2.point_pos+2],c))
                             product1.front=product2.s[product2.point_pos+2];
				 else{
                       for(i=0;product2.s[product2.point_pos+2]!=vn1[i];i++);
                  product1.front=ft[i];
				 }             
				 product1.point_pos=0;
			 product1.go=select[n].NVT[product1.point_pos+1];
			 product1.pcode=n+j;
             pi.push_back(product1);
		 }
		 for(vector<Item_container>::iterator vc=pi.begin();vc!=pi.end();vc++)
		 {
			 product3=*vc; 
			 if(product_Item.insert(product3.s+','+product3.front).second==true)
		      qu.push(*vc);
          } 
	  }
	}//while()循环

	Item_set.insert(Item_set.end(),product_Item);

	for(set<Item>::iterator it=Item_set.begin();it!=Item_set.end();it++)
	{
		product_Item=*it;
		for(set<string>::iterator vi=product_Item.begin();vi!=product_Item.end();vi++)
		{
			cout<<*vi<<endl;
          vt.push_back(*vi);
		}

		str=vt.front();
		vt.pop_back();

		  for(vector<Item_container>::iterator vc=pi.begin();vc!=pi.end();vc++)
		 {
			 product3=*vc; 
			 if((product3.s+','+product3.front)==str)
		      qu.push(*vc);
		   for(vector<string>::iterator vv=vt.begin();vv!=vt.end();vv++)
		   {		
		    	str1=vt.front();
		      for(vector<Item_container>::iterator vc1=pi.begin();vc1!=pi.end();vc1++)
			  { 
			    product1=*vc1; 
			    if((product1.s+','+product1.front)==str1&&product1.go==product3.go)
					qu.push(*vc1);
			  } 
		   }
		  }
	}
}

void main()
{
 void  First(struct Vn pv2[],int i,sq first[],int c,char s2[],char vn1[]);
    int Find(pseqstack S,sq st[],int v);
	 void dels(sq st[],int i);
void project_set(char vn1[],int c,struct set2 select[],string ft[]);

  int i,n,t,h=0,j=0,c=0,l;
char VN,T='@'; pl s1;
string ft[10];
     pseqstack S;
sq first[20],p;
char vn1[20],string[20],scanout[20],s2[2]={'-','>'};
 FILE *fp,*fset;
 pv1=pv;pv4=pv2; S=Init_seqstack();
   printf("请输入所用产生式的文件名：");
   scanf("%s",scanout);
if((fp=fopen(scanout,"r"))==NULL)
{
printf("\n打开词法分析的文件出错了!\n");
exit(0);
}
getchar();

 fset=fopen("set.txt","w");
 s2[2]='\0';
  while(fgets(string,20,fp)!=NULL&&!feof(fp))//从文件读入产生式
  {
	VN=string[0];
	if(VN!=T)
	{   
		pv[c].ch=VN;
		pv2[c].ch=VN;
		vn1[c]=pv[c].ch;	
		pv[c].tag=1;
		pv2[c].tag=1;
		select[h].n=c;
		pv[c].info=-1;
    	pv2[c].info=-1;
		for(i=0,l=0,n=3;string[n]!='\n';n++)
		{
			string[i++]=string[n];	
	        select[h].NVT[l++]=string[n];
		}
	    string[i]='\0'; 
        select[h].NVT[l]='\0';		
		select[h].len=l;
	    pv[c].p=(pl)malloc(sizeof(l));init(pv[c].p);
	    pv2[c].p=(pl)malloc(sizeof(l));init(pv2[c].p);
		strassign(pv1[c].p,string);	
		strassign(pv4[c].p,string);	
		T=pv[c].ch;
		t=c;
		c++;     
		h++;
	}
	else
	{   
		s1=(pl)malloc(sizeof(l));
			 init(s1);
		   pv[t].tag++;
		   pv2[t].tag++;
		   select[h].n=t;
		   for(i=0,n=3;string[n]!='\n';n++)
	          select[h].NVT[i++]=string[n];
			select[h].NVT[i]='\0';
			select[h].len=i;

		   for(i=0,n=1;string[n]!='\n';n++)
			string[i++]=string[n];
	        string[i]='\0';
			strassign(s1,string);
		  strinsert(pv[t].p, pv[t].p->length,s1 );  
 		  strinsert(pv2[t].p, pv2[t].p->length,s1 );   
 		   h++;
	}
  }  
   fclose(fp);//

     Check_kong(c,h,s2,vn1);
	 
	 for(i=0;i<c;i++)
		 pv2[i].info=pv[i].info; 

	 for(i=0;i<c;i++)//初始化FIRST和FOLLOW集合的头结点
		{
			first[i]=(sq)malloc(sizeof(sql));
			first[i]->f=-1;
			first[i]->lable=1;
			first[i]->val.key=i;
			first[i]->next=NULL;
		}//

    	for(i=0;i<c;i++)
		{
		   First(pv2,i,first,c,s2,vn1);
		}		  

		for(i=0;i<c;i++)
		{
			for(j=0;j<c;j++)
              visited[j]=0;
			Find(S,first,i);
			dels(first,i);
		} 
		
		
		for(i=0;i<c;i++)
		{				
		  p=first[i]->next;  
		  T=pv2[i].ch;
		  fprintf(fset,"first(%c)={",T);
		  j=0;
		  while(p!=NULL)
		  {
			  if(p->val.ch=='@')
				  p=p->next;
			  else{
				  string[j]=p->val.ch;
			     fprintf(fset,"%c ",p->val.ch);
			     p=p->next;
			     j++;
			  }
		  }
		  string[j]='\0';
		  ft[i]=string;
		  fprintf(fset,"}\n");	
		} 		

     	fprintf(fset,"\n\n");
         fclose(fset);
		 project_set(vn1,c,select,ft);//我在这里。。。。。
	  		

}	
		
 void First(struct Vn pv[],int i,sq first[],int c,char s2[],char vn1[])//求FIRST集合
{
	sql *s,*t;pl s1;
	int j,h,k,pos=0;
	t=first[i];
	s1=(pl)malloc(sizeof(l));
    init(s1);
	strassign(s1,s2);

	for(j=0;j<pv[i].p->length;)
	{
		if(pv[i].p->ch[j]!='-'&&pv[i].p->ch[j]!='>')
		{			
			h=strindex(pv[i].p,s1,pos);
			if(pv[i].p->ch[j]=='@'||!memchr(vn1,pv[i].p->ch[j],c))
			{
				s=(sq)malloc(sizeof(sql));
				s->val.ch=pv[i].p->ch[j];
				s->f=0;
				s->lable=0;
				t->next=s;
				t=s; 
				if(h>0)
				{
					j=h+2;
			        pos=j;
				}
				else
				j=pv[i].p->length;
			}
		
			else
			{
				for(k=0;k<c&&pv[i].p->ch[j]!=vn1[k];k++);
					s=(sq)malloc(sizeof(sql));
					s->val.key=k;
					s->f=1;
					s->lable=1;
					t->next=s;
					t=s;
				  if(h>0)
				  { 
					if(pv[k].info==1)
					{	
					   if(j<h)
						 j++; 
					}
					  else
					  {	
					    j=h+2;
					     pos=j;
					   }
				  }	
				  else
				{
					if(pv[k].info==1)
						j++;
					else
					{	
					j=pv[i].p->length;					  
					}

				}
			}
		}
		else 
		{
			j=h+2;
		pos=j;
		}
	}		  
	t->next=NULL;
}
				   
int Repstr(sql *s,int i,int j,sql *t)//串替换
{
	int k;
	sql *p=s->next,*pl=t->next,*q,*r=s;
	if(i<=0||i>strlength(s)||j<0||i+j-1>strlength(s))
		return 0;
	for(k=0;k<i-1;k++)
	{
		r=p;
		p=p->next;
	}
	for(k=0;k<j;k++)
	    p=p->next;
	
	while(pl!=NULL)
	{	
		q=(sq)malloc(sizeof(sql));
		if(pl->lable==0)			  
             q->val.ch=pl->val.ch;
		else
			 q->val.key=pl->val.key;
		 q->f=pl->f;
	     q->lable=pl->lable;	
	     q->next=NULL;	
	      r->next=q;
		r=q;
		pl=pl->next;
	}	
	while(p!=NULL)
	{	
		
		r->next=p;
		r=p;	
		p=p->next;
	}
	r->next=NULL;/**/
	return 1;
}
	
int Find(pseqstack S,sq st[],int v) 
{
	sql *p;
	info temp;
    int	t=0,j,k;
	visited[v]=1;
	p=st[v]->next;	
	while(p!=NULL)
	{
		t++;		
		if(p->lable==1)
			if(visited[p->val.key]==0)
			{	
				temp.t=t;
				temp.v=v;
				push_seqstack(S,temp); 
				Find(S,st,p->val.key);			
				y=p->val.key;
                t=t+strlength(st[y])-1;
			}		 

			p=p->next;
	}				
	if(!empty(S))
	{  
		pop_seqstack(S,&temp);
		k=temp.v;
		j=temp.t;				
	    Repstr(st[k],j,1,st[v]);
	}
	return 0;
}

 void dels(sq st[],int i)//删除集合中重复的元素
{
	 sql *p=st[i]->next,*q,*r,*t;
	 while(p!=NULL)
	 {
		 q=p;
		 r=q->next;
		 while(r!=NULL)
		 {
		   if(r->lable==1&&r->f==2)
		   {
			   if(r->val.key!=i)
			 {
				   if(r->val.key==p->val.key)
				   {
					   t=r->next;
			           q->next=t;
			           free(r);
			           r=t;
				   }
			  
				   else
				   {
			        q=r;
			        r=r->next;
				   }
			   }
		   else
		   {
			   t=r->next;
			   q->next=t;
			   free(r);
			   r=t;
		   }
		 }
		   else
		   {
			   if(r->val.ch==p->val.ch)
			   {
				   t=r->next;
				   q->next=t;
				   free(r);
			        r=t;
			   }
			   	else
				{
			        q=r;
			        r=r->next;
				}
			   }
		 }
	 p=p->next;
	 }
}
/**/