3 ms·
In the second grammar, additive-expression2 is still contains a recursive call in the right-hand term, so it would produce a parse tree that's right associative
by caditinpiscinam 3y ago
In the second grammar, additive-expression2 is still contains a recursive call in the right-hand term, so it would produce a parse tree that's right associative. For example, given the string `A - B - C` you'd get:
(additive-expression
(multiplicative-expression A)
(additive-expression2
-
(multiplicative-expression B)
(additive-expression2
-
(multiplicative-expression C)
<null>
)
)
)
Which corresponds to the right-associative expression `(A - (B - C))`. You could do some post-processing on the results to invert it and make it left-associative, but I don't think the two grammars are equivalent.
- owlstuffing 3y agoThe 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.