Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 601
Shraddha Avatar asked Oct 19 '22 08:10

Shraddha


1 Answers

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.

like image 76
sepp2k Avatar answered Oct 21 '22 14:10

sepp2k