/* Production Rules Used: X -> S@ S -> ABC A -> a|bbD B -> a|# C -> b|# D -> c|# P.S.- Assuming Epsilon transition to be # */ #include #define len(a) sizeof(a)/sizeof(a[0]) using namespace std; char expr[100][100]={0},first[100][100]={0},follow[100][100]={0}; string s[] = {"","X=S@","S=ABC","A=a|bbD","B=a|#","C=b|#","D=c|#"}; vector< char > duplicate; int num_of_production = len(s),epsilon_detector = 0,NT=0; void add_first(char r, char l){ duplicate.clear(); if(l=='#')epsilon_detector = 1; int index=-1,j=1; for(int i =1;i "; while(first[i][j]!=0){ cout << first[i][j]<<" "; j++; } cout << endl; j=0; } cout << endl; } int check_NT(char r, char l){ int j =1; NT=1; for(int i =1;i='A'&&expr[i][2]<='Z')counter++; } return counter; } void print_follow(){ int j; cout << "FOLLOW of the given expressions: "< "; while(follow[i][j]!=0){ cout <0)return; j++;} follow[index][j]= l; } void add_follow_NT_R(char r,char l){ int index1, index2,j=1,x=0; epsilon_detector=0; duplicate.clear(); for(int i =1;i0) duplicate.push_back(follow[index1][x]); x++;} while(follow[index2][j]!=0) { if(!count(duplicate.begin(),duplicate.end(),follow[index2][j])){ follow[index1][x]=follow[index2][j]; x++; } j++; } } void add_follow_NT(char r, int x , int y){ epsilon_detector=0; duplicate.clear(); if(expr[x][y]==0 || expr[x][y]=='|'){add_follow_NT_R(r,expr[x][0]);} int index1,j,index2; for(int i =1;i0) duplicate.push_back(follow[index2][j]); j++;} int counter1 =1; while(first[index1][counter1]!=0){ if(first[index1][counter1]=='#'){epsilon_detector=2; counter1++; continue;} if(!count(duplicate.begin(),duplicate.end(),first[index1][counter1])) {follow[index2][j]=first[index1][counter1]; j++;} //cout <<"Adding "<='A' && expr[i][j]<='Z')){ add_first(expr[i][0],expr[i][j]); while(expr[i][j]!='|' && expr[i][j]!=0)j++; j++; }else{ //cout << "NT Detected - "<='A' && expr[i][j]<='Z'){ epsilon_detector=0; NT=0; check_NT(expr[i][0],expr[i][j]); } NT=0; if(epsilon_detector){ if(expr[i][j]!='|' && expr[i][j]!='\0'){add_first(expr[i][0],expr[i][j]);j++;} else add_first(expr[i][0],'#');} epsilon_detector = 0; NT=0; while(expr[i][j]!='|' && expr[i][j]!='\0')j++; j++; } } } } /* FOLLOW */ for(int i =1;i='A' && expr[i][j] <='Z' && expr[i][j+1]>='A' && expr[i][j+1] <='Z'){ add_follow_NT(expr[i][j],i,j+1); }else if(expr[i][j]>='A' && expr[i][j] <='Z' && (expr[i][j+1]==0 || expr[i][j+1]=='|')){ add_follow_NT_R(expr[i][j],expr[i][0]); }else if (expr[i][j]>='A' && expr[i][j] <='Z' && !((expr[i][j+1]>='A' && expr[i][j+1] <='Z'))){ add_follow_T(expr[i][j],expr[i][j+1]); } j++; } } } print_production(); print_first(); print_follow(); return 0; }

FIRST-FOLLOW (Compiler)