suanfuyouxian.cpp

采用算法优先分析对表达式进行分析

/* 实验题目： 对下列文法    */
/*    E->E+T|E-T|T   */
/*    T->T*F|T/F|F   */
/*    F->(E)|i    */

/*  0=+ 1=- 2=* 3=/ 4=( 5=) 6=i 7=# */
/*          */
/*   算符优先关系表    */
/* -------------------------------- */
/*     +   -   *   /   (   )   i   #  */
/* +   >   >   <   <   <   >   <   >  */
/* -   >   >   <   <   <   >   <   >  */
/* *   >   >   >   >   <   >   <   >  */
/* /   >   >   >   >   <   >   <   >  */
/* (   <   <   <   <   <   =   <   ?  */
/* )   >   >   >   >   ?   >   ?   >  */
/* i   >   >   >   >   ?   >   ?   >   */
/* #   <   <   <   <   <   ?   <   =  */
/* -------------------------------- */



#include "stdio.h"   
#include "malloc.h"   
struct Lchar 
{  
  char char_ch;  
  struct Lchar *next; 
}LLchar,*p,*h,*temp,*top,*base; 
int table[8][8]={{1,1,-1,-1,-1,1,-1,1},   
    {1,1,-1,-1,-1,1,-1,1},   
    {1,1,1,1,-1,1,-1,1},   
    {1,1,1,1,-1,1,-1,1},   
    {-1,-1,-1,-1,-1,-1,-1,0},   
    {1,1,1,1,0,1,0,1},   
    {1,1,1,1,0,1,0,1},   
    {-1,-1,-1,-1,-1,0,-1,-1}};   
//存储算符优先关系表，大于为1，小于或等于为-1，其它为0表示出  
char curchar;   
char curcmp;   
int right;    /*设置开关项，当出错时为0*/   
int i,j;   
int k;        /*比较字符在栈的位置*/   
void push(char pchar)   /*入栈函数*/   
{   
 temp=(Lchar*)malloc(sizeof(LLchar));   
 temp->char_ch=pchar;   
 temp->next=top;   
 top=temp;   
}   
void pop()  /*出栈函数*/   
{   
 if(top->char_ch!='#')   
  top=top->next;   
}   
int changchartoint(char ch)  /*将字符转为数字，以得到算符优先值*/   
{   
 int t;   
 switch(ch)   
 {   
  case '+':t=0;break;   
  case '-':t=1;break;   
  case '*':t=2;break;   
  case '/':t=3;break;   
  case '(':t=4;break;   
  case ')':t=5;break;   
  case 'i':t=6;break;   
  case '#':t=7;   
 }   
 return t;   
}   
void dosome()   
{   
 k=1;   
 for(;;)   
 {   
  curchar=h->char_ch;   
  temp=top;   
  for(;;)   
  {   
   if(temp->char_ch=='N')   
   {   
    temp=temp->next;   
    k++;   
   }   
   else   
   {   
    curcmp=temp->char_ch;   
    break;   
   }   
  }   
  printf("\n%d\t%d\t",table[i][j],k);   
  temp=top;   
  for(;;)    /*打印栈*/   
  {   
   printf("%c",temp->char_ch);   
   if(temp->char_ch=='#')   
    break;   
   else   
    temp=temp->next;   
  }   
  printf("\t");   
  temp=h;   
  for(;;)    /*打印待比较的字符*/   
  {   
   printf("%c",temp->char_ch);   
      
   if(temp->char_ch=='#')   
    break;   
   else   
    temp=temp->next;   
  }   
  i=changchartoint(curcmp);   
  j=changchartoint(curchar);   
  if(table[i][j]==0)  /*算符优先值为空*/   
  {   
   printf("\n%d\t%d\t%c\t%cterror1",table[i][j],k,curcmp,curchar);   
   right=0;   
   break;   
  }   
  else                 /*算符优先值不为空*/   
  {   
   if(table[i][j]<0)   /*算符优先值为-1，移进*/   
   {   
    if(curchar=='#')   /*待比较字符为空*/   
    {   if(k==2)          /*当前比较字符在栈的位置为两个元素*/   
      break;   
     else   
     {   
      printf("\n%d\t%d\t%c\t%c\terror2",table[i][j],k,curcmp,curchar); 
      right=0;   
      break;   
     }   
    }   
    push(curchar);   
    k=1;   
    curcmp=curchar;   
    h=h->next;   
   }   
   else              /*算符优先值为1，归约*/   
   {   
    if(curcmp=='i')  /*当前比较为i,出栈一次*/   
     pop();   
    else             /*当前比较不为i,出栈三次*/   
    {   
     pop();   
     pop();   
     pop();   
    }   
    push('N');       /*归约到N*/   
    k=1;   
   }   
  }   
 }   
}   
void main()   
{   
 char ch;   
 right=1;   
 base=(Lchar*)malloc(sizeof(LLchar));   
 base->next=NULL;   
 base->char_ch='#';   //栈底压入#
 top=base;            //初态栈底和栈顶相同
 h=(Lchar*)malloc(sizeof(LLchar));   
 h->next=NULL;   
 p=h;   
 do{                 //输入待比较字符串，以’#’结束   
  ch=getchar();   
  putchar(ch);   
  if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')   
  {   
   temp=(Lchar*)malloc(sizeof(LLchar));   
   temp->next=NULL;   
   temp->char_ch=ch;   
   h->next=temp;   
   h=h->next;   
  }   
  else   
  {   
   temp=p->next;   
   printf("\nInput a wrong char!Input again:\n"); 
//   for(;;)   
 //  {       
    if (temp!=NULL)   
     printf("%c",temp->char_ch);         
//    else   
//     break;   
//    temp=temp->next;   
//   }   
  }   
 }while(ch!='#');      /*输入待比较字符串，以’#’结束*/   
 p=p->next;   
 h=p;   
 dosome();             /*开始识别*/   
 if(right)   
  printf("\nOK!\n");   
 else   
  printf("\nError!\n");   
// getchar();   
}