#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();
}