#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char A[20];/*分析棧*/
char B[20];/*剩余串*/
char v1[20]={'i','+','*','(',')','#'};/*終結符  */
char v2[20]={'E','G','T','S','F'};/*非終結符   */

int j=0,b=0,top=0,l,m,n;/*l為輸入串長度 */
char ch,x;/*x為當前棧頂字符*/
int k=1,flag=0,finish=0;

typedef struct type/*產生式類型定義      */
{
char origin;/*大寫字符  */
char array[5];/*產生式右邊字符 */
int length;/*字符個數      */
}type;




void print()/*輸出分析棧  */
 {
    int a;                 /*指針*/
    for(a=0;a<=top+1;a++)
        printf("%c",A[a]);
    printf("\t\t");
 }

void print1()/*輸出剩余串*/
{
    int j;
    for(j=0;j<b;j++)
        printf(" ");
    for(j=b;j<=l;j++)
        printf("%c",B[j]);
    printf("\t\t\t");
}


int main(){
    type e,t,g,g1,s,s1,f,f1,cha;/*結構體變量  */
    type C[10][10];/*預測分析表
         */
      /*把文法產生式賦值結構體*/
    e.origin='E';
    strcpy(e.array,"TG");
    e.length=2;/*更改 length 賦值*/
    t.origin='T';
    strcpy(t.array,"FS");
    t.length=2;/*更改 length 賦值*/
    g.origin='G';
    strcpy(g.array,"+TG");
    g.length=3;/*更改 length 賦值*/
    g1.origin='G';
    g1.array[0]='^';
    g1.array[1]='\0';/*更改 字符串結束標志*/
    g1.length=1;/*更改 length 賦值*/
    s.origin='S';
    strcpy(s.array,"*FS");
    s.length=3;/*更改 length 賦值*/
    s1.origin='S';
    s1.array[0]='^';
    s1.array[1]='\0';/*更改 字符串結束標志*/
    s1.length=1;/*更改 length 賦值*/
    f.origin='F';
    strcpy(f.array,"(E)");
    f.length=3;/*更改 length 賦值*/
    f1.origin='F';
    f1.array[0]='i';
    f1.array[1]='\0';/*更改 字符串結束標志*/
    f1.length=1;/*更改 length 賦值*/

    for(m=0;m<=4;m++)/*初始化分析表*/
            for(n=0;n<=5;n++)
                C[m][n].origin='N';/*全部賦為空*/
       /*填充分析表*/
    C[0][0]=e;C[0][3]=e;
    C[1][1]=g;C[1][4]=g1;C[1][5]=g1;
    C[2][0]=t;C[2][3]=t;
    C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;
    C[4][0]=f1;C[4][3]=f;




    printf("可輸入的字符為\'i\',\'+\',\'*\',\'(\',\')\',\'#\'注意：以第一個\'#\'作為字符串結束:\n");
    do/*讀入分析串*/{
        scanf("%c",&ch);
        if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
        {
            printf("Error!輸入串中有非法字符!\n");
            exit(1);
        }
        B[j]=ch;
        j++;
    }while(ch!='#');
    printf("對字符串的分析過程如下：\n");
    l=j;/*分析串長度*/
    ch=B[0];/*當前分析字符*/
    A[top]='#'; A[++top]='E';/*'#','E'進棧*/
    printf("步驟\t\t分析棧\t\t剩余字符\t\t所用產生式 \n");




    /*推導過程如下*/
    do
    {
        x=A[top--];/*x為當前棧頂字符*/
        printf("%d",k++);/*步驟序號*/
        printf("\t\t");
        for(j=0;j<=5;j++)/*判斷是否為終結符*/
            if(x==v1[j])
            {
                flag=1;
                break;
            }
        if(flag==1)/*如果是終結符*/
        {
            if(x=='#')
            {
                if(ch=='#')
                {


                    finish=1;/*結束標記*/
                    print();/*更改 最后成功時對齊*/
                    print1();


                    printf("acc!\n");/*接受 */
                    printf("輸入串符合該文法！\n");
                    getchar();
                    getchar();
                    exit(1);
                }
                else
                {
                    print();
                    print1();
                    printf("Error!\n");
                    printf("當前分析棧中是#，但是剩余串還有字符未匹配。\n");
                    printf("輸入串不符合該文法！\n");
                    getchar();
                    getchar();
                    exit(0);
                }
            }
            if(x==ch)
            {
                print();
                print1();
                printf("%c匹配\n",ch);
                ch=B[++b];/*下一個輸入字符*/
                flag=0;/*恢復標記*/
            }
            else
            {
                if(ch=='#')
                {
                    print();
                    print1();
                    printf("Error!\n");
                    printf("剩余串中是#，但是分析棧還有字符未匹配。\n");
                    printf("輸入串不符合該文法！\n");
                    getchar();
                    getchar();
                    exit(0);
                }
                else
                {
                    print();
                    print1();
                    printf("Error!%c匹配出錯\n",ch);/*輸出出錯終結符*/
                    printf("與當前輸入字符不匹配！\n");
                    printf("輸入串不符合該文法！\n");
                    getchar();
                    getchar();
                    exit(1);
                }
            }
        }
        else/*非終結符處理*/
        {
            for(j=0;j<=4;j++)
                if(x==v2[j])
                {
                    m=j;/*行號*/
                    break;
                }
            for(j=0;j<=5;j++)
                if(ch==v1[j])
                {
                    n=j;/*列號*/
                    break;
                }
            cha=C[m][n];/*記錄應用的產生式*/
            if(cha.origin!='N')
            {
                print();
                print1();
                printf("%c->",cha.origin);
                for(j=0;j<cha.length;j++)
                    printf("%c",cha.array[j]);
                printf("\n");
                for(j=(cha.length-1);j>=0;j--)
                {
                    A[++top]=cha.array[j];
                    if(A[top]=='^')/*為空則不進棧*/
                    top--;
                }
            }
            else
            {
                print();
                print1();
                printf("Error!\n");
                printf("當前棧頂元素是非終結符，但是找不到當前輸入字符相應的產生式！\n");
                printf("輸入串不符合該文法！\n");
                getchar();
                    getchar();
                exit(0);
            }
        }
    }while(true);
    return 0;
}