testfirst.c

一个C语言编译器

/*#define R_SIZE 8
#define N_SIZE 5
#define T_SIZE 7  
#include "parse.c"
#include <string.h>
#include <ctype.h>
#include <stdio.h>
#define R_SIZE 7
#define N_SIZE 4
#define T_SIZE 7  
//#define ID 320
#define MAX_STATE 100
#define STACK_SIZE 100
//int NT[N_SIZE+T_SIZE]={'E','A','T','B','F','+','(',')','*',ID,'#','$'};
int NT[N_SIZE+T_SIZE]={'S','E','T','F','+','*','(',')',ID,'#','$'};

struct node
{	
	int len;       //产生式长度
	int s[10];  //s[0] 代表左部 ，s[1]---s[len]是产生式右部各文法符号的索引
} infer[R_SIZE];  //存取的是产生式集合
struct group
{
	int len;        //集合中的元素的个数
	int s[T_SIZE];  //存取的是终结符的索引
} First[N_SIZE],Follow[N_SIZE];        //分别代表first集，follow集
struct item
{
    int index ; //在infer数组中的位置（产生式的序号）
    int position; //在产生式中的位置 
    struct item *next; 
} ;   
struct cluster
{
    int size;         //项目集中所含项目的个数
    struct item *head;   //指向首项目
} item_cluster[MAX_STATE];  //存取的集簇

struct s_stack
{
	int tag;    //0表示状态，1表示输入的文法符号
	int value;  //表示状态值或者文法符号值
} ; 
struct m_stack        //文法符号栈
{
	int top;
	struct s_stack syntax_stack[STACK_SIZE]; 
}  main_stack;ss
int curr_state=0; //当前状态集

int gto[MAX_STATE][N_SIZE+T_SIZE];
struct do_action
{
	int actioning;   //-1表示错误,0表示接受,1表示用产生式规约,2表示状态转移,3预置其他状态
	int number;
} action[MAX_STATE][T_SIZE]; */

#include <syntax.h>
void init_syntax()
{	
	int i,j;
	init();
/*	infer[0].s[0]=ntoindex('E');
	infer[0].s[1]=ntoindex('T');
	infer[0].s[2]=ntoindex('A');
	infer[0].s[3]=ntoindex('$');
	infer[0].len=2;

	infer[1].s[0]=ntoindex('A');
	infer[1].s[1]=ntoindex('+');
	infer[1].s[2]=ntoindex('T');
	infer[1].s[3]=ntoindex('A');
	infer[1].s[4]=ntoindex('$');
	infer[1].len=3;

	infer[2].s[0]=ntoindex('A');
	infer[2].s[1]=ntoindex('#');
	infer[2].s[2]=ntoindex('$');
	infer[2].len=1;

	infer[3].s[0]=ntoindex('T');
	infer[3].s[1]=ntoindex('F');
	infer[3].s[2]=ntoindex('B');
	infer[3].s[3]=ntoindex('$');
	infer[3].len=2;

	infer[4].s[0]=ntoindex('B');
	infer[4].s[1]=ntoindex('*');
	infer[4].s[2]=ntoindex('F');
	infer[4].s[3]=ntoindex('B');
	infer[4].s[4]=ntoindex('$');
	infer[4].len=3;
	
	infer[5].s[0]=ntoindex('B');
	infer[5].s[1]=ntoindex('#');
	infer[5].s[2]=ntoindex('$');
	infer[5].len=1;

	infer[6].s[0]=ntoindex('F');
	infer[6].s[1]=ntoindex('(');
	infer[6].s[2]=ntoindex('E');
	infer[6].s[3]=ntoindex(')');
	infer[6].s[4]=ntoindex('$');
	infer[6].len=3;

	infer[7].s[0]=ntoindex('F');
	infer[7].s[1]=ntoindex(ID);
	infer[7].s[2]=ntoindex('$');
	infer[7].len=1;   */
	for(i=0;i<R_SIZE;i++)
	{
		for(j=0;j<10;j++)
			infer[i].s[j]=-1;
	}

	infer[0].s[0]=ntoindex('S');
	infer[0].s[1]=ntoindex('E');
	infer[0].s[2]=ntoindex('$');
	infer[0].len=1;

	infer[1].s[0]=ntoindex('E');
	infer[1].s[1]=ntoindex('E');
	infer[1].s[2]=ntoindex('+');
	infer[1].s[3]=ntoindex('T');
	infer[1].s[4]=ntoindex('$');
	infer[1].len=3;

	infer[2].s[0]=ntoindex('E');
	infer[2].s[1]=ntoindex('T');
	infer[2].s[2]=ntoindex('$');
	infer[2].len=1;
	
	infer[3].s[0]=ntoindex('T');
	infer[3].s[1]=ntoindex('T');
	infer[3].s[2]=ntoindex('*');
	infer[3].s[3]=ntoindex('F');
	infer[3].s[4]=ntoindex('$');
	infer[3].len=3;

	infer[4].s[0]=ntoindex('T');
	infer[4].s[1]=ntoindex('F');
	infer[4].s[2]=ntoindex('$');
	infer[4].len=1;

	infer[5].s[0]=ntoindex('F');
	infer[5].s[1]=ntoindex('(');
	infer[5].s[2]=ntoindex('E');
	infer[5].s[3]=ntoindex(')');
	infer[5].s[4]=ntoindex('$');
	infer[5].len=3;
	
	infer[6].s[0]=ntoindex('F');
	infer[6].s[1]=ntoindex(ID);
	infer[6].s[2]=ntoindex('$');
	infer[6].len=1;




	for(i=0;i<N_SIZE;i++)
	{
		First[i].len=0;
	}
	
  Follow[0].s[0]=ntoindex('$');
  Follow[0].len=1;	
  
  //item_cluster[0].size=1;
  //item_cluster[0].head=(struct cluster *)malloc(sizeof(struct cluster));
 // head->index=0;
 // head->position=1;
  //head->next=NULL;
  
  for(i=0;i<MAX_STATE;i++)
  {
      item_cluster[i].size=0;
  } 
  for(i=0;i<MAX_STATE;i++)
  {
	  for(j=0;j<N_SIZE+T_SIZE;j++)
		  gto[i][j]=-1;
  }
    for(i=0;i<MAX_STATE;i++)
  {
	  for(j=0;j<T_SIZE;j++)
	  {
		  action[i][j].actioning=-1;
	  }
  }
}
int total_len(struct group First[])
{
	int i;
	int sum=0;
	for(i=0;i<N_SIZE;i++)
	{
		sum+=First[i].len;
	}
	return sum;
}
int ntoindex(int n)
{
	int i;	
	for(i=0;i<N_SIZE+T_SIZE;i++)
	{
		if(NT[i]==n)
		{			
			return i;
		}
	}
	return -1;
}

int is_in(int member,int t) //t代表索引,member代表终结符的索引
{
	int i;
	int k=0;
	for(i=0;i<First[t].len;i++)
	{
		if(member==First[t].s[i])
		{
			k=1;
			break;
		}
	}
	if(k==1)
		return i;
	else
		return -1;
}
void add_char(int next,int curr,int div) //div 有效时均为空
{ 
	int i;
	int k;
	if(next==9)
	printf("enter id\n");
	if(next==10)
	printf("enter #");
	if(next>=N_SIZE)
	{
		if(is_in(next,curr)==-1)
		{	
		First[curr].s[First[curr].len]=next;
		(First[curr].len)++;
		printf(" terminator %c add to %c\n",NT[next],NT[curr]);
		}
	}
	else
	{
    for(i=0;i<First[next].len;i++)
	{
		if(is_in(First[next].s[i],curr)==-1)
		{
			if(First[next].s[i]==div)
				continue;
			if(First[next].s[i]>=N_SIZE)
			{	
		First[curr].s[First[curr].len]=First[next].s[i];
		(First[curr].len)++;
		printf("next terminator %c add to %c\n",NT[next],NT[curr]);
		    }
		/*	else
			{
				First[curr].s[First[curr].len]=next;
				(First[curr].len)++;
				printf("nonterminator %c add to %c",NT[next],NT[curr]);
			} */
		}
	}
	}	
}
void first(int index)
{
	int i=0;
	int j,k;
	j=infer[index].s[0];
	for(i=1;i<=infer[index].len;i++)
	{		
		k=infer[index].s[i];		
		if(k>=N_SIZE)
		{
			add_char(k,j,-10);
		//	printf("add a terminator\n");
		if(k==9 || k==10)
		  printf("enter %c\n",NT[k]);
			break;
		}
		if(k<N_SIZE)
		{
			
			if(is_in(ntoindex('#'),k)==-1)
			{
				add_char(k,j,-10);
			//	printf("add a nonterminator has no #\n");
				break;
			}
			if(i<infer[index].len-1)
			{
			add_char(k,j,ntoindex('#'));
		//	printf("add a nonterminator has # \n");
            }			
			else
			{
                   add_char(k,j,-10);
  	        //       printf("add a nonterminator has # last\n");
           }    
			
		}	

	}
}

int in_follow(int member,int t)
{
    int i;
	int k=0;
	for(i=0;i<Follow[t].len;i++)
	{
		if(member==Follow[t].s[i])
		{
			k=1;
			break;
		}
	}
	if(k==1)
		return i;
	else
		return -1;
}  
  
void first_follow(int next,int curr,int div)
{
	int i;
	int k;
	if(next==9)
	printf("enter id\n");
	if(next==10)
	printf("enter #");
	if(next>=N_SIZE)
	{
		if(in_follow(next,curr)==-1)
		{	
		Follow[curr].s[Follow[curr].len]=next;
		(Follow[curr].len)++;
		printf(" terminator %c add to %c\n",NT[next],NT[curr]);
		}
	}
	else
	{
    for(i=0;i<First[next].len;i++)
	{
		if(in_follow(First[next].s[i],curr)==-1)
		{
			if(First[next].s[i]==div)
				continue;
			if(First[next].s[i]>=N_SIZE)
			{	
		Follow[curr].s[Follow[curr].len]=First[next].s[i];
		(Follow[curr].len)++;
		printf("next terminator %c add to %c\n",NT[next],NT[curr]);
		    }
		/*	else
			{
				First[curr].s[First[curr].len]=next;
				(First[curr].len)++;
				printf("nonterminator %c add to %c",NT[next],NT[curr]);
			} */
		}
	}
}		
}
void follow_follow(int source,int des)
{
  int i,j;
  if(source>=N_SIZE || des>=N_SIZE)
  printf("error\n");
  
  for(i=0;i<Follow[source].len;i++)
  {
      
      if(in_follow(Follow[source].s[i],des)==-1)
      {
          if(Follow[source].s[i]>=N_SIZE)
          {
          Follow[des].s[Follow[des].len++]=Follow[source].s[i];
          printf("add follow %c to %c\n",NT[source],NT[des]);
      }    
      }    
  }      
} 
   
void follow(int index)
{
    int i,j,k,l,len;
    int flag=0;
    i=infer[index].s[0];    
    for(k=1;k<=infer[index].len;k++)
    {
        if(infer[index].s[k]>=N_SIZE)
        continue;       
               
        for(l=k+1;l<=infer[index].len;l++)
        {
            if(infer[index].s[l]>=N_SIZE)
            {             
                    first_follow(infer[index].s[l],infer[index].s[k],-10);
                    flag=1; 
                    break;                               
            }    
          if(is_in(ntoindex('#'),infer[index].s[l])==-1)
            {
                flag=1;
                first_follow(infer[index].s[l],infer[index].s[k],10);
                break;
            } 
            first_follow(infer[index].s[l],infer[index].s[k],10);                  
        } 
        if(flag==0)         
             follow_follow(i,infer[index].s[k]) ;  
    }    
} 
int add_more_item(struct item *q,int state_index)
{
  struct item *m;
  int i,j;
  m=item_cluster[state_index].head;
  j=item_cluster[state_index].size;
  i=0;
  while(i<j)
  {
      if(q->index==m->index && q->position==m->position)  //不能添加该item返回0,否则返回1
      return 0;
      m=m->next;
      i++;
  } 
  return 1;    
}     
int closure(struct item *p)               //返回所加入的状态集的指针,参数是项目
{
    int i,j,k;
	int f_number,n_number;   
    struct item *curr;
	struct item *curr_add;	

	int add[R_SIZE];
	for(i=0;i<R_SIZE;i++)
	{
		add[i]=0;
	}
	f_number=0;
	n_number=1;

	item_cluster[curr_state].head=(struct item *)malloc(sizeof(struct item));	
	item_cluster[curr_state].head->index=p->index;
	item_cluster[curr_state].head->position=p->position;
	item_cluster[curr_state].head->next=NULL;
	item_cluster[curr_state].size++;
	curr=item_cluster[curr_state].head;
	add[curr->index]=1;
	curr_add=curr;	
	while(f_number!=n_number)
	{
		k=n_number-f_number;
		f_number=item_cluster[curr_state].size;
		printf("---f_number : %d----\n",f_number);
		for(j=0;j<k;j++)
		{
			for(i=0;i<R_SIZE;i++)
			{			
     
					if(!add[i])
				{				
                    if(infer[i].s[0]==infer[curr->index].s[curr->position])
					{
					
                        curr_add->next=(struct item *)malloc(sizeof(struct item));	
						curr_add->next->index=i;
						curr_add->next->position=1;
						(item_cluster[curr_state].size)++;
						curr_add->next->next=NULL;
						curr_add=curr_add->next;
						add[i]=1;
						printf("add number %d and position %dto group\n",i,1);
					}
				}
			}
			
			curr=curr->next;
		}        		
		n_number=item_cluster[curr_state].size;
		printf("----n_number : %d----\n",n_number);
	}
	curr=item_cluster[curr_state].head;
	for(i=0;i<n_number;i++)
	{
	//	printf("infer %d position %d\n",curr->index,curr->position);
		curr=curr->next;
	}
    return (curr_state++);
}  

struct item * get_closure(struct item *p)               //返回所加入的状态集的指针,参数是项目
{
    int i,j,k;
    int add[R_SIZE];
	int f_number,n_number; 
    int i_size=0;   
    struct item *curr;
	struct item *curr_add;	
	struct item *head;	
	for(i=0;i<R_SIZE;i++)
		add[i]=0;
	f_number=0;
	n_number=1;

	head=(struct item *)malloc(sizeof(struct item));	
	head->index=p->index;
    head->position=p->position;
    head->next=NULL;
	i_size++;
	curr=head;	
	curr_add=curr;	
	//printf("added header is %c\n",NT[infer[curr->index].s[curr->position]]);
	while(f_number!=n_number)
	{
		k=n_number-f_number;
		f_number=i_size;
		//printf("---f_number : %d----\n",f_number);
		for(j=0;j<k;j++)
		{
			for(i=0;i<R_SIZE;i++)
			{			
     
					if(!add[i])
				{				
                    if(infer[i].s[0]==infer[curr->index].s[curr->position])
					{
					
                        curr_add->next=(struct item *)malloc(sizeof(struct item));	
						curr_add->next->index=i;
						curr_add->next->position=1;
						i_size++;
						curr_add->next->next=NULL;
						curr_add=curr_add->next;
						add[i]=1;
						//printf("add number %d and position %d to group\n",i,1);
					}
				}
			}
		//	printf("added header is %c\n",NT[infer[curr->index].s[curr->position]]);
			curr=curr->next;
			
		}        		
		n_number=i_size;
		//printf("----n_number : %d----\n",n_number);
	}
	curr=head;
	printf("-----get closure ------\n ");
	for(i=0;i<n_number;i++)
	{
		//printf("infer %d position %d\n",curr->index,curr->position);
		curr=curr->next;