Need help in running a SLR parser program.
I need help in running a program that makes a SLR Parser Table.
Here is the code :
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 :
PHP 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!
Re: Need help in running a SLR parser program.
Re: Need help in running a SLR parser program.
Quote:
Originally Posted by
garvit184
I need help in running a program that makes a SLR Parser Table.
Why is your code double-spaced, making it twice as hard to read it?
What do you mean by "help in running"? You compile the code, you link the code, you run the code, you debug the code using the debugger if there are issues.
Regards,
Paul McKenzie
Re: Need help in running a SLR parser program.
are you able to run this prog or still looking for help
cheers!!!
Vatsa
www.objectiveprogramming.com
