HarshVardhanKumar/First_and_Follow_Compiler_Design.cpp

## First_and_Follow_Compiler_Design.cpp
#include <iostream>
#include <unordered_map>
#include <set>

using namespace std ;
unordered_map<string, set<string> > productions, first_values, follow_values;
set<string> non_terminals, terminals;
string start_symbol ;

string getBody(string produc) {
    return produc.substr(produc.find('=')+1, produc.length()) ;
}

void calculate_first_values() {
    // need to repeat the procedure more than one time because doing so simply ensures that all the references to other variables will finally get resolved.
    for(string c: terminals) first_values[c].insert(c) ;
    for(int a = productions.size(); a>=0; a--) {
        for (pair<string, set<string> > p: productions) {
            for (string s : p.second) {
                if (terminals.count(s)) // if s is terminal.
                    first_values[p.first].insert(s); // s is a terminal, so directly attach it to the first of the head. This saves us from the terminal "id" ;
                else {
                    bool add_null = true;
                    for (char C : s) {
                        for (string f : first_values[string(1, C)]) first_values[p.first].insert(f);
                        if (!first_values[string(1, C)].count("#")) { // by default assume that we have to add a null to the first of the <head>. However, if some production character does not has null in its FIRST, then, we should not add a null to the FIRST of the head. So, we quit the process of adding a null.
                            add_null = false;
                            break; // breaks the char search sequence in the parent loop.
                        }
                    }
                    if (add_null) first_values[p.first].insert("#");
                }
            }
        }
    }
}

void calculate_follow_values() {
    // will operate on productions and first_values to find out the follow_values.
    follow_values[start_symbol].insert("$") ;

    for(int i = 0 ; i<productions.size(); i++) {
        for(pair<string, set<string> > p : productions) {
            // we are processing every production n times.
            for(string body: p.second) {
                bool union_follow_of_head = true ;

                char last_char = body[body.length()-1] ;
                if(!isupper(last_char)) union_follow_of_head = false ; // if last char is a terminal, then there is no chance of union of head's follow.
                else { // if the last char is a non-terminal, then it's follow must contain the follow of the head.
                    if(string(1,last_char) != p.first) for(string fv:follow_values[p.first]) follow_values[string(1,last_char)].insert(fv) ;
                    union_follow_of_head = (bool) first_values[string(1,last_char)].count("#") ;
                }

                for(int index = body.length()-2; index>=0 ; index--) {
                    last_char = body[index]; // now, last_char will refer to the current char being processed.
                    if(!isupper(last_char)) {union_follow_of_head = false ;}
                    else {
                        for (string fv: first_values[string(1, body[index + 1])])
                            follow_values[string(1, body[index])].insert(fv);
                        if(union_follow_of_head) {
                            if (string(1, last_char) != p.first)
                                for (string fv:follow_values[p.first])
                                    follow_values[string(1, last_char)].insert(fv);
                            union_follow_of_head = (bool) first_values[string(1, last_char)].count("#");
                        }
                        int j = 2;
                        while((index+j)<body.length() && first_values[string(1,body[index+j-1])].count("#")) {
                            for(string f: first_values[string(1,body[index+j])])
                                follow_values[string(1,body[index])].insert(f) ;
                            j++ ;
                        }
                    }
                }
            }
        }
    }
}

int main() {
    cout<<"Enter no. of productions"<<endl ;
    int n ; cin>>n ;
    cout<<"Enter the productions in the form head=body. No spaces are in between. \nAny non_terminal should consist of EXACTLY one character. '#' is the null character"<<endl ;
    string prod; string head; string body;
    while(n--) {
        cin>>prod ;
        head = string(1, prod[0]) ; body = getBody(prod) ;
        productions[head].insert(body) ;
        non_terminals.insert(head) ;
        if(body == "id") terminals.insert("id"); // "id" is a special terminal consisting of more than one character.
        for(char c : body) if(body!="id" && (!isupper(c) || c=='#')) terminals.insert(string(1,c)) ;
    }
    cout<<"Enter the starting non-terminal symbol"<<endl;
    cin>>start_symbol ; if(!non_terminals.count(start_symbol)) {cout<<"Process terminated! Please enter a valid start symbol"<<endl; exit(0);}

    calculate_first_values() ;
    // now, print the first() values;
    for(pair<string, set<string> > p : first_values) {
        if(isupper(p.first[0])) {
            cout << p.first << "= {";
            for (string s : p.second) cout << s << ",";
            cout << "}" << endl;
        }
    }

    calculate_follow_values() ;
    // now, print the values
    for(pair<string, set<string> > p : follow_values) {
        if(isupper(p.first[0])) {
            cout << p.first << "= {";
            for (string s : p.second) if(s!="#")cout << s << ",";
            cout << "}" << endl;
        }
    }
}
	#include <iostream>
	#include <unordered_map>
	#include <set>

	using namespace std ;
	unordered_map<string, set<string> > productions, first_values, follow_values;
	set<string> non_terminals, terminals;
	string start_symbol ;

	string getBody(string produc) {
	return produc.substr(produc.find('=')+1, produc.length()) ;
	}

	void calculate_first_values() {
	// need to repeat the procedure more than one time because doing so simply ensures that all the references to other variables will finally get resolved.
	for(string c: terminals) first_values[c].insert(c) ;
	for(int a = productions.size(); a>=0; a--) {
	for (pair<string, set<string> > p: productions) {
	for (string s : p.second) {
	if (terminals.count(s)) // if s is terminal.
	first_values[p.first].insert(s); // s is a terminal, so directly attach it to the first of the head. This saves us from the terminal "id" ;
	else {
	bool add_null = true;
	for (char C : s) {
	for (string f : first_values[string(1, C)]) first_values[p.first].insert(f);
	if (!first_values[string(1, C)].count("#")) { // by default assume that we have to add a null to the first of the <head>. However, if some production character does not has null in its FIRST, then, we should not add a null to the FIRST of the head. So, we quit the process of adding a null.
	add_null = false;
	break; // breaks the char search sequence in the parent loop.
	}
	}
	if (add_null) first_values[p.first].insert("#");
	}
	}
	}
	}
	}

	void calculate_follow_values() {
	// will operate on productions and first_values to find out the follow_values.
	follow_values[start_symbol].insert("$") ;

	for(int i = 0 ; i<productions.size(); i++) {
	for(pair<string, set<string> > p : productions) {
	// we are processing every production n times.
	for(string body: p.second) {
	bool union_follow_of_head = true ;

	char last_char = body[body.length()-1] ;
	if(!isupper(last_char)) union_follow_of_head = false ; // if last char is a terminal, then there is no chance of union of head's follow.
	else { // if the last char is a non-terminal, then it's follow must contain the follow of the head.
	if(string(1,last_char) != p.first) for(string fv:follow_values[p.first]) follow_values[string(1,last_char)].insert(fv) ;
	union_follow_of_head = (bool) first_values[string(1,last_char)].count("#") ;
	}

	for(int index = body.length()-2; index>=0 ; index--) {
	last_char = body[index]; // now, last_char will refer to the current char being processed.
	if(!isupper(last_char)) {union_follow_of_head = false ;}
	else {
	for (string fv: first_values[string(1, body[index + 1])])
	follow_values[string(1, body[index])].insert(fv);
	if(union_follow_of_head) {
	if (string(1, last_char) != p.first)
	for (string fv:follow_values[p.first])
	follow_values[string(1, last_char)].insert(fv);
	union_follow_of_head = (bool) first_values[string(1, last_char)].count("#");
	}
	int j = 2;
	while((index+j)<body.length() && first_values[string(1,body[index+j-1])].count("#")) {
	for(string f: first_values[string(1,body[index+j])])
	follow_values[string(1,body[index])].insert(f) ;
	j++ ;
	}
	}
	}
	}
	}
	}
	}

	int main() {
	cout<<"Enter no. of productions"<<endl ;
	int n ; cin>>n ;
	cout<<"Enter the productions in the form head=body. No spaces are in between. \nAny non_terminal should consist of EXACTLY one character. '#' is the null character"<<endl ;
	string prod; string head; string body;
	while(n--) {
	cin>>prod ;
	head = string(1, prod[0]) ; body = getBody(prod) ;
	productions[head].insert(body) ;
	non_terminals.insert(head) ;
	if(body == "id") terminals.insert("id"); // "id" is a special terminal consisting of more than one character.
	for(char c : body) if(body!="id" && (!isupper(c) \|\| c=='#')) terminals.insert(string(1,c)) ;
	}
	cout<<"Enter the starting non-terminal symbol"<<endl;
	cin>>start_symbol ; if(!non_terminals.count(start_symbol)) {cout<<"Process terminated! Please enter a valid start symbol"<<endl; exit(0);}

	calculate_first_values() ;
	// now, print the first() values;
	for(pair<string, set<string> > p : first_values) {
	if(isupper(p.first[0])) {
	cout << p.first << "= {";
	for (string s : p.second) cout << s << ",";
	cout << "}" << endl;
	}
	}

	calculate_follow_values() ;
	// now, print the values
	for(pair<string, set<string> > p : follow_values) {
	if(isupper(p.first[0])) {
	cout << p.first << "= {";
	for (string s : p.second) if(s!="#")cout << s << ",";
	cout << "}" << endl;
	}
	}
	}