lab 5

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

int main() {
    ifstream file("text.txt");
    if (!file) {
        cout << "Input file not found!\n";
        exit(1);  // Return error code 1
    }

    int number = 0, index = 1;

    map<char, int> mp;
    map<int, char> reverse_mp;
    map<int, vector<vector<char>>> production_list;

    string line;
    while (getline(file, line)) {
        number++;

        bool start = false;
        char nonTerminal = ' ';

        vector<char> production_;

        for (char inputchar : line) {
            if (!start) {
                nonTerminal = inputchar;
                start = true;

                if (mp[nonTerminal] == 0) {
                    mp[nonTerminal] = index++;
                    reverse_mp[mp[nonTerminal]] = nonTerminal;
                }
            } else {
                if (inputchar == '-' || inputchar == '>' || inputchar == ' ' || inputchar == '\n') {
                    // Ignore these characters
                } else if (inputchar == '|') {
                    production_list[mp[nonTerminal]].push_back(production_);
                    production_.clear();
                } else {
                    production_.push_back(inputchar);
                }
            }
        }

        // Add last production for the current non-terminal
        if (!production_.empty()) {
            production_list[mp[nonTerminal]].push_back(production_);
        }
    }

    // Compute the FIRST sets
    map<char, set<char>> first;

    // Function to calculate FIRST set for a given non-terminal
    function<void(char)> computeFirst = [&](char nonTerminal) {
        if (first.count(nonTerminal)) return;  // Already computed

        for (const auto& production : production_list[mp[nonTerminal]]) {
            for (char symbol : production) {
                if (mp[symbol] == 0) {  // Terminal
                    first[nonTerminal].insert(symbol);
                    break;
                } else {  // Non-terminal
                    computeFirst(symbol);
                    first[nonTerminal].insert(first[symbol].begin(), first[symbol].end());
                    if (first[symbol].count('^') == 0) break;  // Stop if no epsilon
                }
            }
        }
    };

    for (int i = 1; i < index; i++) {
        char nonTerminal = reverse_mp[i];
        computeFirst(nonTerminal);
    }

    // Print the FIRST sets (optional for debugging)
    // for (auto [u, v] : first) {
    //     cout << "FIRST(" << u << ") = { ";
    //     for (auto w : v) {
    //         cout << w << ", ";
    //     }
    //     cout << "}\n";
    // }

    // Compute the FOLLOW sets
    map<char, set<char>> follow;

    // Function to calculate FOLLOW set for a given non-terminal
    function<void(char)> computeFollow = [&](char nonTerminal) {
        if (follow.count(nonTerminal)) return;  // Already computed

        if (nonTerminal == reverse_mp[1]) {  // Start symbol
            follow[nonTerminal].insert('$');
        }

        for (int i = 1; i < index; i++) {
            for (const auto& production : production_list[i]) {
                for (int j = 0; j < production.size(); j++) {
                    if (production[j] == nonTerminal) {
                        if (j + 1 < production.size()) {
                            char nextSymbol = production[j + 1];
                            if (mp[nextSymbol] == 0) {
                                follow[nonTerminal].insert(nextSymbol);  // Terminal
                            } else {
                                follow[nonTerminal].insert(first[nextSymbol].begin(), first[nextSymbol].end());
                                if (first[nextSymbol].count('^')) {
                                    follow[nonTerminal].insert(follow[reverse_mp[i]].begin(), follow[reverse_mp[i]].end());
                                }
                            }
                        } else {
                            follow[nonTerminal].insert(follow[reverse_mp[i]].begin(), follow[reverse_mp[i]].end());
                        }
                    }
                }
            }
        }
    };

    // Compute FOLLOW sets for all non-terminals
    for (int i = 1; i < index; i++) {
        computeFollow(reverse_mp[i]);
    }

    // Print the FOLLOW sets (optional for debugging)
    // for (auto [u, v] : follow) {
    //     cout << "FOLLOW(" << u << ") = { ";
    //     for (auto w : v) {
    //         cout << w << ", ";
    //     }
    //     cout << "}\n";
    // }

    // Construct the LL(1) parse table
    map<pair<char, char>, vector<char>> parse_table;
    bool cannot = false;

    for (auto [u, v] : production_list) {
        for (const auto& production : v) {
            char alpha = production[0];
            char A = reverse_mp[u];

            if (mp[alpha] == 0) {  // Terminal
                if (alpha == '^') {  // Epsilon
                    for (auto t : follow[A]) {
                        if (parse_table[{A, t}].empty()) {
                            parse_table[{A, t}] = production;
                        } else {
                            cannot = true;
                        }
                    }
                } else {  // Non-epsilon terminal
                    if (parse_table[{A, alpha}].empty()) {
                        parse_table[{A, alpha}] = production;
                    } else {
                        cannot = true;
                    }
                }
            } else {  // Non-terminal
                for (auto w : first[alpha]) {
                    if (w == '^') {
                        for (auto t : follow[A]) {
                            if (parse_table[{A, t}].empty()) {
                                parse_table[{A, t}] = production;
                            } else {
                                cannot = true;
                            }
                        }
                    } else {
                        if (parse_table[{A, w}].empty()) {
                            parse_table[{A, w}] = production;
                        } else {
                            cannot = true;
                        }
                    }
                }
            }
        }
    }

    // Output a message if a conflict occurs in the parse table
    if (cannot) {
        cout << "Error: The grammar is not LL(1).\n";
    } else {
        cout << "The grammar is LL(1) and the parse table is constructed.\n";
    }

    // Optionally, print the parse table for debugging
    // for (auto [key, value] : parse_table) {
    //     cout << "Parse Table[" << key.first << ", " << key.second << "] = ";
    //     for (auto ch : value) {
    //         cout << ch << " ";
    //     }
    //     cout << endl;
    // }

    string input;
    cout << "Enter the input string: ";
    cin >> input;
    input += '$';  // Add end-of-input marker

    stack<char> parse_stack;
    parse_stack.push('$');
    parse_stack.push(reverse_mp[1]);  // Push the start symbol onto the stack

    cout << "Start Parsing:\n";
    while (!parse_stack.empty()) {
        char top = parse_stack.top();
        char current_input = input[0];

        if (top == current_input) {
            // If top of the stack matches the current input symbol, pop it and move input forward

            cout << top << " matches " << current_input << endl;
            parse_stack.pop();
            input = input.substr(1);  // Move the input pointer forward
        } else if (mp[top] > 0) {
            // If top is a non-terminal, use the parse table to expand it
            auto it = parse_table.find({top, current_input});
            if (it != parse_table.end()) {
                cout << top << " expands to ";
                const vector<char>& production = it->second;

                // Push the right-hand side of the production onto the stack in reverse order
                parse_stack.pop();  // Pop the non-terminal
                for (auto rit = production.rbegin(); rit != production.rend(); ++rit) {
                    if (*rit != '^') {  // Skip epsilon productions
                        parse_stack.push(*rit);
                    }
                }

                for (auto sym : production) {
                    cout << sym << " ";
                }
                cout << endl;
            } else {
                cout << "Parse error: No rule for " << top << " with input " << current_input << endl;
                return 0;
            }
        } else {
            // If top is not a terminal and no production is found, it's a parsing error
            cout << "Parse error: " << top << " doesn't match " << current_input << endl;
            return 0;
        }
    }

    if (input.empty()) {
        cout << "String matches the grammar!\n";
    } else {
        cout << "Input string could not be completely parsed.\n";
    }

    return 0;
}