fool2fish/dragon-book-exercise-answers

Quick question for solution to exercise 2.4 (2.4.md)

PritishC opened this issue · 0 comments

Hey, thanks for the solutions you've spent so much time to put on GitHub for us. Newbie dragon book reader here, had a quick question for this exercise.

Doesn't S -> S ( S ) S | ε suffer from being left-recursive (S -> Sα | β, where α = ( S ) S, and β = ε)? The text mentioned that we can't write a recursive-descent parser for such grammars (not without removing left recursion). I noticed that in the code for this you start with match("("), which skips the S at the start. I wanted to know the logic behind that, I'm unable to get how it came about. I must be missing something.

I tried to remove left recursion the way they did in the text -:

S -> βR = R // because beta is null
R -> ( S ) S | ε

This gives the code -:

void S() { R(); }
void R() {
    if (lookahead == "(") {
        match("("); S(); match(")"); S(); R();
    } // doing nothing means applying R -> ε
}

I have no way of knowing if this way is correct either. I think there also has to be some place where we report syntax errors. I'd be grateful for any insight.