testfirst.c

一个C语言编译器

	}
	if(p->index==5 && p->position==2)
	{
		if(i_size!=7)
		printf("add cluster error\n");
	}
    return head;
}  
int is_in_cluster(struct cluster test)
{
	int i;
	int j;
	int flag=0;
	struct item *q;	
	for(i=0;i<curr_state;i++)
	{
		q=test.head;
        if(test.size!=item_cluster[i].size)		
             continue;
		for(j=0;j<test.size;j++)		
		{
		
             if(add_more_item(q,i))
				{
                 flag=1;           
                 break;
                } 
                                 
			q=q->next;
		}	
		if(!flag)	
		return i;
		if(flag)
			flag=0;
	}
	//if(i==7)
	//	printf("can't find it\n");
	return -1;
}


struct cluster *goto_state(int state_index,int T_index)
{
	//int add[R_SIZE];
	int i;
	struct item *p;
	struct item header;
	struct item *curr;
	struct cluster *cer;
	cer=(struct cluster *)malloc(sizeof(struct cluster));
	cer->size=0;
	p=item_cluster[state_index].head;
	//for(i=0;i<R_SIZE;i++)
	//	add[i]=0;
	curr=cer->head=(struct item *)malloc(sizeof(struct item));
	curr->next=NULL;
	//printf(" ----- goto %c -------\n",NT[T_index]);
	for(i=0;i<item_cluster[state_index].size;i++)
	{
		
		if(infer[p->index].s[p->position]==T_index)
		{		
				if(infer[p->index].s[p->position+1]>=0 && infer[p->index].s[p->position+1]<N_SIZE)			
				{	
					header.index=p->index;
					header.position=p->position+1;
					header.next=NULL;
						if(!cer->size)
						{				
						curr=get_closure(&header);
						free(cer->head);
						cer->head=curr;
						}
						else
						curr->next=	get_closure(&header);			
						
						//printf("get closure success\n");
						while(curr->next!=NULL)
						{
							cer->size++;
							curr=curr->next;
						} 
						cer->size++;
					//	printf("----closure of last item to state:%d goto %c---index:%d,position:%d",state_index,NT[T_index],curr->index,curr->position);
				}
				else if(infer[p->index].s[p->position+1]>=N_SIZE)
				{				
			   		
					if(!cer->size)
					{				
						curr->index=p->index;
						curr->position=p->position+1;					
						cer->size++;						
					}
					
					else
					{
						curr->next=(struct item  *)malloc(sizeof(struct item));
						curr->next->index=p->index;
						curr->next->position=p->position+1;
						curr->next->next=NULL;						
						cer->size++;
						curr=curr->next;					
					}	

				}
				else ;       			
				
		}
		
		p=p->next;
	}
	
	if(!cer->size)
	{     
     free(cer->head);
     free(cer);
     return NULL;
    }        
	return cer;
}

void free_block(struct cluster *cer)
{
	struct item *head;
	struct item *curr;
	int i;
	head=cer->head;
	for(i=0;i<cer->size;i++)
	{
		curr=head->next;
		free(head);
		head=curr;
	}
	free(cer);
}
void items()
{
    int i,j,k;
	struct item header;
	int f_number,n_number;
/*	header.index=0;
	header.position=1;
	header.next=NULL;
	closure(&header);*/
	struct cluster *cer; 
	f_number=1;
	n_number=0;
	freopen("err.txt","wr",stdout);
	while(f_number!=n_number)
	{
	    f_number=curr_state;
	    //printf("-----begin item:%d-----\n",f_number);
	   for(i=0;i<f_number;i++)
	{
		for(j=0;j<N_SIZE+T_SIZE;j++)
		{
			if(j==ntoindex('$'))
				continue;
			cer=goto_state(i,j);
		//	printf("goto %d,%d\n",i,j);
			if(cer==NULL)
			continue;			
			k=is_in_cluster(*cer);	
			if(k==4 && j<N_SIZE)
					printf("---state %d,T_index:%d goto state %d---\n",i,j,k);
			if(k==-1)
			{
				item_cluster[curr_state]=*cer;
				gto[i][j]=curr_state;
				curr_state++;
				if(j<N_SIZE)
				printf("add cluster state %d:from (%d, %c)\n",curr_state-1,i,NT[j]);
			}
			else if(k>=0)
			{
				gto[i][j]=k;
				if(j<N_SIZE)
				printf("goto cluster state %d:from (%d, %c)\n",k ,i,NT[j]);
				free_block(cer);
			}
			else ;
		}
	}
	n_number=curr_state;

	}	
}

void print_item()
{
	int i,j,k;
	struct item *curr;
	struct item *move;
	printf("-----item group------\n");
	printf("-----max state:%d----------\n",curr_state);
	for(i=0;i<curr_state;i++)
	{
		curr=item_cluster[i].head;
		printf("----state %d\n",i); 
		for(j=0;j<item_cluster[i].size;j++)
		{
			printf("infer %d:%c--->",curr->index,NT[infer[curr->index].s[0]]);
			for(k=1;k<=infer[curr->index].len;k++)
			{
				if(k==curr->position)
					printf(".");
				if(infer[curr->index].s[k]==ntoindex(ID))
					printf("ID");
				else
					printf("%c",NT[infer[curr->index].s[k]]);

			}
			if(curr->position>infer[curr->index].len)
			printf(".");
			printf("\n");
			curr=curr->next;
		}
	}
	printf("-----item group------\n"); 
	printf("-----goto matrix--------\n");
	printf("------------");
	for(i=N_SIZE;i<N_SIZE+T_SIZE;i++)
		printf("%c     ",NT[i]);
	printf("\n");
	
	for(i=0;i<curr_state;i++)
	{
		if(i<10)
		printf("%d\t    ",i); 
		else
		printf("%d\t    ",i); 
		for(j=N_SIZE;j<N_SIZE+T_SIZE;j++)
		{
			if(gto[i][j]>10 || gto[i][j]< 0)
			{
				printf("%d    ",gto[i][j]);
				continue;
			}
			printf("%d     ",gto[i][j]);
		}
		printf("\n");
	}
	printf("-----goto matrix--------");
}
void get_action()
{
	int i,j,k,m,n,b;
	struct item *curr;
	n=ntoindex('$');
	printf("--------GET ACTION----------\n");
	for(i=0;i<curr_state;i++)
	{
		curr=item_cluster[i].head;
		for(j=0;j<item_cluster[i].size;j++)
		{
			k=infer[curr->index].s[curr->position];
			m=infer[curr->index].s[0];		
			printf("state %d item %d:infer %d[%c],position %d[%c]\n",i,j,curr->index,NT[m],curr->position,NT[k]);
			  if(k==n && m==0)
			{				
					printf("enter branch 1\n");
					action[i][n-N_SIZE].actioning=0;					
			}
			else if(k==n && m!=0)
			{ 
				printf("enter branch 2\n");			
				for(b=0;b<Follow[m].len;b++)
				{
					printf("enter follow (%d,%c)\n",b,NT[Follow[m].s[b]]);
					{
						action[i][Follow[m].s[b]-N_SIZE].actioning=1;
						action[i][Follow[m].s[b]-N_SIZE].number=curr->index;
					}
				}
			}
			else if(k>=N_SIZE)
			{
				printf("enter branch 3\n");
				if(gto[i][k]>=0)
				{					
					printf("enter goto %d,%d[%c]\n",i,k,NT[k]);
					action[i][k-N_SIZE].actioning=2;
					action[i][k-N_SIZE].number=gto[i][k];
					printf("action (%d,%d)=(%d,%d)\n",i,k-N_SIZE,action[i][k-N_SIZE].actioning,action[i][k-N_SIZE].number);
				}

			}
			
			else ;
			curr=curr->next;
			printf("action %d=%d\n",j,action[i][j].actioning);
		}
		for(j=0;j<T_SIZE;j++)
			printf("action[%d]=%d\n",j,action[i][j].actioning);
		printf("\n");
	}
}
void print_action()
{
	int i,j,k;
	printf("----------------action function-----------\n");
	printf("--state list--");
	for(j=0;j<T_SIZE;j++)
		printf("%c       ",NT[j+N_SIZE]);
	printf("\n");

	for(i=0;i<curr_state;i++)
	{
		if(i>=10)
			printf("%d\t     ",i);
		else
			printf("%d\t     ",i);		
		for(j=0;j<T_SIZE;j++)
		{
			if(action[i][j].actioning==0)
				printf("sr      ");
			else if(action[i][j].actioning==-1)
				printf("-1      ");
			else if(action[i][j].actioning==1)
			{
				if(action[i][j].number>10)
				printf("r%d     ",action[i][j].number);
				else
				printf("r%d      ",action[i][j].number);
			}
			else if(action[i][j].actioning==2)
			{
				if(action[i][j].number>10)
				printf("s%d     ",action[i][j].number);
				else
				printf("s%d      ",action[i][j].number);
			}
			else ;
			/*printf("(%d,%d)",action[i][j].actioning,action[i][j].number);
			if(action[i][j].actioning==-1)
				printf(" ");
			if(action[i][j].number >10 || action[i][j].number < 0)
				printf(" ");*/
		}
		printf("\n");
	}	
	printf("action (0,2)=(%d,%d)\n",action[0][2].actioning,action[0][2].number);
}
void init_stack()
{
		main_stack.top=-1;
		main_stack.[++main_stack.top].tag=0;
		main_stack.[main_stack.top].value=0;
}
struct s_stack  pop_stack()
{	
	return main_stack.syntax_stack[main_stack.top--];
}
void push_stack(struct s_stack st)  //保持top始终指向一个新加入的项
{
	main_stack.top++;
	if(full_stack())
	{
		printf("can"t push,stack is full\n");
			reutrn ;
	}
	main_stack..syntax_stack[main_stack.top]=st;
}
int empty_stack()
{
	if(main_stack.top<=-1)
	{
		printf("empty syntax stack\n");
		return 1;
    }
	return 0;
}
int full_stack()
{
	if(main_stack.top>=STACK_SIZE)
	{
		printf("syntax stack full\n"):
		return 1;
	}
	return 0;
}
struct s_stack top_stack()
{
	return main_stack.syntax_stack[main_stack.top];
}
void print_infer(int index)
{
	int i;
	printf("infer %d: %c-->",index,NT[infer[index].s[0]]);
	for(i=1;i<infer[index].len;i++)
	{
		printf("%c",NT[infer[index].s[i]]);	
	}
	printf("\n");
}
void syntax()
{
	int i,j;
	int token;
	int token_index;
	int top_state;
	struct s_stack temp;
	int s_number;
	token=word_parse();
	init_stack();
	token_index=ntoindex(token);
	temp=top_stack();
	top_state=temp.value;
	while(token!=DONE)
	{
		if(action[top_state][token_index].actioning==2)
		{
				temp.tag=1;
				temp.value=token_index;
				push_stack(temp);
				temp.tag=0;
				temp.value=action[top_state][token_index].number;
				push_stack(temp);
				token=word_parse();
				token_index=ntoindex(token);
				temp=top_stack();
				top_state=temp.value;
		}
		else if(action[top_state][token_index].actioning==1)
		{
				for(i=0;i<infer[action[top_state][token_index].number].len;i++)
					if(!empty_stack())
						pop_stack();
				j=infer[action[top_state][token_index].number].s[0];
				temp.tag=1;
				temp.value=j
				push_stack(temp);
				temp=top_stack();
				top_state=temp.value;
				temp.tag=0;
				temp.value=gto[top_state][j];
				push_stack(temp);			
				print_infer(action[top_state][token_index].number);
			 
		}
		else if(action[top_state][token_index].actioning==0)
		{
				printf("------infer sentence %d over-------\n",s_number++);
				token=word_parse();
				token_index=ntoindex(token);
				temp=top_stack();
				top_state=temp.value;
		}
		else
			syntax_error(token_index);
			
	}
}
int main()
{
	int i;
	int j,k;
	int add[R_SIZE];
	struct item header;
	struct item *move;
	init_syntax();
	k=-1;
	j=0;
	printf("---infer print-----\n");
		for(i=0;i<R_SIZE;i++)
	{
		printf("--- %c -->",NT[infer[i].s[0]]);
		for(j=1;j<=infer[i].len;j++)
		{
			if(infer[i].s[j]==ntoindex(ID))
			printf(" ID ");
			else
            printf("%c", NT[infer[i].s[j]]);
		}
		printf("----\n");
	}
		printf("---infer print-----\n");
	while(j!=k)
	{
	printf("-----total len----\n");
    j=total_len(First);
    printf("begin:%d    ",j);
	for(i=R_SIZE-1;i>=0;i--)
		first(i);
	k=total_len(First);
   printf("end :%d\n",k);   
	}
	printf("------First group--------\n");
	for(i=0;i<N_SIZE;i++)
	{
		printf("---First(%c)={",NT[i]);
		for(j=0;j<First[i].len;j++)
		{
			    if(First[i].s[j]==ntoindex(ID))
			    printf(" ID ");
			    else
               printf("%c  ", NT[First[i].s[j]]);
		}
		printf("}\n");
	}
	printf("---------Follow group------------\n");
	do
	{
	printf("-----total len----\n");
    j=total_len(Follow);
    printf("begin:%d    ",j);
	for(i=R_SIZE-1;i>=0;i--)
		follow(i);
	k=total_len(Follow);
   printf("end :%d\n",k);   
	}	while(j!=k);
		
  for(i=0;i<N_SIZE;i++)
	{
		printf("---Follow(%c)={",NT[i]);
		for(j=0;j<Follow[i].len;j++)
		{
			    if(Follow[i].s[j]==ntoindex(ID))
			    printf(" ID ");
			    else
               printf("%c  ", NT[Follow[i].s[j]]);
		}
		printf("}\n");
	}	

	printf("-----------Closure ------------\n");
	header.index=0;
	header.position=1;
	header.next=NULL;
	closure(&header);
	move=item_cluster[0].head;
	for(i=0;i<item_cluster[0].size;i++)
	{
		printf("%c --->",NT[infer[ move->index].s[0]]);
		for(j=1;j<=infer[move->index].len;j++)
		{
			if(j==move->position)
				printf(".");
			if(infer[move->index].s[j]==ntoindex(ID))
			{
				printf("ID");
				continue;
			}			
				printf("%c",NT[infer[move->index].s[j]]);
		}
		printf("\n");
		move=move->next;
	}
	for(i=0;i<R_SIZE;i++)
		add[i]=0;
	header.index=5;
	header.position=2;
	get_closure(&header);
	items();
	print_item();
	get_action();
	print_action();
	syntax();
}