Implementation of SLR Parser

November 30, 2013

/* 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

Author
Recent Posts

Follow me

Mohit Arora

Hi, I am Mohit Arora , a passionate blogger and addicted reader. Currently working as a Technology Analyst in INFOSYS Ltd.
You can check my other blog - CatchUpdates.com

You can connect with me on Instagram Or Quora And Linkedin as well.

Follow me

1 thought on “Implementation of SLR Parser”

vid onApril 23, 2018

what is t_no, nt_no

Your email address will not be published. Required fields are marked *

Comment *

Name *

Email *

Website

All the data shown above will be stored by TutorialsJar on https://www.tutorialsjar.com/. At any point of time, you can contact us and select the data you wish to anonymize or delete so it cannot be linked to your email address any longer. When your data is anonymized or deleted, you will receive an email confirmation. We also use cookies and/or similar technologies to analyze customer behaviour, administer the website, track users' movements, and to collect information about users. This is done in order to personalize and enhance your experience with us.

I have read and accepted the Privacy Policy *

By using this form you agree with the storage and handling of your data by this website. *

Notify me of follow-up comments by email.

Notify me of new posts by email.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

TutorialsJar

Implementation of SLR Parser

Related

1 thought on “Implementation of SLR Parser”

Leave a Reply