4 ms·

Yes, however there is a much simpler approach to removing left recursion. For example, a left recursive additive expression grammar: additive-expression

Yes, however there is a much simpler approach to removing left recursion. For example, a left recursive additive expression grammar: additive-expression <multiplicative-expression> <additive-expression> + <multiplicative-expression> <additive-expression> - <multiplicative-expression> Left recursion removed from this grammar is: additive-expression <multiplicative-expression> <additive-expression2> additive-expression2 + <multiplicative-expression> <additive-expression2> - <multiplicative-expression> <additive-expression2> <null> Then implement additive-expression2 as a simple loop. No need for Pratt and implementation follows more closely with BNF.

a_e_k 3y ago
Yep. And whenever I've implemented a recursive-descent parser and dealt with left-associative operators, I've just inlined the equivalent of additive-expression2 and the loop. E.g.: def parseAddExpr(): parseMultExpr() while peekToken in ["+", "-"]: consumeToken() parseMultExpr() Honestly, I really like recursive-descent parsing, even for expressions. It's very straightforward once you've learn a few simple patterns like that. Decently large precedence hierarchies (15-20) don't bother me; I'll typically just number the levels rather than use names like "term", "factor", "additive", or "multiplicative". It can get a little verbose, yes, but it's easy to write and skim through. (Golang-like from what I've read, though I'm not a user of Golang.) But I also find it scales better once you start adding things like ternary expressions, function calls, and type casts -- things that aren't just simple binary operators. Handling those feels a lot less clean to me with Pratt, precedence climbing, shunting yard, etc. One main downside that I'll admit to recursive descent though is that it's a bit harder to have a language with user-defined operators. I don't like those much, though, so that's not much of a loss to me.
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 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 ago
    I 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.

a_e_k 3y ago

Yep. And whenever I've implemented a recursive-descent parser and dealt with left-associative operators, I've just inlined the equivalent of additive-expression2 and the loop. E.g.: def parseAddExpr(): parseMultExpr() while peekToken in ["+", "-"]: consumeToken() parseMultExpr() Honestly, I really like recursive-descent parsing, even for expressions. It's very straightforward once you've learn a few simple patterns like that. Decently large precedence hierarchies (15-20) don't bother me; I'll typically just number the levels rather than use names like "term", "factor", "additive", or "multiplicative". It can get a little verbose, yes, but it's easy to write and skim through. (Golang-like from what I've read, though I'm not a user of Golang.) But I also find it scales better once you start adding things like ternary expressions, function calls, and type casts -- things that aren't just simple binary operators. Handling those feels a lot less clean to me with Pratt, precedence climbing, shunting yard, etc. One main downside that I'll admit to recursive descent though is that it's a bit harder to have a language with user-defined operators. I don't like those much, though, so that's not much of a loss to me.

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 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 ago
  I 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.