Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Need Help In Running A Slr Parser Program.

SLR c++ cpp parser table windows anything best top

  • Please log in to reply
1 reply to this topic

#1 garvit184

garvit184

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 27 April 2012 - 01:15 AM

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!

  • 0

#2 kernelcoder

kernelcoder

    CC Devotee

  • Expert Member
  • PipPipPipPipPipPip
  • 990 posts
  • Location:Dhaka
  • Programming Language:C, Java, C++, C#, Visual Basic .NET
  • Learning:Objective-C, PHP, Python, Delphi/Object Pascal

Posted 27 April 2012 - 02:02 AM

The first catch I got is that the second line from last of your main method -- print_table(S) -- the value for S is here passing as zero. Now try to find out why the value of S is zero while calling print_table method.
  • 0





Also tagged with one or more of these keywords: SLR, c++, cpp, parser, table, windows, anything, best, top

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download