0% found this document useful (0 votes)
10 views2 pages

Predictive Parser Program in C

The document is a C program that constructs a predictive parsing table for a given grammar. It defines production rules, first sets, and follow sets, and populates a table based on these definitions. The program outputs the grammar and the resulting predictive parsing table to the console.

Uploaded by

Ridya Gupta
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
10 views2 pages

Predictive Parser Program in C

The document is a C program that constructs a predictive parsing table for a given grammar. It defines production rules, first sets, and follow sets, and populates a table based on these definitions. The program outputs the grammar and the resulting predictive parsing table to the console.

Uploaded by

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

#include<stdio.

h>
#include<string.h>

char prol[7][10] = {"s", "A", "A", "B", "B", "C", "C"};


char pror[7][10] = {"Aa", "Bb", "Cd", "aB", "@", "Cc", "@"};
char prod[7][10] = {"s-->A", "A-->Bb", "A-->Cd", "B-->aB", "B-->@", "C-->Cc", "C--
>@"};
char first[7][10] = {"abcd", "ab", "cd", "a@", "@", "c@", "@"};
char follow[7][10] = {"$", "$", "$", "a$", "b$", "c$", "d$"};
char table[5][6][10];

int numr(char c) {
switch (c) {
case 'S': return 0;
case 'A': return 1;
case 'B': return 2;
case 'C': return 3;
case 'a': return 0;
case 'b': return 1;
case 'c': return 2;
case 'd': return 3;
case '$': return 4;
}
return 2; // Default case
}

int main() {
int i, j, k;

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


for (j = 0; j < 6; j++)
strcpy(table[i][j], " ");

printf("\n The following is the predictive parsing table for the following
grammar:\n");
for (i = 0; i < 7; i++)
printf("%s\n", prod[i]);

printf("\n Predictive parsing table is:\n ");

for (i = 0; i < 7; i++) {


k = strlen(first[i]);
for (j = 0; j < 10; j++)
if (first[i][j] != '@')
strcpy(table[numr(prol[i][0]) + 1][numr(first[i][j]) + 1],
prod[i]);
}

for (i = 0; i < 7; i++) {


if (strlen(pror[i]) == 1) {
if (pror[i][0] == '@') {
k = strlen(follow[i]);
for (j = 0; j < k; j++)
strcpy(table[numr(prol[i][0]) + 1][numr(follow[i][j]) + 1],
prod[i]);
}
}
}
strcpy(table[0][0], " ");
strcpy(table[0][1], "a");
strcpy(table[0][2], "b");
strcpy(table[0][3], "c");
strcpy(table[0][4], "d");
strcpy(table[0][5], "$");
strcpy(table[1][0], "S");
strcpy(table[2][0], "A");
strcpy(table[3][0], "B");
strcpy(table[4][0], "C");

printf("\
n-----------------------------------------------------------------------------\n");
for (i = 0; i < 5; i++) {
for (j = 0; j < 6; j++) {
printf("%s\t", table[i][j]);
}
printf("\n");
}

printf("---------------------------------------------------------------------------
--\n");

return 0;
}

Common questions

Powered by AI

Challenges include handling empty productions ('@'), multiple productions for the same non-terminal, and ensuring all grammar rules are incorporated. Errors in converting symbols to table indices could lead to missing or incorrect entries. These can be mitigated by thorough validation of first and follow set computations, rule consistency checks, and confirming that all expected table entries are populated. Additional debugging and error logging can help identify mismatches and overlooked rules during table construction.

The program iterates over each production, filling the parsing table based on the first and follow sets. For each production's first set, entries are added to the table unless the first character is '@'. If the production contains '@', indicating an epsilon production, entries based on the follow set are added instead. The numr function maps the non-terminal and terminal characters to appropriate indices in the table, determining where each production rule is stored.

The 'numr' function converts grammar symbols into index values to facilitate mapping non-terminals and terminals to appropriate positions in the parsing table. This conversion is necessary to match the grammar symbols with their corresponding slots in the predictive parsing table. By providing a consistent mapping between symbols and their indices, 'numr' ensures that production rules are stored in correct table cells.

The 'first' array stores the first set for each production in the grammar, which consists of terminals that begin the strings derivable from a non-terminal. The 'follow' array stores the follow set, which consists of terminals that can immediately follow a non-terminal in some 'sentential' form. These sets are used to construct the predictive parsing table, allowing the parser to anticipate and resolve choices based on input tokens.

The described method might struggle with grammars that are not LL(1), i.e., those that require lookahead beyond a single token, due to ambiguities or left recursion. Such grammars might lead to conflicts in the parsing table or require complex adjustments that aren't easily handled by this setup. To address these limitations, the grammar may need transformation into an equivalent LL(1) form or alternative parsing strategies that support more complex lookaheads and resolve ambiguities.

The program utilizes the 'numr' function to derive indices for non-terminals and terminals based on the characters in the productions, first, and follow arrays. This conversion maps non-terminals to specific rows and terminals to columns in the table. It combines these indices with logic to populate cells corresponding to the derivable first and follow sets of each production, ensuring each rule's correct entry in the parsing table.

Efficacy can be verified by testing the parsing table against various input strings to ensure that all valid strings are correctly parsed while invalid ones are rejected. This can involve designing test cases that cover diverse scenarios, including edge cases of the grammar. Additionally, reviewing whether generated tables conform to theoretical expectations and cross-verifying with manual or alternative computationally generated tables would ensure correctness. Automated tools or scripts might be employed for extensive testing and validation.

Epsilon productions are handled by filling the respective parsing table entry based on the follow set instead of the first set. When the production is precisely '@', the table entries for each symbol in the follow set of the non-terminal are populated with the epsilon production rule. This ensures that the parser can correctly complete derivations when non-terminals can derive an empty string.

The parsing table is initialized with empty strings to ensure all entries are explicitly defined before use, preventing accidental utilization of undefined or garbage values. This setup allows the table to correctly reflect the grammar's rules in its defined locations and is critical for robust and error-free population of the parsing table with valid production rules.

The predictive parsing table is pivotal for implementing a recursive descent parser that performs top-down parsing without backtracking. It acts as a decision-making guide for selecting the appropriate grammar rule based on the current input and parsing state, allowing the parser to efficiently anticipate and apply productions. The table helps automate the syntactic analysis of an input string, ensuring correctness of parse operations against a defined grammar.

You might also like