递归下降语法分析器.txt

用C++实现LR(0)语法分析 用C++实现LR(0)语法分析

＃i nclude "stdio.h"
＃i nclude "malloc.h"
＃i nclude "math.h"

struct Lchar{
 char char_ch;
 struct Lchar *next;
}Lchar,*p,*h,*temp,*top,*base;
struct Lint{
 int int_t;
 struct Lint *next;
}Lint,*itop,*ibase,*itemp;

int table[12][9]={{0,0,-4,0,-5,0,1,2,3},
    {-6,0,0,0,0,100,0,0,0},
    {12,-7,12,12,12,12,0,0,0},
    {14,14,14,14,14,14,0,0,0},
    {0,0,-4,0,-5,0,8,2,3},
    {16,16,16,16,16,16,0,0,0},
    {0,0,-4,0,-5,0,0,9,3},
    {0,0,-4,0,-5,0,0,0,10},
    {-6,0,0,-11,0,0,0,0,0},
    {11,-7,11,11,11,11,0,0,0},
    {13,13,13,13,13,13,0,0,0},
    {15,15,15,15,15,15,0,0,0}};
/*存储LR(0)分析表，大于10为归约，小于0为进栈，0表示出错，1到10表示状态转移，100表示接受*/

char curchar;
char curtocmp;
int curstate;
int right;/*设置开关项，当出错时为0*/
int i,j;

void push(char pchar)/*字符栈入栈函数*/
{
 temp=malloc(sizeof(Lchar));
 temp->char_ch=pchar;
 temp->next=top;
 top=temp;
}

void pop(void)/*字符栈出栈函数*/
{
 if(top->next!=NULL)
  top=top->next;
}

void ipop(void)/*状态栈出栈函数*/
{
 if(itop->next!=NULL)
  itop=itop->next;
}

void ipush(int pint)
{
 itemp=malloc(sizeof(Lint));
 itemp->int_t=pint;
 itemp->next=itop;
 itop=itemp;
}

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 'i':t=4;break;
  case '#':t=5;break;
  case 'E':t=6;break;
  case 'T':t=7;break;
  case 'F':t=8;break;
 }
 return t;
}

void doforpush(int t)
{
 switch(t)
 {
 case 1:push('E');break;
 case 2:push('E');break;
 case 3:push('T');break;
 case 4:push('T');break;
 case 5:push('F');break;
 case 6:push('F');
 }
}

void dosome(void)
{
 int t;
 printf("\nCharStack\tCharLink\tStateStack\n");
 for(;;)
 {
  curchar=h->char_ch;
  curtocmp=top->char_ch;
  curstate=itop->int_t;
  i=changchartoint(curchar);
  t=table[curstate][i];  
  temp=top;
  printf("\n");
  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;
  }
  printf("\t");
  itemp=itop;
  for(;;)/*打印状态栈*/
  {
   printf("%d",itemp->int_t);  
   if(itemp->next==NULL)
    break;
   else
    itemp=itemp->next;
  }
  printf("\t");
  if(t==0)/*LR(0)分析表为0，出错*/
  {
   right=0;
   break;   
  }
  else/*LR(0)分析表不为0*/
  {
   if(t<0)/*LR(0)分析表小于0，入栈*/
   {
    push(curchar);  /*字符入字符栈*/
    ipush(abs(t));  /*状态栈入栈*/
    h=h->next;
   }
   else/*LR(0)分析表大于0，归约*/
   {
    if(t==100)/*LR(0)分析表等于100，正确*/
     break;
    if(t==12||t==14||t==16)/*产生式右部和状态出栈*/
    {
     pop();
     ipop();
    }
    else
    {
     pop();pop();pop();
     ipop();ipop();ipop();
    }                      /*产生式右部和状态出栈*/
    doforpush(t-10);/*产生式左部出栈*/
    j=changchartoint(top->char_ch);
    curstate=itop->int_t;
    ipush(table[curstate][j]);/*状态转移，状态入栈*/
   }
  }
 }
}
void main(void)
{
 char ch;
 base=malloc(sizeof(Lchar));
 base->next=NULL;
 base->char_ch='#';
 top=base;/*初始化字符栈*/
 ibase=malloc(sizeof(Lint));
 ibase->int_t=0;
 ibase->next=NULL;
 itop=ibase;/*初始化状态栈*/
 h=malloc(sizeof(Lchar));
 h->next=NULL;
 p=h;
 do{    /*输入待比较字符串，以'#'结束*/
  ch=getch();
  putch(ch);
  if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#')/*输入合法字符串*/
  {
   temp=malloc(sizeof(Lchar));
   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;
 right=1;/*初始化开关项*/
 dosome();/*开始识别*/
 if(right)
  printf("\nOK!\n");
 else
  printf("\nError!\n");
 getch();
}