LL(1)文法的判别

一、实验名称

LL（1）文法的判别

二、实验目的

（1）能导出空串的非终结符算法

（2）实现首符集，后跟符集和可选集算法

（3）输出要指出是否为LL（1）文法， 

三、实验原理

① 将数组X[ ]中对应每一非终结符的标记置初值为"未定"。

② 扫描文法中的产生式。

(a) 删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出ε。

(b) 若某一非终结符的某一产生式右部为ε，则将数组中对应该非终结符的标志置为"是"，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为"是"。

③ 扫描产生式右部的每一符号。

(a) 若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。

(b) 若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。

④ 重复③，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。由②中(a) 、(b)得知例中对应非终结符D的标志改为"否"，对应非终结符A、B的标志改为"是"。经过上述②中(a)、(b)两步后文法中的产生式只剩下：S→AB和C→AD ，也就是只剩下右部全是非终结符串的产生式。再由③中的(a)步扫描到产生式S→AB时，在数组中A、B对应的标志都为"是"，删去后S的右部变为空，所以S对应标志置为"是"。

最后由③中的(b)扫描到产生式C→AD时，其中，A对应的标志为"是"，D对应的标志是"否"，删去该产生式后，再无左部为C的产生式，所以C的对应标志改为"否"

四、实验小结

通过本次实验，熟悉了LL（1）文法，掌握了LL（1）文法的判定方法，具体实践了FIRST集、FOLLOW集、SELECT集的计算，加深了对LL（1）文法的理解。此外，将理论用于实践，亲身体会到了怎样求FIRST集等。

如何理解转化的过程是相当重要，以及如何去创建程序去实现这一转化过程。这样的编程对于我来说是相当困难的，这次的程序并非自己编写的。但是我会一步步去理解该程序的每步含义，争取就算自己不会编写代码，但至少做到实现过程、步骤。

通过实验进一步理解编译原理这门课程，知道这么可是多么难学，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。在这次课程设计中，我们组就是按照实验指导的思想来完成，加强培养实践动手能力和程序开发能力。

五、附录

#include

#include

int count=0;              /*分解的产生式的个数*/

int number;               /*所有终结符和非终结符的总数*/

char start;               /*开始符号*/

char termin[50];          /*终结符号*/

char non_ter[50];         /*非终结符号*/

char v[50];               /*所有符号*/

char left[50];            /*左部*/

char right[50][50];       /*右部*/

char first[50][50],follow[50][50];       /*各产生式右部的FIRST和左部的FOLLOW集合*/

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 validity=1;           /*表示输入文法是否有效*/

int ll=1;                 /*表示输入文法是否为LL(1)文法*/

int M[20][20];            /*分析表*/

char choose;              /*用户输入时使用*/

char empt[20];            /*求_emp()时使用*/

char fo[20];              /*求FOLLOW集合时使用*/

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,non_ter)==1)

        c++;

    return(c);

}//得到一个不是非终结符的符号

void recur(char *point)// 分解含有左递归的产生式

{                     /*完整的产生式在point[]中*/

    int j,m=0,n=3,k;

    char temp[20],ch;

    ch=c();           /*得到一个非终结符*/

    k=strlen(non_ter);

    non_ter[k]=ch;

    non_ter[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("请输入文法的非终结符号串：");

    scanf("%s",vn);

 getchar();

    i=strlen(vn);

    memcpy(n,vn,i);

 n[i]='\\0';

 printf("请输入文法的终结符号串：");

    scanf("%s",vt);

 getchar();

    i=strlen(vt);

    memcpy(t,vt,i);

 t[i]='\\0';

    printf("请输入文法的开始符号：");

 scanf("%c",&s);

 getchar();

 printf("请输入文法产生式的条数：");

    scanf("%d",&i);

 getchar();

for(j=1;j<=i;j++)

 { printf("请输入文法的第%d条（共%d条）产生式：",j,i);

  scanf("%s",p[j-1]);

        getchar();

} for(j=0;j<=i-1;j++)

if(p[j][1]!='-'||p[j][2]!='>')

  { printf("\\ninput error!");

      validity=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       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]);    /*j为右部的长度*/

   if(j==1&&in(right[i][0],empty)==1)

       return(1);

   else if(j==1&&in(right[i][0],termin)==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       continue;

else if(result==1&&i       return(1); } }

}int judge()//判断读入的文法是否正确

{ int i,j;

for(i=0;i<=count-1;i++)

 { if(in(left[i],non_ter)==0)

  { /*若左部不在非终结符中，报错*/

   printf("\\nerror1!");

   validity=0;

   return(0);

} for(j=0;j<=strlen(right[i])-1;j++) {if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^')

   {/*若右部某一符号不在非终结符、终结符中且不为，报错*/   printf("\\nerror2!");validity=0;return(0); } } } return(1);

} void first2(int i)//求单个符号的FIRST

{/*i为符号在所有输入符号中的序号*/

 char c,temp[20]; int j,k,m; char ch='^'; c=v[i]; emp(ch);

 if(in(c,termin)==1)       /*若为终结符*/ {first1[i][0]=c;

     first1[i][1]='\\0';

 }  else if(in(c,non_ter)==1)       /*若为非终结符*/

{ for(j=0;j<=count-1;j++)

  {if(left[j]==c)  {if(in(right[j][0],termin)==1||right[j][0]=='^')

    {temp[0]=right[j][0];

        temp[1]='\\0';

     merge(first1[i],temp,1);

    }else if(in(right[j][0],non_ter)==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      {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);

}

      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';

}void FIRST(int i,char *p) //求各产生式右部的FIRST

{

 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   { 

                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;

  }

 }

}

void FOLLOW(int i) //求各产生式左部的FOLLOW

{

 int j,k,m,n,result=1;

 char c,temp[20];

 c=non_ter[i];             /*c为待求的非终结符*/

 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';

}

int ll1() //判断读入文法是否为一个LL(1)文法

{

    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("\\n单个符号的FIRST集合为:");

for(j=0;j<=strlen(v)-1;j++)

  printf("%c:%s  ",v[j],first1[j]);

    printf("\\n能推出^的非终结符:%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(non_ter)-1;j++)

    {                               /*求FOLLOW*/

  if(fo[j]==0)

  {

   fo[0]='\\0';

      FOLLOW(j);}}

 printf("\\n每个产生式右部符号串的FIRST集合为:");

for(i=0;i<=count-1;i++)

     printf("%s ",first[i]);

 printf("\\n每个非终结符的FOLLOW集合为:");

for(i=0;i<=strlen(non_ter)-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("\\n每个产生式的SELECT集合为:");

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)  else

  {temp[0]='\\0';   memcpy(temp,select[i],strlen(select[i]);

   temp[strlen(select[i])]='\\0';

  }}

 return(1);

}

void MM() //构造分析表M

{ int i,j,k,m;

for(i=0;i<=19;i++)

for(j=0;j<=19;j++)

   M[i][j]=-1;

    i=strlen(termin);

    termin[i]='#';     /*将#加入终结符数组*/

    termin[i+1]='\\0';

for(i=0;i<=count-1;i++)

 { for(m=0;;m++)

   if(non_ter[m]==left[i])

    break;      /*m为产生式左部非终结符的序号*/

for(j=0;j<=strlen(select[i])-1;j++)

  { if(in(select[i][j],termin)==1)

   {for(k=0;;k++)

     if(termin[k]==select[i][j])

      break;        /*k为产生式右部终结符的序号*/

                M[m][k]=i;

   }

  }

 }

}

void syntax() //总控算法

{

 int i,j,k,m,n,p,q;

    char ch;

 char S[50],str[50];

    printf("请输入该文法的句型：");

 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],termin)==1)

  {

            if(S[strlen(S)-1]!=ch)

   {

    printf("该符号串不是文法的句型！");

                return;

   }

   else if(S[strlen(S)-1]=='#')

   {

                printf("该符号串是文法的句型.");

                return; }

   else

   {S[strlen(S)-1]='\\0';

    j++;

    ch=str[j];

   }}

  else 

  {   for(i=0;;i++)

    if(non_ter[i]==S[strlen(S)-1])

     break;

   for(k=0;;k++)

   { 

    if(termin[k]==ch)

     break;

    if(k==strlen(termin))

    {

     printf("词法错误！");

     return;

    }

   }

   if(M[i][k]==-1)

   {

    printf("语法错误！");

    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()// 一个用户调用函数

{

 syntax();

 printf("\\n是否继续？(y or n):");

 scanf("%c",&choose);

 getchar();

 while(choose=='y')

  { 

   menu();

  }

}

void main() //主函数

{

 int i,j;

start=grammer(termin,non_ter,left,right); 

//    printf("count=%d",count);

// printf("\\nstart:%c",start);

 strcpy(v,non_ter);

 strcat(v,termin);

// printf("\\nv:%s",v);

// printf("\\nnon_ter:%s",non_ter);

//    printf("\\ntermin:%s",termin);

// printf("\\nright:");

//for(i=0;i<=count-1;i++)

//     printf("%s   ",right[i]); 

//    printf("\\nleft:");

//for(i=0;i<=count-1;i++)

 // printf("%c   ",left[i]);            

    if(validity==1)

     validity=judge();

 //   printf("\\nvalidity=%d",validity);

 if(validity==1)

 {

        ll=ll1();

  //printf("\\nll=%d",ll);

  if(ll==0)

   printf("\\n该文法不是一个LL1文法！");

  else

  {

      printf("\\n该文法是LL1文法！");

     /* MM();

            printf("\\n");

for(i=0;i<=19;i++)

for(j=0;j<=19;j++)

if(M[i][j]>=0)

            printf("M[%d][%d]=%d ",i,j,M[i][j]);

      menu();*/

  }

 }

}