Untitled
#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