4 ms·
Expression parsing without left recursion can be straightforward: https://github.com/darius/parson/blob/master/eg_calc.py https://github.com/darius/parson/blob/
by abecedarius 9y ago
Expression 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.