27

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

Simon Johnson
  • 7,802
  • 5
  • 37
  • 49
Benjamin Confino
  • 2,344
  • 3
  • 26
  • 30

2 Answers2

33

consider:

A ::= A B

the equivalent code is

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

see the infinite recursion?

cadrian
  • 7,332
  • 2
  • 33
  • 42
22

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.

BCS
  • 75,627
  • 68
  • 187
  • 294
  • First time I've seen that, I always saw advice to use a new non-terminal, usually called A' – Benjamin Confino May 11 '09 at 20:14
  • Well some BNF based tools won't allow () groups so you end up stuck with the new rule solution. I'm kinda partial to the form I proposed because my parser generator needs to do the action transformation as well so it's a lot easier to make it work without a new rule. – BCS May 11 '09 at 20:20
  • 1
    This doesn't really answer the question. Would be better as a comment. – Kristopher Johnson Jan 24 '11 at 13:10
  • @Kristopher: Check the date, IIRC the comment size limit was way to small for this back then. – BCS Jan 24 '11 at 15:49
  • I ended up figuring this out myself by going over the code in my head, glad to see a sort of confirmation I got it right! – Lennard Fonteijn Oct 17 '13 at 10:56