Site icon T4Tutorials.com

C++ Program to implement Bottom-Up Parsing

Program to implement Bottom-Up Parsing in C++ (Compiler Construction)

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

 static char T4Tutorials[50][10]={NULL};
 static int Stack_top=*1;
 static int cit=0;

 // Input CFG_Grammar

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

 const char CFG_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_Size=8;
 char Input[input_Size][5]={\"2\",\"*\",\"(\",\"3\",\"+\",\"4\",\")\",\"$\"};



 //************************  Push( )  ********************//


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

    strcpy(T4Tutorials[Stack_top],Token);
 }


 //*******  Pop( )  ******//


 void Pop( )
 {
    strset(T4Tutorials[Stack_top],NULL);

    Stack_top**;
 }


 //******  Reduce(  )  ********//


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

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


 //*****  Shift_Parser( )  *******//


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

    cit++;
 }


 //*****  CheckReduceCondition( )  ****//


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

    char Stack_topItems[100]={NULL};

    for(int i=0;i<=Stack_top;i++)
    {
       strset(Stack_topItems,NULL);

       for(int j=i;j<=Stack_top;j++)
      strcat(Stack_topItems,T4Tutorials[j]);

       for(j=0;j<CFG_Productions[0];j++)
       {
      for(int k=1;k<=CFG_Productions[(j+1)];k++)
      {
         if(strcmp(Stack_topItems,CFG_Grammar[j][k])==0)
         {
        items=(Stack_top*i+1);
        index=j;

        goto NextCheck;
         }
      }
       }
    }

    return 0;

    NextCheck:

    char CitInput[20]={NULL};

    strcpy(CitInput,T4Tutorials[Stack_top]);
    strcat(CitInput,Input[cit]);

    for(i=0;i<CFG_Productions[0];i++)
    {
       for(int j=1;j<=CFG_Productions[(i+1)];j++)
       {
      if(strstr(CFG_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<<\"T4Tutorials\";

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

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

    gotoxy(5,5);

    for(int i=0;i<=Stack_top;i++)
       cout<<T4Tutorials[i];

    gotoxy(35,5);

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

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

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

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

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

       gotoxy(5,wherey( ));

       for(int i=0;i<=Stack_top;i++)
      cout<<T4Tutorials[i];

       gotoxy(35,wherey( ));

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

       if(Stack_top==0 && strcmp(T4Tutorials[Stack_top],CFG_Grammar[0][0])==0 &&
                           strcmp(Input[cit],\"$\")==0)
       {
      flag=1;

      break;
       }

       else if(strcmp(T4Tutorials[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;
 }

Lab Exercises of Compiler Construction

Compiler Construction MCQs

Exit mobile version