Search code examples
parsingformal-languagespegleft-recursionpegjs

How to resolve left recursions in PEG

The problem is, that PEGs (parsing expression grammars) do not allow left-recursive rules. I have read the available answers on this topic, however problem specific (like this one) or quite simple (e.g. x = symbol:(x '.')).

I've created the following very simple grammar to illustrate the problem

EXAMPLE = x+

x = symbol:(x y* / x y z)

y = symbol:('.' x)
z = symbol:('$')

This grammar can be tested using the PEG.js parser generator.

Could someone who is "fluent" in formal languages describe how one would rewrite this rule / set of rules to PEG? Or is there a general approach / algorithm that allows one to resolve left recursions?

Edit: I just found this Wikipedia page, which describes a way to remove left recursions, I will look into it and try to apply it to the grammar shown above.

Solution

  • A PEG parser is essentially LL(*) with infinite lookahead and ordered choice. Your grammar must present one or more choices for the very next symbol, to allow the parser to choose.

    Your grammar looks broken, but if I read your intent correctly it has groups of dots and a dollar at the end of each group. So it goes something like:

    x -> ('.'+ '$')+

    There are formal rewrite algorithms, but mostly it's enough to just figure out 'what could come next?' and 'what comes after that?' and 'how does it repeat?'.