Parse Table

using namespace std;
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <vector>

#define Range 20

struct nonTerminal {
    char nt;
    vector <char> first, follow, production[Range], fp[Range];
    vector <string> pstring;
    int npro;
} nterm[Range];

struct pos {
    int x, y, z;
} p;

map <char, int> m;
map < char, map <char, string> > produc;
vector <string> grammer;
string parseTable[Range][Range];
bool dp[Range];

set <char> row, column;

string charToString(char c) {
    stringstream ss;
    ss << c;
    return (ss.str());
}


void first(char c) {
    if(dp[m[c]]) return;
    for(int i = 0; i < nterm[m[c] - 1].npro; i++) {
        if(!m[nterm[m[c] - 1].production[i][0]]) {
            nterm[m[c] - 1].first.push_back(nterm[m[c] - 1].production[i][0]);
        } else {
            first(nterm[m[c] - 1].production[i][0]);
            nterm[m[c] - 1].first = nterm[m[nterm[m[c] - 1].production[i][0]] - 1].first;
        }
    }
    dp[m[c]] = true;
}

pos search(char c) {
    for(int i = 0; i < grammer.size(); i++)
        for(int j = 0; j < nterm[i].npro; j++)
            for (int k = 0; k < nterm[i].production[j].size(); k++)
                if(nterm[i].production[j][k] == c) {
                    p.x = i, p.y = j, p.z = k;
                    return p;
                }
}

void follow(char c) {
    pos _p = search(c);
    nterm[m[c] - 1].follow.push_back('$');
    if( _p.z < nterm[_p.x].production[_p.y].size() - 1) {
        char var = nterm[_p.x].production[_p.y][_p.z + 1];
        if(!m[var]) { // f = (e)
            nterm[m[c] - 1].follow.push_back(var);
            return;
        }
        int item = m[var] - 1;

        for(int i = 0; i < nterm[item].first.size(); i++) {
            char t = nterm[item].first[i];
            if(t == '0') continue;
            nterm[m[c] - 1].follow.push_back(t);
        }
        for (int k = 0; k < nterm[item].npro; k++) {
            if(nterm[item].production[k].size() == 1 && nterm[item].production[k][0] == '0') {
                //here is a confusion
                for(int x = 0; x < nterm[m[nterm[_p.x].nt] - 1].follow.size(); x++) {
                    char t = nterm[m[nterm[_p.x].nt] - 1].follow[x];
                    if(t == '$') continue;
                    nterm[m[c] - 1].follow.push_back(t);
                }
                break;
            }
        }

    } else {
        for(int i = 0; i < nterm[m[nterm[_p.x].nt] - 1].follow.size(); i++) {
            char t = nterm[m[nterm[_p.x].nt] - 1].follow[i];
            if(t == '$') continue;
            nterm[m[c] - 1].follow.push_back(t);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    string in, str, save;
    while(getline (cin, in)) {
        grammer.push_back(in);
    }
    int i, j;
    for(i = 0; i < grammer.size(); i++) {
        stringstream stream(grammer[i]);
        char variable;
        stream >> variable;
        row.insert(variable);
        m[variable] = i + 1;
        str = charToString(variable);
        str.append(" -> ");
        save = str; //back up
        nterm[i].nt = variable;
        stream >> variable;
        stream >> variable;
        int n = 0;
        while(stream >> variable) {
            if(variable == '|') {
                nterm[i].pstring.push_back(str);
                str = save; //restore
                n++;
                continue;
            }
            nterm[i].production[n].push_back(variable);
            str.append(charToString(variable));
        }
        nterm[i].pstring.push_back(str);
        nterm[i].npro = n + 1;
    }

    memset(dp, false, sizeof dp);
    for(j = 0; j < i; j++) first(nterm[j].nt);
    for(j = 0; j < i; j++) follow(nterm[j].nt);

    for(j = 0; j < i; j++) {
        for (int k =0; k < nterm[j].npro; k++) {
            bool flag = false;
            for(int l = 0; l < nterm[j].production[k].size(); l++) {
                char var = nterm[j].production[k][l];
                if(!m[var]) {
                    if(var == '0') {
                        for(int x = 0; x < nterm[j].follow.size(); x++) {
                            nterm[j].fp[k].push_back(nterm[j].follow[x]);
                        }
                    } else nterm[j].fp[k].push_back(nterm[j].production[k][l]);
                    break;
                }
                for(int x = 0; x < nterm[m[var] - 1].first.size(); x++) {
                    if(nterm[m[var] - 1].first[x] == '0') flag = true;
                    nterm[j].fp[k].push_back(nterm[m[var] - 1].first[x]);
                }
                if(flag == false) break;
            }
        }
    }


    for(j = 0; j < i; j++) {
        for (int k = 0; k < nterm[j].npro; k++) {
            for(int l = 0; l < nterm[j].fp[k].size(); l++) {
                column.insert(nterm[j].fp[k][l]);
                produc[nterm[j].nt][nterm[j].fp[k][l]] = nterm[j].pstring[k];
            }
        }
    }

    set <char> ::iterator it, jt;

    cout << "\n-------------------------------------Table------------------------------------\n";
    cout << "\nNon_Terminal                         Input Symbol\n\n";

    cout << "        ";
    for (it = column.begin(); it != column.end(); it++) printf("%9c", *it);
    cout << "\n\n";

    for (it = row.begin(); it != row.end(); it++) {
        printf("%5c", *it);
        for (jt = column.begin(); jt != column.end(); jt++) {
            if(produc[*it][*jt]!= "") printf("%10s", (produc[*it][*jt]).c_str());
            else printf("          ");
        }
        cout << "\n\n";
    }
    return false;
}

/**

----- input.txt -------
e -> tE
E -> +tE | 0
t -> fT
T -> *fT | 0
f -> (e) | x | y



-----------output.txt-----------------


-------------------------------------Table------------------------------------

Non_Terminal                         Input Symbol

                $        (        )        *        +        x        y

    E    E -> 0              E -> 0            E -> +tE

    T    T -> 0              T -> 0  T -> *fT    T -> 0

    e             e -> tE                                 e -> tE   e -> tE

    f            f -> (e)                                  f -> x    f -> y

    t             t -> fT                                 t -> fT   t -> fT




**/