编译原理-语法分析.cpp

编译原理LR(0) 语法分析器 编译原理LR(0) 语法分析器

#include "stdio.h"
#include "malloc.h"
#include "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=(struct Lchar *)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=(struct Lint *)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\t");
     temp=h;
     for(;;)/*打印待比较的字符*/
	 {
          printf("%c",temp->char_ch);  
          if(temp->char_ch=='#')
               break;
          else
               temp=temp->next;
	 }
     printf("\t\t");
     itemp=itop;
     for(;;)/*打印状态栈*/
	 {
          printf("%d",itemp->int_t);  
          if(itemp->next==NULL)
                break;
          else
                itemp=itemp->next;
	 }
     printf("\t\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;
     printf("请输入一个句子：") ;
     base=(struct Lchar *)malloc(sizeof(Lchar));
     base->next=NULL;
     base->char_ch='#';
     top=base;/*初始化字符栈*/
     ibase=(struct Lint *)malloc(sizeof(Lint));
     ibase->int_t=0;
     ibase->next=NULL;
     itop=ibase;/*初始化状态栈*/
     h=(struct Lchar *)malloc(sizeof(Lchar));
     h->next=NULL;
     p=h;
     do{    /*输入待比较字符串，以'#'结束*/
           ch=getchar();
           putchar(ch);
           if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#')/*输入合法字符串*/
		   {
                  temp=(struct Lchar *)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("\n合法句子\n");
     else
          printf("\n错误句子\n");
     getchar();
	 getchar();
}