parson

I believe left recursion is a frill, because you don't really miss it when you write a recursive-descent parser. You just write the actions a little bit differently for a left-associative operator than a right-associative one, with a loop instead of recursion. Since PEGs are supposed to be the theory abstracting recursive-descent parsers, I would want semantic actions to be added to the theory in a way that can handle both kinds of operators, instead of complicating the parsing algorithm with left recursion. Here's an example of how that can work: https://github.com/darius/parson/blob/master/eg_calc.py -- the '-' operator associates left, while the '^' op associates to the right. (Like Ohm, my system separated the semantic actions from the grammar: .bind(operator) on line 24. It's older than Ohm, actually, but unfinished and undocumented

The clearest case of this I've seen was Norvig's Udacity CS212 class: in the third week there were despairing and even angry posts to the forum about his code to generate strings from regular expressions. (Here's a version of it, with small changes plus a regex parser, since Udacity started requiring login: https://github.com/darius/parson/blob/master/eg_regex.py) But some people have also told me that was a great learning experience -- they spent many hours understanding this half page of code, and felt they'd really grown once they'd mastered it.