#include <bits/stdc++.h>
#include <iomanip> // For setw
using namespace std;

// Structure to represent a grammar rule (item)
struct Rule {
    string lhs;
    vector<string> rhs;

    // Equality operator to compare two rules
    bool operator==(const Rule& other) const {
        return lhs == other.lhs && rhs == other.rhs;
    }
};

// Function to print a rule
void printRule(const Rule& rule) {
    cout << rule.lhs << " -> ";
    for(auto it = rule.rhs.begin(); it != rule.rhs.end(); ++it){
        cout << *it << " ";
    }
    cout << "\n";
}

// Function to split a string based on a single character delimiter
vector<string> split(const string& s, char delimiter) {
    vector<string> tokens;
    string token;
    istringstream tokenStream(s);
    while(getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

// Function to split a string based on a string delimiter
vector<string> splitByString(const string& s, const string& delimiter){
    vector<string> tokens;
    size_t pos = 0, prev = 0;
    while((pos = s.find(delimiter, prev)) != string::npos){
        tokens.push_back(s.substr(prev, pos - prev));
        prev = pos + delimiter.length();
    }
    tokens.push_back(s.substr(prev));
    return tokens;
}

// Function to tokenize RHS based on terminals and non-terminals
vector<string> getTokens(const string& rhs, const vector<string>& terminals, const vector<string>& nonterminals){
    vector<string> tokens;
    int i =0;
    while(i < (int)rhs.size()){
        bool matched = false;
        // Try matching terminals by longest first
        for(auto it = terminals.begin(); it != terminals.end(); ++it){
            string terminal = *it;
            int len = terminal.length();
            if(i + len <= (int)rhs.size() && rhs.substr(i, len) == terminal){
                tokens.push_back(terminal);
                i += len;
                matched = true;
                break;
            }
        }
        if(matched) continue;
        // If not matched, assume it's a non-terminal (single character)
        // To handle multi-character non-terminals, modify as needed
        // Here, we assume non-terminals are single uppercase letters
        if(i < (int)rhs.size()){
            string nonterminal(1, rhs[i]);
            tokens.push_back(nonterminal);
            i +=1;
        }
        else{
            // Unexpected character
            i +=1;
        }
    }
    return tokens;
}

// Function to perform grammar augmentation
vector<Rule> grammarAugmentation(const vector<string>& rules, const vector<string>& nonterm_userdef, const string& start_symbol, const vector<string>& terminals) {
    vector<Rule> newRules;
    string newChar = start_symbol + "'";
    // Ensure the new start symbol is unique
    while(find(nonterm_userdef.begin(), nonterm_userdef.end(), newChar) != nonterm_userdef.end()){
        newChar += "'";
    }
    // Adding augmented start rule
    Rule augmentedRule;
    augmentedRule.lhs = newChar;
    // Insert '.' before start symbol
    augmentedRule.rhs.push_back(".");
    augmentedRule.rhs.push_back(start_symbol);
    newRules.push_back(augmentedRule);
    // Process existing rules
    for(const auto& rule_str : rules){
        // Split by "->"
        vector<string> parts = splitByString(rule_str, "->");
        if(parts.size() !=2){
            cerr << "Invalid rule format: " << rule_str << "\n";
            continue; // Skip invalid rules
        }
        string lhs = parts[0];
        string rhs_str = parts[1];
        // Split RHS by '|'
        vector<string> multirhs = split(rhs_str, '|');
        for(auto& rhs : multirhs){
            // Remove leading and trailing spaces
            rhs.erase(rhs.begin(), find_if(rhs.begin(), rhs.end(), [](unsigned char ch) { return !isspace(ch); }));
            rhs.erase(find_if(rhs.rbegin(), rhs.rend(), [](unsigned char ch) { return !isspace(ch); }).base(), rhs.end());
            // Tokenize the RHS
            vector<string> rhs_tokens = getTokens(rhs, terminals, nonterm_userdef);
            // Insert '.' at the beginning
            rhs_tokens.insert(rhs_tokens.begin(), ".");
            // Create and add the rule
            Rule rule;
            rule.lhs = lhs;
            rule.rhs = rhs_tokens;
            newRules.push_back(rule);
        }
    }
    return newRules;
}

// Function to compute closure
vector<Rule> findClosure(const vector<Rule>& items, const vector<Rule>& allRules, const vector<string>& nonterm_userdef){
    vector<Rule> closure = items;
    bool added = true;
    while(added){
        added = false;
        vector<Rule> new_items;
        for(const auto& rule : closure){
            auto it = find(rule.rhs.begin(), rule.rhs.end(), ".");
            if(it != rule.rhs.end()){
                int pos = distance(rule.rhs.begin(), it);
                if(pos < (int)rule.rhs.size() -1){
                    string symbol_after_dot = rule.rhs[pos +1];
                    // If the symbol after dot is a non-terminal
                    if(find(nonterm_userdef.begin(), nonterm_userdef.end(), symbol_after_dot) != nonterm_userdef.end()){
                        // Add all rules where lhs == symbol_after_dot
                        for(const auto& r : allRules){
                            if(r.lhs == symbol_after_dot){
                                // To avoid duplication
                                if(find(closure.begin(), closure.end(), r) == closure.end() && 
                                   find(new_items.begin(), new_items.end(), r) == new_items.end()){
                                    new_items.push_back(r);
                                    added = true;
                                }
                            }
                        }
                    }
                }
            }
        }
        // Add any new items found
        closure.insert(closure.end(), new_items.begin(), new_items.end());
    }
    return closure;
}

// Function to compute GOTO
vector<Rule> compute_GOTO(const vector<Rule>& current_items, const string& symbol, const vector<Rule>& allRules, const vector<string>& nonterm_userdef){
    vector<Rule> moved;
    for(const auto& rule : current_items){
        auto it = find(rule.rhs.begin(), rule.rhs.end(), ".");
        if(it != rule.rhs.end()){
            int pos = distance(rule.rhs.begin(), it);
            if(pos < (int)rule.rhs.size() -1 && rule.rhs[pos +1] == symbol){
                // Move the dot past the symbol
                Rule new_rule = rule;
                // Swap '.' with the symbol
                swap(new_rule.rhs[pos], new_rule.rhs[pos +1]);
                moved.push_back(new_rule);
            }
        }
    }
    // Get the closure of the moved items
    return findClosure(moved, allRules, nonterm_userdef);
}

// Function to compute FIRST sets
map<string, set<string>> compute_FIRST(const vector<Rule>& allRules, const vector<string>& nonterm_userdef, const vector<string>& term_userdef){
    map<string, set<string>> FIRST;
    // Initialize FIRST for terminals
    for(const auto& terminal : term_userdef){
        FIRST[terminal].insert(terminal);
    }
    // Initialize FIRST for non-terminals to empty sets
    for(const auto& nonterminal : nonterm_userdef){
        FIRST[nonterminal] = set<string>();
    }
    bool changed = true;
    while(changed){
        changed = false;
        for(const auto& rule : allRules){
            string A = rule.lhs;
            vector<string> alpha = rule.rhs;
            // Process the RHS
            for(int i = 0; i < (int)alpha.size(); ++i){
                string X = alpha[i];
                // If X is a terminal
                if(find(term_userdef.begin(), term_userdef.end(), X) != term_userdef.end()){
                    if(FIRST[A].find(X) == FIRST[A].end()){
                        FIRST[A].insert(X);
                        changed = true;
                    }
                    break;
                }
                // If X is a non-terminal
                else{
                    bool has_epsilon = false;
                    for(const auto& sym : FIRST[X]){
                        if(sym != "#"){
                            if(FIRST[A].find(sym) == FIRST[A].end()){
                                FIRST[A].insert(sym);
                                changed = true;
                            }
                        }
                        else{
                            has_epsilon = true;
                        }
                    }
                    if(!has_epsilon){
                        break;
                    }
                }
                // If result contains epsilon, continue to next symbol
                if(i == (int)alpha.size() -1 && FIRST[X].find("#") != FIRST[X].end()){
                    if(FIRST[A].find("#") == FIRST[A].end()){
                        FIRST[A].insert("#");
                        changed = true;
                    }
                }
            }
        }
    }
    return FIRST;
}

// Function to compute FOLLOW sets
map<string, set<string>> compute_FOLLOW(const vector<Rule>& allRules, const vector<string>& nonterm_userdef, const vector<string>& term_userdef, const map<string, set<string>>& FIRST, const string& start_symbol_augmented){
    map<string, set<string>> FOLLOW;
    // Initialize FOLLOW sets to empty
    for(const auto& nonterminal : nonterm_userdef){
        FOLLOW[nonterminal] = set<string>();
    }
    // Add $ to FOLLOW(augmented_start_symbol)
    FOLLOW[start_symbol_augmented].insert("$");
    bool changed = true;
    while(changed){
        changed = false;
        for(const auto& rule : allRules){
            string A = rule.lhs;
            vector<string> alpha = rule.rhs;
            for(int i =0; i < (int)alpha.size(); ++i){
                string B = alpha[i];
                if(find(nonterm_userdef.begin(), nonterm_userdef.end(), B) != nonterm_userdef.end()){
                    // Beta is the rest of the alpha after B
                    if(i +1 < (int)alpha.size()){
                        vector<string> beta(alpha.begin()+i+1, alpha.end());
                        // Compute FIRST(beta)
                        set<string> FIRST_beta;
                        bool has_epsilon = true;
                        for(auto sym : beta){
                            // Add all symbols in FIRST(sym) except epsilon
                            for(auto fi : FIRST.at(sym)){
                                if(fi != "#") FIRST_beta.insert(fi);
                            }
                            // If FIRST(sym) doesn't contain epsilon, break
                            if(FIRST.at(sym).find("#") == FIRST.at(sym).end()){
                                has_epsilon = false;
                                break;
                            }
                        }
                        // Add FIRST(beta) - epsilon to FOLLOW(B)
                        int initial_size = FOLLOW[B].size();
                        for(auto fi : FIRST_beta){
                            FOLLOW[B].insert(fi);
                        }
                        if(FOLLOW[B].size() > initial_size){
                            changed = true;
                        }
                        // If FIRST(beta) contains epsilon, add FOLLOW(A) to FOLLOW(B)
                        if(has_epsilon){
                            initial_size = FOLLOW[B].size();
                            for(auto fi : FOLLOW[A]){
                                FOLLOW[B].insert(fi);
                            }
                            if(FOLLOW[B].size() > initial_size){
                                changed = true;
                            }
                        }
                    }
                    else{
                        // If B is at the end, add FOLLOW(A) to FOLLOW(B)
                        int initial_size = FOLLOW[B].size();
                        for(auto fi : FOLLOW[A]){
                            FOLLOW[B].insert(fi);
                        }
                        if(FOLLOW[B].size() > initial_size){
                            changed = true;
                        }
                    }
                }
            }
        }
    }
    return FOLLOW;
}

// Function to display FIRST sets
void display_FIRST(const map<string, set<string>>& FIRST){
    cout << "\nFIRST sets:\n";
    for(auto& pair : FIRST){
        cout << "FIRST(" << pair.first << ") = { ";
        for(auto it = pair.second.begin(); it != pair.second.end(); ++it){
            cout << *it << " ";
        }
        cout << "}\n";
    }
}

// Function to display FOLLOW sets
void display_FOLLOW(const map<string, set<string>>& FOLLOW){
    cout << "\nFOLLOW sets:\n";
    for(auto& pair : FOLLOW){
        cout << "FOLLOW(" << pair.first << ") = { ";
        for(auto it = pair.second.begin(); it != pair.second.end(); ++it){
            cout << *it << " ";
        }
        cout << "}\n";
    }
}

// Function to compare two states (vectors of Rules)
bool areStatesEqual(const vector<Rule>& s1, const vector<Rule>& s2){
    if(s1.size() != s2.size()) return false;
    // Sort both states for comparison
    vector<Rule> sorted_s1 = s1;
    vector<Rule> sorted_s2 = s2;
    sort(sorted_s1.begin(), sorted_s1.end(), [&](const Rule& a, const Rule& b) -> bool{
        if(a.lhs != b.lhs) return a.lhs < b.lhs;
        return a.rhs < b.rhs;
    });
    sort(sorted_s2.begin(), sorted_s2.end(), [&](const Rule& a, const Rule& b) -> bool{
        if(a.lhs != b.lhs) return a.lhs < b.lhs;
        return a.rhs < b.rhs;
    });
    return sorted_s1 == sorted_s2;
}

// Function to display parse table using tabulate-like formatting
void displayParseTable(const vector<string>& terminals, const vector<string>& nonterminals,
                      const map<int, map<string, string>>& ACTION,
                      const map<int, map<string, int>>& GOTO_table){
    // Headers
    cout << "\nSLR(1) Parsing Table:\n\n";
    cout << left << setw(8) << "State";
    for(auto& terminal : terminals){
        cout << left << setw(10) << terminal;
    }
    cout << left << setw(10) << "$";
    for(auto& nonterminal : nonterminals){
        cout << left << setw(10) << nonterminal;
    }
    cout << "\n";
    // Separator
    cout << string(8 + 10*(terminals.size()+1+nonterminals.size()), '-') << "\n";
    // Rows
    for(auto& state_pair : ACTION){
        int state = state_pair.first;
        cout << left << setw(8) << ("I" + to_string(state));
        // ACTION columns
        for(auto& terminal : terminals){
            if(ACTION.find(state) != ACTION.end() && ACTION.at(state).find(terminal) != ACTION.at(state).end()){
                cout << left << setw(10) << ACTION.at(state).at(terminal);
            }
            else{
                cout << left << setw(10) << "";
            }
        }
        // '$' column
        if(ACTION.find(state) != ACTION.end() && ACTION.at(state).find("$") != ACTION.at(state).end()){
            cout << left << setw(10) << ACTION.at(state).at("$");
        }
        else{
            cout << left << setw(10) << "";
        }
        // GOTO columns
        for(auto& nonterminal : nonterminals){
            if(GOTO_table.find(state) != GOTO_table.end() && GOTO_table.at(state).find(nonterminal) != GOTO_table.at(state).end()){
                cout << left << setw(10) << ("I" + to_string(GOTO_table.at(state).at(nonterminal)));
            }
            else{
                cout << left << setw(10) << "";
            }
        }
        cout << "\n";
    }
    cout << "\n";
}

// Function to display parsing steps
void displayParsingSteps(const vector<vector<string>>& data, const vector<string>& headers){
    // Display headers
    for(auto& header : headers){
        cout << left << setw(25) << header;
    }
    cout << "\n";
    // Display separator
    cout << string(25 * headers.size(), '-') << "\n";
    // Display data
    for(auto& row : data){
        for(int i =0; i < (int)row.size(); ++i){
            cout << left << setw(25) << row[i];
        }
        cout << "\n";
    }
    cout << "\n";
}

// Function to parse the input string using ACTION and GOTO tables
bool parseString(const string& input, const map<int, map<string, string>>& ACTION,
                const map<int, map<string, int>>& GOTO,
                const map<int, Rule>& prod_num){

    vector<int> stack;
    stack.push_back(0);
    int pointer = 0;
    // Tokenize input
    // Using the enhanced tokenizer to handle cases like "id$"
    vector<string> tokens;
    string token;
    istringstream tokenStream(input);
    while(tokenStream >> token){
        // Check if token ends with '$'
        if(token.back() == '$'){
            // Remove '$' from the token
            string actual_token = token.substr(0, token.size()-1);
            if(!actual_token.empty()){
                tokens.push_back(actual_token);
            }
            tokens.push_back("$");
        }
        else{
            tokens.push_back(token);
        }
    }
    // Append '$' if not present
    if(tokens.empty() || tokens.back() != "$"){
        tokens.push_back("$");
    }
    vector<vector<string>> parse_steps;
    bool accepted = false;
    while(true){
        int state = stack.back();
        if(pointer >= (int)tokens.size()){
            // No more input tokens
            break;
        }
        string current_token = tokens[pointer];
        // Log current stack and input
        string stack_str = "";
        for(auto it = stack.begin(); it != stack.end(); ++it){
            stack_str += to_string(*it) + " ";
        }
        string input_str = "";
        for(int i = pointer; i < (int)tokens.size(); ++i){
            input_str += tokens[i] + " ";
        }
        // Determine action
        string action = "";
        auto action_it = ACTION.find(state);
        if(action_it != ACTION.end()){
            auto symbol_it = action_it->second.find(current_token);
            if(symbol_it != action_it->second.end()){
                action = symbol_it->second;
            }
        }
        // Record the step
        vector<string> step = {stack_str, input_str, action};
        parse_steps.push_back(step);
        // Determine action type
        if(action.empty()){
            // Error
            parse_steps.back()[2] = "Error";
            break;
        }
        if(action == "ACC"){
            // Accepted
            break;
        }
        if(action.find("S") == 0){
            // Shift
            int next_state;
            try{
                next_state = stoi(action.substr(1));
            }
            catch(...){
                // Invalid shift action
                parse_steps.back()[2] = "Error";
                break;
            }
            stack.push_back(next_state);
            pointer +=1;
        }
        else if(action.find("R") ==0){
            // Reduce
            int prod_number;
            try{
                prod_number = stoi(action.substr(1));
            }
            catch(...){
                // Invalid reduce action
                parse_steps.back()[2] = "Error";
                break;
            }
            // Find the rule corresponding to this production number
            if(prod_num.find(prod_number) == prod_num.end()){
                // Invalid production number
                parse_steps.back()[2] = "Error";
                break;
            }
            Rule rule = prod_num.at(prod_number);
            // Determine the number of symbols to pop (stack symbols and states)
            // Each symbol and state occupy two entries in the stack
            if(!(rule.rhs.size() ==1 && rule.rhs[0] == "#")){
                int pop_length = 2 * rule.rhs.size(); // symbol and state
                if(pop_length > (int)stack.size()){
                    // Stack underflow
                    parse_steps.back()[2] = "Error";
                    break;
                }
                for(int i =0; i < pop_length; ++i){
                    stack.pop_back();
                }
            }
            // Get the current state from stack
            int current_state = stack.back();
            // Push LHS
            // Retrieve GOTO state
            auto goto_it = GOTO.find(current_state);
            if(goto_it != GOTO.end()){
                auto nonterm_it = goto_it->second.find(rule.lhs);
                if(nonterm_it != goto_it->second.end()){
                    int goto_state = nonterm_it->second;
                    stack.push_back(goto_state);
                }
                else{
                    // Error: No GOTO state for this non-terminal
                    parse_steps.back()[2] = "Error";
                    break;
                }
            }
            else{
                // Error: Current state not in GOTO table
                parse_steps.back()[2] = "Error";
                break;
            }
            // Log the reduce action
            parse_steps.back()[2] = "Reduce using production " + to_string(prod_number) + ": " + rule.lhs + " -> ";
            for(auto& sym : rule.rhs){
                parse_steps.back()[2] += sym + " ";
            }
        }
        else{
            // Error
            parse_steps.back()[2] = "Error";
            break;
        }
    }
    // Display parsing steps
    vector<string> headers = {"Stack", "Input", "Action"};
    displayParsingSteps(parse_steps, headers);
    // Determine acceptance
    return (parse_steps.back()[2] == "ACC");
}

int main(){
    // Sample Grammar
    // E -> E + T | T
    // T -> T * F | F
    // F -> ( E ) | id

    // Grammar definitions
    vector<string> rules = {
        "E -> E + T | T",
        "T -> T * F | F",
        "F -> ( E ) | id"
    };

    vector<string> nonterminals = {"E", "T", "F"};
    vector<string> terminals = {"id", "+", "*", "(", ")"};
    string start_symbol = "E";

    // Perform grammar augmentation
    vector<Rule> augmented_rules = grammarAugmentation(rules, nonterminals, start_symbol, terminals);

    cout << "\nOriginal Grammar Input:\n\n";
    for(const auto& rule : rules){
        cout << rule << "\n";
    }

    cout << "\nGrammar after Augmentation:\n\n";
    for(const auto& rule : augmented_rules){
        printRule(rule);
    }

    // Initialize states
    // State 0: closure of [E' -> . E]
    Rule start_rule_obj = augmented_rules[0];
    vector<Rule> initial_items = {start_rule_obj};
    vector<Rule> closure = findClosure(initial_items, augmented_rules, nonterminals);
    // States will be stored in a vector of vectors
    vector<vector<Rule>> States;
    States.push_back(closure);
    // Map to store state keys for identification (hashing)
    map<string, int> stateMap;
    // Function to create a unique key for a state
    auto createStateKey = [&](const vector<Rule>& state) -> string{
        vector<string> key_parts;
        for(const auto& rule : state){
            string temp = rule.lhs + "->";
            for(const auto& sym : rule.rhs){
                temp += sym;
            }
            key_parts.push_back(temp);
        }
        sort(key_parts.begin(), key_parts.end());
        string key = "";
        for(auto& part : key_parts){
            key += part + "|";
        }
        return key;
    };
    // Initialize stateMap with initial state
    string initial_key = createStateKey(States[0]);
    stateMap[initial_key] = 0;
    // Generate states
    int state_count =1;
    for(int i =0; i < (int)States.size(); ++i){
        // Get all unique symbols that can be transitioned on
        set<string> symbols;
        for(const auto& rule : States[i]){
            auto it = find(rule.rhs.begin(), rule.rhs.end(), ".");
            if(it != rule.rhs.end()){
                int pos = distance(rule.rhs.begin(), it);
                if(pos < (int)rule.rhs.size() -1){
                    symbols.insert(rule.rhs[pos +1]);
                }
            }
        }
        // For each symbol, compute GOTO
        for(const auto& sym : symbols){
            vector<Rule> goto_result = compute_GOTO(States[i], sym, augmented_rules, nonterminals);
            if(goto_result.empty()) continue;
            string key = createStateKey(goto_result);
            if(stateMap.find(key) == stateMap.end()){
                States.push_back(goto_result);
                stateMap[key] = state_count;
                state_count++;
            }
        }
    }

    // Display generated states
    cout << "\nStates Generated:\n\n";
    for(int st =0; st < (int)States.size(); ++st){
        cout << "State I" << st << ":\n";
        for(const auto& rule : States[st]){
            printRule(rule);
        }
        cout << "\n";
    }

    // Compute FIRST sets
    map<string, set<string>> FIRST = compute_FIRST(augmented_rules, nonterminals, terminals);
    display_FIRST(FIRST);

    // Compute FOLLOW sets
    // The augmented start symbol is the first rule's lhs
    string start_symbol_augmented = augmented_rules[0].lhs;
    map<string, set<string>> FOLLOW = compute_FOLLOW(augmented_rules, nonterminals, terminals, FIRST, start_symbol_augmented);
    display_FOLLOW(FOLLOW);

    // Create Parse Tables
    // ACTION table: state -> input symbol -> action
    map<int, map<string, string>> ACTION;
    // GOTO table: state -> non-terminal -> state
    map<int, map<string, int>> GOTO_table;

    // Production numbering (for reduce actions)
    // Production 0 is the augmented start rule
    map<int, Rule> prod_num; // Production number to Rule mapping
    int prod_number = 1;
    for(int i =1; i < (int)augmented_rules.size(); ++i){
        prod_num[prod_number] = augmented_rules[i];
        prod_number++;
    }

    // Fill ACTION and GOTO tables
    for(int i =0; i < (int)States.size(); ++i){
        for(const auto& rule : States[i]){
            auto it = find(rule.rhs.begin(), rule.rhs.end(), ".");
            if(it != rule.rhs.end()){
                int pos = distance(rule.rhs.begin(), it);
                if(pos < (int)rule.rhs.size() -1){
                    string sym = rule.rhs[pos +1];
                    // If a terminal
                    if(find(terminals.begin(), terminals.end(), sym) != terminals.end()){
                        // Compute GOTO on sym
                        vector<Rule> goto_result = compute_GOTO(States[i], sym, augmented_rules, nonterminals);
                        if(goto_result.empty()) continue;
                        // Create key for stateMap
                        string key = "";
                        for(auto& r : goto_result){
                            key += r.lhs + "->";
                            for(auto& s : r.rhs){
                                key += s;
                            }
                            key += "|";
                        }
                        // Find the state number
                        if(stateMap.find(key) != stateMap.end()){
                            int goto_state = stateMap[key];
                            // Add Shift action
                            if(ACTION[i].find(sym) != ACTION[i].end()){
                                ACTION[i][sym] += "/S" + to_string(goto_state);
                            }
                            else{
                                ACTION[i][sym] = "S" + to_string(goto_state);
                            }
                        }
                    }
                }
            }
            else{
                // If dot at end, it's a potential reduce or accept
                if(rule.lhs == start_symbol_augmented){
                    ACTION[i]["$"] = "ACC";
                }
                else{
                    // Find production number
                    int p_number = -1;
                    for(auto& p : prod_num){
                        if(p.second == rule){
                            p_number = p.first;
                            break;
                        }
                    }
                    if(p_number == -1) continue; // Production not found
                    // For all terminals in FOLLOW(lhs), add R production
                    for(const auto& terminal : FOLLOW[rule.lhs]){
                        if(ACTION[i].find(terminal) != ACTION[i].end()){
                            ACTION[i][terminal] += "/R" + to_string(p_number);
                        }
                        else{
                            ACTION[i][terminal] = "R" + to_string(p_number);
                        }
                    }
                }
            }
        }
        // Fill GOTO table
        for(const auto& nonterminal : nonterminals){
            // Compute GOTO on nonterminal
            vector<Rule> goto_result = compute_GOTO(States[i], nonterminal, augmented_rules, nonterminals);
            if(goto_result.empty()) continue;
            // Create key for stateMap
            string key = "";
            for(auto& r : goto_result){
                key += r.lhs + "->";
                for(auto& s : r.rhs){
                    key += s;
                }
                key += "|";
            }
            // Find the state number
            if(stateMap.find(key) != stateMap.end()){
                int goto_state = stateMap[key];
                GOTO_table[i][nonterminal] = goto_state;
            }
        }
    }

    // Display Parse Tables
    // Terminals + '$' are for ACTION table
    vector<string> action_terminals = terminals;
    // Display parse table
    displayParseTable(action_terminals, nonterminals, ACTION, GOTO_table);

    // Input string to parse
    cout << "Enter the string to be parsed (tokens separated by space, use '$' for end): ";
    string input;
    getline(cin, input);
    // Ensure space before '$' if it's attached to the last token
    if(!input.empty() && input.back() != '$'){
        input += " $";
    }

    // Parsing the string
    bool accepted = parseString(input, ACTION, GOTO_table, prod_num);

    if(accepted){
        cout << "The string is parsable and accepted!\n";
    }
    else{
        cout << "The string is not parsable and is rejected.\n";
    }

    return 0;
}