First - Follow [Zanjo]

/*
@Author : Zanjo
@Date Of Creation : 25/08/2018

Production Rules Used:
X -> S@
S -> ABC
A -> a|bbD
B -> a|#
C -> b|#
D -> c|#

P.S.- Assuming Epsilon transition to be #
*/
#include<bits/stdc++.h>
#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<num_of_production;i++){
        if (first[i][0] == r) {
            index =i;
            break;
        }
    }
    if(index !=-1){
        while(first[index][j]!=0){
                duplicate.push_back(first[index][j]);
                j++;}
        if(!(NT && l=='#') && !count(duplicate.begin(),duplicate.end(),l)){
        first[index][j] = l;}
    }else{
        j=1;
        while(first[j][0]!=0)j++;
        first[j][0]=r;
        first[j][1]=l;
    }
}
void print_first(){
    int j;
    cout << "FIRST of the given expressions: "<<endl<<endl;
    for(int i =1;i<num_of_production;i++){
            j=0;
            cout << first[i][j++] << " -> ";
        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<num_of_production;i++){
        if(first[i][0] == l){
            while(first[i][j]!=0){
                add_first(r,first[i][j]);
                j++;
            }
            return true;
        }
    }
    return false;
}
int num_of_NT(){
    int counter = 0;
    for(int i =1;i<num_of_production;i++)
    {
        if (expr[i][2]>='A'&&expr[i][2]<='Z')counter++;

    }
    return counter;
}
void print_follow(){
     int j;
     cout << "FOLLOW of the given expressions: "<<endl<<endl;
    for(int i =1;i<num_of_production;i++){
            j=0;
            cout << follow[i][j++] << " -> ";
        while(follow[i][j]!=0){
            cout <<follow[i][j]<<" ";
            j++;
        }
        cout << endl;
    }
    cout << endl;
}
void add_follow_T(char r,char l){
    int index=0;

    for(int i =1;i<num_of_production;i++){
        if(r==follow[i][0]){index =i;break;}

    }
    int j=0;
    while(follow[index][j]!=0){
            if(follow[index][j]==l&&j>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;i<num_of_production;i++){
        if(follow[i][0]==r)index1 = i;
        if(follow[i][0]==l)index2=i;
    }
    while(follow[index1][x]!=0){
            if(x>0)
            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;i<num_of_production;i++){
        if(first[i][0]==expr[x][y])index1 =i;
        if(follow[i][0]==r)index2=i;
    }
    j=0;
    while(follow[index2][j]!=0){

            if(j>0)
            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 "<<first[index1][counter1]<<index2<<endl ;
        counter1++;
    }
    if(epsilon_detector==2)add_follow_NT(r,  x ,  y+1);
}
void print_production(){
    cout << "Given Production Rules:\n\n";
    for(int i =1;i<num_of_production;i++){
        cout <<s[i]<<endl;
    }
    cout << endl;
}
int main(){
    int j =0;
    for(int i =1;i<num_of_production;i++)
        strcpy(expr[i],s[i].c_str());


    int x =num_of_NT()+1;
    int counter = x;
    while(counter--){
        for(int i = 1;i <num_of_production;i++){
                    j=2;
                    while(expr[i][j]!=0){
                            epsilon_detector = 0;
                            NT=0;
                        if(!(expr[i][j]>='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 - "<<expr[i][j]<<" ";
                                epsilon_detector=0;
                                NT=0;
                            check_NT(expr[i][0],expr[i][j]);
                            NT=0;
                            while(epsilon_detector && expr[i][++j] >='A' && expr[i][j]<='Z'){
                                epsilon_detector=0;
                                NT=0;
                                check_NT(expr[i][0],expr[i][j]);

                            }
                            NT=0;
                            if(epsilon_detector){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<num_of_production;i++){
        follow[i][0] = expr[i][0];
    }
    counter =x;
    while(counter--){
            if(counter == x-1)add_follow_T(expr[1][0],'$');
        for(int i = 1;i <num_of_production;i++){
                j = 2;
            while(expr[i][j]!=0){

                if(expr[i][j]>='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++;

            }
        }


    }

    //cout << endl;
    print_production();
    print_first();
    print_follow();

    return 0;
}