CODEWITHSUNDEEP
parsingcompiler-constructionleft-recursion
Shraddha
Shraddha

Reputation: 99

Why do right recursive parsers not loop infinitely?

Left recursion will make the parser go into an infinite loop. So why does the same not happen with right recursion?

Upvotes: 8

Views: 2086

Answers (2)

Chris Smith
Chris Smith

Reputation: 2645

If you're puzzled by the lack of symmetry, another way of looking at this is that left recursion causes problems for recursive descent parsers is because we typically parse languages from left to right. That means that if a parser is left-recursive, then the recursive symbol is the first one that's tried, and it's tried in the same state as the parent rule, guaranteeing that the recursion will continue infinitely.

If you really think about it, there's no fundamental reason why we parse languages from left-to-right; it's just a convention! (There are reasons, such as that it's faster to read files from disk that way; but those are consequences of the convention.) If you wrote a right-to-left recursive descent parser, which started at the end of the file and consumed characters from the end first, working backwards to the beginning of the file, then right recursion is what would cause problems, and you would need to rewrite your right-recursive grammars to be left-recursive before you can parse them. That's because if you're handling the right symbol first, then it's the one that's parsed with the same state as the parent.

So there you are; symmetry is preserved. Just as left-to-right recursive descent parsers struggle with left recursion, similarly right-to-left recursive descent parsers struggle with right recursion.

Upvotes: 2

sepp2k
sepp2k

Reputation: 370465

In a recursive descent parser a grammar rule like A -> B C | D is implemented by trying to parse B at the current position and then, if that succeeds, trying to parse C at the position where B ended. If either fail, we try to parse D at the current position¹.

If C is equal to A (right recursion) that's okay. That simply means that if B succeeds, we try to parse A at the position after B, which means that we try to first parse B there and then either try A again at a new position or try D. This will continue until finally B fails and we try D.

If B is equal to A (left recursion), however, that is very much a problem. Because now to parse A, we first try to parse A at the current position, which tries to parse A at the current position ... ad infinitum. We never advance our position and never try anything except A (which just keeps trying itself), so we never get to a point where we might terminate.

¹ Assuming full back tracking. Otherwise A might fail without trying D if B and/or C consumed any tokens (or more tokens than we've got lookahead), but none of this matters for this discussion.

Upvotes: 7

Related Questions