#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h>
void add_symbol(char *, char);
void FIND_FIRST(char *, char);
void FIND_FOLLOW(char *, char);
void FIRST_SHOW();
void FOLLOW_SHOW();
int CREATE_LL1_TABLE();
void PARSING_TABLE_SHOW(int);
void LL1_PARSER(char *);
int top = 0; int t, nt, ch, cr, count; char FIRST[100][100], FOLLOW[100][100]; char T[100], NT[100], G[100][100], STACK[100]; int LL1[100][100];
int main() { int i, j, flag, fl, ch1; char STR[100]; printf("Enter production rules of grammar in the form A->B\n\n"); flag = 1; fl = 1; while (flag == 1) { printf("\n1) Insert Production Rules\n2) Show Grammar\n3) Exit"); printf("\nEnter your choice: "); scanf("%d", &ch1); switch (ch1) { case 1: printf("Enter number %d rules of grammar: ", cr + 1); scanf("%s", G[cr++]); for (i = 0; i < nt && fl == 1; i++) { if (NT[
[i] == G[cr - 1][0]) {
fl = 0;
}
}
if (fl == 1) {
NT[nt++] = G[cr - 1][0];
}
fl = 1;
for (i = 3; i < strlen(G[cr - 1]); i++) {
if (!isupper(G[cr - 1][i]) && G[cr - 1][i] != '|' && G[cr - 1][i] != 'e') {
for (j = 0; j < t && fl == 1; j++) {
if (T[j] == G[cr - 1][i]) {
fl = 0;
}
}
if (fl == 1) {
T[t++] = G[cr - 1][i];
}
fl = 1;
}
}
break;
case 2:
printf("\nGrammar:\n");
for (i = 0; i < cr; i++) {
printf("%s\n", G[i]);
}
break;
case 3:
flag = 0;
break;
default:
printf("Invalid choice! Please try again.\n");
}
}
for (i = 0; i < nt; i++) {
FIND_FIRST(FIRST[i], NT[i]);
}
for (i = 0; i < nt; i++) {
FIND_FOLLOW(FOLLOW[i], NT[i]);
}
FIRST_SHOW();
FOLLOW_SHOW();
if (CREATE_LL1_TABLE()) {
PARSING_TABLE_SHOW(1);
printf("\nEnter the string to be parsed: ");
scanf("%s", STR);
LL1_PARSER(STR);
} else {
printf("\nThe given grammar is not LL(1)!\n");
}
return 0;
}
void add_symbol(char *arr, char symbol) {
int i;
for (i = 0; arr[i] != '\0'; i++) {
if (arr[i] == symbol) {
return;
}
}
arr[i] = symbol;
arr[i + 1] = '\0';
}
void FIND_FIRST(char *result, char symbol) {
int i, j, k;
char subresult[20];
subresult[0] = '\0';
result[0] = '\0';
if (!isupper(symbol)) {
add_symbol(result, symbol);
return;
}
for (i = 0; i < cr; i++) {
if (G[i][0] == symbol) {
if (G[i][3] == 'e') {
add_symbol(result, 'e');
} else {
j = 3;
while (G[i][j] != '\0') {
int found_epsilon = 0;
FIND_FIRST(subresult, G[i][j]);
for (k = 0; subresult[k] != '\0'; k++) {
if (subresult[k] == 'e') {
found_epsilon = 1;
} else {
add_symbol(result, subresult[k]);
}
}
if (!found_epsilon) {
break;
}
j++;
}
if (G[i][j] == '\0') {
add_symbol(result, 'e');
}
}
}
}
}
void FIND_FOLLOW(char *result, char symbol) {
int i, j, k;
char subresult[20];
subresult[0] = '\0';
result[0] = '\0';
if (symbol == NT[0]) {
add_symbol(result, '$');
}
for (i = 0; i < cr; i++) {
for (j = 3; G[i][j] != '\0'; j++) {
if (G[i][j] == symbol) {
if (G[i][j + 1] != '\0') {
FIND_FIRST(subresult, G[i][j + 1]);
for (k = 0; subresult[k] != '\0'; k++) {
if (subresult[k] != 'e') {
add_symbol(result, subresult[k]);
}
}
if (strchr(subresult, 'e') != NULL) {
FIND_FOLLOW(subresult, G[i][0]);
for (k = 0; subresult[k] != '\0'; k++) {
add_symbol(result, subresult[k]);
}
}
} else {
if (G[i][0] != symbol) {
FIND_FOLLOW(subresult, G[i][0]);
for (k = 0; subresult[k] != '\0'; k++) {
add_symbol(result, subresult[k]);
}
}
}
}
}
}
}
void FIRST_SHOW() {
int i;
printf("\nFIRST sets:\n");
for (i = 0; i < nt; i++) {
printf("FIRST(%c) = { %s }\n", NT[i], FIRST[i]);
}
}
void FOLLOW_SHOW() {
int i;
printf("\nFOLLOW sets:\n");
for (i = 0; i < nt; i++) {
printf("FOLLOW(%c) = { %s }\n", NT[i], FOLLOW[i]);
}
}
int CREATE_LL1_TABLE() {
int i, j, k, m, n;
char subresult[20];
subresult[0] = '\0';
for (i = 0; i < nt; i++) {
for (j = 0; j < t; j++) {
LL1[i][j] = -1;
}
}
for (i = 0; i < cr; i++) {
char lhs = G[i][0];
char rhs[20];
strcpy(rhs, G[i] + 3);
FIND_FIRST(subresult, rhs[0]);
for (j = 0; subresult[j] != '\0'; j++) {
if (subresult[j] != 'e') {
for (k = 0; k < nt; k++) {
if (NT[k] == lhs) {
for (m = 0; m < t; m++) {
if (T[m] == subresult[j]) {
if (LL1[k][m] == -1) {
LL1[k][m] = i;
} else {
return 0; // Not LL(1)
}
}
}
}
}
}
}
if (strchr(subresult, 'e') != NULL) {
FIND_FOLLOW(subresult, lhs);
for (j = 0; subresult[j] != '\0'; j++) {
for (k = 0; k < nt; k++) {
if (NT[k] == lhs) {
for (m = 0; m < t; m++) {
if (T[m] == subresult[j] || subresult[j] == '$') {
if (LL1[k][m] == -1) {
LL1[k][m] = i;
} else {
return 0; // Not LL(1)
}
}
}
}
}
}
}
}
return 1;
}
void PARSING_TABLE_SHOW(int flag) {
int i, j;
printf("\nLL(1) Parsing Table:\n");
printf(" ");
for (i = 0; i < t; i++) {
printf(" %c", T[i]);
}
printf("\n");
for (i = 0; i < nt; i++) {
printf("%c ", NT[i]);
for (j = 0; j < t; j++) {
if (LL1[i][j] != -1) {
printf(" %s", G[LL1[i][j]]);
} else {
printf(" -");
}
}
printf("\n");
}
}
void LL1_PARSER(char *input) {
int i, j, k, m, n;
char symbol, top_stack;
int input_len = strlen(input);
input[input_len] = '$';
input[input_len + 1] = '\0';
STACK[top++] = '$';
STACK[top++] = NT[0];
i = 0;
while (STACK[top - 1] != '$') {
top_stack = STACK[--top];
symbol = input[i];
if (top_stack == symbol) {
i++;
} else if (!isupper(top_stack)) {
printf("Error: Invalid symbol on stack\n");
return;
} else {
for (j = 0; j < nt; j++) {
if (NT[j] == top_stack) {
for (k = 0; k < t; k++) {
if (T[k] == symbol) {
if (LL1[j][k] != -1) {
char *rhs = G[LL1[j][k]] + 3;
for (m = strlen(rhs) - 1; m >= 0; m--) {
if (rhs[m] != 'e') {
STACK[top++] = rhs[m];
}
}
} else {
printf("Error: No rule to apply\n");
return;
}
}
}
}
}
}
}
if (input[i] == '$') {
printf("String is successfully parsed\n");
} else {
printf("Error: Input not fully parsed\n");
}
}