librelist archives

« back to archive

Left recursion

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)