Untitled

#include <iostream> // Correct header for C++ standard input/output
#include <string>
#include <vector>

using namespace std;

struct Production {
    char lhs;    // Left-hand side (non-terminal)
    string rhs;  // Right-hand side (production rule)
    bool flagged = false; // Flag to mark if the production is left factored
};

vector<Production> productions; // List of all productions
vector<Production> newProductions; // List of new productions after left factoring
vector<char> specialChars; // List of special characters
char epsilon = '^'; // Epsilon symbol

// Function to input special characters
void inputSpecialChars() {
    int count;
    cout << "Enter the number of special characters (except non-terminals): ";
    cin >> count;
    cout << "Enter the special characters for your productions: ";
    for (int i = 0; i < count; ++i) {
        char ch;
        cin >> ch;
        specialChars.push_back(ch);
    }
}

// Function to input the productions
void inputProductions() {
    int numProds;
    cout << "Enter the number of productions: ";
    cin >> numProds;
    productions.resize(numProds);
    for (int i = 0; i < numProds; ++i) {
        cout << "Enter production " << (i + 1) << " (in the form A->alpha): ";
        cin >> productions[i].lhs >> productions[i].rhs;
    }
}

// Function to perform left factoring
void leftFactor() {
    int specialCharIndex = 0;  // Index for special characters

    // Loop through each pair of productions
    for (size_t i = 0; i < productions.size(); ++i) {
        for (size_t j = i + 1; j < productions.size(); ++j) {
            // Check if the left-hand sides are the same
            if (productions[i].lhs == productions[j].lhs) {
                string commonPrefix;
                size_t k = 0;
                
                // Find the common prefix in the right-hand sides
                while (k < productions[i].rhs.length() &&
                       k < productions[j].rhs.length() &&
                       productions[i].rhs[k] == productions[j].rhs[k]) {
                    commonPrefix += productions[i].rhs[k];
                    ++k;
                }

                // If a common prefix is found
                if (!commonPrefix.empty()) {
                    // Mark the productions as factored
                    productions[i].flagged = productions[j].flagged = true;

                    // Create a new production for the common prefix
                    newProductions.push_back({productions[i].lhs, commonPrefix + specialChars[specialCharIndex]});

                    // Create a new production for the remaining part of production[i]
                    if (k < productions[i].rhs.length()) {
                        newProductions.push_back({specialChars[specialCharIndex], productions[i].rhs.substr(k)});
                    } else {
                        newProductions.push_back({specialChars[specialCharIndex], string(1, epsilon)});
                    }

                    // Create a new production for the remaining part of production[j]
                    if (k < productions[j].rhs.length()) {
                        newProductions.push_back({specialChars[specialCharIndex], productions[j].rhs.substr(k)});
                    } else {
                        newProductions.push_back({specialChars[specialCharIndex], string(1, epsilon)});
                    }

                    // Move to the next special character for the next factoring
                    ++specialCharIndex;
                }
            }
        }
    }

    // Add all unflagged productions to the new list
    for (const auto& prod : productions) {
        if (!prod.flagged) {
            newProductions.push_back(prod);
        }
    }
}

// Function to display the updated productions
void displayProductions() {
    cout << "\nUpdated Productions after Left Factoring:\n";
    for (const auto& prod : newProductions) {
        cout << prod.lhs << " -> " << prod.rhs << "\n";
    }
}

int main() {
    inputSpecialChars();   // Input special characters
    inputProductions();   // Input the productions
    leftFactor();         // Perform left factoring
    displayProductions(); // Display the new productions
    return 0;
}