ll1.c

实现编译原理中的LL1文法

                        else if(_emp(right[j][k])==1&&k==strlen(right[j])-1)
                        {
                            temp[0]='$';
                            temp[1]='\0';
                            merge(first1[i],temp,1);
                        }
                        else 
                            break;
                    }
                }
            }
        }
    }
    f[i]='1';
}

/***************************求各产生式右部的FIRST***************************/
void FIRST(int i,char *p)
{
    int length;
    int j,k,m;
    char temp[20];
    length=strlen(p);
    if(length==1)                  /*如果右部为单个符号*/
    {
        if(p[0]=='$')
        {   
            if(i>=0)
            {
                first[i][0]='$';
                first[i][1]='\0';
            }
            else
            {
                TEMP[0]='$';
                TEMP[1]='\0';
            }
        }
        else
        {    
            for(j=0;;j++)
                if(v[j]==p[0])
                    break;
            if(i>=0)
            {
                memcpy(first[i],first1[j],strlen(first1[j]));
                first[i][strlen(first1[j])]='\0';
            }
            else
            {
                memcpy(TEMP,first1[j],strlen(first1[j]));
                TEMP[strlen(first1[j])]='\0';
            }
        }
    }
    else                      /*如果右部为符号串*/
    {
        for(j=0;;j++)
            if(v[j]==p[0])
                break;
        if(i>=0)
            merge(first[i],first1[j],2);
        else
            merge(TEMP,first1[j],2);
        for(k=0;k<=length-1;k++)
        {
            empt[0]='\0';
            if(_emp(p[k])==1&&k<length-1)
            { 
                for(m=0;;m++)
                    if(v[m]==right[i][k+1])
                        break;
                if(i>=0)
                    merge(first[i],first1[m],2);
                else
                    merge(TEMP,first1[m],2);
            }
            else if(_emp(p[k])==1&&k==length-1)
            {
                
                temp[0]='$';
                temp[1]='\0';
                if(i>=0)
                    merge(first[i],temp,1);   
                else
                    merge(TEMP,temp,1);
            }
            else if(_emp(p[k])==0)
                break;
        }
    }
}

/************************求各产生式左部的FOLLOW******************/
void FOLLOW(int i)
{
    int j,k,m,n,result=1;
    char c,temp[20];
    c=VN[i];
    temp[0]=c;
    temp[1]='\0';
    merge(fo,temp,1);
    if(c==start)
    {                         /*若为开始符号*/
        temp[0]='#';
        temp[1]='\0';
        merge(follow[i],temp,1);
    }
    for(j=0;j<=count-1;j++)
    {
        if(in(c,right[j])==1)     /*找一个右部含有c的产生式*/
        {
            for(k=0;;k++)
                if(right[j][k]==c)
                    break;       /*k为c在该产生式右部的序号*/
            for(m=0;;m++)
                if(v[m]==left[j])
                    break;        /*m为产生式左部非终结符在所有符号中的序号*/
            if(k==strlen(right[j])-1)
            {              /*如果c在产生式右部的最后*/
                if(in(v[m],fo)==1)
                {
                    merge(follow[i],follow[m],1);
                    continue;
                }
                if(F[m]=='0')
                {
                    FOLLOW(m);
                    F[m]='1';
                }
                merge(follow[i],follow[m],1);
            }
            else 
            {              /*如果c不在产生式右部的最后*/
                for(n=k+1;n<=strlen(right[j])-1;n++)
                {    
                    empt[0]='\0';
                    result*=_emp(right[j][n]);
                }
                if(result==1)
                {         /*如果右部c后面的符号串能推出$*/
                    if(in(v[m],fo)==1)
                    {           /*避免出现循环递归*/
                        merge(follow[i],follow[m],1);
                        continue;
                    }
                    if(F[m]=='0')
                    {
                        FOLLOW(m);
                        F[m]='1';
                    }
                    merge(follow[i],follow[m],1);
                }
                for(n=k+1;n<=strlen(right[j])-1;n++)
                    temp[n-k-1]=right[j][n];       
                temp[strlen(right[j])-k-1]='\0';
                FIRST(-1,temp);
                merge(follow[i],TEMP,2);
            }
        }
    }
    F[i]='1';
}

/**************判断读入文法是否为一个LL(1)文法******************/
int ll1()
{
    int i,j,length,result=1;
    char temp[50];
    for(j=0;j<=49;j++)
    {                               /*初始化*/
        first[j][0]='\0';
        follow[j][0]='\0';
        first1[j][0]='\0';
        select[j][0]='\0';
        TEMP[j]='\0';
        temp[j]='\0';
        f[j]='0';
        F[j]='0';
    }
    for(j=0;j<=strlen(v)-1;j++)
        first2(j);                /*求单个符号的FIRST集合*/
    printf("\nfirst1:");
    for(j=0;j<=strlen(v)-1;j++)
        printf("%c:%s  ",v[j],first1[j]);
    printf("\nempty:%s",empty);
    printf("\n_emp:");
    for(j=0;j<=strlen(v)-1;j++)
        printf("%d  ",_emp(v[j]));
    for(i=0;i<=count-1;i++)
        FIRST(i,right[i]);          /*求FIRST*/
    for(j=0;j<=strlen(VN)-1;j++)
    {                               /*求FOLLOW*/
        if(fo[j]==0)
        {
            fo[0]='\0';
            FOLLOW(j);
        }
    }
    printf("\nfirst:");
    for(i=0;i<=count-1;i++)
        printf("%s ",first[i]);
    printf("\nfollow:");
    for(i=0;i<=strlen(VN)-1;i++)
        printf("%s ",follow[i]);
    for(i=0;i<=count-1;i++)
    {                          /*求每一产生式的SELECT集合*/
        memcpy(select[i],first[i],strlen(first[i]));
        select[i][strlen(first[i])]='\0';
        for(j=0;j<=strlen(right[i])-1;j++)
            result*=_emp(right[i][j]);
        if(strlen(right[i])==1&&right[i][0]=='$')
            result=1;
        if(result==1)
        {    
            for(j=0;;j++)
                if(v[j]==left[i])
                    break;
            merge(select[i],follow[j],1);
        }
    }
    printf("\nselect:");
    for(i=0;i<=count-1;i++)
        printf("%s ",select[i]);
    memcpy(temp,select[0],strlen(select[0]));
    temp[strlen(select[0])]='\0';
    for(i=1;i<=count-1;i++)
    {                 /*判断输入文法是否为LL(1)文法*/
        length=strlen(temp);
        if(left[i]==left[i-1])
        {
            merge(temp,select[i],1);
            if(strlen(temp)<length+strlen(select[i]))
                return(0);
        }
        else
        {
            temp[0]='\0';
            memcpy(temp,select[i],strlen(select[i]));
            temp[strlen(select[i])]='\0';
        }
    }
    return(1);
}

/**************************构造分析表M【】【】********************/
void MM()
{
    int i,j,k,m;
    for(i=0;i<=19;i++)
        for(j=0;j<=19;j++)
            M[i][j]=-1;
    i=strlen(VT);
    VT[i]='#';     /*将#加入终结符数组*/
    VT[i+1]='\0';
    for(i=0;i<=count-1;i++)
    {
        for(m=0;;m++)        /*m为产生式左部非终结符的序号*/
            if(VN[m]==left[i])
                break;
        for(j=0;j<=strlen(select[i])-1;j++)
        {
            if(in(select[i][j],VT)==1)
            {
                for(k=0;;k++)   /*k为产生式右部终结符的序号*/
                    if(VT[k]==select[i][j])
                        break;
                M[m][k]=i;
            }
        }
    }
}

/************************总控算法***********************/
void Control()
{
    int i,j,k,m,n,p,q;
    char ch;
    char S[50],str[50];
    printf("\please input the string:");
    scanf("%s",str);
    getchar();
    i=strlen(str);
    str[i]='#';
    str[i+1]='\0';
    S[0]='#';
    S[1]=start;
    S[2]='\0';
    j=0;
    ch=str[j];
    while(1)
    {
        if(in(S[strlen(S)-1],VT)==1)
        {
            if(S[strlen(S)-1]!=ch)
            {
                printf("the string is not a grammar of G[S]!");
                return;
            }
            else if(S[strlen(S)-1]=='#')
            {
                printf("the string is a grammar of G[S]!!!");
                return;
            }
            else
            {
                S[strlen(S)-1]='\0';
                j++;
                ch=str[j];
            }
        }
        else 
        {   
            for(i=0;;i++)
                if(VN[i]==S[strlen(S)-1])
                    break;
            for(k=0;;k++)
            {    
                if(VT[k]==ch)
                    break;
                if(k==strlen(VT))
                {
                    printf("the lexical is error！");
                    return;
                }
            }
            if(M[i][k]==-1)
            {
                printf("the grammar is error！");
                return;
            }
            else
            {
                m=M[i][k];
                if(right[m][0]=='$')
                    S[strlen(S)-1]='\0';
                else
                {
                    p=strlen(S)-1;
                    q=p;
                    for(n=strlen(right[m])-1;n>=0;n--)
                        S[p++]=right[m][n];
                    S[q+strlen(right[m])]='\0';
                }
            }
        }
        printf("S:%s  str:",S);
        for(p=j;p<=strlen(str)-1;p++)
            printf("%c",str[p]);
        printf(" \n");
    }
}
/*********************用于再输入的函数******************************/
void menu()
{
    Control();
    printf("\n input again