main.cpp

ll1文法分析器

   }
  }
 }
 f[i]='1';
}
/*******************************************
 求各产生式右部的FIRST
********************************************/
void __fastcall TForm1::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 __fastcall TForm1::FOLLOW(int i)
{
 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==starter)
 {                         /*若为开始符号*/
  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 __fastcall TForm1::ll1()
{
    int i,j,length,result=1;
 char temp[50];
 for(j=0;j<50;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集合*/
 Form2->Memo1->Lines->Add("文法符号的first集:");
 AnsiString str2=" ";
 for(j=0;j<strlen(v);j++)
    { AnsiString str1=v[j];
      str1+=":  ";
       for(int m=0;m<50;m++)
       str1+=first1[j][m];
       Form2->Memo1->Lines->Add(str1);}
  //printf("%c:%s  ",v[j],first1[j]);
   // printf("\nempty:%s",empty);
   str2+="empty: ";
   int q=0;
   while(empty[q]!='\0')
   {str2+=empty[q];str2+=" ";q++; }
    Form2->Memo1->Lines->Add(str2);

 //printf("\n:::\n_emp:");
 Form2->Memo1->Lines->Add(":::");
 AnsiString stremp="_emp:";
 for(j=0;j<=strlen(v)-1;j++)
    { stremp+=_emp(v[j]);
     stremp+=" ";}
     Form2->Memo1->Lines->Add(stremp);
        //printf("%d  ",_emp(v[j]));
 for(i=0;i<=count-1;i++)
     FIRST(i,right[i]);          /*求FIRST*/
   Form2->Memo1->Lines->Add(" ");
 for(j=0;j<=strlen(non_ter)-1;j++)
    {                               /*求FOLLOW*/
  if(fo[j]==0)
  {
   fo[0]='\0';
      FOLLOW(j);
  }
    }

 Form2->Memo1->Lines->Add("产生式右部的first集:");
 AnsiString firststr=0;
 for(i=0;i<=count-1;i++)
     {firststr+=p[i];firststr+=":  ";
      firststr+=first[i];
        firststr+="    ";
   Form2->Memo1->Lines->Add(firststr);firststr=i+1;  }

    Form2->Memo1->Lines->Add("产生式左部的follow集:");
    AnsiString followstr=0;
    for(i=0;i<=strlen(non_ter)-1;i++)
       {followstr+=p[i];followstr+=":  ";
        followstr+=follow[i];followstr+="    ";
     Form2->Memo1->Lines->Add(followstr);followstr=i+1;   }
 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);
  }
 }

 Form2->Memo1->Lines->Add("产生式的select集:");
 AnsiString selectstr="0";
 for(i=0;i<=count-1;i++)
  { selectstr+=p[i];selectstr+=":  ";
    selectstr+=select[i];selectstr+="    ";
    Form2->Memo1->Lines->Add(selectstr);selectstr=i+1;   }
 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 __fastcall TForm1::MM()
{
    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 __fastcall TForm1::syntax()
{
 int i,j,k,m,n,p,q;
    char ch;
 char S[50];
   char str[50];
   char *buf;
   buf=new char[Form3->Edit1->Text.Length()];
   strcpy(buf,Form3->Edit1->Text.c_str());
   for(i=0;i<=Form3->Edit1->Text.Length();i++)
   str[i]=buf[i];

//scanf("%s",str);
//getchar();
 i=strlen(str);
 str[i]='#';
 str[i+1]='\0';
 S[0]='#';
 S[1]=starter;
 S[2]='\0';
 j=0;
 ch=str[j];
    while(1)
 {
  if(in(S[strlen(S)-1],termin)==1)
  {
            if(S[strlen(S)-1]!=ch)
   {
    Form3->Memo1->Lines->Add("该符号串不是文法的句型！");
                return;
   }
   else if(S[strlen(S)-1]=='#')
   {
      Form3->Memo1->Lines->Add("该符号串是文法的句型.");
                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))
    {
     Form3->Memo1->Lines->Add("\n词法错误！");
     return;
    }
   }
   if(M[i][k]==-1)
   {
    Form3->Memo1->Lines->Add("\n语法错误！");
    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("\nS:%s str:",S);
       AnsiString strS="S:";
       strS+=S;
       strS+="  ";
       strS+="str:";
 for(p=j;p<=strlen(str)-1;p++)
       strS+=str[p];
       Form3->Memo1->Lines->Add(strS);
 
 }
}

/*******************************************
 一个用户调用函数
********************************************/
/*void menu()
{
 syntax();
 printf("\n是否继续？(y or n):");
 scanf("%c",&choose);
 getchar();
 while(choose=='y')
  {
   menu();
  }
} */










void __fastcall TForm1::Button2Click(TObject *Sender)
{if(open==false)ShowMessage("无产生式，请输入...");
 else{
 Form2->Show();
 int i,j;
 grammer(termin,non_ter,left,right);


AnsiString strstarter;
strstarter="开始符号: ";
strstarter+=starter;
 Form2->Memo1->Lines->Add(strstarter);
 strcpy(v,non_ter);
 strcat(v,termin);
 AnsiString strv;
 strv="所有符号: ";
 strv+=v;
 Form2->Memo1->Lines->Add(strv);
 AnsiString strnon_ter,strtermin;
 for(int k=0;k<50;k++)
 {strnon_ter+=non_ter[k];
   strtermin+=termin[k];
   }
 Form2->Memo1->Lines->Add("(非终结符)non_termin:  "+strnon_ter);
 Form2->Memo1->Lines->Add("(终结符)termin:  "+strtermin);
 AnsiString strright,strleft;
 for(i=0;i<=count-1;i++)
     {strright+=right[i];strleft+=left[i];}
 Form2->Memo1->Lines->Add("(各右部符号)right:  "+strright);
 Form2->Memo1->Lines->Add("(各左部符号)left:  "+strleft);
 //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);
 AnsiString strvalidity;
 strvalidity="validity=";
 strvalidity+=validity;
 Form2->Memo1->Lines->Add(strvalidity);
 if(validity==1)
 {
       Form2->Memo1->Lines->Add("文法有效!");
  ll=ll1();
  //printf("\nll=%d",ll);
  AnsiString strll;
  strll="ll=";
  strll+=ll;
  Form2->Memo1->Lines->Add(strll);
  if(ll==0)
   Form2->Memo1->Lines->Add("该文法不是一个LL1文法!");
  else
  {   Form2->Memo1->Lines->Add("该文法是一个LL1文法，故有构造分析表如下：");
      MM();
      Form2->Memo1->Lines->Add("MM:");
      AnsiString Mstr;
      for(i=0;i<=19;i++)
         {
          for(j=0;j<=19;j++)
           if(M[i][j]>=0)
           { Mstr+="M[";
             Mstr+=i;
             Mstr+="][";
             Mstr+=j;
             Mstr+="]=";
             Mstr+=M[i][j];
             Mstr+="  ";
                }   }
           Form2->Memo1->Lines->Add(Mstr);
           
            //printf("M[%d][%d]=%d ",i,j,M[i][j]);


  }
 }

 }
}
//---------------------------------------------------------------------------