### Left recursion

- From:
- Kaspar Schiess
- Date:
- 2011-03-08 @ 08:41

Hi Everyone,
parslet has now not one, but two attempts going on at allowing left
recursive grammars using Warths et al.'s algorithm. [1][2][3] The short
summary of these efforts for me is that the losses outweigh the gains:
- writing grammars is now not so intuitive anymore. Top-down aligns
well with method call semantics, left recursion does not.
- The algorithm is not very elegant IMHO. It makes a mess out of
parslets clean internals.
- One largely unsolved difficulty is the construction of proper tree
output from such (left recursive) rules. I suspect that we have some
trouble lurking there.
- And lastly: The algorithm is also inherently flawed, as exposed by
[4]. I find the concerns he raises very valid and aligning with my first
point.
But all is not lost. Luckily [4] also exposes a way of saving the day,
using grammar transformations. Since parslet doesn't have semantic
actions associated with the grammar, we might even have an easy game
lurking there - perhaps going the right associative route and then using
a tree transform.
But I haven't really finished investigating! If you come up with
something interesting (and elegant) - please show it to us all!
kaspar
[1] https://github.com/kschiess/parslet/pull/30
[2]
https://github.com/kschiess/parslet/tree/110311-left_recursion_warth_et_al-experiment
[3] *Packrat Parsers Can Support Left Recursion*, Alessandro Warth,
>> James R. Douglass, and Todd Millstein (2008)
[4] *Direct Left-Recursive Parsing Expression Grammars*, Laurence Tratt
(2010)