4 ms·

Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is t

Many PEG-based parser generators do not support left recursion — requiring grammar authors to use repetition or right recursion instead. But left recursion is the most straightforward way to express left associative operators, which is why left recursion is supported by Ohm. Does Ohm have any limitation with regard to left recursion? The last time I checked there was a paper by Warth et al. [1] extending PEG Packrat Parsers to handle left recursion but later a paper by Tratt [2] pointed out a flaw in that algorithm and only managed to fix the problem for a limited subset of grammars. [1] http://www.vpri.org/pdf/tr2007002_packrat.pdf http://www.vpri.org/pdf/tr2007002_packrat.pdf [2] http://tratt.net/laurie/research/pubs/papers/tratt__direct_left_recursive_parsing_expression_grammars.pdf http://tratt.net/laurie/research/pubs/papers/tratt__direct_l...

pdubroy 9y ago
Ohm implements the same algorithm described in [1] -- Alex Warth (the author of that paper) created Ohm. We're understand the complaint in [2], but we strongly disagree with Laurie's claim that these are "incorrect" parses. He proposes a different way of handling left recursion, which is just that -- different. You can find a more thorough discussion here: https://github.com/harc/ohm/issues/55 https://github.com/harc/ohm/issues/55
abecedarius 9y ago
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 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 -- just something I've been using in my own projects.) Of course, another reason to support left recursion is to let you use a grammar someone else has already written with left-recursion baked in, without having to mess with it.

pdubroy 9y ago

Ohm implements the same algorithm described in [1] -- Alex Warth (the author of that paper) created Ohm. We're understand the complaint in [2], but we strongly disagree with Laurie's claim that these are "incorrect" parses. He proposes a different way of handling left recursion, which is just that -- different. You can find a more thorough discussion here: https://github.com/harc/ohm/issues/55 https://github.com/harc/ohm/issues/55

abecedarius 9y ago

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 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 -- just something I've been using in my own projects.) Of course, another reason to support left recursion is to let you use a grammar someone else has already written with left-recursion baked in, without having to mess with it.