Recursive descent parser C program

Question

I have the following grammar and need to write a recursive descent parser in C

E->E+E|E*E|(E)|i

I used left-factoring to get the following grammar

E->EX|Y
X->+E|*E
Y->(E)|i

Now, I eliminated left recursion to get the following grammar

E->YE`
X->+E|*E
Y->(E)|i
E`->XE`|e

e denotes epsilon

Now I have written C program for this grammar but I get a segmenation fault

#include<stdio.h>
static char c[10];
int j=0;
int main()
{
    printf("Enter a string\n");
    scanf("%s",c);
    E();
    if(c[j]=='$')
        printf("Valid string\n");
    else
        printf("Invalid string\n");
    return 0;
}
E()
{
    Y();
    Eprime();
    return;
}
X()
{
    if(c[j]=='+')
    {
        j++;
        E();
    }
    else if(c[j]=='*')
    {
        j++;
        E();
    }
    return;
}
Y()
{
    if(c[j]=='(')
    {
        j++;
        E();
        if(c[j]==')')
            j++;
    }
    else if(c[j]=='i')
        j++;
    return;
}

Eprime()
{
    X();
    Eprime();
    return;
}

Sam Harwell Sam Harwell · Accepted Answer · 2013-03-15T17:43:12

In your implementation, you moved the ε handling from Eprime() to X():

Eprime() does not allow ε directly
X() does allow matching ε

This results in a stack overflow for the following sequence when trying to match ε with Eprime:

Eprime calls X, which matches ε
Eprime always calls Eprime (guaranteed stack overflow if Eprime is ever called)

Recursive descent parser C program

1 Answers