Implementation of SLR Parser

/* Implementation of SLR Parser */

#include<stdio.h>

#include<ctype.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include<iostream.h>

#define epsilon '^'

char prod[20][20],T[20],NT[20],c[10][10],foll[10][10],fir[10][10];

int tt,tnt,tp,a;

int follow[20][20],first[20][20];

void first_of(char);

int count(int j);

void rhs(int j);

void read_tnt();

int rhs(int j);

void read_tnt()

{       cout<<"For SLR parser: ";

        cout<<"\nEnter number of terminals: ";

        cin>>tt;

        cout<<"\nEnter terminals: ";

        for(int i=0;i<tt;i++)

        T[i]=getche();

        getch();

        cout<<"\nEnter number of Non-terminals: ";

        cin>>tnt;

        cout<<"\nEnter Non-terminals: ";

        for(i=0;i<tnt;i++)

               NT[i]=getche();

        getch();      }
Also Read : C program to implement lexical analyzer

void read_prod()

{       int j;

        char x=0;

        cout<<"\n\nEnter number of productions: ";

        cin>>tp;

        cout<<"\n Enter productions: ";

        for(int i=0;i<tp;i++)

        {       j=x=0;

               while(x!='\r')

               {       prod[i][j]=x=getche();

                       j++;    }

               cout<<"\n";             }

        getch();                                      }

  return(i);

if(t=='$')

  return(tt);

return(-1);            }

int terminal(char x)

{       for(int i=0;i<tt;i++)

        if(T[i]==x)

               return(1);

        return(0);             }

int nonterminal(char x)

{       for(int i=0;i<tnt;i++)

        if(NT[i]==x)

               return(1);

        return(0);             }

int in_rhs(char *s,char x)

{       for(int i=0;i<=strlen(s);i++)

               if(*(s+i)==x)

                       return(i);

               return(-1);                    }

void find_first()

{       for(int i=0;i<tnt;i++)

        first_of(NT[i]);               }

void first_of(char n)

{       int t1,t2,p1,cnt=0,i,j;

        char x;

        static int over[20];

        p1=t_no(epsilon);

        if(terminal(n))

                return;

        t1=nt_no(n);

        if(over[t1])

               return;

        over[t1]=1;

        for(i=0;i<tp;i++)

        {       t1=nt_no(prod[i][0]);

               if(prod[i][0]==n)

               {       int k=0;

                       cnt=count(1);

                       rhs(i);

                       while(k<cnt)

                       {       x=c[i][k];

                               if(terminal(x))

                               {       t2=t_no(x);

                                       first[t1][t2]=1;

                                       break;                 }

                               else

                               {       t2=nt_no(x);

                                       first_of(x);

                                       for(int j=0;j<tt;j++)

         first[t1][p1]=1;      }   }   }

void follow_of(char n)

{       int f,t1,t2,p1,t,cnt=0;

        char x,beta;

        static int over[20];

        p1=t_no(epsilon);

        t1=nt_no(n);

        if(over[t1])

               return;

        over[t1]=1;

        if(NT[0]==n)

        follow[nt_no(NT[0])][tt]=1;

        for(int i=0;i<tp;i++)

        {       rhs(i);

               cnt=count(i);

               t=in_rhs(c[i],n);

                       int bno;

                       for(int j=0;j<tt;j++)

                       {

                               bno=nt_no(beta);

                               if((first[bno][j]) && (j!=p1))

                                       follow[t1][j]=1;       }

                               if((p1!=-1) && (first[bno][p1]==1))

                                       continue;

                               else if((t==(cnt-1)||(k>=cnt)))

                               {       follow_of(prod[i][0]);

                                      t1=nt_no(prod[i][0]);

                                      for(int l=0;l<=tt+1;l++)

                                      if(follow[t][l])

                                       follow[t1][l]=1;       }       }       }       }

                                      int count(int j)

                                      {  int c1=0;

                                         for(int q=3;prod[j][q]!='\r';q++)

                                         c1++;

                                         return(c1);         }

void show_follow()

{       int b=0;

        a=0;

        cout<<"\n\n Follow Table For Grammar: \n";

        for(int i=0;i<tnt;i++)

        {

               b=0;

               cout<<"\n FOLLOW ("<<NT[i]<<" )= { ";

               for(int j=0;j<tt+1;j++)

               if(follow[i][j] && j!=tt)

               {       foll[a][b]=T[j];

                       b++;

                       cout<<T[j]<<" ";       }

               else

                       if(j==tt)

                       {       foll[a][b]='$';

                               b++;

                               cout<<'$';     }

                       a++;

                       cout<<" } ";           }

                       getch();               }

                       void show_first()

                       {       int b=0;

                               a=0;

                               cout<<"\n\n First Table For Grammar: \n";

                               for(int i=0;i<tnt;i++)

                               {       b=0;

                                      cout<<"\n FIRST ("<<NT[i]<<" )= { ";

                                      for(int j=0;j<tt+1;j++)

                                      if(first[i][j] && j!=tt)

                                      {       fir[a][b]=T[j];

                                              b++;

                                              cout<<T[j]<<" ";       }

                                      a++;

                                      cout<<" } ";           }

                                      getch()}}}}

To construct parse table:

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<ctype.h>

#include<stdlib.h>

#include<iostream.h>

#include"c:\tc\bin\SLR.h"

int S=0,i=0,j=0,state[20];

char TNT[15];

struct node

{       int pno,dpos;  };

struct t

{       char s;

        int n;         };

struct t1

{       struct t lr[10];

        int gr[5];     };

struct t1 action[15];

struct node closure[10][10];

int g[15][10];

int l;

void sclosure(int,int);

int added(int);

int t_into(char);

void print_table(int);

void parser(void);

void find_closure(int,int);

void SLR(void);

void main()

{       clrscr();

        mainf();

        getch();

        for(int i=0;i<tnt;i++)

               TNT[i]=NT[i];

        for(int j=0;j<tt;j++)

        {       TNT[i]=T[j];

               i++;    }

        strcat(T,"$");

        i=j=0;

        SLR();

        print_table(S);

        getch();       }

void SLR()

{       int clno,no=0,x,y,z,len,cnt=-1,d=0;

        closure[i][j].pno=0;

        closure[i][j++].dpos=3;

        find_closure(no,3);

        sclosure(i,j);

        state[i]=j;

        S=0;

        do

        {       cnt++;

               z=state[cnt];

               for(int k=0;k<tnt+tt;k++)

               {       i++;

                       j=0;d=0;

                       for(int l=0;l<z;l++)

                       {       x=closure[cnt][1].pno;

                               y=closure[cnt][1].dpos;

                               if(prod[x][y]==TNT[k])

    {    d=1;

         closure[i][j].pno=x;

         closure[i][j++].dpos=++y;

         if((y<strlen(prod[x])) && (isupper(prod[x][y])))

           find_closure(x,y);          }       }

   if(d==0)

   {    i--;

        continue;      }

   sclosure(i,j);

   else

   {    action[cnt].lr[k-tnt].s='S';

        action[cnt].lr[k-tnt].n=clno;

   }

   if(added(i-1)!=-1)

    i--;

   else

   {    S++;

        for(l=0;l<state[i];l++)

        {       if(closure[i][1].pno==0)

                {       action[i].lr[tt].s='A';

                       continue;      }

                       len=(strlen(prod[closure[i][l].pno])-1);

                       if(len==closure[i][l].dpos)

                       {       char v=prod[closure[i][l].pno][0];

                               int u=nt_no(v);

                               for(x=0;x<strlen(foll[u]);x++)

                               { int w=t_ino(foll[u][x]);

                                 action[i].lr[w].s='R';

                                 action[i].lr[w].n=closure[i][l].pno;}}}}}}

                                 while(cnt!=S);       }

Also Read:

void print_table(int states)

{       int lin=5;

        cout<<"\n\n Parser Table: \n";

        for(int i=0;i<tt;i++)

               cout<<"\t"<<T[i];

               cout<<"\t$";

        for(i=0;i<tnt;i++)

        cout<<"\t"<<NT[i];

  cout<<"\n______________________________________________________________\n";

  for(i=0;i<=states;i++)

  {     gotoxy(l,lin);

        cout<<"I"<<i<<"\t";

        for(int j=0;j<=tt;j++)

        {       if(action[i].lr[j].s!='\x0')

               {       if(action[i].lr[j].s=='A')

                       {       cout<<"Acc";

                               continue;      }

    else

         cout<<"\t";   }

   for(j=0;j<tnt;j++)

    if(action[i].gr[j])

    {    cout<<action[i].gr[j];

         cout<<"\t";   }

    else

         cout<<"\t";

    lin++;

    cout<<"\n";        }

   cout<<"\n______________________________________________________";        }

void sclosure(int clno,int prodno)

{ struct node temp;

  for(int i=0;i<prodno-1;i++)

  { for(int j=i+1;j<prodno;j++)

   {  if(closure[clno][i].pno>closure[clno][j].pno)

    {    temp=closure[clno][i];

         closure[clno][i]=closure[clno][j];

         closure[clno][j]=temp;        }}}

  for(i=0;i<prodno-1;i++)

  {for(j=i+1;j<prodno;j++)

   {if((closure[clno][i].dpos>closure[clno][j].dpos) &&

           (closure[clno][i].pno==closure[clno][j].pno))

    {    temp=closure[clno][i];

         closure[clno][i]=closure[clno][j];

         closure[clno][j]=temp;}}}}

int added(int n)

{ int d=1;

  for(int k=0;k<=n;k++)

  {if(state[k]==state[n+1])

   { d=0;

return(k);     }       }

  return(-1);      }

void find_closure(int no,int dp)

{ int k;

  char temp[5];

  if(isupper(prod[no][dp]))

  {for(k=0;k<tp;k++)

   {if(prod[k][0]==prod[no][dp])

    {    int t_ino(char t)

{  for(int i=0;i<=tt;i++)

   if(T[i]==t)

    return(i);

  return(-1);          }

char pops2;

struct node1

{       char s2;int s1;        };

struct node1 stack[10];

int pops1,top=0;

void parser(void)

{ int r,c;

  struct t lr[10];

  char t,acc='f',str[10];

  cout<<"Enter I/p String To Parse: ";

  cin>>str;

  strcat(str,"$");

  stack[0].s1=0;

  stack[0].s2='\n';

  cout<<"\n\n STACK";

  cout<<"\t\t INPUT";

  cout<<"\t\t ACTION";

  for(int j=0;j<strlen(str);j++)

   cout<<str[j];

  do

  {r=stack[top].s1;

   c=find_index(str[i]);

   if(c==-1)

    cout<<"\n Error! Invalid String!";

   return;     }

  while(top!=0);

  switch(action[r],lr[c].s)

  {case 'S':   {  push(str[i],action[r].lr[c].n);

                  i++;

                  cout<<"\t\t\t Shift";

                  break;      }

  case 'R':    { t=prod[action[r].lr[c].n][3];

                 do    {       pop();  }

                 while(pops2!=t);

                 t=prod[action[r].lr[c].n][0];

                 r=stack[top].s1;

                 c=find_index(t);

                 push(t,action[r].gr[c-tt-1]);

                 cout<<"\t\t\t Reduce";

                 break;}

  case 'A':{     cout<<"\t\t\t Accept";

                 cout<<"\n\n\n String accepted";

                 acc='t';

                 getch();

                 return;      }

  default: {     cout<<"\n\n\n Error! String not accepted!";

                 getch();

                 exit(0);}}

for(j=0;j<=top;j++)

  cout<<stack[j].s2<<stack[j].s1;

if(top<4)

  cout<<"\t\t\t";

else

  cout<<"\t\t";

for(j=i;j<strlen(str);j++)

  cout<<str[j];

if(acc=='t')

  return;      }

int find_index(char temp)

{for(int i=0;i<=tt+tnt;i++)

 {if(i<=tt)

  { if(T[i]==temp)

    return(i);}

    else

   if(NT[i-tt-1]==temp)

    return(i); }

return(-1);    }

void push(char t2,int t1)

{++top;

stack[top].s1=t1;

stack[top].s2=t2;

return;        }

void pop(void)

{pops1=stack[top].s1;

pops2=stack[top].s2;

--top; getch(); }

 Download its output and program in docx form SLR PARSER.docx