yufa.cpp

语法分析器

#include<iostream.h>

#include <string.h>

#include <stdlib.h>

#define stack_size 20
#define stackincrement 10

char Vn[3]={'S','A','B'};
char Vt[4]={'a','b','c','#'};

typedef struct {
    char *bottom;
    char *top;
    int size;
}stack;

int Initstack(stack &s)        //初始化栈
{
   s.bottom=(char *)malloc(stack_size*sizeof(char));
   if(!s.bottom) exit(-1);
   s.top=s.bottom;
   s.size=stack_size;
   return(1);
}

int push(stack &s,char e)      //入栈
{
   if(s.top-s.bottom>=s.size){
      s.bottom=(char *)realloc(s.bottom,(stack_size+stackincrement)*sizeof(char));
      if(!s.bottom) exit(-1);
      s.top=s.bottom+s.size;
      s.size+=stackincrement;
   }
   *s.top++=e;
   return(1);
}

int pop(stack &s,char *e)       //出栈
{
   if(s.top==s.bottom) return(0);
   *e=*--s.top;
   return(1);
}

int is_Vt(char Vt[],int n,char a)     //LL分析分法X=Vt的处理情形
{
   int i;
   for(i=0; i<n; i++)
     if(a==Vt[i]) 
        break;
   if(i==n&&a!=Vt[n-1]) return(0);
   else return(1);
}

int is_Vn(char Vn[],int n,char a)    //LL分析分法X=Vn的处理情形
{
   int i;
   for(i=0; i<n; i++)
     if(a==Vn[i]) 
        break;
   if(i==n&&a!=Vn[n-1]) return(0);
   else return(1);
}

void main()
{  
   char x,ch;
   int i=0,index=0;
   char st[20];
   stack s;
   cout<<"LL 语法分析分法----自顶向下分析："<<endl;
   cout<<"文法G[s]：S->aBc|bAB,A->aAb|b,B->b|λ "<<endl;
   cout<<endl;
   cout<<"\t 输入要分析的字符串(length<20,end by '#'):"<<endl;
   cin>>st[0];
   while(st[i]!='#'){
     i++;
     cin>>st[i];
   }  
   Initstack(s);
   push(s,'#');
   push(s,'S');
   ch=st[index];
   index++;
   while(1){
       pop(s,&x);
       if(is_Vn(Vn,3,x)){
          if(x=='S'&&ch=='a'){
             push(s,'c'); push(s,'B'); push(s,'a');    
          }
          if(x=='S'&&ch=='b'){
             push(s,'B'); push(s,'A'); push(s,'b');    
          }
          if(x=='A'&&ch=='a'){
             push(s,'b'); push(s,'A'); push(s,'a');    
          }
          if(x=='A'&&ch=='b'){
             push(s,'b');   
          }
          if(x=='B'&&ch=='b'){
             push(s,'b');
          }
          if(x=='B'&&ch=='c'){
             push(s,'$');  
          }
          if(x=='B'&&ch=='#'){
             push(s,'$');  
          }
       }
       if(is_Vt(Vt,4,x)){
          if(x==ch){
            if(x!='#'){
                ch=st[index];
               index++;
            }
            else{  
                for(int j=0; j<i; j++)
                cout<<st[j];
                cout<<"是G[s]文法的句子！"<<endl;
                break; 
              }
          }
          else{
              for(int j=0; j<i; j++)
               cout<<st[j];
               cout<<"不是G[s]文法的句子！"<<endl;
               break; 
          } 
        }    
      if(x=='$')  continue; 
   }
}