chomsky.cpp

Chomsky文法识别。编译原理课程实习作业

#include<stdio.h>
int vnlen=0,vtlen=0,vtalen=0;
char vn[20],vna[20],vt[100],vta[100],G[4];
char left[10][10],right[10][20]; 

int numl[10],numr[10]; 
int ia,ib,ja,jb,tag,tag1,tag2;        

bool is_vn(char ch)
{
    int i;
    for(i=0;i<vnlen;i++)
        if(vna[i]==ch)
            return true;
    return false;
}
bool is_vt(char ch)
{
    int i;
    for(i=0;i<vtalen;i++)
        if(vta[i]==ch)
            return true;
    return false;
}    
void judge()
{
    int i,j,s,k=0,num=0;
    int right1[10][10],right2[10];
    for(i=0;i<=ja;i++)
    {
        k=0;num=0;
        for(j=0;j<numr[i];j++)
            if(right[i][j]=='|')
            {
               k++;
               num=0;
            }
            else
            {
                num++;
                right1[i][k]=num;
                right2[i]=k;
            }
    }     
    for(i=0;i<=ia;i++)
        for(j=0;j<=right2[i];j++)
            if(numl[i]>right1[i][j])
            {
                tag1=0;
                printf("             该文法为Chomsky %d 型文法！\n",tag1);
                return;
            }
    for(i=0;i<=ia;i++)
        for(j=0;j<=right2[i];j++)
            if((numl[i]>1))
            {
                tag1=1;
                printf("             该文法为Chomsky %d 型文法！\n",tag1);
                return;
            }
    for(i=0;i<=ia;i++)
    {
        s=0;
        for(j=0;j<=right2[i];j++)
            if((numl[i]==1)&&(is_vn(left[i][0])))
            {
                
                if((right1[i][j]==1)&&is_vt(right[i][s]))
                {
                    tag1=3;
                    s+=2;
                }        
                else if((right1[i][j]==2)&&(is_vt(right[i][s])&&is_vn(right[i][s+1])))
                {
                    tag1=3;
                    s+=3;
                }
                else 
                {
                    tag1=2;
                    printf("             该文法为Chomsky %d 型文法！\n",tag1);
                       return;
                }     
            }    
    }    
     printf("             该文法为Chomsky %d 型文法！\n",tag1); 
    
}

void output()
{
    int i=0,j,k;
    printf("\t--------------------------------------\n");
    printf("             文法：");
    while(G[i]!='\0')
    { 
        printf("%c",G[i]);
        i++;
    }
    printf("=");
    printf("({");
    i=0;
    while(i<(vnlen-1))
    {
        printf("%c,",vna[i]);
        i++;
    }
    printf("%c",vna[i]);
    printf("},");
    
    printf("{");
    i=0;
    while(i<(vtalen-1))
    {
        printf("%c,",vta[i]);
        i++;
    }
    printf("%c",vta[i]);
    
    printf("},");
    printf("P,");
    printf("%c)",left[0][0]);
    printf("\n");
    printf("             产生式P:\n");
    for(i=0;i<=ia;i++)
    {
        printf("\t\t");
        for(j=0;j<numl[i];j++)
            printf("%c",left[i][j]);
        printf("::=");
        for(k=0;k<numr[i];k++)
            printf("%c",right[i][k]);
        printf("\n");
    }
}        
              
int main()
{
    char c,p[100];
    int i=0,j,k;
    printf("请输入文法:");
    gets(G); 
    printf("请输入非终结符号集(用逗号隔开):");
    gets(vn);
    while((c=vn[i])!='\0')
    {
        
        if(c==',')
            i++;
        else
        {
            vna[vnlen]=vn[i];
            i++;
            vnlen++;
        }
    }        
    printf("请输入产生式(产生式之间用逗号隔开)：");
    gets(p);
    i=0;ia=0;ib=0;ja=0;jb=0;
    tag=0;
    while((c=p[i])!='\0')
    {
        if(c==',')
        {
            i++;
            ia++;ja++;
            tag=0;        //新的产生式开始 
            ib=0;jb=0;
        }    
        else if(c==':')
        {
            
            i+=3;
            tag=1;         //左部结束 
        }    
        else if(tag==0)
        {
            left[ia][ib]=c;
            i++;
            ib++;
            numl[ia]=ib;
        }       
        else if(tag==1)   
        { 
            right[ja][jb]=c;
            i++;jb++;
            numr[ja]=jb; //记录右部有几个字符串 
        }
    }

        
    
    vtlen=0;
    for(i=0;i<=ia;i++)
    {
        for(j=0;j<numl[i];j++)
        {
            vt[vtlen]=left[i][j];
            vtlen++;
            
        }
    }
             
    for(i=0;i<=ja;i++)
    {
        for(j=0;j<numr[i];j++)
        {
            if(right[i][j]!='|')
            {
               vt[vtlen]=right[i][j];
               vtlen++;
            }
            
        }             
    }
   
    
    //消除VT中的重复字符 
    for(i=0;i<vtlen;i++)
        for(j=i+1;j<vtlen;)
        {
            if(vt[i]==vt[j])
            {
                for(k=j;k<vtlen-1;k++)
                    vt[k]=vt[k+1];
                    vtlen--;
                }
            else   j++;
        }

    vtalen=0;tag2=0;
    for(i=0;i<vtlen;i++)
    {
        tag2=0;
        for(j=0;j<vnlen;j++)
        {
            if(vt[i]==vna[j])
            {
                tag2=1;
                break;
            }
        }
        if(tag2==0)
        {
            vta[vtalen]=vt[i];
            vtalen++;
            
        }    
    }        

    output();   
    judge();
    printf("\t--------------------------------------\n");       
                
    getchar();
    return 0;
}