lr.c

LR0分析器,一个LALR(1)语法分析器

#include"stdio.h"   
  #include"string.h"   
    
  #define   R     30   
  #define   C     20   
    
  typedef   struct   elem   
  {   
          char   e[4];   
  }Elem;       //ACTION表与GoTo表中的元素类型   
    
  Elem   LR[R][C];                             //存放ACTION表与GoTo表中的内容   
    
  typedef   struct   out   
  {   
          int     order;                   //序号   
          int     state[10];           //状态栈   
          char   sign[30];             //符号栈   
          char   grasen[20];         //产生式   
          char   input[30];           //输入串   
          char   explen[50];         //解释说明   
  }OutNode;       //输出结果中每一行的类型   
    
  OutNode   out[20];                         //存放输出结果   
    
  char   Sentence[20];                     //存放文法的一个句子   
  char   GramSent[10][20];             //存放文法的一组产生式   
  int   row,colno;                             //row为状态个数数，colno为ACTION表与GoTo表列总数   
  int   stateTop=0,signTop=0;               //状态栈与符号栈的栈顶位置(值与栈中元素的个数相等)   
    
  void   input_GramSent()   
  {   
          int   i,num;   
          printf("请输入文法中产生式的个数\n");   
          scanf("%d",&num);   
          for(i=1;i<=num;i++)   
          {   
                printf("请输入文法的第%d个产生式\n",i);   
                scanf("%s",GramSent+i-1);   
          }   
          printf("请输入文法的一个句子\n");   
          scanf("%s",Sentence);   
            
          printf("**********************************************************\n");   
          printf("*     文法的产生式如下：                                                                         *\n");   
          printf("**********************************************************\n");   
          for(i=0;i<num;i++)   
                  printf("%s\n",GramSent+i);   
          printf("**********************************************************\n");   
          printf("*     文法的句子如下：                                                                             *\n");   
          printf("**********************************************************\n");   
              printf("%s\n",Sentence);   
  }   
  void   input_LR(int   row,int   colno)                                 //row为行总数，colno为列总数   
  {   
      int   i,j;   
      char   mid[4];   
      printf("**********************************************************\n");   
      printf("*     提示：每输入一个元素后就回车                                                     *\n");   
      printf("**********************************************************\n");   
    
      printf("请输入LR分析表的终结符(包括#)与非终结符\n");   
      for(j=0;j<colno;j++)   
            scanf("%s",LR[0][j].e);   
    
      for(i=0;i<row;i++)   
      {   
              printf("请输入%d号状态所对应的各列的元素,空白的地方用s代替\n",i);   
              for(j=0;j<colno;j++)   
              {   
                      scanf("%s",mid);   
                      if(strcmp(mid,"s")==0||strcmp(mid,"S")==0)   
                              strcpy(LR[i+1][j].e,"   ");   
                      else   
                              strcpy(LR[i+1][j].e,mid);   
              }   
      }       
  }   
  void   output_LR(int   row,int   colno)   
  {   
      int   i,j;   
      printf("**********************************************************\n");   
      printf("*     LR分析表如下：                                                                                 *\n");   
      printf("**********************************************************\n");   
      printf("\n");   
    
      printf("         ");   
      for(j=0;j<colno;j++)   
                      printf("%s       ",LR[0][j].e);   
      printf("\n");   
    
      for(i=1;i<=row;i++)   
      {         
              printf("%d       ",i-1);   
              for(j=0;j<colno;j++)   
                      printf("%s       ",LR[i][j].e);   
              printf("\n");   
      }   
      printf("\n");   
  }   
    
  int   SignNum(char   ch)//给定一个终结符或非终结符,返回其在ACTION表与GoTo表中的列位置   
  {   
      int   i;   
      char   c[2]="0";   
      c[0]=ch;   
      for(i=0;i<colno;i++)   
              if(strcmp(c,LR[0][i].e)==0)   
                      return   i;   
      return   -1;   
  }   
    
  int   CharChangeNum(char*   ch)//给定一数字字符串,返回其所对应的数字   
  {   
          int   result=0;   
          while(*ch!='\0')   
          {   
                  result=result*10+(*ch-'0');   
                  ch++;   
          }   
          return   result;   
  }   
  int   OutResult(int   s,int   c,int   i)//输出结果的第i+1行处理函数,(s为状态，c为列)   
  {   
          char   mid[4],gra[20];   
          int   s_num,r_num;   
          int   n,len,j;   
    
          strcpy(mid,LR[s+1][c].e);   
          if(strcmp(mid,"   ")==0)   
          {     printf("不能规约\n");       return   -2;     }   
    
          if(strcmp(mid,"acc")==0||strcmp(mid,"ACC")==0)   
          {     printf("规约成功\n");       return   -1;     }   
    
          out[i+1].order=i+2;   
    
          if(mid[0]=='s'||mid[0]=='S')   
          {   
                  s_num=CharChangeNum(mid+1);//s_num为S后的数字   
                  for(j=0;j<stateTop;j++)   
                          out[i+1].state[j]=out[i].state[j];   
                  out[i+1].state[stateTop]=s_num;     
                  out[i+1].state[++stateTop]=-1;       //完成第i+1行的状态栈赋值   
    
                  strcpy(out[i+1].sign,out[i].sign);   
                  out[i+1].sign[signTop]=out[i].input[0];   
                  out[i+1].sign[++signTop]='\0';     //完成第i+1行的符号栈的赋值   
    
                  strcpy(out[i+1].grasen,"   ");                                 //完成第i+1行的产生式的赋值   
    
                  strcpy(out[i+1].input,out[i].input+1);         //完成第i+1行的输入符号串的赋值   
    
                  //说明暂时不写   
          }   
          else   if(mid[0]=='r'||mid[0]=='R')   
          {   
                  r_num=CharChangeNum(mid+1);//r_num为r后的数字   
                  strcpy(gra,*(GramSent+r_num-1));   
                  len=strlen(gra);   
                  for(j=0;j<len;j++)   
                          if(gra[j]=='-'   &&   gra[j+1]=='>')   
                          break;   
                  n=strlen(gra+j+2);   
            
                  stateTop-=n;     signTop-=n;   
    
                  for(j=0;j<stateTop;j++)   
                          out[i+1].state[j]=out[i].state[j];   
                  j=SignNum(gra[0]);   
                  out[i+1].state[stateTop]=CharChangeNum(LR[out[i+1].state[stateTop-1]+1][j].e);     
                  out[i+1].state[++stateTop]=-1;       //完成第i+1行的状态栈赋值   
    
                  strcpy(out[i+1].sign,out[i].sign);   
                  out[i+1].sign[signTop]=gra[0];   
                  out[i+1].sign[++signTop]='\0';     //完成第i+1行的符号栈的赋值   
    
                  strcpy(out[i+1].grasen,gra);                                 //完成第i+1行的产生式的赋值   
    
                  strcpy(out[i+1].input,out[i].input);         //完成第i+1行的输入符号串的赋值   
    
                  //说明暂时不写   
          }   
          return   1;   
  }   
    
  void   OutputResult(int   r)   
  {     
          int   i,j;   
          printf("**********************************************************\n");   
          printf("*     句子：%s   用LR分析表   规约过程如下：                                     *\n",Sentence);   
          printf("**********************************************************\n");   
          for(i=0;i<=r;i++)   
          {   
                  j=0;   
                  printf("%2d     ",out[i].order);   
                  while(out[i].state[j]!=-1)   
                          printf("%d",out[i].state[j++]);   
                  printf("     %s     %s     %s\n",out[i].sign,out[i].grasen,out[i].input);   
          }   
  }   
    
  int   OutControl()//输出结果的总控函数   
  {   
          int   s_num,i=0;   
          out[0].order=1;                                   //序号赋值   
          out[0].state[0]=0;     stateTop=1;     out[0].state[stateTop]=-1;           //状态栈赋值，置栈顶位   
          strcpy(out[0].sign,"#");       signTop=1;       //符号栈赋值，置栈顶位   
          strcpy(out[0].grasen,"   ");                             //产生式为空   
          strcpy(out[0].input,Sentence);                     //以下两行为输入串赋值   
          strcat(out[0].input,"#");   
          strcpy(out[0].explen,"0和#进栈");               //解释说明   
          //初使化输出结果的第一行   
            
          while(1)   
          {   
                  s_num=SignNum(out[i].input[0]);   
                  //if(s_num!=-1)   
                  if(OutResult(out[i].state[stateTop-1],s_num,i)!=1)   
                          break;   
                  i++;   
          }   
          return   i;   
  }   
    
  main()   
  {   
          int   r;   
          printf("**********************************************************\n");   
          printf("*     函数的输入:   文法的产生式,文法句型的一个句子,LR分析表     *\n");   
          printf("*     函数的输出:   LR分析器的工作过程与说明                                     *\n");   
          printf("**********************************************************\n");   
          printf("请输入LR分析表中终结符与非终结符的总个数\n");   
          scanf("%d",&colno);   
          printf("请输入LR分析表中状态的总个数\n");   
          scanf("%d",&row);   
          input_LR(row,colno);   
          output_LR(row,colno);   
          input_GramSent();   
          r=OutControl();     //r为输出结果的行数   
          OutputResult(r);   
  }