#include "stdio.h"
#include "malloc.h"
struct Lchar{
 char char_ch;
 struct Lchar *next;
}Lchar,*p,*h,*temp,*top,*base;
char curchar;
char curtocmp;
int right;
int table[5][8]={{1,0,0,0,0,1,0,0},
    {0,1,1,0,0,0,1,1},
    {1,0,0,0,0,1,0,0},
    {0,1,1,1,1,0,1,1},
    {1,0,0,0,0,1,0,0}};
int i,j;

void push(char pchar)
{
 temp=malloc(sizeof(Lchar));
 temp->char_ch=pchar;
 temp->next=top;
 top=temp;
}

void pop(void)
{
 curtocmp=top->char_ch;
 if(top->char_ch!='#')
  top=top->next;
}

void doforpush(int t)
{
 switch(t)
 {
  case 0:push('A');push('T');break;
  case 5:push('A');push('T');break;
  case 11:push('A');push('T');push('+');break;
  case 12:push('A');push('T');push('-');break;
  case 20:push('B');push('F');break;
  case 25:push('B');push('F');break;
  case 33:push('B');push('F');push('*');break;
  case 34:push('B');push('F');push('/');break;
  case 40:push('i');break;
  case 45:push(')');push('E');push('(');
 }
}

void changchartoint()
{
 switch(curtocmp)
 {
  case 'A':i=1;break;
  case 'B':i=3;break;
  case 'E':i=0;break;
  case 'T':i=2;break;
  case 'F':i=4;
 }
 switch(curchar)
 {
  case 'i':j=0;break;
  case '+':j=1;break;
  case '-':j=2;break;
  case '*':j=3;break;
  case '/':j=4;break;
  case '(':j=5;break;
  case ')':j=6;break;
  case '#':j=7;
 }
}

void dosome(void)
{
 int t;
 for(;;)
 {
  pop();
  curchar=h->char_ch;
  printf("\n%c\t%c\n",curchar,curtocmp);  
  if(curtocmp=='#' && curchar=='#')
   break;
  if(curtocmp=='A'||curtocmp=='B'||curtocmp=='E'||curtocmp=='T'||curtocmp=='F')
  {
   if(curtocmp!='#')
   {
    changchartoint();
    if(table[i][j])
    {
     t=10*i+j;
     doforpush(t);
     continue;
    }
    else
    {
     right=0;
     break;
    }
   }
   else
    if(curtocmp!=curchar)
    {
     right=0;
     break;
    }
    else
     break;
  }
  else
   if(curtocmp!=curchar)
   {
    right=0;
    break;
   }
   else
   {
    h=h->next;
    continue;
   }
 }
}

void main(void)
{
 char ch;
 right=1;
 base=malloc(sizeof(Lchar));
 base->next=NULL;
 base->char_ch='#';
 temp=malloc(sizeof(Lchar));
 temp->next=base;
 temp->char_ch='E';
 top=temp;
 h=malloc(sizeof(Lchar));
 h->next=NULL;
 p=h;
 do{
  ch=getch();
  putch(ch);
  if(ch=='i'||ch=='+'||ch=='-'||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;
 dosome();
 if(right)
  printf("\nOK!\n");
 else
  printf("\nError!\n");
 getch();
}
/*LL(1)文法分析程序 
/************************************/
/* 程序名稱： LL(1)文法分析程序 */
/* 程序用途： 編譯原理實(shí)驗(yàn)(三) */
/* 編寫日期： 2005年11月9日  */
/* 實(shí)驗(yàn)題目： 識別下列表達(dá)式  */
/*    E->E+T|E-T|T  */
/*    T->T*F|T/F|F  */
/*    F->(E)|i   */
/* 程序版本： 1.0 Final   */
/* 程序作者： 黃記瑤 B0226047  */
/* 作者郵箱： hjy2920@163.com  */
/************************************/

/********************************************/
/*     程序相關(guān)說明              */
/*   A=E'  B=T'    */
/*  0=E 1=E' 2=T 3=T' 4=F  */
/* 0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=# */
/************************************/