analysis.c

编译原理LL1语法分析的实验程序

#include"global.h"
void init_analy(struct analy*t,int i){
	t->interm=i;
	t->isnull=0;
	t->first=NULL;
	t->follow=NULL;
	t->next=NULL;
	t->row=NULL;
};
//find 
struct analy* find_analy(int i){
	struct analy*temp;
	for(temp=ff;temp!=NULL;temp=temp->next)
		if(temp->interm==i)
			break;
	return temp;
}
//is int i int list a
struct node* find_element(struct node*start,int n){
	struct node*temp;
	for(temp=start;temp!=NULL;temp=temp->next){
		if(temp->element==n)
			break;
	}
	return temp;
}
//put element of a to b,*f==0 meaning first 
int  add_analy(int a,int af,int b,int bf){
	struct analy *ap;
	struct analy *bp;
	struct node*temp_b;
	struct node**temp_a;
	struct node *temp;
	int i,n;
	//find a and b;
	ap=find_analy(a);
	if(ap==NULL){
		printf("can't find %d,%s",a,ass_sym(a));
		return 0;
	}
	bp=find_analy(b);
	if(bp==NULL){
		printf("can't find %d,%s",b,ass_sym(b));
		return 0;
	}
	if(af==0)
		temp_a=&ap->first;
	else
		temp_a=&ap->follow;
	temp_b=(bf==0)?bp->first:bp->follow;
	n=0;
	for(;temp_b!=NULL;temp_b=temp_b->next){
		i=temp_b->element;
		temp=find_element(*temp_a,i);
		if(temp!=NULL)
			continue;
		n++;
		temp=*temp_a;
		*temp_a=(struct node*)malloc(sizeof(struct node));
		(*temp_a)->next=temp;
		(*temp_a)->element=i;
	}
	return n;
};
//add a node to the M[A,a],
int add_analy_m(int interm,int term,int pro){
	struct analy*temp_a;
	struct analy_node*temp_b;
	for(temp_a=ff;temp_a!=NULL;temp_a=temp_a->next)
		if(temp_a->interm==interm)
			break;
	if(temp_a==NULL){
		printf("can't find %s\n",ass_sym(interm));
		return -1;
	}
	for(temp_b=temp_a->row;temp_b!=NULL;temp_b=temp_b->next)
		if(temp_b->terminal==term&&temp_b->production==pro)
			break;
	if(temp_b!=NULL){
		return 1;
	}
	temp_b=temp_a->row;
	temp_a->row=(struct analy_node*)malloc(sizeof(struct analy_node));
	temp_a->row->next=temp_b;
	temp_a->row->terminal=term;
	temp_a->row->production=pro;
	return 0;
}
//is this symbol noted null ,0 mean null
int getnull(int i){
	struct analy*t;
	if(i==bound_v-1)
		return 0;
	if(i<bound_v)
		return 1;
	t=find_analy(i);
	if(t==NULL){
		printf("error can't find assign %d\n",i);
		return 0;
	}
	if(t->isnull==1)
		return 0;
	return 1;
}

//here nin mean number of interminal,np mean number of production
int analy_p_null(int i){
	int n,*t;
	struct analy*temp;
	t=pro_l[i].p;
	for(n=1;n<=max_right_d;n++){
		if(t[n]==0)
			break;
		if(getnull(t[n]))
			return 0;
	}
	temp=find_analy(t[0]);
	temp->isnull=1;
	return 1;
}
int analy_p_first(int i){
	int n,*t;
	struct analy*temp_a;
	struct node*temp;
	t=pro_l[i].p;
	temp_a=find_analy(t[0]);
	for(n=1;n<=max_right_d;n++){
		if(t[n]==0)
			break;
		if(t[n]==bound_v-1)
			break;
		if(t[n]<bound_v){
			temp=find_element(temp_a->first,t[n]);
			if(temp!=NULL)
				break;//already in the first set
			temp=temp_a->first;
			temp_a->first=(struct node*)malloc(sizeof(struct node));
			temp_a->first->element=t[n];
			temp_a->first->next=temp;
			break;
		}
		//here t[n+1] must be a interminal
		//put FIRST(t[n+1])to FIRST(t[0])
		add_analy(t[0],0,t[n],0);
		//can't derive null
		if(getnull(t[n])==1)
			break;
	}
	return 0;
}
int analy_p_follow(int i){
	struct analy*temp_a;
	struct node*temp;
	int j,n,*t;
	t=pro_l[i].p;
	for(n=1;n<max_right_d;n++){
		if(t[n]==0)
			break;
		if(t[n]<bound_v)
			continue;
		//here t[n] is interminal
		for(j=n+1;j<=max_right_d;j++){
			if(t[j]==0)
				break;
			if(t[j]<bound_v){
				temp_a=find_analy(t[n]);
				if(find_element(temp_a->follow,t[j])!=NULL)
					break;
				temp=temp_a->follow;
				temp_a->follow=(struct node*)malloc(sizeof(struct node));
				temp_a->follow->next=temp;
				temp_a->follow->element=t[j];
				break;
			}
			//here t[j] is interminal
			add_analy(t[n],1,t[j],0);
			if(getnull(t[j])!=0)
				break;
		}
		//if it break at the end of the production,
		if((j==max_right_d+1)||(t[j]==0))
			add_analy(t[n],1,t[0],1);
	}
	return 0;
}
int analy_p(int i){
	int n,*t;
	struct analy*temp_a;
	struct node* temp;
	t=pro_l[i].p;
	for(n=1;n<=max_right_d;n++){
		if(t[n]==0)
			break;
		if(t[n]==bound_v-1)
			break;
		if(t[n]<bound_v){
			add_analy_m(t[0],t[n],i);
			return 1;
		}
		//here t[n] is interminal
		temp_a=find_analy(t[n]);
		for(temp=temp_a->first;temp!=NULL;temp=temp->next)
			add_analy_m(t[0],temp->element,i);
		if(temp_a->isnull!=1)
			return 1;
	}
	//here t[0] can derive null
	temp_a=find_analy(t[0]);
	for(temp=temp_a->follow;temp!=NULL;temp=temp->next)
		add_analy_m(t[0],temp->element,i);
	return 0;
}
void analysis(void){
	struct node*temp;
	struct analy*temp_a;
	int nin,np,i,j;
	//count
	nin=0;
	for(temp_a=ff;temp_a!=NULL;temp_a=temp_a->next)
		nin++;
	for(np=0;np<max_production;np++)
		if(pro_l[np].p[0]==0)
			break;
	// first let's note the symbol which can derive null 
	for(i=0;i<nin;i++)
		for(j=0;j<np;j++)
			analy_p_null(j);
	//let's construct the FIRST set
	for(i=0;i<nin;i++)
		for(j=0;j<np;j++)
			analy_p_first(j);
	//let's construct the FOLLOW set
	//add $ to FOLLOW(start)
	temp_a=find_analy(bound_v);
	temp=(struct node*)malloc(sizeof(struct node));
	temp_a->follow=temp;
	temp->element=0;
	temp->next=NULL;
	for(i=0;i<nin;i++)
		for(j=0;j<np;j++)
			analy_p_follow(j);
	//now let's construct the anlay table
	for(j=0;j<np;j++)
		analy_p(j);
	printf("end analysis\n");
}

/*
//test
int main(void){
	FILE*in;
	int i;
	struct analy*temp_a;
	struct node*temp;
	struct analy_node*temp_b;
	in=fopen("g.txt","r");
	load_grammer(in);
	fclose(in);
	//print all productions
	for(i=0;i<max_production;i++){
		if(pro_l[i].p[0]==0)
			break;
		print_pro(i);
	}
	analysis();
	//print the FIRST and FOLLOW set
	for(temp_a=ff;temp_a!=NULL;temp_a=temp_a->next){
		printf("FIRST(%s)=\t",ass_sym(temp_a->interm));
		for(temp=temp_a->first;temp!=NULL;temp=temp->next)
			printf("%s\t",ass_sym(temp->element));
		if(temp_a->isnull==1)
			printf("null");
		printf("\nFOLLOW(%s)=\t",ass_sym(temp_a->interm));
		for(temp=temp_a->follow;temp!=NULL;temp=temp->next)
			printf("%s\t",ass_sym(temp->element));
		printf("\n");
	}
	//print the M[A,a] table
	for(temp_a=ff;temp_a!=NULL;temp_a=temp_a->next)
	{
		printf("%s\n",ass_sym(temp_a->interm));
		for(temp_b=temp_a->row;temp_b!=NULL;temp_b=temp_b->next){
			printf("\t\t%s\t\t",ass_sym(temp_b->terminal));
			print_pro(temp_b->production);
		}
	}
	parse();
	return i;
}*/