1 2 3 |
/* Implementation of SLR Parser */ #include<stdio.h> |
1 |
#include<ctype.h> |
1 |
#include<conio.h> |
1 |
#include<stdlib.h><!--more--> |
1 |
#include<string.h> |
1 |
#include<iostream.h> |
1 |
#define epsilon '^' |
1 |
char prod[20][20],T[20],NT[20],c[10][10],foll[10][10],fir[10][10]; |
1 |
int tt,tnt,tp,a; |
1 |
int follow[20][20],first[20][20]; |
1 |
void first_of(char); |
1 |
int count(int j); |
1 |
void rhs(int j); |
1 |
void read_tnt(); |
1 |
int rhs(int j); |
1 |
void read_tnt() |
1 |
{ cout<<"For SLR parser: "; |
1 |
cout<<"\nEnter number of terminals: "; |
1 |
cin>>tt; |
1 |
cout<<"\nEnter terminals: "; |
1 |
for(int i=0;i<tt;i++) |
1 |
T[i]=getche(); |
1 |
getch(); |
1 |
cout<<"\nEnter number of Non-terminals: "; |
1 |
cin>>tnt; |
1 |
cout<<"\nEnter Non-terminals: "; |
1 |
for(i=0;i<tnt;i++) |
1 |
NT[i]=getche(); |
1 2 |
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 |
void read_prod() |
1 |
{ int j; |
1 |
char x=0; |
1 |
cout<<"\n\nEnter number of productions: "; |
1 |
cin>>tp; |
1 |
cout<<"\n Enter productions: "; |
1 |
for(int i=0;i<tp;i++) |
1 |
{ j=x=0; |
1 |
while(x!='\r') |
1 |
{ prod[i][j]=x=getche(); |
1 |
j++; } |
1 |
cout<<"\n"; } |
1 |
getch(); } |
1 |
return(i); |
1 |
if(t=='$') |
1 |
return(tt); |
1 |
return(-1); } |
1 |
int terminal(char x) |
1 |
{ for(int i=0;i<tt;i++) |
1 |
if(T[i]==x) |
1 |
return(1); |
1 |
return(0); } |
1 |
int nonterminal(char x) |
1 |
{ for(int i=0;i<tnt;i++) |
1 |
if(NT[i]==x) |
1 |
return(1); |
1 |
return(0); } |
1 |
int in_rhs(char *s,char x) |
1 |
{ for(int i=0;i<=strlen(s);i++) |
1 |
if(*(s+i)==x) |
1 |
return(i); |
1 |
return(-1); } |
1 |
void find_first() |
1 |
{ for(int i=0;i<tnt;i++) |
1 |
first_of(NT[i]); } |
1 |
void first_of(char n) |
1 |
{ int t1,t2,p1,cnt=0,i,j; |
1 |
char x; |
1 |
static int over[20]; |
1 |
p1=t_no(epsilon); |
1 |
if(terminal(n)) |
1 |
return; |
1 |
t1=nt_no(n); |
1 |
if(over[t1]) |
1 |
return; |
1 |
over[t1]=1; |
1 |
for(i=0;i<tp;i++) |
1 |
{ t1=nt_no(prod[i][0]); |
1 |
if(prod[i][0]==n) |
1 |
{ int k=0; |
1 |
cnt=count(1); |
1 |
rhs(i); |
1 |
while(k<cnt) |
1 |
{ x=c[i][k]; |
1 |
if(terminal(x)) |
1 |
{ t2=t_no(x); |
1 |
first[t1][t2]=1; |
1 |
break; } |
1 |
else |
1 |
{ t2=nt_no(x); |
1 |
first_of(x); |
1 |
for(int j=0;j<tt;j++) |
1 |
first[t1][p1]=1; } } } |
1 |
void follow_of(char n) |
1 |
{ int f,t1,t2,p1,t,cnt=0; |
1 |
char x,beta; |
1 |
static int over[20]; |
1 |
p1=t_no(epsilon); |
1 |
t1=nt_no(n); |
1 |
if(over[t1]) |
1 |
return; |
1 |
over[t1]=1; |
1 |
if(NT[0]==n) |
1 |
follow[nt_no(NT[0])][tt]=1; |
1 |
for(int i=0;i<tp;i++) |
1 |
{ rhs(i); |
1 |
cnt=count(i); |
1 |
t=in_rhs(c[i],n); |
1 |
int bno; |
1 |
for(int j=0;j<tt;j++) |
1 |
{ |
1 |
bno=nt_no(beta); |
1 |
if((first[bno][j]) && (j!=p1)) |
1 |
follow[t1][j]=1; } |
1 |
if((p1!=-1) && (first[bno][p1]==1)) |
1 |
continue; |
1 |
else if((t==(cnt-1)||(k>=cnt))) |
1 |
{ follow_of(prod[i][0]); |
1 |
t1=nt_no(prod[i][0]); |
1 |
for(int l=0;l<=tt+1;l++) |
1 |
if(follow[t][l]) |
1 |
follow[t1][l]=1; } } } } |
1 |
1 |
int count(int j) |
1 |
{ int c1=0; |
1 |
for(int q=3;prod[j][q]!='\r';q++) |
1 |
c1++; |
1 |
return(c1); } |
1 |
void show_follow() |
1 |
{ int b=0; |
1 |
a=0; |
1 |
cout<<"\n\n Follow Table For Grammar: \n"; |
1 |
for(int i=0;i<tnt;i++) |
1 |
{ |
1 |
b=0; |
1 |
cout<<"\n FOLLOW ("<<NT[i]<<" )= { "; |
1 |
for(int j=0;j<tt+1;j++) |
1 |
if(follow[i][j] && j!=tt) |
1 |
{ foll[a][b]=T[j]; |
1 |
b++; |
1 |
cout<<T[j]<<" "; } |
1 |
else |
1 |
if(j==tt) |
1 |
{ foll[a][b]='$'; |
1 |
b++; |
1 |
cout<<'$'; } |
1 |
a++; |
1 |
cout<<" } "; } |
1 |
getch(); } |
1 |
void show_first() |
1 |
{ int b=0; |
1 |
a=0; |
1 |
cout<<"\n\n First Table For Grammar: \n"; |
1 |
for(int i=0;i<tnt;i++) |
1 |
{ b=0; |
1 |
cout<<"\n FIRST ("<<NT[i]<<" )= { "; |
1 |
for(int j=0;j<tt+1;j++) |
1 |
if(first[i][j] && j!=tt) |
1 |
{ fir[a][b]=T[j]; |
1 |
b++; |
1 |
cout<<T[j]<<" "; } |
1 |
a++; |
1 |
cout<<" } "; } |
1 |
getch()}}}} |
1 |
1 |
To construct parse table: |
1 |
1 |
#include<stdio.h> |
1 |
#include<conio.h> |
1 |
#include<string.h> |
1 |
#include<ctype.h> |
1 |
#include<stdlib.h> |
1 |
#include<iostream.h> |
1 |
#include"c:\tc\bin\SLR.h" |
1 |
1 |
int S=0,i=0,j=0,state[20]; |
1 |
char TNT[15]; |
1 |
struct node |
1 |
{ int pno,dpos; }; |
1 |
struct t |
1 |
{ char s; |
1 |
int n; }; |
1 |
struct t1 |
1 |
{ struct t lr[10]; |
1 |
int gr[5]; }; |
1 |
struct t1 action[15]; |
1 |
struct node closure[10][10]; |
1 |
int g[15][10]; |
1 |
int l; |
1 |
void sclosure(int,int); |
1 |
int added(int); |
1 |
int t_into(char); |
1 |
void print_table(int); |
1 |
void parser(void); |
1 |
void find_closure(int,int); |
1 |
void SLR(void); |
1 |
void main() |
1 |
{ clrscr(); |
1 |
mainf(); |
1 |
getch(); |
1 |
for(int i=0;i<tnt;i++) |
1 |
TNT[i]=NT[i]; |
1 |
for(int j=0;j<tt;j++) |
1 |
{ TNT[i]=T[j]; |
1 |
i++; } |
1 |
strcat(T,"$"); |
1 |
i=j=0; |
1 |
SLR(); |
1 |
print_table(S); |
1 |
getch(); } |
1 |
void SLR() |
1 |
{ int clno,no=0,x,y,z,len,cnt=-1,d=0; |
1 |
closure[i][j].pno=0; |
1 |
closure[i][j++].dpos=3; |
1 |
find_closure(no,3); |
1 |
sclosure(i,j); |
1 |
state[i]=j; |
1 |
S=0; |
1 |
do |
1 |
{ cnt++; |
1 |
z=state[cnt]; |
1 |
for(int k=0;k<tnt+tt;k++) |
1 |
{ i++; |
1 |
j=0;d=0; |
1 |
for(int l=0;l<z;l++) |
1 |
{ x=closure[cnt][1].pno; |
1 |
y=closure[cnt][1].dpos; |
1 |
if(prod[x][y]==TNT[k]) |
1 |
{ d=1; |
1 |
closure[i][j].pno=x; |
1 |
closure[i][j++].dpos=++y; |
1 |
if((y<strlen(prod[x])) && (isupper(prod[x][y]))) |
1 |
find_closure(x,y); } } |
1 |
if(d==0) |
1 |
{ i--; |
1 |
continue; } |
1 |
sclosure(i,j); |
1 |
else |
1 |
{ action[cnt].lr[k-tnt].s='S'; |
1 |
action[cnt].lr[k-tnt].n=clno; |
1 |
} |
1 |
if(added(i-1)!=-1) |
1 |
i--; |
1 |
else |
1 |
{ S++; |
1 |
for(l=0;l<state[i];l++) |
1 |
{ if(closure[i][1].pno==0) |
1 |
{ action[i].lr[tt].s='A'; |
1 |
continue; } |
1 |
len=(strlen(prod[closure[i][l].pno])-1); |
1 |
if(len==closure[i][l].dpos) |
1 |
{ char v=prod[closure[i][l].pno][0]; |
1 |
int u=nt_no(v); |
1 |
for(x=0;x<strlen(foll[u]);x++) |
1 |
{ int w=t_ino(foll[u][x]); |
1 |
action[i].lr[w].s='R'; |
1 |
action[i].lr[w].n=closure[i][l].pno;}}}}}} |
1 2 3 |
while(cnt!=S); } Also Read: |
1 |
void print_table(int states) |
1 |
{ int lin=5; |
1 |
cout<<"\n\n Parser Table: \n"; |
1 |
for(int i=0;i<tt;i++) |
1 |
cout<<"\t"<<T[i]; |
1 |
cout<<"\t$"; |
1 |
for(i=0;i<tnt;i++) |
1 |
cout<<"\t"<<NT[i]; |
1 |
cout<<"\n______________________________________________________________\n"; |
1 |
for(i=0;i<=states;i++) |
1 |
{ gotoxy(l,lin); |
1 |
cout<<"I"<<i<<"\t"; |
1 |
for(int j=0;j<=tt;j++) |
1 |
{ if(action[i].lr[j].s!='\x0') |
1 |
{ if(action[i].lr[j].s=='A') |
1 |
{ cout<<"Acc"; |
1 |
continue; } |
1 |
else |
1 |
cout<<"\t"; } |
1 |
for(j=0;j<tnt;j++) |
1 |
if(action[i].gr[j]) |
1 |
{ cout<<action[i].gr[j]; |
1 |
cout<<"\t"; } |
1 |
else |
1 |
cout<<"\t"; |
1 |
lin++; |
1 |
cout<<"\n"; } |
1 |
cout<<"\n______________________________________________________"; } |
1 |
void sclosure(int clno,int prodno) |
1 |
{ struct node temp; |
1 |
for(int i=0;i<prodno-1;i++) |
1 |
{ for(int j=i+1;j<prodno;j++) |
1 |
{ if(closure[clno][i].pno>closure[clno][j].pno) |
1 |
{ temp=closure[clno][i]; |
1 |
closure[clno][i]=closure[clno][j]; |
1 |
closure[clno][j]=temp; }}} |
1 |
for(i=0;i<prodno-1;i++) |
1 |
{for(j=i+1;j<prodno;j++) |
1 |
{if((closure[clno][i].dpos>closure[clno][j].dpos) && |
1 |
(closure[clno][i].pno==closure[clno][j].pno)) |
1 |
{ temp=closure[clno][i]; |
1 |
closure[clno][i]=closure[clno][j]; |
1 |
closure[clno][j]=temp;}}}} |
1 |
int added(int n) |
1 |
{ int d=1; |
1 |
for(int k=0;k<=n;k++) |
1 |
{if(state[k]==state[n+1]) |
1 |
{ d=0; |
1 |
return(k); } } |
1 |
return(-1); } |
1 |
void find_closure(int no,int dp) |
1 |
{ int k; |
1 |
char temp[5]; |
1 |
if(isupper(prod[no][dp])) |
1 |
{for(k=0;k<tp;k++) |
1 |
{if(prod[k][0]==prod[no][dp]) |
1 |
{ int t_ino(char t) |
1 |
{ for(int i=0;i<=tt;i++) |
1 |
if(T[i]==t) |
1 |
return(i); |
1 |
return(-1); } |
1 |
char pops2; |
1 |
struct node1 |
1 |
{ char s2;int s1; }; |
1 |
struct node1 stack[10]; |
1 |
int pops1,top=0; |
1 |
void parser(void) |
1 |
{ int r,c; |
1 |
struct t lr[10]; |
1 |
char t,acc='f',str[10]; |
1 |
cout<<"Enter I/p String To Parse: "; |
1 |
cin>>str; |
1 |
strcat(str,"$"); |
1 |
stack[0].s1=0; |
1 |
stack[0].s2='\n'; |
1 |
cout<<"\n\n STACK"; |
1 |
cout<<"\t\t INPUT"; |
1 |
cout<<"\t\t ACTION"; |
1 |
for(int j=0;j<strlen(str);j++) |
1 |
cout<<str[j]; |
1 |
do |
1 |
{r=stack[top].s1; |
1 |
c=find_index(str[i]); |
1 |
if(c==-1) |
1 |
cout<<"\n Error! Invalid String!"; |
1 |
return; } |
1 |
while(top!=0); |
1 |
switch(action[r],lr[c].s) |
1 |
{case 'S': { push(str[i],action[r].lr[c].n); |
1 |
i++; |
1 |
cout<<"\t\t\t Shift"; |
1 |
break; } |
1 |
case 'R': { t=prod[action[r].lr[c].n][3]; |
1 |
do { pop(); } |
1 |
while(pops2!=t); |
1 |
t=< |