- Kaspar Schiess
- 2011-03-08 @ 08:41
parslet has now not one, but two attempts going on at allowing left
recursive grammars using Warths et al.'s algorithm.  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
. I find the concerns he raises very valid and aligning with my first
But all is not lost. Luckily  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!
 *Packrat Parsers Can Support Left Recursion*, Alessandro Warth,
>> James R. Douglass, and Todd Millstein (2008)
 *Direct Left-Recursive Parsing Expression Grammars*, Laurence Tratt