ll1.c

实现编译原理中的LL1文法

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

char VT[50];
char VN[50];
char v[50];                /*   V*  */
int count=0;                /*分解的产生式的个数*/
int number;               /*终结符和非终结符的总数*/
char start;                /*起始非终结符*/
char left[50];            /*产生式左部*/
char right[50][50];       /*产生式右部*/
char follow[50][50];      /*各产生式左部的FOLLOW集合*/
char first[50][50];       /*各产生式右部的FIRST集合*/
char first1[50][50];      /*所有单个符号的FIRST集合*/
char select[50][50];      /*各单个产生式的SELECT集合*/
char f[50],F[50];         /*记录各符号的FIRST和FOLLOW是否已求过*/
char empty[20];           /*保存可推出‘$'的符号*/
char TEMP[50];            /*求FOLLOW时存放某一符号串的FIRST集合*/
int CanUse=1;              /*用于判断文法是否有效的标志位*/
int ll=1;                  /*用于判断文法是否是LL1文法*/
int M[20][20];             /*分析表*/
char choose;               /*用于再输入标志*/
char empt[20];
char fo[20];


/******判断一个字符是否在指定字符串中***********/
int in(char c,char *p)
{
    int i;
    if(strlen(p)==0)
        return(0);
    for(i=0;;i++)
    {    
        if(p[i]==c)
            return(1);       /*若在，返回1*/
        if(i==strlen(p))
            return(0);       /*若不在，返回0*/
    }
}

/********得到产生式右部一非终结符**************/
char c()
{
    char c='A';
    while(in(c,VN)==1)
        c++;
    return(c);
}

/***********分解含有左递归的产生式*******/
void recur(char *point)
{
    int j,m=0,n=3,k;
    char temp[20],ch;
    ch=c();           /*得到一个非终结符*/
    k=strlen(VN);
    VN[k]=ch;
    VN[k+1]='\0';
    for(j=0;j<=strlen(point)-1;j++)
    {    
        if(point[n]==point[0])
        {                          /*如果‘|’后的首符号和左部相同*/
            for(j=n+1;j<=strlen(point)-1;j++)
            {
                   while(point[j]!='|'&&point[j]!='\0')
                    temp[m++]=point[j++];
                left[count]=ch;
                memcpy(right[count],temp,m);
                right[count][m]=ch;
                right[count][m+1]='\0';
                m=0;
                count++;
                if(point[j]=='|')
                {
                    n=j+1;
                    break;
                }
            }
        }
        else
        {
            left[count]=ch;
            right[count][0]='$';
            right[count][1]='\0';
            count++;
            for(j=n;j<=strlen(point)-1;j++)
            {
                if(point[j]!='|')
                    temp[m++]=point[j];
                else
                {
                    left[count]=point[0];
                    memcpy(right[count],temp,m);
                    right[count][m]=ch;
                    right[count][m+1]='\0';
                    printf(" count=%d ",count);
                    m=0;
                    count++;
                }
            }
            left[count]=point[0];
            memcpy(right[count],temp,m);
            right[count][m]=ch;
              right[count][m+1]='\0';
            count++;
            m=0;
        }
    }
}

/**************分解不含有左递归的产生式**********************/
void non_re(char *point)
{
    int m=0,j;
    char temp[20];
    for(j=3;j<=strlen(point)-1;j++)
    {
        if(point[j]!='|')
            temp[m++]=point[j];
        else
        {
            left[count]=point[0];
            memcpy(right[count],temp,m);
            right[count][m]='\0';
            m=0;
            count++;
        }
    }
    left[count]=point[0];
    memcpy(right[count],temp,m);
    right[count][m]='\0';
    count++;
    m=0;
}


/*******************读入一个文法**************************************/
char grammer(char *t,char *n,char *left,char right[50][50])
{
    char vn[50],vt[50];
    char s;
    char p[50][50];
    int i,j,k;
    printf("please input VN:");
    scanf("%s",vn);
    getchar();
    i=strlen(vn);
    memcpy(n,vn,i);
    n[i]='\0';
    printf("please input VT:");
    scanf("%s",vt);
    getchar();
    i=strlen(vt);
    memcpy(t,vt,i);
    t[i]='\0';
    printf("input the start symbols:");
    scanf("%c",&s);
    getchar();
    printf("input the number of production:");
    scanf("%d",&i);
    getchar();
    for(j=1;j<=i;j++)
    {
        printf("input the %d production:",j);
        scanf("%s",p[j-1]);
        getchar();
    }
    for(j=0;j<=i-1;j++)
        if(p[j][1]!='-'||p[j][2]!='>')
        {    printf("\ninput error!");
            CanUse=0;
            return('\0');
        }            /*检测输入错误*/
   for(k=0;k<=i-1;k++)
   {                        /*分解输入的各产生式*/
        if(p[k][3]==p[k][0])
            recur(p[k]);
        else
            non_re(p[k]);
    }
    return(s);
}



/********************将单个符号或符号串并入另一符号串***************/
void merge(char *d,char *s,int type)
{                 /*d是目标符号串，s是源串，type＝1，源串中的‘ $ ’一并并入目串；
                   type＝2，源串中的‘ $ ’不并入目串*/
    int i,j;
    for(i=0;i<=strlen(s)-1;i++)
    {
        if(type==2&&s[i]=='$')
            ;
        else
        {
            for(j=0;;j++)
            {
                if(j<strlen(d)&&s[i]==d[j])
                   break;
                if(j==strlen(d))
                {
                    d[j]=s[i];
                    d[j+1]='\0';
                    break;
                }
            }
        }
    }
}



/***************求所有能直接推出$的符号***************************/
void emp(char c)
{                   /*求所有由‘ $ ’推出的符号*/
    char temp[10];
    int i;
    for(i=0;i<=count-1;i++)
    {
        if(right[i][0]==c&&strlen(right[i])==1)
        {
            temp[0]=left[i];
            temp[1]='\0';
            merge(empty,temp,1);
            emp(left[i]);
        }
    }
}

/*********** 求某一符号能否推出‘ $ ’************************/
int _emp(char c)
{                  /*若能推出，返回1；否则，返回0*/
    int i,j,k,result=1,mark=0;
    char temp[20];
    temp[0]=c;
    temp[1]='\0';
    merge(empt,temp,1);
    if(in(c,empty)==1)
        return(1);
    for(i=0;;i++)
    {
        if(i==count)
            return(0);
        if(left[i]==c)         /*找一个左部为c的产生式*/
        {
            j=strlen(right[i]);
            if(j==1&&in(right[i][0],empty)==1)
                return(1);
            else if(j==1&&in(right[i][0],VT)==1)
                return(0);
            else 
            {
                for(k=0;k<=j-1;k++)
                    if(in(right[i][k],empt)==1)
                        mark=1;
                if(mark==1)
                    continue;
                else
                {
                    for(k=0;k<=j-1;k++)
                    {
                        result*=_emp(right[i][k]);
                        temp[0]=right[i][k];
                        temp[1]='\0';
                        merge(empt,temp,1);
                    }
                }
            }
            if(result==0&&i<count)
                continue;
            else if(result==1&&i<count)
                return(1);
        }
    }
}


/******************判断读入的文法是否正确**************************/
int judge()
{
    int i,j;
    for(i=0;i<=count-1;i++)
    {
        if(in(left[i],VN)==0)
        {                    /*若左部不在非终结符中，报错*/
            printf("\nerror1!");
            CanUse=0;
            return(0);
        }
        for(j=0;j<=strlen(right[i])-1;j++)
        {
            if(in(right[i][j],VN)==0&&in(right[i][j],VT)==0&&right[i][j]!='$')
            {               /*若右部某一符号不在非终结符、终结符中且不为‘ $ ’，报错*/
                printf("\nerror2!");
                CanUse=0;
                return(0);
            }
        }
    }
    return(1);
}

/**********************求单个符号的FIRST*************/
void first2(int i)
{                     /*i为符号在所有输入符号中的序号*/
    char ch,c,temp[20];
    int j,k,m;
    c=v[i];
    ch='$';
    emp(ch);
    if(in(c,VT)==1)       /*若为终结符*/
    {
        first1[i][0]=c;
        first1[i][1]='\0';
    }   
    else if(in(c,VN)==1)       /*若为非终结符*/
    {
        for(j=0;j<=count-1;j++)
        {
            if(left[j]==c)
            {
                if(in(right[j][0],VT)==1||right[j][0]=='$')
                {
                    temp[0]=right[j][0];
                    temp[1]='\0';
                    merge(first1[i],temp,1);
                }
                else if(in(right[j][0],VN)==1)
                {
                    if(right[j][0]==c)
                        continue;
                    for(k=0;;k++)
                        if(v[k]==right[j][0])
                            break;
                    if(f[k]=='0')
                    {   
                        first2(k);
                        f[k]='1';
                    }
                    merge(first1[i],first1[k],2);
                    for(k=0;k<=strlen(right[j])-1;k++)
                    {
                        empt[0]='\0';
                        if(_emp(right[j][k])==1&&k<strlen(right[j])-1)
                        {
                            for(m=0;;m++)
                                if(v[m]==right[j][k+1])
                                    break;
                            if(f[m]=='0')
                            {
                                first2(m);
                                f[m]='1';
                            }
                            merge(first1[i],first1[m],2);
                        }