garvit184 0 Newbie Poster

I need help in running a program that makes a SLR Parser Table.
Here is the code :

Code to find first and follow:

saved as SLR.h


#include<stdio.h>

#include<ctype.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include<iostream.h>


#define epsilon '^' 


 // since I didn't know how to type epsilon symbol  temporily I am using ^


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();

}


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();

}


int nt_no(char n)

{

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

 if(NT[i]==n)

   return(i);

 return(-1);

}


int t_no(char t)

{

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

 if(T[i]==t)

  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++)

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

        first[t1][j]=1;

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

        k++;

      else

        break;

     }

   }

   if(p1!=-1 && k>=cnt)

     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);

  if(t==-1)

   continue;

  for(int k=t+1;k<=cnt;k++)

  {

   rhs(i);

   beta=c[i][k];

   if(terminal(beta))

   {

    t2=t_no(beta);

    follow[t1][t2]=1;

    break;

   }

   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 rhs(int j)

{

 int a,h=0;

 a=j;

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

 {

  c[a][h]=prod[j][q];

  h++;

 }

}


void find_follow()

{

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

  follow_of(NT[i]);

}


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();

}




void mainf(void)

{

 clrscr();

 read_tnt();

 read_prod();

 find_first();

 find_follow();

 show_follow();

  show_first();

}



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);

int find_index(char);

int t_ino(char);

void pop(void);


void push(char,int);

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();

// clrscr();

// parser();

// 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);

   state[i]=j;

   clno=added(i-1);

   if(clno==-1)

    clno=i;

   if(isupper(TNT[k]))

    action[cnt].gr[k]=clno;

   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);

}


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;

     }

     cout<<action[i].lr[j].s;

     cout<<action[i].lr[j].n;

     cout<<"\t";

    }

    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;

    for(int j=0;j<state[k];j++)

    {

     if((closure[k][j].pno!=closure[n+1][j].pno) ||

        (closure[k][j].dpos!=closure[n+1][j].dpos))

       break;

     else

       d++;

    }

    if(d==state[k])

      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])

    {

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

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

     if(isupper(prod[k][3])&&

       (prod[k][3]!=prod[k][0]))

       find_closure(k,3);

    }

   }

  }

  return;

 }


 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";

  cout<<"\n =====";

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

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

  i=0;

  cout<<"\n";

  cout<<stack[top].s1;

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

  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;

 return;

}

The output should be :

Enter number of terminals: 5

Enter terminals:+*()i

Enter number of non-terminals:3

Enter non-terminals:ETF

Enter number of productions:6

Enter productions:

E->E+T

E->T

T->T*F

T->F

F->(E)

F->i


Follow table:

FOLLOW(E)={+ ) $}

FOLLOW(F)={+ * ) $}

FOLLOW(T)={ + * ) $}


First Table :

FIRST(E)={ ( i }

FIRST(E)={ ( i }

FIRST(E)={ ( i }



Expected parse table:


   +    *       (       )       i       $       E       T       F


I0                      S4              S5              1       2       3               

I1      S6                                      ACC

I2      R1      S7              R1              R1      

I3      R3      R3              R3              R3

I4                      S4              S5      ACC     8       2       3

I5      R5      R5              R5              R5                      

I6                                              ACC

I7                      S4              S5                              9

I8      S10                     S11             ACC             

I9      R2      R2              R2              R2

I10                                             ACC     

I11     R4      R4              R4              R4





Enter i/p string: i+i*i


STACK           INPUT                   ACTION


0                       i+i*i$                  Shift

0i5                     +i*i$                   Reduce

0F3                     +i*i$                   Reduce

0T2                     +i*i$                   Reduce

0E1                     +i*i$                   Shift

0E1+6                          i*i$

ERROR! STRING NOT ACCEPTED!