1

I recently came across parsers in the systems software course. I read that, to make the top down parsing using backtracking efficient, it is needed to eliminate the left recursion in the production rules (for eliminating the infinite looping). For eliminating the left recursion we replace the production rule with left recursion with a pair of production rules using another non-terminal, this way:

if the existing rule is:

A -> Aa|b

then it is replace with:

 A -> bR
 R -> aR | epsilon

Wouldn't such a rule cause right recursion? which in turn can cause infinite looping? Can anyone tell me why this is done?

Millennial
  • 79
  • 7
  • 2
    With right recursion, at least one token is consumed before the recursive call. So you can't get an infinite loop; you will run out of input. With left recursion, the recursive call happens before any input has been consumed. So it can just keep going and going and going (until the stack overflows). – rici Mar 23 '22 at 07:48
  • @rici what does at least one token is consumed before recursive call and running out of input mean? – Millennial Mar 23 '22 at 09:12
  • @sepp2k The answer partially makes sense, but i dont understand why it's not possible to try b for the new position in left recursion: `A ->Aa | b` just like how they have mentioned that in right recursion: `A->aA | b` we can try b in the new position – Millennial Mar 23 '22 at 13:13
  • @Millennial `b` is tried in the current position, not a new one, but either way it is only tried if the left side of the `|` fails. `a A` will fail when there is no `a` at the current position or if there is an `a` at the current position, but `A` does not match at the *next* position. `Aa` never fails because keeps checking whether `A` matches at the *current* position infinitely. It never gets to checking whether there's an `a` anywhere. – sepp2k Mar 23 '22 at 14:18
  • 2
    The left- and right-recursive examples you give are for different languages. `A -> Aa | b` matches `b`, `ba`, `baa`, `baaa` etc. `A -> aA | b` matches `b`, `ab`, `aab`, `aaab`, etc. Both of them involve repeated matches of `A`, but the right-recursive one matches each `A` at a different location (and hence must terminate) whereas the left-recursive one matches all of the `A`s at the same location (which is the current input position). "Consuming" input means precisely that: moving the input position over a matched symbol ("token"). – rici Mar 23 '22 at 16:05
  • 2
    No-one is saying that the left-recursive grammar cannot be parsed. Obviously it can be. But it cannot be parsed with the top-down algorithm. It's easy to write a recursive descent parser, or to emulate its operation on a large piece of paper. Doing that will give you much more insight than trying to read SO answers (or comments). As an old prof of mine once said, to learn algorithms you need to use your hands. – rici Mar 23 '22 at 16:09

0 Answers0