Help in SLR parser

[vithasekar]

Hi ,

I am implementing SLR parser in my project. I got a code to construct parsing table and to parse a string. But it is not giving correct answer. Can u help me?

Thank u..

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

[dirkfirst]

Hey vithasekar, I can't help you but thought I would post a definition. I read your post and had no idea what an SLR was.

A Simple LR parser or SLR parser is an LR parser for which the parsing tables are generated as for an LR(0) parser except that it only performs a reduction with a grammar rule A → w if the next symbol on the input stream is in the follow set of A (see LL parser for a definition of follow set). Such a parser can prevent certain shift-reduce and reduce-reduce conflicts (see LR parser) that occur in LR(0) parsers and it can therefore deal with more grammars.

[WingedPanther]

Can you give an example of the input, incorrect output, and expected output?

[vithasekar]

Expected output for posted code:

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!