首页 > 代码库 > 递归下降分析

递归下降分析

 

对于给定的文法G[E] :

E→E+T|E-T|T
T→T*F| T/F|F
F→(E)|i

消除左递归后的文法是:
E→TE‘

E‘→+TE‘|-TE‘|∑

T→FT‘

T‘→*FT‘|/FT‘|∑

F→(E)|i

是否是LL(1)文法?

select(E→TE‘)=first(TE‘)={(,i}
select(E‘→+TE‘)=first(+TE‘)={+}
select(E‘→-TE‘)=first(-TE‘)={-}
select(E‘→∑)=follow(E‘)={),#}
select(T→FT‘)=first(FT‘)={(,i}
select(T‘→*FT‘)=first(*FT‘)={*}
select(T‘→/FT‘)=first(/FT‘)={/}
select(T‘→∑)=follow(T‘)={+,-,),#)
select(F→(E))=first((E))={(}
select(F→i)=first(i)={i}

由上分析,得知此文法满足LL(1)文法.

 

C语言代码如下:

#include<stdio.h>
#include <string.h>
void scaner();
void E();
void E1();
void T();
void T1();
void F();
void error();
char proce[100],ch,token[20];
int syn,i,j,m,sum=0;
char *keyword[6]= {"begin","if","then","while","do","end"};
main()
{
    i=0;//记录输入多少个字符
    printf("\n 请输入词法分析程序:");
      do{
                 ch=getchar();
                 proce[i]=ch;
                 i++;
      }while (ch!=#);
      i=0;
      do{
          scaner();
          switch(syn)
                  {
                     case 11: printf("\n(%d,%d)",syn,sum);
                              break;
                     case -1: printf("\n(%s,#)",token);
                              break;
                     default: printf("\n(%d,%s)",syn, token);
                  }
       }while (syn!=0);
  printf("\n");

    i=0;

    scaner();
     E();
     if (syn==0)
              printf("\n 语法正确. \n");
     else     printf("\n  语法失败. \n");

}
void scaner()
{
        for (j=0;j<20;j++)
            token[j]=NULL;//将token赋值为空
        m=0;
        sum=0;
        ch=proce[i];
        i++;
        while (ch== )
        {
            ch=proce[i++];
        }
        if (ch>=a&& ch<=z)
           {while (ch>=a&& ch<=z||ch>=0 && ch<=9)
                  {
                   token[m++]=ch;
                   ch=proce[i++];//继续看后面的
                  }

            syn=10;i--;//判断为变量
            for (j=0;j<6;j++)
                if(strcmp(token,keyword[j])==0)
                    {
                        syn=j+1;
                         break;
                     }//如果有可以匹配的就为关键字
           }
 else
            if(ch>=0 && ch<=9)
            {while (ch>=0 && ch<=9)
              {
                sum=sum*10+(ch-0);
                ch=proce[i];
                i++;
              }
              syn=11;
              i--;
            }
          else
                switch(ch)
                {
                  case <: token[m]=ch;
                             m++;
                            ch=proce[i];
                            i++;
                            if (ch==>)
                                {
                                    syn=21;
                                   token[m]=ch;
                                   m++;
                                 }
                            else if (ch===)
                                {
                                    syn=22;
                                   token[m]=ch;
                                   m++;
                                 }
                                 else
                                    {
                                        syn=20;
                                        i--;
                                    }
                             break;

                  case >: m=0;
                            token[m]=ch;
                            m++;
                            ch=proce[i];
                            i++;
                            if (ch===)
                            {
                             syn=24;
                             token[m]=ch;
                             m++;
                            }
                            else
                                {
                                    syn=23;
                                    i--;
                                }
                            break;
                  case :: m=0;
                            token[m++]=ch;
                            ch=proce[i++];
                            if (ch===)
                            {
                                syn=18;
                              token[m++]=ch;
                            }
                            else
                                {
                                    syn=17;
                                    i--;
                                }
                            break;
                 case +:
                     syn=13;
                     token[0]=ch;
                     break;
                  case -:
                      syn=14;
                      token[0]=ch;
                      break;
                  case *:
                      syn=15;
                      token[0]=ch;
                      break;
                  case /:
                      syn=16;
                      token[0]=ch;
                      break;
                  case =:
                      syn=25;
                      token[0]=ch;
                      break;
                  case ;:
                      syn=26;
                      token[0]=ch;
                      break;
                  case (:
                     syn=27;
                     token[0]=ch;
                      break;
                  case ):
                      syn=28;
                      token[0]=ch;
                      break;
                  case #:
                      syn=0;
                      token[0]=ch;
                      break;
                  default:
                      syn=-1;
                      token[0]=ch;
                }
}
void E() { printf("E "); T(); E1(); } void E1() { printf("E1 "); if (syn==13) { scaner(); T(); E1(); } else { if (syn!=28 && syn!=0) error(); } } void T() { printf("T "); F(); T1(); } void T1() { printf("T1 "); if (syn==15) { scaner(); F(); T1(); } else { if (syn!=28 && syn!=0 && syn!=13) error(); } } void F() { printf("F "); if (syn==27) { scaner(); E(); if(syn==28) scaner(); else error(); } else if (syn==11 || syn==10) scaner(); } void error() { printf("\n (%d,%s)语法错误! \n",syn, token); }

 

递归下降分析