Untitled

 avatar
unknown
plain_text
15 days ago
3.5 kB
4
Indexable
#include <stdio.h>
#include <string.h>

struct Production {
    char left;  // Left-hand side of production
    char right[10];  // Right-hand side of production
};

struct Production prodn[20], prodn_new[20];  // Original and new productions
int n, b = -1, c = 0;
char alpha[10], extra[10];  // For new non-terminal symbols and common prefixes
char epsilon = '^';  // Used to denote epsilon

// Function to input production rules
void inputProductions() {
    printf("\nEnter the number of productions: ");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        printf("Enter the %d production (Format: A->α): ", i + 1);
        scanf(" %c", &prodn[i].left);  // Adding a space before %c to handle leading whitespaces
        scanf("%s", prodn[i].right);
    }
}

// Function to apply left factoring
void leftFactoring() {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Check if the productions have the same left side
            if (prodn[i].left == prodn[j].left) {
                int k = 0;
                int commonLength = 0;

                // Find the common prefix
                while (prodn[i].right[k] == prodn[j].right[k] && prodn[i].right[k] != '\0') {
                    commonLength++;
                    k++;
                }

                if (commonLength > 0) {
                    // Factor out the common prefix
                    char newNonTerminal = alpha[c++];  // Generate a new non-terminal
                    strncpy(extra, prodn[i].right, commonLength);  // Store the common prefix
                    extra[commonLength] = '\0';

                    // Modify the productions
                    prodn_new[++b].left = prodn[i].left;
                    strcpy(prodn_new[b].right, extra);
                    prodn_new[b].right[commonLength] = newNonTerminal;

                    // Add the new production for the new non-terminal
                    prodn_new[++b].left = newNonTerminal;
                    if (prodn[i].right[commonLength] == '\0') {
                        prodn_new[b].right[0] = epsilon;  // If nothing remains, add epsilon
                    } else {
                        strcpy(prodn_new[b].right, prodn[i].right + commonLength);
                    }

                    // For the second production with the same left-hand side
                    prodn_new[++b].left = newNonTerminal;
                    if (prodn[j].right[commonLength] == '\0') {
                        prodn_new[b].right[0] = epsilon;  // If nothing remains, add epsilon
                    } else {
                        strcpy(prodn_new[b].right, prodn[j].right + commonLength);
                    }
                }
            }
        }
    }
}

// Function to display the final productions
void displayProductions() {
    printf("\nThe new productions after left factoring are: \n");
    for (int i = 0; i <= b; i++) {
        printf("%c -> %s\n", prodn_new[i].left, prodn_new[i].right);
    }
}

// Main function
int main() {
    printf("Enter special characters for new non-terminals (example: X, Y, Z): ");
    scanf("%s", alpha);  // Taking characters to generate new non-terminals

    inputProductions();  // Input production rules
    leftFactoring();     // Apply left factoring to productions
    displayProductions(); // Display the results after factoring

    return 0;
}
Leave a Comment