Left Recursion

Traditional PEG does not support left-recursion in grammars. Pegged does support all sorts of left-recursion since v0.3.0, so you don't need to worry about it. The remainder of this page will explain what left-recursion is, and how Pegged detects and deals with it.

Direct Left-Recursion

Suppose we wanted to match strings like n, n+n, n+n+n, etc. with a grammar like

E <- E '+n' / 'n'

Because the first element of this rule E is itself E, a naive implementation would construct a parser function that would call itself as the first instruction, thereby recursing immediately without doing anything and without ever to return, until you run out of stack space and crash.

Just changing the order of options is not an option, because the first option would always only match the first n, and no attempts would be made to match the rest of the input.

Hidden Left-Recursion

A more subtle form of the same problem is that the recursive element is hidden behind other elements that can succeed without consuming input, like an optional:

E <- F? E '+n' / 'n'

Even though F is tried first, it produces nothing if it doesn't match, and execution falls into the same trap.

Hidden left-recursion can even be more obscured. Consider this:

E <- F E '+n' / 'n'
F <- A B C / D*

Because D* matches the empty string, F succeeds without consuming input, and hides left-recursion in E. You can imagine that there is no end to how deep left-recursion can be hidden in your grammar.