fir.c

编译方法课程设计之LL（1）语法分析

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

int edit ;
int kr ;
/* 文法数目*/
#define OK 1
#define ERROR 0
# include "struct.h"
# include "ff.h"



void main(int argc,char*argv[])
{
    char t[100],ch ;
    int i,j ;
    FILE*in ;
    struct node*ps,*pt,*pr,*p ;
    struct node s ;
    struct ffnode*pfir,*pfol ;
    for(i=0;i<100;i++)
    {
        t[i]='\0' ;
    }
    if(argc==2)
    {
        if((in=fopen(argv[1],"rb"))==NULL)
        {
            do 
            {
                printf("找不到该文件\n请再次输入文法所在的文件:");
                gets(t);
            }
            while((in=fopen(t,"rb"))==NULL);
        }
    }
    
    else 
    {
        while(1)
        {
            t[0]='\0' ;
            printf("输入文法所在的文件(直接ENTER则打开文件gfin.txt):\n");
            gets(t);
            if(t[0]=='\0')
            {
                if((in=fopen("gfin.txt","rb"))==NULL)
                {
                    printf("can't find the file:\'gfin.txt\'\n");
                }
                else break ;
            }
            else if((in=fopen(t,"rb"))!=NULL)break ;
            
        }
    }
    
    
    
    
    for(i=0;i<100;i++)
    {
        t[i]='\0' ;
    }
    
    i=0 ;
    kr=0 ;
    while(1)
    {
        ch=fgetc(in);
        if(feof(in)||ch=='\r')
        {
            if(i!=0)
            {
                if(kr==0)
                {
                    s.id=t[0];
                    s.type=1 ;
                    pr=ps=p=&s ;
                    kr++;
                }
                else 
                {
                    p->pm=(struct node*)malloc(LEN);
                    pr=ps=p=p->pm ;
                    p->id=t[0];
                    p->type=1 ;
                    kr++;
                }
                i=1 ;
                while(t[i]!='\0')
                {
                    if((t[i]==':')||(t[i]=='|'))
                    {
                        if(t[i]=='|')pr->pm=ps ;
                        ps->next=NULL ;
                        pr->pn=(struct node*)malloc(LEN);
                        ps=pr=pr->pn ;
                        i=i+1 ;
                        ps->id=t[i];
                        if(t[i]=='#')ps->type=3 ;
                        else if(t[i]<'A'||t[i]>'Z')ps->type=2 ;
                        else ps->type=1 ;
                        
                        
                    }
                    else 
                    {
                        ps->next=(struct node*)malloc(LEN);
                        ps->next->pm=ps ;
                        ps=ps->next ;
                        ps->id=t[i];
                        if(t[i]=='#')
                        {
                            ps->type=3 ;
                        }
                        else 
                        {
                            if(t[i]<'A'||t[i]>'Z')ps->type=2 ;
                            else ps->type=1 ;
                        }
                    }
                    i++;
                }
                pr->pm=ps ;
                pr->pn=NULL ;
                ps->next=NULL ;
                for(j=0;j<100;j++)t[j]='\0' ;
                i=0 ;
            }
            if(ch=='\r')continue ;
            else break ;
        }
        
        else if(ch<=32)continue ;
        else t[i]=ch ;
        i++;
    }
    p->pm=NULL ;
    fclose(in);
    
    
    
    /*    
        pt=&s ;
        while(pt!=NULL)
        {
            pr=pt ;
            while(pr!=NULL)
            {
                ps=pr ;
                while(ps!=NULL)
                {
                    printf("%c",ps->id);
                    ps=ps->next ;
                }
                printf("\n");
                pr=pr->pn ;
            }
            pt=pt->pm ;
        }
        printf("%d",kr); 显示已存储的文法规则式 */
   
  /* 为每个非终分配一个HEAD 结点  */
   ff=(struct head*)calloc(kr,sizeof(struct head));
    
    p=&s ;
    for(i=0;i<kr;i++)
    {
        ff[i].id=p->id ;
        ff[i].first=NULL ;
        ff[i].follow=NULL ;
        p=p->pm ;
    }
    /*求FIRST 集合*/
    do 
    {
        edit=0 ;
        p=&s ;
        i=0 ;
        while(p!=NULL)
        {
            ps=p->pn ;
            while(ps!=NULL)
            {
                pr=ps ;
                while(1)
                {
                    if(pr==NULL)
                    {
                        if(ff[i].kong)
                        {
                            if(ff[i].kg!=ps)
                            {
                                printf("\n不是LL(1)文法 error at %d ",i+1);
                                printf("\n %c-> ",ff[i].id);
                                pt=ps ;
                                while(pt!=NULL)
                                {
                                    printf("%c",pt->id);
                                    pt=pt->next ;
                                }
                                printf("|");
                                pt=ff[i].kg ;
                                while(pt!=NULL)
                                {
                                    printf("%c",pt->id);
                                    pt=pt->next ;
                                }
                                printf("  有交集为'#'\n");
                                exit_pause();
                            }
                        }
                        else 
                        {
                            ff[i].kg=ps ;
                            edit=1 ;
                            ff[i].kong=1 ;
                            
                            
                        }
                        break ;
                    }
                    if(pr->type==3)pr=pr->next ;
                    else if(pr->type==1)
                    {
                        putfir1(pr->id,i,ps);
                        
                        if(ff[find_f(pr->id)].kong==0)break ;
                        else pr=pr->next ;
                    }
                    else 
                    {
                        putfir2(pr->id,i,ps);
                        break ;
                    }
                }
                ps=ps->pn ;
            }
            p=p->pm ;
            i++;
        }
    }
    while(edit!=0);
   /*求FOLLOW集合*/ 
    do 
    {
        edit=0 ;
        p=&s ;
        i=0 ;
        while(p!=NULL)
        {
            ps=p->pn ;
            while(ps!=NULL)
            {
                pr=ps->pm ;
                while(1)
                {
                    
                    
                    if(pr->type==2)break ;
                    else if(pr->type==1)
                    {
                        
                        j=find_f(pr->id);
                        putfoli(i,j);
                        if(ff[j].kong!=1)break ;
                        
                    }
                    
                    
                    if(pr==ps)break ;
                    pr=pr->pm ;
                    
                }
                pr=ps ;
                if(pr->next!=NULL)
                {
                    while(pr!=NULL)
                    {
                        if(pr->type==1)
                        {
                            pt=pr->next ;
                            while(pt!=NULL)
                            {
                                if(pt->type==2)
                                {
                                    
                                    putfolch(pt->id,find_f(pr->id));
                                    break ;
                                }
                                else if(pt->type==1)
                                {
                                    j=find_f(pt->id);
                                    
                                    
                                    putfirtofol(j,find_f(pr->id));
                                    
                                    if(ff[j].kong==1)pt=pt->next ;
                                    else break ;
                                }
                                else pt=pt->next ;
                            }
                            
                        }
                        pr=pr->next ;
                    }
                }
                /*if*/
                
                ps=ps->pn ;
            }
            /*/while(ps!=NULL)*/
            p=p->pm ;
            i++;
        }
        /*/while (p!=NULL)*/
        
        
        
        
    }
    while(edit!=0);
    
    
    
    
    
    printf("\nfirst集合:");
    for(i=0;i<kr;i++)
    {
        printf("\n     %c:",ff[i].id);
        if(ff[i].kong)printf(" #");
        pfir=ff[i].first ;
        while(pfir!=NULL)
        {
            printf(" %c",pfir->id);
            pfir=pfir->nt ;
        }
        
    }
    printf("\nfollow集合:");
    for(i=0;i<kr;i++)
    {
        printf("\n     %c:",ff[i].id);
        pfol=ff[i].follow ;
        while(pfol!=NULL)
        {
            printf(" %c",pfol->id);
            pfol=pfol->nt ;
        }
        
    }
    
    
    
    
    while(1)
    { for(i=0;i<100;i++)t[i]='\0' ;
        printf("\n输入一个句子或包含若干句子的文件:\n");
       
        gets(t);if(t[0]=='\0')break ;
        if((in=fopen(t,"rb"))==NULL)
        
        {
            
            
            if(judge(t,&s))printf("OK!符合该文法\n");
            else printf("*****错误位置---%d\n",edit);
            
            
        }
        else 
        {
            for(i=0;i<100;i++)t[i]='\0' ;
            i=0 ;
            while(1)
            {
                ch=fgetc(in);
                if(feof(in)||ch=='\r')
                
                {
                    puts(t);
                    if(judge(t,&s))printf("OK!符合该文法\n");
                    else printf("*****错误位置---%d\n",edit);
                    for(i=0;i<100;i++)t[i]='\0' ;
                    i=0 ;
                    
                    if(feof(in))break ;
                }
                if(ch<=32)continue ;
                else t[i]=ch ;
                i++;
                
            }
            fclose(in);
        }
        
    }
	
  free(ff);
}