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!