3 ms·

I’ve always considered recursive descent easier to understand and maintain than Pratt. Shrug.

caditinpiscinam 3y ago
Even with recursive decent, you still need a strategy to deal with left-associative binary operators. This is where Pratt parsing comes in: not to replace recursive descent, but to supplement it.
- owlstuffing 3y ago
  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.
sneed_chucker 3y ago
Recursive descent is great for parsing most of an algol-like programming language. Once you get into expressions, you'll really want to do precedence climbing or Pratt parsing to get things working correctly. This assumes that you want PEMDAS-like operator precedence in the first place. It does seem like a waste once you've implemented it and realize how little it's actually utilized by most code. Maybe the Lisp and forth people have a point...

Even with recursive decent, you still need a strategy to deal with left-associative binary operators. This is where Pratt parsing comes in: not to replace recursive descent, but to supplement it.

owlstuffing 3y ago
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.

sneed_chucker 3y ago

Recursive descent is great for parsing most of an algol-like programming language. Once you get into expressions, you'll really want to do precedence climbing or Pratt parsing to get things working correctly. This assumes that you want PEMDAS-like operator precedence in the first place. It does seem like a waste once you've implemented it and realize how little it's actually utilized by most code. Maybe the Lisp and forth people have a point...