Design An Top-Down Parser Which Generate A Parsing Table With No Backtracking An Simple And Easy Code

 Mathematica:

E -> T E'

E' -> + T E' | ε

T -> F T'

T' -> * F T' | ε

F -> ( E ) | id

Simple C program for a top-down parser:

#include <stdio.h> #include <stdlib.h> #include <string.h> // Define terminals and non-terminals enum { PLUS, TIMES, LPAREN, RPAREN, ID, END, INVALID }; char terminals[] = {'+', '*', '(', ')', 'id', '$'}; char nonTerminals[] = {'E', 'A', 'T', 'B', 'F'}; // Define the LL(1) parsing table int parsingTable[5][6] = { {1, -1, -1, -1, 1, -1}, {-1, 2, -1, -1, -1, 3}, {4, -1, -1, -1, 4, -1}, {-1, -1, 5, -1, -1, 5}, {6, -1, -1, -1, 7, -1} }; // Function to get the index of a terminal/non-terminal int getIndex(char symbol, char* symbols) { for (int i = 0; i < strlen(symbols); i++) { if (symbols[i] == symbol) { return i; } } return -1; } // Function to get the type of a symbol int getSymbolType(char symbol) { if (symbol == '+') return PLUS; if (symbol == '*') return TIMES; if (symbol == '(') return LPAREN; if (symbol == ')') return RPAREN; if (symbol == 'id') return ID; if (symbol == '$') return END; return INVALID; } // Function to perform parsing void parseInput(char input[]) { char stack[100]; int top = -1; stack[++top] = 'E'; // Push start symbol to the stack int inputIndex = 0; printf("Parsing Steps:\n"); while (top >= 0) { char stackTop = stack[top]; char currentInput = input[inputIndex]; printf("Stack: %s\tInput: %s\t", stack, input + inputIndex); if (stackTop == currentInput && currentInput == '$') { printf("Accepted\n"); break; } int stackIndex = getIndex(stackTop, nonTerminals); int inputIndex = getIndex(currentInput, terminals); if (stackIndex == -1 || inputIndex == -1) { printf("Error\n"); break; } int productionIndex = parsingTable[stackIndex][inputIndex]; if (productionIndex == -1) { printf("Error\n"); break; } else { printf("Use production: %c -> ", stackTop); switch (productionIndex) { case 1: printf("TE'\n"); break; case 2: printf("+TE'\n"); break; case 3: printf("ε\n"); break; case 4: printf("FT'\n"); break; case 5: printf("*FT'\n"); break; case 6: printf("(E)\n"); break; case 7: printf("id\n"); break; } top--; // Pop from the stack // Push production to the stack in reverse order switch (productionIndex) { case 1: stack[++top] = 'E'; stack[++top] = '\''; stack[++top] = 'T'; break; case 2: stack[++top] = 'E\''; stack[++top] = 'T'; stack[++top] = '+'; break; case 3: break; // ε, do nothing case 4: stack[++top] = 'T\''; stack[++top] = 'F'; break; case 5: stack[++top] = 'T\''; stack[++top] = 'F'; stack[++top] = '*'; break; case 6: stack[++top] = ')'; stack[++top] = 'E'; stack[++top] = '('; break; case 7: stack[++top] = 'id'; break; } } if (currentInput != '$') { inputIndex++; // Move to the next input symbol } } } int main() { char input[100]; // Get input from the user printf("Enter the input string (end with $): "); scanf("%s", input); // Add $ to the end of the input strcat(input, "$"); // Parse the input parseInput(input); return 0; }

Output:

1

Enter the input string (end with $): id$

Parsing Steps:

Stack: E Input: id$ Use production: id

Stack: E' Input: $ Use production: ε

Stack: Input: $ Accepted

2

Enter the input string (end with $): id+$

Parsing Steps:

Stack: Eⁿ┐ì┴ Input: id+$ Use production: id

Stack: E'┐ì┴ Input: +$ Use production: ε

Stack: Eⁿ┐ì┴ Input: $ Use production: E' -> ε

Accepted

3

Enter the input string (end with $): id+id$

Parsing Steps:

Stack: E∙⌂┼≡ Input: id+id$ Use production: id

Stack: T∙⌂┼≡ Input: +id$ Use production: FT'

Stack: F∙⌂┼≡ Input: +id$ Use production: id

Stack: T'∙⌂┼≡ Input: +id$ Use production: ε

Stack: E'∙⌂┼≡ Input: +id$ Use production: +TE'

Stack: T∙⌂┼≡ Input: id$ Use production: FT'

Stack: F∙⌂┼≡ Input: id$ Use production: id

Stack: T'∙⌂┼≡ Input: id$ Use production: ε

Stack: E'∙⌂┼≡ Input: id$ Use production: ε

Stack: T∙⌂┼≡ Input: $ Use production: ε

Stack: E'∙⌂┼≡ Input: $ Use production: ε

Stack: Accepted