#include "stdio.h"
#include "string.h"
#include "stdlib.h"
//----------------------Global Declarition---------------------------------
#define SIZE 20
#define staNumber 12         //有12個狀態
#define Act 6          //有6個非終結符
#define gSIZE 3          //要遇到的非終結符進行轉移
#define proNumber 6         //有6個產生式
#define MAXSIZE 3
//---------------------Finish defining struct-------------------------------------
typedef struct Pro
{
        char head;       //左邊的非終結符
        char gen[4];       //右邊的推到出的表達式 
}Produce;//--------------------------------表達式的基本結構
typedef struct A
{
 int st[Act];       //移近數組
 int re[Act];       //規約 數組
}Action;//----------------------------------動作表數據結構
typedef struct G
{
 char head[gSIZE];      //非終結符E F T
 int gt[gSIZE];       //gSIZE=3,存放跳轉到的狀態
}GOTO;//------------------------------------轉移狀態結構
int status[SIZE];                          //狀態棧數組                                 
int  staMark;           //top of stack of status  狀態棧棧頂
char symbol[SIZE];                          //非終結符的棧
int  symMark;        //Current index of symbol stack
char string[SIZE];                      //存放輸入的字符串數組
int  expMark;                             //index of inputed expression
int  exptop;        //輸入的字符串頂部
int  step;         //在構造分析表的時候，用于標記步驟的
int  IsAccept = 0;       //分析表 accept flag to 0 /字符串被接受標志位置0
Produce gene[proNumber +1];
Action act[staNumber];
GOTO go[staNumber];

void GOTOForm(int sta, char symb);//GOTO表 Symb是非終結符

void Syntax(void)//將6個產生式輸出
{
 
 printf("-------------LR(1) Syntax---------------\n");
 printf("--------------規定的文法-----------------\n");
 printf(" (0)E -> E + T\n (1)E -> T\n (2)T -> T*F\n (3)T -> F\n (4)F -> E\n (5)F -> (i)\n");
 printf("-----------------------------------------\n");
}

void InputString(void)//輸入要分析的字符串
{
     char ch;
     printf("請輸入分析串：");
     printf("[包括:{+ - * /( )i #}以'#'結束]:\n");
     expMark = 0;
  do                                
  {
     scanf("%c",&ch);
     if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='#')&&(ch!='(')&&(ch!=')'))
     {
     printf("輸入的非終結符不符合要求：請按任意鍵跳出!\n");
     getchar();
     exit(0);
     }
     string[expMark++]=ch;
  }while(ch!='#');                       
  printf("---------字符串分析表---------\n");
  getchar();
}

void PrintString(void)//將輸入的字符串輸出
{
     int i = 0;
     printf("You have inputed below:\n");
     for(i = 0; i < expMark; i++)
     printf("%c",string[i]);
  printf("\n");
}

void PrintStatus(void)//將狀態棧輸出
{
 int i = 0;
 for(i = 0; i <= staMark; i++)//
 {
  printf("%d", status[i]);
 }
 printf("\t\t");
}

void PrintRestExp(void)//輸出其他的非終結符
{
 int i = 0;
 for(i = 0; i < exptop; i++)
  printf(" ");
 for(i = exptop; i <= expMark; i++)
 {
  printf("%c", string[i]);
 }
 printf("\t\t");
}

void Format()
{
 printf("步驟 \t 狀態棧 \t符號棧   \t 剩余輸入串 \t 動作\n");
}



void Initlize(void)//將LR(1)的分析表建立出來
{
//將產生式放入數組行用到了數據結構中的引用
 gene[1].head = 'E';
 strcpy(gene[1].gen,"E+T");//Generate gene[geSIZE +1];
                           //Action act[sSIZE];
                           //GOTO go[sSIZE];
 gene[2].head = 'E';
 strcpy(gene[2].gen,"T");
 
 gene[3].head = 'T';
 strcpy(gene[3].gen,"T*F");
 
 gene[4].head = 'T';
 strcpy(gene[4].gen,"F");
 
 gene[5].head = 'F';
 strcpy(gene[5].gen,"(E)");
 
 gene[6].head = 'F';
 strcpy(gene[6].gen,"i");
 //-----------------------------------完成產生式的存儲
 //----------------------------------- 產生式的動作表
 act[0].st[0] = 5;
 act[0].st[3] = 4;
 
 act[1].st[1] = 6;
// act[1].st[5] = 10;
 act[2].re[1] = 2;
 act[2].st[2] = 7;
 act[2].re[4] = 2;
 act[2].re[5] = 2;
 
 act[3].re[1] = 4;
 act[3].re[2] = 4;
 act[3].re[4] = 4;
 act[3].re[5] = 4;
 
 act[4].st[1] = 5;
 act[4].st[3] = 4;
 
 act[5].re[1] = 6;
 act[5].re[2] = 6;
 act[5].re[4] = 6;
 act[5].re[5] = 6;
 
 act[6].st[0] = 5;
 act[6].st[3] = 4;
 
 act[7].st[0] = 5;
 act[7].st[3] = 4;
 
 act[8].re[1] = 6;
 act[8].re[4] = 11;
 
 act[9].re[1] = 1;
 act[9].re[2] = 7;
 act[9].re[4] = 1;
 act[9].re[5] = 1;
 
 act[10].re[1] = 3;
 act[10].re[2] = 3;
 act[10].re[4] = 3;
 act[10].re[5] = 3;
 
 act[11].re[1] = 5;
 act[11].re[2] = 5;
 act[11].re[4] = 5;
 act[11].re[5] = 5;
 //-----------------------------------完成分析動作表
 //-----------------------------------分析表的GOTO狀態
 go[0].head[0] = 'E';
 go[0].head[1] = 'T';
 go[0].head[2] = 'F';
 go[0].gt[0] = 1;
 go[0].gt[1] = 2;
 go[0].gt[2] = 3;
 
 go[4].head[0] = 'E';
 go[4].head[1] = 'T';
 go[4].head[2] = 'F';
 go[4].gt[0] = 8;//go[]shi 狀態，gt[]是存放非終結符的，這個是代表4狀態遇到分析表中的第一個非終結符轉移到8狀態
 go[4].gt[1] = 2;
 go[4].gt[2] = 3;
 
 go[6].head[1] = 'T';
 go[6].head[2] = 'F';
 go[6].gt[1] = 9;
 go[6].gt[2] = 3;
 
 go[7].head[2] = 'F';
 go[7].gt[2] = 10;
 //完成 Goto表
 //Initlize global vari
 staMark = 0;                       
 status[staMark] = 0;                
 step = 1;
 symMark = 0;
 symbol[symMark] = '#';
 IsAccept = 0;
 exptop = 0;
}

void Reduce(int sta, char symb,int col)//規約動作
{
unsigned int i = 0;
 for(i = 0; i < strlen(gene[act[sta].re[col]].gen); i++)//進行規約的時候從狀態棧和符號棧去掉R個符號，即指針要減R
 {
  symbol[symMark--] = '\0';//符號棧自頂向下去掉strlen(gene[act[sta].re[col]].gen個符號
 }
 symbol[++symMark] = gene[act[sta].re[col]].head;//把產生式的左部給symbol[++symMark]進行規約
 for(i = 0; i < strlen(gene[act[sta].re[col]].gen) ; i++)
 {
  status[staMark - i] = '\0';//符號棧自頂向下去掉strlen(gene[act[sta].re[col]].gen個狀態
 }
 staMark -= i; 
 GOTOForm(status[staMark], symbol[symMark]);//狀態遇到（symbol[symMark]）非終結符進行轉移
}



void ActionTable(int sta, char symb,int col)//動作表int col是
{
 if(sta == 1 && col == 5)//狀態1遇到第6個終結符接受
 {
  printf("accept\n");
  IsAccept = 1;
  return;
 }
 if(act[sta].st[col] != 0)
 {
  printf(" S \n");
  status[++staMark] = act[sta].st[col];//狀態進入狀態棧，staMark相當于狀態棧的指針
  symbol[++symMark] = symb;//符號進入符號棧，symMark相當于非終結符的指針
  exptop ++;
 }
 else if(act[sta].re[col] != 0)//進行規約處理
 {
  printf("  R  \n");
  Reduce(sta, symb, col);//規約是將規約成的非終結符放入符號棧，狀態棧和符號棧先去掉字符在入棧
 }
 else
 {
  printf("error\n");//出錯原因是某個狀態后有固定的后跟非終結符。
  getchar();
  exit(1);
 }
  
}



void GOTOForm(int sta, char symb)//GOTO表 狀態轉換表
{
 int i = 0;
 for(i = 0; i < staNumber; i++)
 {
   if(go[sta].head[i] == symb)
  {
   //printf("Head %d\n",go[sta].gt[i]);
   status[++staMark] = go[sta].gt[i];
   return;
  }
 }
}


void Launch(void)
{
 int s = status[staMark];
 char exp = string[exptop];//棧頂元素
 char sym = symbol[symMark];//符號
 while(IsAccept != 1)//沒有被接受的時候發生的事情，即移近，規約，接受，報錯
 {
  s = status[staMark];
  exp = string[exptop];//棧頂元素
  sym = symbol[symMark];
  printf("%d\t ",step++);
  PrintStatus();//輸出狀態棧
  printf(" %s\t\t", symbol);//輸出符號棧的內容
  PrintRestExp();
  switch(exp)
  {
   case 'i':
    ActionTable(s, exp, 0); 
    break;
   case '+':
    ActionTable(s, exp, 1);
    break;
   case '*':
    ActionTable(s, exp, 2);
    break;
   case '(':
    ActionTable(s, exp, 3);
    break;
   case ')':
    ActionTable(s, exp, 4);
    break;
   case '#':
    ActionTable(s, exp, 5);
    break;
  }
 }
}


int main()
{
  Syntax();
  InputString();//輸入字符串
  //PrintExpression();
  Initlize();//建立LR（1）的分析表
  Format();//輸出對串分析的時候的常用符號
  Launch();//對表進行分析
  getchar();
  return 1;
}