Scribd
Upload
7 views6 pages

C Program for Predictive Parsing

This document contains a C program that implements a predictive parser using an LL(1) parsing table. It defines non-terminals, terminals, and a parsing table, and includes functions for parsing input strings based on these definitions. The program prompts the user for an input string and displays the parsing process, including stack and input state at each step.

Uploaded by

peddireddy1215
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
7 views6 pages

C Program for Predictive Parsing

This document contains a C program that implements a predictive parser using an LL(1) parsing table. It defines non-terminals, terminals, and a parsing table, and includes functions for parsing input strings based on these definitions. The program prompts the user for an input string and displays the parsing process, including stack and input state at each step.

Uploaded by

peddireddy1215
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

C Program to implement Predictive Parser

#include <stdio.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

const char *nonTerminals[] = { "E", "Q", "T", "R", "F" };


const char *terminals[] = { "i", "+", "*", "(", ")", "$" };

// Parsing Table: nonTerminal x terminal


const char *table[5][6] = {
// i + * ( ) $
{ "TQ", "", "", "TQ", "", "" }, // E
{ "", "+TQ", "", "", "e", "e" }, // Q
{ "FR", "", "", "FR", "", "" }, // T
{ "", "e", "*FR", "", "e", "e" }, // R
{ "i", "", "", "(E)", "", "" } // F
};

int getRow(char nonterminal) {


for (int i = 0; i < 5; i++) {
if (nonTerminals[i][0] == nonterminal)
return i;
}
return -1;
}

int getCol(char terminal) {


for (int i = 0; i < 6; i++) {
if (terminals[i][0] == terminal)
return i;
}
return -1;
}

int isTerminal(char c) {
return !(c >= 'A' && c <= 'Z');
}

void push(char c) {
stack[++top] = c;
}

char pop() {
return stack[top--];
}

char peek() {
return stack[top];
}
void printStack() {
for (int i = 0; i <= top; i++)
printf("%c", stack[i]);
}

void displayParseTable() {
printf("\nLL(1) Parsing Table:\n\n");
printf("%-5s", "");
for (int i = 0; i < 6; i++) {
printf("%-10s", terminals[i]);
}
printf("\n");

for (int i = 0; i < 5; i++) {


printf("%-5s", nonTerminals[i]);
for (int j = 0; j < 6; j++) {
if (table[i][j][0] == '\0')
printf("%-10s", "-");
else
printf("%-10s", table[i][j]);
}
printf("\n");
}
printf("\n");
}

void predictiveParse(const char *input) {


int i = 0;
char a, X;

push('$');
push('E');

printf("%-20s%-20s%-20s\n", "Stack", "Input", "Action");

while (1) {
printStack();
printf("%20s", input + i);

X = peek();
a = input[i];

if (X == '$' && a == '$') {


printf("%20s\n", "Accepted");
break;
}

if (isTerminal(X)) {
if (X == a) {
pop();
i++;
printf("%20s\n", "Match");
} else {
printf("%20s\n", " Error: Terminal mismatch");
break;
}
} else {
int row = getRow(X);
int col = getCol(a);

if (row == -1 || col == -1) {


printf("%20s\n", " Error: Invalid symbol");
break;
}

const char *production = table[row][col];

if (production[0] == '\0') {
printf("%20s\n", "Error: No rule");
break;
}

printf(" %c -> %s\n", X, strcmp(production, "e") == 0 ? "ε" : production);


pop();

if (strcmp(production, "e") != 0) {
int len = strlen(production);
for (int k = len - 1; k >= 0; k--) {
push(production[k]);
}
}
}
}
}

int main() {
char input[MAX];

printf("Enter input string (use 'i' for id, no spaces): ");


scanf("%s", input);
strcat(input, "$");

displayParseTable();
predictiveParse(input);

return 0;
}

You might also like