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)
