Program to show the implementation of Bottom-Up Parsing

 # include <iostream.h>
 # include   <string.h>
 # include    <conio.h>

 static char Stack[50][10]={NULL};
 static int top=-1;
 static int cit=0;

 // Input Grammar

 static int productions[6]={5,1,7,7,2,10};

 const char Grammar[5][11][10]={
               {\"S\",\"E\"},
               {\"E\",\"E+T\",\"E-T\",\"E*T\",\"E/T\",\"E%T\",\"E^T\",\"T\"},
               {\"T\",\"T+F\",\"T-F\",\"T*F\",\"T/F\",\"T%F\",\"T^F\",\"F\"},
               {\"F\",\"(E)\",\"D\"},
               {\"D\",\"0\",\"1\",\"2\",\"3\",\"4\",\"5\",\"6\",\"7\",\"8\",\"9\"}
             };

 // Input Statement

 const int input_length=8;
 char Input[input_length][5]={\"2\",\"*\",\"(\",\"3\",\"+\",\"4\",\")\",\"$\"};



 //------------------------------  Push( )  ------------------------------//


 void Push(const char* Token)
 {
    top++;

    strcpy(Stack[top],Token);
 }


 //-------------------------------  Pop( )  ------------------------------//


 void Pop( )
 {
    strset(Stack[top],NULL);

    top--;
 }


 //-----------------------------  Reduce( )  -----------------------------//


 void Reduce(const int items,const int index)
 {
    for(int i=0;i<items;i++)
       Pop( );

    Push(Grammar[index][0]);
 }


 //------------------------------  Shift( )  -----------------------------//


 void Shift( )
 {
    Push(Input[cit]);

    cit++;
 }


 //-----------------------  CheckReduceCondition( )  ---------------------//


 const int CheckReduceCondition( )
 {
    int items;
    int index;

    char TopItems[100]={NULL};

    for(int i=0;i<=top;i++)
    {
       strset(TopItems,NULL);

       for(int j=i;j<=top;j++)
      strcat(TopItems,Stack[j]);

       for(j=0;j<productions[0];j++)
       {
      for(int k=1;k<=productions[(j+1)];k++)
      {
         if(strcmp(TopItems,Grammar[j][k])==0)
         {
        items=(top-i+1);
        index=j;

        goto NextCheck;
         }
      }
       }
    }

    return 0;

    NextCheck:

    char CitInput[20]={NULL};

    strcpy(CitInput,Stack[top]);
    strcat(CitInput,Input[cit]);

    for(i=0;i<productions[0];i++)
    {
       for(int j=1;j<=productions[(i+1)];j++)
       {
      if(strstr(Grammar[i][j],CitInput)!=NULL)
         return 0;
       }
    }

    Reduce(items,index);

    return 1;
 }



 /*******************************  main( )  *******************************/



 int main( )
 {
    clrscr( );

    int flag=0;

    cout<<\"    /////*****+++++-----.....  Bottom-Up Parsing  .....-----+++++*****/////\";

    gotoxy(5,3);
    cout<<\"Stack\";

    gotoxy(35,3);
    cout<<\"Input\";

    gotoxy(65,3);
    cout<<\"Next Action\";

    gotoxy(5,5);

    for(int i=0;i<=top;i++)
       cout<<Stack[i];

    gotoxy(35,5);

    for(int j=cit;j<input_length;j++)
       cout<<Input[j];

    gotoxy(65,5);
    cout<<\"Shift\";

    do
    {
       if(!CheckReduceCondition( ))
       {
      Shift( );

      gotoxy(65,(wherey( )+1));
      cout<<\"Shift\";
       }

       else
       {
      gotoxy(65,(wherey( )+1));
      cout<<\"Reduce\";
       }

       gotoxy(5,wherey( ));

       for(int i=0;i<=top;i++)
      cout<<Stack[i];

       gotoxy(35,wherey( ));

       for(int j=cit;j<input_length;j++)
      cout<<Input[j];

       if(top==0 && strcmp(Stack[top],Grammar[0][0])==0 &&
                           strcmp(Input[cit],\"$\")==0)
       {
      flag=1;

      break;
       }

       else if(strcmp(Stack[top],\"$\")==0)
       {
      flag=0;
      break;
       }
    }
    while(1);

    if(flag)
       cout<<\"\\n\\n    Input is Correct...\";

    else
       cout<<\"\\n\\n    Input is Incorrect...\";

    getch( );
    return 0;
 }
[/Code]