ff.h

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

int find_f(char ch)
{
    int j ;
    for(j=0;j<kr;j++)
    {
        if(ff[j].id==ch)break ;
    }
    if(j>=kr)
    {
        printf("\n该文法有错误!");
        exit(1);
    }
    else return j ;
}
/* 把ch  放到第kk个head结点的 first中*/
void putfir2(char ch,int kk,struct node*pp)
{
    struct ffnode*p ;
    struct node*r ;
    p=ff[kk].first ;
    while(p!=NULL)
    {
        if(ch==p->id)
        {
            if(p->fp!=pp)
            {
                printf("\n不是LL(1)文法error at %d\n%c->",kk+1,ff[kk].id);
                
                r=p->fp ;
                while(r!=NULL)
                {
                    printf("%c",r->id);
                    r=r->next ;
                }
                printf("|");
                r=pp ;
                while(r!=NULL)
                {
                    printf("%c",r->id);
                    r=r->next ;
                }
                printf("  有相交部分 \'%c\'\n",ch);
                
                exit_pause();
            }
            
            
            
            
            break ;
        }
        p=p->nt ;
    }
    if(p==NULL)
    {
        if(ff[kk].first==NULL)
        {
            ff[kk].first=(struct ffnode*)malloc(sizeof(struct ffnode));
            p=ff[kk].first ;
        }
        else 
        {
            p=ff[kk].first ;
            while(p->nt!=NULL)p=p->nt ;
            p->nt=(struct ffnode*)malloc(sizeof(struct ffnode));
            p=p->nt ;
        }
        p->id=ch ;
        p->nt=NULL ;
        
        p->fp=pp ;
        edit=1 ;
    }
    
}
/* 把ch的first  放到第kk个head结点的 first中*/
void putfir1(char ch,int kk,struct node*pp)
{
    
    struct ffnode*p,*q ;
    struct node*r ;
    p=ff[find_f(ch)].first ;
    while(p!=NULL)
    {
        q=ff[kk].first ;
        while(q!=NULL)
        {
            if(q->id==p->id)break ;
            q=q->nt ;
        }
        if(q==NULL)putfir2(p->id,kk,pp);
        else 
        {
            
            if(q->fp!=pp)
            {
                printf("\n不是LL(1)文法 error at %d \n\'%c\'->",kk+1,ff[kk].id);
                r=q->fp ;
                while(r!=NULL)
                {
                    printf("%c",r->id);
                    r=r->next ;
                }
                printf("|");
                r=pp ;
                while(r!=NULL)
                {
                    printf("%c",r->id);
                    r=r->next ;
                }
                printf("有相交部分 \'%c\'\n",q->id);
                exit_pause();
            }
        }
        p=p->nt ;
    }
    
}
/* 把KK的 follow 放到第i个head结点的 follow中*/
void putfoli(int kk,int i)
{
    struct ffnode*q,*p ;
    p=ff[kk].follow ;
    
    
    while(p!=NULL)
    {
        if(ff[i].follow==NULL)
        {
            ff[i].follow=(struct ffnode*)malloc(sizeof(struct ffnode));
            q=ff[i].follow ;
            q->id=p->id ;
            q->nt=NULL ;
            edit=1 ;
        }
        else 
        {
            q=ff[i].follow ;
            if(q->id!=p->id)
            {
                while(q->nt!=NULL)
                {
                    if(q->nt->id==p->id)break ;
                    q=q->nt ;
                }
                
                if(q->nt==NULL)
                {
                    q->nt=(struct ffnode*)malloc(sizeof(struct ffnode));
                    q=q->nt ;
                    q->id=p->id ;
                    q->nt=NULL ;
                    edit=1 ;
                }
            }
        }
        
        p=p->nt ;
        
    }
}
/* 把KK的 first 放到第i个head结点的 follow中*/
void putfirtofol(int kk,int i)
{
    struct ffnode*q,*p=ff[kk].first ;
    q=ff[i].follow ;
    while(p!=NULL)
    {
        if(ff[i].follow==NULL)
        {
            ff[i].follow=(struct ffnode*)malloc(sizeof(struct ffnode));
            q=ff[i].follow ;
            q->id=p->id ;
            q->nt=NULL ;
            edit=1 ;
        }
        else 
        {
            
            if(q->id!=p->id)
            {
                while(q->nt!=NULL)
                {
                    if(q->nt->id==p->id)break ;
                    q=q->nt ;
                }
                
                if(q->nt==NULL)
                {
                    q->nt=(struct ffnode*)malloc(sizeof(struct ffnode));
                    q=q->nt ;
                    q->id=p->id ;
                    q->nt=NULL ;
                    edit=1 ;
                }
            }
        }
        p=p->nt ;
        
    }
    
    
}
/* 把ch 放到 第i个head结点的 follow中*/
void putfolch(char ch,int i)
{
    struct ffnode*q ;
    q=ff[i].follow ;
    
    if(q==NULL)
    {
        ff[i].follow=(struct ffnode*)malloc(sizeof(struct ffnode));
        q=ff[i].follow ;
        q->id=ch ;
        q->nt=NULL ;
        edit=1 ;
    }
    else 
    {
        if(q->id!=ch)
        {
            while(q->nt!=NULL)
            {
                if(q->nt->id==ch)break ;
                q=q->nt ;
            }
            
            if(q->nt==NULL)
            {
                q->nt=(struct ffnode*)malloc(sizeof(struct ffnode));
                q=q->nt ;
                q->id=ch ;
                q->nt=NULL ;
                edit=1 ;
            }
        }
    }
    
    
    
}

/*   从first 或 follow 集合中找ch,若成功则返回一个指向该规则式的指针,否则返回NULL  */

struct node*find_fl(char ch,struct ffnode*p)
{
    while(p!=NULL)
    {
        if(p->id==ch)break ;
        p=p->nt ;
    }
    if(p!=NULL)return p->fp ;
    else return NULL ;
}

/*   判断能否从bh推导出ch,若能则返回一个指向该规则式的指针, 否则返回NULL */
struct node*LL1(char ch,char bh)
{
    int j ;
    struct node*p ;
    struct ffnode*q ;
    j=find_f(bh);
    if((p=find_fl(ch,ff[j].first))!=NULL)return p ;
    
    else if(ff[j].kong)
    {
        if(ch=='\0')return ff[j].kg ;
        else 
        {
            q=ff[j].follow ;
            while(q!=NULL)
            {
                if(q->id==ch)break ;
                q=q->nt ;
            }
            if(q!=NULL)return ff[j].kg ;
            else return NULL ;
        }
    }
    else return NULL ;
}

/* 判断字符串t中的句子能否由start指向的文法推导出来,若不能将错误位置放到edit中*/
int judge(char*t,struct node*start)
{
    stack sk ;
    char ch ;
    int i ;
    struct node*r,*q ;
    initstack(&sk);
    push(&sk,start->id);
    i=0 ;
    while(t[i]!='\0')
    {
        if(sk.base==sk.top)break ;
        gettop(&sk,&ch);
        while(ch=='#')
        {
            pop(&sk,&ch);
            gettop(&sk,&ch);
        }
        if(ch==t[i])
        {
            pop(&sk,&ch);
            i++;
        }
        else if((r=LL1(t[i],ch))!=NULL)
        {
            pop(&sk,&ch);
            q=r ;
            do 
            {
                q=q->pm ;
                push(&sk,q->id);
            }
            while(q!=r);
            
            
        }
        else break ;
        
    }
    
    
    
    while(sk.base!=sk.top)
    {
        gettop(&sk,&ch);
        while(ch=='#')
        {
            pop(&sk,&ch);
            gettop(&sk,&ch);
        }
        
        if(ff[find_f(ch)].kong)
       pop(&sk,&ch);
        else break ;
    }
    
    
    edit=i+1 ;
    if(sk.base==sk.top&&t[i]=='\0'){destroy(&sk); return OK ;}
    else {destroy(&sk); return ERROR ;}
    
    
}