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 then 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, F? does nothing if F doesn't match, and in that case execution proceeds to call E on the same input and thereby 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.

Indirect Left-Recursion

We've seen that direct left-recursion happens when E calls into itself on the same input. Indirect left-recursion happens when E calls any number of other rules, that at one or more points call back into E with the same input. For example:

E <- F '+n' / 'n'
F <- G H / J
J <- K / E L

This causes this left-recursive cycle: E <- F <- J <- E.