CODEWITHSUNDEEP
parsingtheory
Benjamin Confino
Benjamin Confino

Reputation: 2374

Why can't a recursive-descent parser handle left recursion

Could someone please explain to me why recursive-descent parsers can't work with a grammar containing left recursion?

Upvotes: 27

Views: 5705

Answers (2)

BCS
BCS

Reputation: 78635

For whoever is interested

 A ::= A B | A C | D | E

can be rewritten as:

 A ::= (D | E) (B | C)*

The general form of the transformation is: any one of the non left recursive disjuncts followed by any number of the left recursive disjuncts without the first element.

Reforming the action code is a bit trickery but I thing that can be plug-n-chug as well.

Upvotes: 22

cadrian
cadrian

Reputation: 7376

consider:

A ::= A B

the equivalent code is

boolean A() {
    if (A()) {
        return B();
    }
    return false;
}

see the infinite recursion?

Upvotes: 33

Related Questions