4 ms·
The technique I use is widely known and published. Generally, any left associative production: A → Aα | β Can be refactored as right associative: A → βA’
by owlstuffing 3y ago
The technique I use is widely known and published. Generally, any left associative production:
A → Aα | β
Can be refactored as right associative:
A → βA’
A’ → αA’ | ∈
This is a cornerstone of recursive descent parsers.
- caditinpiscinam 3y agoI get what you're saying: the grammars are equivalent in the sense that they match the same language. Maybe "equivalent" was the wrong word to use on my part. My point is that this refactoring doesn't actually give us an implementation that solves the issue of left-associativity. As you said, you still need to introduce some sort of loop to do this. It doesn't have to be complex, but it is different from the right-associative case where expressions are built up directly through recursion. My argument is that once you introduce explicit iteration, you're no longer really doing recursive descent, you're doing Pratt or shunting-yard or something else.