3 ms·
Yeah, I agree. When writing this I spent a lot of time keeping track of LR states to decide how to split things up into functions, but in a recursive descent pa
by Rusky 9y ago
Yeah, I agree. When writing this I spent a lot of time keeping track of LR states to decide how to split things up into functions, but in a recursive descent parser that's already decided by the grammar.
I can see myself using it for expression parsing, though, since that's almost inherently left-recursive. I usually use top-down operator precedence (AKA pratt parsing) for that, but recursive ascent might simplify it in some ways.
- abecedarius 9y agoExpression parsing without left recursion can be straightforward: https://github.com/darius/parson/blob/master/eg_calc.py https://github.com/darius/parson/blob/master/eg_calc.py A left-associative operator means a Kleene star in the grammar, while a right-associative operator means right-recursion. I think the common view that it's left-recursive is just a weakness of the most common scheme for semantic actions. (I mean, yes, if you need to go through a parse tree first then the tree needs to be left-recursive -- but it seems simpler not to do that.)
- Rusky 9y agoThe idea that it's left-recursive is not changed by the existence of top-down operator precedence, or kleene stars, or right recursion. And it's not a weakness, either- just one way to think about the problem which happens to map fairly naturally to how people think about expressions.