正文

语法分析器2007-06-23 11:59:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/tld5yj/27036.html

分享到:

这是一个能识别加法和乘法的语法分析器,例如在提示输入后输入一个算式:3+5*2*(2+1)这类的,那么就会给出匹配过程,并判断是不是成功,请赏析!由于构造了first集,follow集,select集之类,所以比较占篇幅,惭愧!

#include<string.h>

int isterminal(char a)
{if((a=='i')||(a=='+')||(a=='*')||(a=='(')||(a==')')||(a=='$'))
 return(1);
 else return(0);
}

int notin(char a,char *b)
{char *c;
 for(c=b;(*c)!='\0';c++)
 {if((*c)==a) break;
 }
 if((*c)=='\0') return(1);
 else return(0);
}

void add(char *g,char *q,char *a)
{char *tem;
 tem=a;
 for(;(*tem)!='\0';tem++)
 {if(notin((*tem),g))
  {(*q)=(*tem);
   q++;
   (*q)='\0';
  }
 }
}

int maybenull(char E)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
 int i;
 for(i=0;i<8;i++)
 {if((product[i][0]==E)&&(product[i][1]=='\0'))
  break;
 }
 if(i<8) return(1);
 else if(i>=8) return(0);
}

char *first(char E)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
 char group[200],*q;
 int i,j;
 q=group;
 if(isterminal(E))
 {(*q)=E;
  q++;
  (*q)='\0';
 }
 else
 {for(i=0;i<8;i++)
  {if(product[i][0]==E)
   {if(isterminal(product[i][1])&&notin(product[i][1],group))
    {(*q)=product[i][1];
     q++;
     (*q)='\0';
    }
    else if((!isterminal(product[i][1]))&&((product[i][1])!='\0'))
    {add(group,q,first(product[i][1]));
     for(j=1;j<(strlen(product[i]));j++)
     {if(maybenull(product[i][j])&&(product[i][j+1]!='\0'))
      add(group,q,first(product[i][j+1]));
     }
    }
   }
  }
 }
 return(group);
}

char *follow(char E)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
 char group[200],*q,*tem;
 int i,j,k;
 q=group;
 if(E=='S')
 {(*q)='$';
  q++;
  (*q)='\0';
 }
 for(i=0;i<8;i++)
 {for(j=1;j<strlen(product[i]);j++)  /*startfor1*/
  {if(product[i][j]==E)  /*startif*/
   {if(isterminal(product[i][j+1]))  /*startif1*/
    {(*q)=product[i][j+1];
     q++;
     (*q)='\0';
    }  /*endif1*/
    else if(!isterminal(product[i][j+1]))  /*startif2*/
    {if(product[i][j+1]=='\0')  /*startif3*/
     {if(product[i][0]!=E)
      add(group,q,follow(product[i][0]));
     }  /*startif3*/
     else if(product[i][j+1]!='\0')  /*startif4*/
     {tem=first(product[i][j+1]);
      for(;(*tem)!='\0';tem++)
      {if(notin((*tem),group))
       {(*q)=(*tem);
        q++;
        (*q)='\0';
       }
      }
      for(k=j+1;k<(strlen(product[i])-1);k++)  /*startfor2*/
      {if(maybenull(product[i][k]))
       {add(group,q,first(product[i][k+1]));
       }
       else break;
      }  /*endfor2*/
      if(k==(strlen(product[i])-1))add(group,q,follow(product[i][k]));
     }  /*endif4*/
    }  /*endif2*/
   }  /*endif*/
  }  /*endfor1*/
 }
 return(group);
}

char *select(int n)
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
 char group[200],*q;
 int i=1,j=0;
 q=group;
 if(product[n][i]!='\0')
 {add(group,q,first(product[n][1]));
  for(j=i;j<(strlen(product[n]));j++)
  {if(maybenull(product[n][j]))
   {if(product[n][j+1]!='\0')
    add(group,q,first(product[n][j+1]));
    else if(product[n][j+1]=='\0') add(group,q,follow(product[n][0]));
   }
   else break;
  }
 }
 else if(product[n][1]=='\0') add(group,q,follow(product[n][0]));
 return(group);
}

void print(char *a)
{char *b=a;
 if(strlen(a)==1)printf("%c->null",*b);
 else
 {printf("%c->",*b);
  for(b++;(*b)!='\0';b++)printf("%c",*b);
 }
}

main()
{char product[8][5]={"SBA","A+BA","A","BDC","C*DC","C","D(S)","Di"};
 char s[200],*p,sentence[40][7],type[40],stack[15]="$S";
 int count=0,i,j,k=0;
 printf("Please write in the string you want to analysis:\n");
 gets(s);
 p=s;
 while((*p)!='\0')  /*while1*/
 {if(((*p)=='+')||((*p)=='*')||((*p)=='(')||((*p)==')'))
  {sentence[count][0]=(*p);
   type[count]=(*p);
   type[count+1]='$';
   type[count+2]='\0';
   sentence[count][1]='\0';
   p++;
   count++;
  }
  else if((*p)>='0'&&(*p)<='9')
  {for(i=0;(*p)>='0'&&(*p)<='9';i++)
   {sentence[count][i]=(*p);
    p++;
   }
   sentence[count][i]='\0';
   type[count]='i';
   type[count+1]='$';
   type[count+2]='\0';
   count++;
  }
  else
  {printf("Fail to analyse!");
   break;
  }
 }  /*endwhile1*/
 sentence[count][0]='$';
 sentence[count][1]='\0';
 count++;
 printf("The process of analysis is below:\n\n");
 printf("Stack\t\t\tInput String\t\tOutput\n\n");
 printf("%s\t\t\t%s$\n",stack,s);
 p=type;
 while((*p)!='\0')
 {if(stack[strlen(stack)-1]=='$')break;
  if(!isterminal(stack[strlen(stack)-1]))
  {for(i=0;i<8;i++)
   {if((product[i][0]==stack[strlen(stack)-1])&&(!(notin((*p),select(i)))))
    {stack[strlen(stack)-1]='\0';
     if(strlen(product[i])>1)
     {for(j=strlen(product[i])-1;j>=1;j--)
      stack[strlen(stack)]=product[i][j];
     }
     printf("%s\t\t\t",stack);
     for(j=k;j<count;j++)printf("%s",sentence[j]);
     printf("\t\t\t");
     print(product[i]);
     printf("\n");
     break;
    }
    else continue;
   }
   if(i>=8)
   {printf("\nError analysis!");
    break;
   }
  }
  else if(isterminal(stack[strlen(stack)-1]))
  {if(stack[strlen(stack)-1]==(*p))
   {stack[strlen(stack)-1]='\0';
    p++;
    printf("%s\t\t\t",stack);
    for(j=k;j<count;j++)printf("%s",sentence[j]);
    printf("\n");
    k++;
   }
   else printf("Error analysis!");
  }
 }
 if(((*p)=='$')&&stack[strlen(stack)-1]=='$')
 printf("Analyse Successfully!");
 getch();
}

阅读(4653) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册