Untitled

backing up (this is true for most parsers), and produces a rightmost derivation in reverse: it does a bottom-up parse – not a top-down LL parse or ad-hoc parse.

Program:-
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
char stack[30];
int top=-1;
void push(char c)
{
    top++;
    stack[top]=c;
}
char pop()
{
    char c;
    if(top!=-1)
    {
        c=stack[top];
        top--;
        return c;
    }
    return'x';
}
void printstat()
{
    int i;
    printf("\n\t\t\t $");
    for(i=0;i<=top;i++)
    printf("%c",stack[i]);
}
void main()
{
    int i,j,k,l;
    char s1[20],s2[20],ch1,ch2,ch3;
    clrscr();
    printf("\n\n\t\t LR PARSING");
    printf("\n\t\t ENTER THE EXPRESSION");
    scanf("%s",s1);
    l=strlen(s1);
    j=0;
    printf("\n\t\t $");
    for(i=0;i<l;i++)
    {
        if(s1[i]=='i' && s1[i+1]=='d')
        {
            s1[i]=' ';
            s1[i+1]='E';
            printstat();
            printf("id");
            push('E');
            printstat();
        }
        else if(s1[i]=='+'||s1[i]=='-'||s1[i]=='*' ||s1[i]=='/' ||s1[i]=='d')
        {
            push(s1[i]);
            printstat();
        }
    }
    printstat();
    l=strlen(s2);
    while(l)
    {
        ch1=pop();
        if(ch1=='x')
        {
            printf("\n\t\t\t $");
            break;
        }
        if(ch1=='+'||ch1=='/'||ch1=='*'||ch1=='-')
        {
            ch3=pop();
            if(ch3!='E')
            {
                printf("errror");
                exit(1);
            }
            else
            {
                push('E');
                printstat();
            }
        }
        ch2=ch1;
    }
    getch();
}
Output:

             Write a c program for implementation of a shift reduce parser using stack data structure to accept a given input string of a given grammar
             Description:
             
             Shift Reduce parser attempts for the construction of parse in a similar manner as done in bottom-up parsing i.e. the parse tree is constructed from leaves(bottom) to the root(up). A more general form of the shift-reduce parser is the LR parser. 
             This parser requires some data structures i.e. 
             An input buffer for storing the input string.
             A stack for storing and accessing the production rules.
             
             
             Program:
             
             //Including Libraries
             #include<stdio.h>
             #include<stdlib.h>
             #include<string.h>
              
              //Global Variables
              int z = 0, i = 0, j = 0, c = 0;
               
               // Modify array size to increase 
               // length of string to be parsed
               char a[16], ac[20], stk[15], act[10]; 
                
                // This Function will check whether
                // the stack contain a production rule 
                // which is to be Reduce.
                // Rules can be E->2E2 , E->3E3 , E->4
                void check()
                {
                        // Copying string to be printed as action
                            strcpy(ac,"REDUCE TO E -> ");  
                                 
                                     // c=length of input string
                                         for(z = 0; z < c; z++) 
                                             {
                                                        //checking for producing rule E->4
                                                                if(stk[z] == '4') 
                                                                        {
                                                                                        printf("%s4", ac);
                                                                                                    stk[z] = 'E';
                                                                                                                stk[z + 1] = '\0';
                                                                                                                             
                                                                                                                                         //printing action
                                                                                                                                                     printf("\n$%s\t%s$\t", stk, a); 
                                                                        }
                                             }
                                                      
                                                          for(z = 0; z < c - 2; z++)
                                                              {
                                                                        //checking for another production
                                                                                if(stk[z] == '2' && stk[z + 1] == 'E' && 
                                                                                                                stk[z + 2] == '2') 
                                                                                                                        {
                                                                                                                                        printf("%s2E2", ac);
                                                                                                                                                    stk[z] = 'E';
                                                                                                                                                                stk[z + 1] = '\0';
                                                                                                                                                                            stk[z + 2] = '\0';
                                                                                                                                                                                        printf("\n$%s\t%s$\t", stk, a);
                                                                                                                                                                                                    i = i - 2;
                                                                                                                        }
                                                                                                                                 
                                                              }
                                                                       
                                                                           for(z=0; z<c-2; z++)
                                                                               {
                                                                                        //checking for E->3E3
                                                                                                if(stk[z] == '3' && stk[z + 1] == 'E' && 
                                                                                                stk[z + 2] == '3') 
                                                                                                        {
                                                                                                                        printf("%s3E3", ac);
                                                                                                                                    stk[z]='E';
                                                                                                                                                stk[z + 1]='\0';
                                                                                                                                                            stk[z + 1]='\0';
                                                                                                                                                                        printf("\n$%s\t%s$\t", stk, a);
                                                                                                                                                                                    i = i - 2;
                                                                                                        }
                                                                               }
                                                                                   return ; //return to main
                }
                 
                 //Driver Function
                 int main()
                 {
                        printf("GRAMMAR is -\nE->2E2 \nE->3E3 \nE->4\n");    
                             
                                 // a is input string
                                     strcpy(a,"32423"); 
                                          
                                              // strlen(a) will return the length of a to c
                                                  c=strlen(a); 
                                                       
                                                           // "SHIFT" is copied to act to be printed
                                                               strcpy(act,"SHIFT"); 
                                                                    
                                                                        // This will print Labels (column name)
                                                                            printf("\nstack \t input \t action"); 
                                                                                 
                                                                                     // This will print the initial 
                                                                                         // values of stack and input
                                                                                             printf("\n$\t%s$\t", a); 
                                                                                                  
                                                                                                      // This will Run upto length of input string
                                                                                                          for(i = 0; j < c; i++, j++) 
                                                                                                              {
                                                                                                                        // Printing action
                                                                                                                                printf("%s", act); 
                                                                                                                                         
                                                                                                                                         printf("\n$%s\t%s$\t", stk, a)// Pushing into stack
                                                                                                                                                 stk[i] = a[j];     
                                                                                                                                                         stk[i + 1] = '\0';
                                                                                                                                                                  
                                                                                                                                                                          // Moving the pointer
                                                                                                                                                                                  a[j]=' ';
                                                                                                                                                                                           
                                                                                                                                                                                                   // Printing action
                                                                                                                                                                                                           printf("\n$%s\t%s$\t", stk, a); 
                                                                                                                                                                                                                    
                                                                                                                                                                                                                            // Call check function ..which will 
                                                                                                                                                                                                                                    // check the stack whether its contain
                                                                                                                                                                                                                                            // any production or not
                                                                                                                                                                                                                                                    check(); 
                                                                                                              }
                                                                                                                   
                                                                                                                       // Rechecking last time if contain
                                                                                                                           // any valid production then it will
                                                                                                                               // replace otherwise invalid
                                                                                                                                   check(); 
                                                                                                                                        
                                                                                                                                            // if top of the stack is E(starting symbol)
                                                                                                                                                // then it will accept the input
                                                                                                                                                    if(stk[0] == 'E' && stk[1] == '\0') 
                                                                                                                                                            printf("Accept\n");
                                                                                                                                                                else //else reject
                                                                                                                                                                        printf("Reject\n");
                 }
                 
                                                                                                              }
                 }
                                                                                                        })
                                                                               }
                                                                                                                        }
                                                              }
                                                                        }
                                             }
                }}
            }
        }
        }
    }
        }
        }
    }
}
}
    }
}
}