Implementation of SLR Parser

/* Implementation of SLR Parser */

#include&lt;stdio.h&gt;

1

2

3

/* Implementation of SLR Parser */

#include<stdio.h>

#include&lt;ctype.h&gt;

1	#include<ctype.h>

#include&lt;conio.h&gt;

1	#include<conio.h>

#include&lt;stdlib.h&gt;<!--more-->

1	#include<stdlib.h><!--more-->

#include&lt;string.h&gt;

1	#include<string.h>

#include&lt;iostream.h&gt;

1	#include<iostream.h>

#define epsilon '^'

1	#define epsilon '^'

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

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

int tt,tnt,tp,a;

1	int tt,tnt,tp,a;

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

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

void first_of(char);

1	void first_of(char);

int count(int j);

1	int count(int j);

void rhs(int j);

1	void rhs(int j);

void read_tnt();

1	void read_tnt();

int rhs(int j);

1	int rhs(int j);

void read_tnt()

1	void read_tnt()

{       cout&lt;&lt;"For SLR parser: ";

1	{ cout<<"For SLR parser: ";

        cout&lt;&lt;"\nEnter number of terminals: ";

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

        cin&gt;&gt;tt;

1

cin>>tt;

        cout&lt;&lt;"\nEnter terminals: ";

1	cout<<"\nEnter terminals: ";

        for(int i=0;i&lt;tt;i++)

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

        T[i]=getche();

1	T[i]=getche();

        getch();

1

getch();

        cout&lt;&lt;"\nEnter number of Non-terminals: ";

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

        cin&gt;&gt;tnt;

1

cin>>tnt;

        cout&lt;&lt;"\nEnter Non-terminals: ";

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

        for(i=0;i&lt;tnt;i++)

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

               NT[i]=getche();

1	NT[i]=getche();

        getch();      }
<strong><span style="color: #ff0000;">Also Read : </span><span style="color: #ff0000;"><a title="Permalink to C program to implement lexical analyzer" href="http://csetips.catchupdates.com/c-program-to-implement-lexical-analyzer/" rel="bookmark"><span style="color: #ff0000;">C program to implement lexical analyzer</span></a></span></strong>

1

2

getch(); }

Also Read : <a title="Permalink to C program to implement lexical analyzer" href="http://csetips.catchupdates.com/c-program-to-implement-lexical-analyzer/" rel="bookmark">C program to implement lexical analyzer</a>

void read_prod()

1	void read_prod()

{       int j;

1

{ int j;

        char x=0;

1

char x=0;

        cout&lt;&lt;"\n\nEnter number of productions: ";

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

        cin&gt;&gt;tp;

1

cin>>tp;

        cout&lt;&lt;"\n Enter productions: ";

1	cout<<"\n Enter productions: ";

        for(int i=0;i&lt;tp;i++)

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

        {       j=x=0;

1

{ j=x=0;

               while(x!='\r')

1	while(x!='\r')

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

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

                       j++;    }

1

j++; }

               cout&lt;&lt;"\n";             }

1	cout<<"\n"; }

        getch();                                      }

1	getch(); }

  return(i);

1	return(i);

if(t=='$')

1	if(t=='$')

  return(tt);

1	return(tt);

return(-1);            }

1	return(-1); }

int terminal(char x)

1	int terminal(char x)

{       for(int i=0;i&lt;tt;i++)

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

        if(T[i]==x)

1	if(T[i]==x)

               return(1);

1	return(1);

        return(0);             }

1	return(0); }

int nonterminal(char x)

1	int nonterminal(char x)

{       for(int i=0;i&lt;tnt;i++)

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

        if(NT[i]==x)

1	if(NT[i]==x)

               return(1);

1	return(1);

        return(0);             }

1	return(0); }

int in_rhs(char *s,char x)

1	int in_rhs(char *s,char x)

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

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

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

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

                       return(i);

1	return(i);

               return(-1);                    }

1	return(-1); }

void find_first()

1	void find_first()

{       for(int i=0;i&lt;tnt;i++)

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

        first_of(NT[i]);               }

1	first_of(NT[i]); }

void first_of(char n)

1	void first_of(char n)

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

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

        char x;

1

char x;

        static int over[20];

1	static int over[20];

        p1=t_no(epsilon);

1	p1=t_no(epsilon);

        if(terminal(n))

1	if(terminal(n))

                return;

1

return;

        t1=nt_no(n);

1	t1=nt_no(n);

        if(over[t1])

1	if(over[t1])

               return;

1

return;

        over[t1]=1;

1	over[t1]=1;

        for(i=0;i&lt;tp;i++)

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

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

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

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

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

               {       int k=0;

1	{ int k=0;

                       cnt=count(1);

1	cnt=count(1);

                       rhs(i);

1

rhs(i);

                       while(k&lt;cnt)

1	while(k<cnt)

                       {       x=c[i][k];

1	{ x=c[i][k];

                               if(terminal(x))

1	if(terminal(x))

                               {       t2=t_no(x);

1	{ t2=t_no(x);

                                       first[t1][t2]=1;

1	first[t1][t2]=1;

                                       break;                 }

1

break; }

                               else

1

else

                               {       t2=nt_no(x);

1	{ t2=nt_no(x);

                                       first_of(x);

1	first_of(x);

                                       for(int j=0;j&lt;tt;j++)

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

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

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

void follow_of(char n)

1	void follow_of(char n)

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

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

        char x,beta;

1	char x,beta;

        static int over[20];

1	static int over[20];

        p1=t_no(epsilon);

1	p1=t_no(epsilon);

        t1=nt_no(n);

1	t1=nt_no(n);

        if(over[t1])

1	if(over[t1])

               return;

1

return;

        over[t1]=1;

1	over[t1]=1;

        if(NT[0]==n)

1	if(NT[0]==n)

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

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

        for(int i=0;i&lt;tp;i++)

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

        {       rhs(i);

1

{ rhs(i);

               cnt=count(i);

1	cnt=count(i);

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

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

                       int bno;

1

int bno;

                       for(int j=0;j&lt;tt;j++)

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

{

1

{

                               bno=nt_no(beta);

1	bno=nt_no(beta);

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

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

                                       follow[t1][j]=1;       }

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

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

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

                                       continue;

1

continue;

                               else if((t==(cnt-1)||(k&gt;=cnt)))

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

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

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

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

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

                                      for(int l=0;l&lt;=tt+1;l++)

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

                                      if(follow[t][l])

1	if(follow[t][l])

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

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

1

                                      int count(int j)

1	int count(int j)

                                      {  int c1=0;

1	{ int c1=0;

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

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

                                         c1++;

1

c1++;

                                         return(c1);         }

1	return(c1); }

void show_follow()

1	void show_follow()

{       int b=0;

1	{ int b=0;

        a=0;

1

a=0;

        cout&lt;&lt;"\n\n Follow Table For Grammar: \n";

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

        for(int i=0;i&lt;tnt;i++)

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

{

1

{

               b=0;

1

b=0;

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

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

               for(int j=0;j&lt;tt+1;j++)

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

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

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

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

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

                       b++;

1

b++;

                       cout&lt;&lt;T[j]&lt;&lt;" ";       }

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

               else

1

else

                       if(j==tt)

1

if(j==tt)

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

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

                               b++;

1

b++;

                               cout&lt;&lt;'$';     }

1	cout<<'$'; }

                       a++;

1

a++;

                       cout&lt;&lt;" } ";           }

1	cout<<" } "; }

                       getch();               }

1	getch(); }

                       void show_first()

1	void show_first()

                       {       int b=0;

1	{ int b=0;

                               a=0;

1

a=0;

                               cout&lt;&lt;"\n\n First Table For Grammar: \n";

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

                               for(int i=0;i&lt;tnt;i++)

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

                               {       b=0;

1

{ b=0;

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

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

                                      for(int j=0;j&lt;tt+1;j++)

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

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

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

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

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

                                              b++;

1

b++;

                                              cout&lt;&lt;T[j]&lt;&lt;" ";       }

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

                                      a++;

1

a++;

                                      cout&lt;&lt;" } ";           }

1	cout<<" } "; }

                                      getch()}}}}

1	getch()}}}}

1

To construct parse table:

1	To construct parse table:

1

#include&lt;stdio.h&gt;

1	#include<stdio.h>

#include&lt;conio.h&gt;

1	#include<conio.h>

#include&lt;string.h&gt;

1	#include<string.h>

#include&lt;ctype.h&gt;

1	#include<ctype.h>

#include&lt;stdlib.h&gt;

1	#include<stdlib.h>

#include&lt;iostream.h&gt;

1	#include<iostream.h>

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

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

1

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

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

char TNT[15];

1	char TNT[15];

struct node

1	struct node

{       int pno,dpos;  };

1	{ int pno,dpos; };

struct t

1

struct t

{       char s;

1

{ char s;

        int n;         };

1

int n; };

struct t1

1

struct t1

{       struct t lr[10];

1	{ struct t lr[10];

        int gr[5];     };

1	int gr[5]; };

struct t1 action[15];

1	struct t1 action[15];

struct node closure[10][10];

1	struct node closure[10][10];

int g[15][10];

1	int g[15][10];

int l;

1

int l;

void sclosure(int,int);

1	void sclosure(int,int);

int added(int);

1	int added(int);

int t_into(char);

1	int t_into(char);

void print_table(int);

1	void print_table(int);

void parser(void);

1	void parser(void);

void find_closure(int,int);

1	void find_closure(int,int);

void SLR(void);

1	void SLR(void);

void main()

1	void main()

{       clrscr();

1	{ clrscr();

        mainf();

1

mainf();

        getch();

1

getch();

        for(int i=0;i&lt;tnt;i++)

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

               TNT[i]=NT[i];

1	TNT[i]=NT[i];

        for(int j=0;j&lt;tt;j++)

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

        {       TNT[i]=T[j];

1	{ TNT[i]=T[j];

               i++;    }

1

i++; }

        strcat(T,"$");

1	strcat(T,"$");

        i=j=0;

1

i=j=0;

        SLR();

1

SLR();

        print_table(S);

1	print_table(S);

        getch();       }

1	getch(); }

void SLR()

1	void SLR()

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

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

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

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

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

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

        find_closure(no,3);

1	find_closure(no,3);

        sclosure(i,j);

1	sclosure(i,j);

        state[i]=j;

1	state[i]=j;

        S=0;

1

S=0;

do

1

do

        {       cnt++;

1

{ cnt++;

               z=state[cnt];

1	z=state[cnt];

               for(int k=0;k&lt;tnt+tt;k++)

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

               {       i++;

1

{ i++;

                       j=0;d=0;

1

j=0;d=0;

                       for(int l=0;l&lt;z;l++)

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

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

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

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

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

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

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

    {    d=1;

1

{ d=1;

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

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

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

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

         if((y&lt;strlen(prod[x])) &amp;&amp; (isupper(prod[x][y])))

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

           find_closure(x,y);          }       }

1	find_closure(x,y); } }

   if(d==0)

1

if(d==0)

   {    i--;

1

{ i--;

        continue;      }

1	continue; }

   sclosure(i,j);

1	sclosure(i,j);

   else

1

else

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

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

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

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

}

1

}

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

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

    i--;

1

i--;

   else

1

else

   {    S++;

1

{ S++;

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

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

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

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

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

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

                       continue;      }

1	continue; }

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

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

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

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

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

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

                               int u=nt_no(v);

1	int u=nt_no(v);

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

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

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

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

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

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

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

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

                                 while(cnt!=S);       }

Also Read:

1

2

3

while(cnt!=S); }

Also Read:

void print_table(int states)

1	void print_table(int states)

{       int lin=5;

1	{ int lin=5;

        cout&lt;&lt;"\n\n Parser Table: \n";

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

        for(int i=0;i&lt;tt;i++)

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

               cout&lt;&lt;"\t"&lt;&lt;T[i];

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

               cout&lt;&lt;"\t$";

1	cout<<"\t$";

        for(i=0;i&lt;tnt;i++)

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

        cout&lt;&lt;"\t"&lt;&lt;NT[i];

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

  cout&lt;&lt;"\n______________________________________________________________\n";

1	cout<<"\n______________________________________________________________\n";

  for(i=0;i&lt;=states;i++)

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

  {     gotoxy(l,lin);

1	{ gotoxy(l,lin);

        cout&lt;&lt;"I"&lt;&lt;i&lt;&lt;"\t";

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

        for(int j=0;j&lt;=tt;j++)

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

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

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

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

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

                       {       cout&lt;&lt;"Acc";

1	{ cout<<"Acc";

                               continue;      }

1	continue; }

    else

1

else

         cout&lt;&lt;"\t";   }

1	cout<<"\t"; }

   for(j=0;j&lt;tnt;j++)

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

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

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

    {    cout&lt;&lt;action[i].gr[j];

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

         cout&lt;&lt;"\t";   }

1	cout<<"\t"; }

    else

1

else

         cout&lt;&lt;"\t";

1	cout<<"\t";

    lin++;

1

lin++;

    cout&lt;&lt;"\n";        }

1	cout<<"\n"; }

   cout&lt;&lt;"\n______________________________________________________";        }

1	cout<<"\n______________________________________________________"; }

void sclosure(int clno,int prodno)

1	void sclosure(int clno,int prodno)

{ struct node temp;

1	{ struct node temp;

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

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

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

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

   {  if(closure[clno][i].pno&gt;closure[clno][j].pno)

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

    {    temp=closure[clno][i];

1	{ temp=closure[clno][i];

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

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

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

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

  for(i=0;i&lt;prodno-1;i++)

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

  {for(j=i+1;j&lt;prodno;j++)

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

   {if((closure[clno][i].dpos&gt;closure[clno][j].dpos) &amp;&amp;

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

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

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

    {    temp=closure[clno][i];

1	{ temp=closure[clno][i];

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

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

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

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

int added(int n)

1	int added(int n)

{ int d=1;

1	{ int d=1;

  for(int k=0;k&lt;=n;k++)

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

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

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

   { d=0;

1

{ d=0;

return(k);     }       }

1	return(k); } }

  return(-1);      }

1	return(-1); }

void find_closure(int no,int dp)

1	void find_closure(int no,int dp)

{ int k;

1

{ int k;

  char temp[5];

1	char temp[5];

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

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

  {for(k=0;k&lt;tp;k++)

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

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

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

    {    int t_ino(char t)

1	{ int t_ino(char t)

{  for(int i=0;i&lt;=tt;i++)

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

   if(T[i]==t)

1	if(T[i]==t)

    return(i);

1	return(i);

  return(-1);          }

1	return(-1); }

char pops2;

1	char pops2;

struct node1

1	struct node1

{       char s2;int s1;        };

1	{ char s2;int s1; };

struct node1 stack[10];

1	struct node1 stack[10];

int pops1,top=0;

1	int pops1,top=0;

void parser(void)

1	void parser(void)

{ int r,c;

1	{ int r,c;

  struct t lr[10];

1	struct t lr[10];

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

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

  cout&lt;&lt;"Enter I/p String To Parse: ";

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

  cin&gt;&gt;str;

1

cin>>str;

  strcat(str,"$");

1	strcat(str,"$");

  stack[0].s1=0;

1	stack[0].s1=0;

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

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

  cout&lt;&lt;"\n\n STACK";

1	cout<<"\n\n STACK";

  cout&lt;&lt;"\t\t INPUT";

1	cout<<"\t\t INPUT";

  cout&lt;&lt;"\t\t ACTION";

1	cout<<"\t\t ACTION";

  for(int j=0;j&lt;strlen(str);j++)

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

   cout&lt;&lt;str[j];

1	cout<<str[j];

do

1

do

  {r=stack[top].s1;

1	{r=stack[top].s1;

   c=find_index(str[i]);

1	c=find_index(str[i]);

   if(c==-1)

1

if(c==-1)

    cout&lt;&lt;"\n Error! Invalid String!";

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

   return;     }

1

return; }

  while(top!=0);

1	while(top!=0);

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

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

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

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

                  i++;

1

i++;

                  cout&lt;&lt;"\t\t\t Shift";

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

                  break;      }

1

break; }

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

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

                 do    {       pop();  }

1	do { pop(); }

                 while(pops2!=t);

1	while(pops2!=t);