5 ms·

There is a part of me that feels we should just forget that LR ever existed and insist on LL(k) for k <= 2 for all new languages. The supposed expressivity bene

by norir 2y ago

There is a part of me that feels we should just forget that LR ever existed and insist on LL(k) for k <= 2 for all new languages. The supposed expressivity benefits are not worth the complexity cost in my not so humble opinion. For me, the best approach is to write the grammar in a dsl that checks that it is unambiguous and in LL(k) and then implement by hand with recursive descent.

marcosdumay 2y ago
Well, IMO, but you write a parser only a couple of times for each language, but you read code all the time. So, anything that makes code easier to read is a must. That includes the extra expressiveness of an LR grammar.
- mhh__ 2y ago
  In 2012 yes, but these days having grammars that lots of tools can parse and output easily is a boon for tooling.
- vidarh 2y ago
  I agree there are a few places like this, but they're usually solved when you want an LL parser for as much as possible of the language by either making them part of the tokenization or by "escaping" a small subset of the grammar. I wish that language designers (looking at you, Ruby - as much as I love using Ruby, the grammar is an abomination) would at least try to stick to LL as much as possible, and consciously, carefully and in a limited fashion "escape" into LR for as small subsets as possible. Break rules if it actually helps developers, sure, but it'd be nice if people tried to make the weird bits as tiny as possible... EDIT: Also, in practice this is often what we end up doing when we write recursive descent anyway, only in a less than formal way. It'd be nice if more tooling let us write grammars that default to LL w/checking, but let you insert clearly delineated exceptions.
  - marcosdumay 2y ago
    Oh, I do agree with that! A language should be LL as much as possible. And also depend on the parsed data as little as possible. Stuff like C's variable declaration must be avoided. But I don't think either of those rules can be made universal. Some language for expressing exceptions would be great.
- haberman 2y ago
  Do you know of any particularly readable constructs that are possible with LR but incompatible with LL? My general opinion is that any constructs that confuse a parser will also confuse a human.
  - marcosdumay 2y ago
    Operators with precedence rules. And given the modern idea of "everything is either an identifier or an operator", precedence became very important.
    - haberman 2y ago
      Operators with precedence rules frequently appear in top-down parsers. I agree that pure-LL form doesn't make this easy, but most languages I have seen use Pratt parsers that allow precedence parsing within a top-down framework. It doesn't require full LR.
      - Rusky 2y ago
        Pratt parsing is essentially hand-written LR. It's certainly bottom-up in the same way, despite Pratt's paper title. (I went into more depth on this a few years ago: https://www.abubalay.com/blog/2021/12/31/lr-control-flow https://www.abubalay.com/blog/2021/12/31/lr-control-flow)
        chubot 2y ago
        Hm I wouldn't call it bottom up -- I would say it's top down, but you consult a table of integers to decide where to recurse. I would even call it a variant of recursive descent, which is top-down. In plain recursive descent, you often choose where to recurse based on the first token (e.g. if while for). In Pratt, you choose based on a table indexed by the second operater token. You can have an an entire arbitrary length subexpression before the "second token", but it is still resolved "eagerly". e.g. consulting the loop here - https://github.com/andychu/pratt-parsing-demo/blob/master/tdop.py#L212 https://github.com/andychu/pratt-parsing-demo/blob/master/td... I skimmed over your post, but I don't really see the bottom-up argument. I guess I could concede that it's neither top down nor bottom up, but I don't see the argument for being bottom up. And maybe this is just a taxonomy thing, which doesn't matter in practice. It could be understood both ways -- I don't think Vaughan Pratt was mistaken when he understood it a certain way :) --- "where to recurse" is basically choosing the parent's production before its children -- that's most similar to top down If you choose the child's production before its parent, then that's LR / bottom-up (using Haberman's explanation - https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demys...) May also be relevant: https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/04/22.html https://www.oilshell.org/blog/2017/04/22.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... I believe some people claimed that Dijikstra is bottom-up and Pratt is top down. That has a certain nice symmetry to it, but I'm not sure it's true :) Dijikstra does use an explicit stack and Pratt uses the call stack -- maybe that is how I'd put it.
dbcurtis 2y ago
I tend to agree. Having done a bunch of DSL's over the years, and becoming extremely fluent with Bison+FLEX, I have to say that a hand-written LL parser with a couple of mutually recursive table-driving functions to parse expressions via precedence climbing is the way to go. Precedence climbing (or I think it is also called Pratt parsing?) is super simple and flexible. But the BIG bonus is in error reporting, and let's face it, most of the user interaction with your parser is with the error messages, otherwise it is push 'enter' and forget. Getting a reasonable error message out of an LR parser is about as much fun as poking yourself in the eye repeatedly with a sharp stick. With LL, you know what structure you are trying to build... with LR, you have to rummage around in parse stack looking for obscure clues.
- Calavar 2y ago
  I am aware this is an unpopular opinion, but I think the idea that recursive descent is inherently better suited to error reporting than table-driven LR is massively cargo-culted. You can handcraft error messages for an LR parser if you overspecify the grammar, meaning that you don't just write productions for the actual language; you also write productions for likely errors and have the predicates for those productions report your handcrafted error message. I'm guessing that a lot of people's first impression of that will be "That's insane, are you seriously suggesting writing two grammars in one?" But that's exactly what you do when you build custom error reporting code into a recursive descent parser. It's just less obvious because the code is procedural instead of declarative.
  - ckcheng 2y ago
    That's a very interesting way of looking at errors. Wouldn’t the grammar of errors have to also be LR? Doesn’t that limit the kind of errors you can report?
    - Calavar 2y ago
      Yes, it does have to be LR. Which can be a real PITA if you're working with a restrictive subset of LR, like LALR. But there are other options too. LR(1) is pretty powerful, and GLR even more so.
o11c 2y ago
I've always been hesitant about LL(1) since it requires a hack for something as common as expression-parsing, whereas LR is fine. Note that the linked article is misleading about LR having a problem with right-recursion: it only affects (data) stack depth, rather than breaking the machine like the LL problem. Still, LL and LR have common ground against the heresy of backtracking at least. I've never met a sane grammar that's not LALR(1). It's unfortunate that LALR(1) is such a leap of complexity beyond SLR(1), which is not practical for real languages. I imagine that LL(1) "mostly" works after the expression hack - what's your particular motivation for LL(2)? A lot of weird grammars lead to code that's hard to parse for humans. (Note also that, for languages (Python, Javascript, etc.) that lack an efficient `switch` statement, table-based is likely to beat function-call-based code)
- ufo 2y ago
  Needing two tokens of lookahead is fairly common. For example, in Lua "local IDENTIFIER" is a local variable declaration and "local function" is a private function declaration.

by norir 2y ago

marcosdumay 2y ago

Well, IMO, but you write a parser only a couple of times for each language, but you read code all the time. So, anything that makes code easier to read is a must. That includes the extra expressiveness of an LR grammar.

mhh__ 2y ago
In 2012 yes, but these days having grammars that lots of tools can parse and output easily is a boon for tooling.
vidarh 2y ago
I agree there are a few places like this, but they're usually solved when you want an LL parser for as much as possible of the language by either making them part of the tokenization or by "escaping" a small subset of the grammar. I wish that language designers (looking at you, Ruby - as much as I love using Ruby, the grammar is an abomination) would at least try to stick to LL as much as possible, and consciously, carefully and in a limited fashion "escape" into LR for as small subsets as possible. Break rules if it actually helps developers, sure, but it'd be nice if people tried to make the weird bits as tiny as possible... EDIT: Also, in practice this is often what we end up doing when we write recursive descent anyway, only in a less than formal way. It'd be nice if more tooling let us write grammars that default to LL w/checking, but let you insert clearly delineated exceptions.
- marcosdumay 2y ago
  Oh, I do agree with that! A language should be LL as much as possible. And also depend on the parsed data as little as possible. Stuff like C's variable declaration must be avoided. But I don't think either of those rules can be made universal. Some language for expressing exceptions would be great.
haberman 2y ago
Do you know of any particularly readable constructs that are possible with LR but incompatible with LL? My general opinion is that any constructs that confuse a parser will also confuse a human.
- marcosdumay 2y ago
  Operators with precedence rules. And given the modern idea of "everything is either an identifier or an operator", precedence became very important.
  - haberman 2y ago
    Operators with precedence rules frequently appear in top-down parsers. I agree that pure-LL form doesn't make this easy, but most languages I have seen use Pratt parsers that allow precedence parsing within a top-down framework. It doesn't require full LR.
    - Rusky 2y ago
      Pratt parsing is essentially hand-written LR. It's certainly bottom-up in the same way, despite Pratt's paper title. (I went into more depth on this a few years ago: https://www.abubalay.com/blog/2021/12/31/lr-control-flow https://www.abubalay.com/blog/2021/12/31/lr-control-flow)
      - chubot 2y ago
        Hm I wouldn't call it bottom up -- I would say it's top down, but you consult a table of integers to decide where to recurse. I would even call it a variant of recursive descent, which is top-down. In plain recursive descent, you often choose where to recurse based on the first token (e.g. if while for). In Pratt, you choose based on a table indexed by the second operater token. You can have an an entire arbitrary length subexpression before the "second token", but it is still resolved "eagerly". e.g. consulting the loop here - https://github.com/andychu/pratt-parsing-demo/blob/master/tdop.py#L212 https://github.com/andychu/pratt-parsing-demo/blob/master/td... I skimmed over your post, but I don't really see the bottom-up argument. I guess I could concede that it's neither top down nor bottom up, but I don't see the argument for being bottom up. And maybe this is just a taxonomy thing, which doesn't matter in practice. It could be understood both ways -- I don't think Vaughan Pratt was mistaken when he understood it a certain way :) --- "where to recurse" is basically choosing the parent's production before its children -- that's most similar to top down If you choose the child's production before its parent, then that's LR / bottom-up (using Haberman's explanation - https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html https://blog.reverberate.org/2013/07/ll-and-lr-parsing-demys...) May also be relevant: https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/03/31.html https://www.oilshell.org/blog/2017/04/22.html https://www.oilshell.org/blog/2017/04/22.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.html https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... I believe some people claimed that Dijikstra is bottom-up and Pratt is top down. That has a certain nice symmetry to it, but I'm not sure it's true :) Dijikstra does use an explicit stack and Pratt uses the call stack -- maybe that is how I'd put it.

dbcurtis 2y ago

I tend to agree. Having done a bunch of DSL's over the years, and becoming extremely fluent with Bison+FLEX, I have to say that a hand-written LL parser with a couple of mutually recursive table-driving functions to parse expressions via precedence climbing is the way to go. Precedence climbing (or I think it is also called Pratt parsing?) is super simple and flexible. But the BIG bonus is in error reporting, and let's face it, most of the user interaction with your parser is with the error messages, otherwise it is push 'enter' and forget. Getting a reasonable error message out of an LR parser is about as much fun as poking yourself in the eye repeatedly with a sharp stick. With LL, you know what structure you are trying to build... with LR, you have to rummage around in parse stack looking for obscure clues.

Calavar 2y ago
I am aware this is an unpopular opinion, but I think the idea that recursive descent is inherently better suited to error reporting than table-driven LR is massively cargo-culted. You can handcraft error messages for an LR parser if you overspecify the grammar, meaning that you don't just write productions for the actual language; you also write productions for likely errors and have the predicates for those productions report your handcrafted error message. I'm guessing that a lot of people's first impression of that will be "That's insane, are you seriously suggesting writing two grammars in one?" But that's exactly what you do when you build custom error reporting code into a recursive descent parser. It's just less obvious because the code is procedural instead of declarative.
- ckcheng 2y ago
  That's a very interesting way of looking at errors. Wouldn’t the grammar of errors have to also be LR? Doesn’t that limit the kind of errors you can report?
  - Calavar 2y ago
    Yes, it does have to be LR. Which can be a real PITA if you're working with a restrictive subset of LR, like LALR. But there are other options too. LR(1) is pretty powerful, and GLR even more so.

o11c 2y ago

I've always been hesitant about LL(1) since it requires a hack for something as common as expression-parsing, whereas LR is fine. Note that the linked article is misleading about LR having a problem with right-recursion: it only affects (data) stack depth, rather than breaking the machine like the LL problem. Still, LL and LR have common ground against the heresy of backtracking at least. I've never met a sane grammar that's not LALR(1). It's unfortunate that LALR(1) is such a leap of complexity beyond SLR(1), which is not practical for real languages. I imagine that LL(1) "mostly" works after the expression hack - what's your particular motivation for LL(2)? A lot of weird grammars lead to code that's hard to parse for humans. (Note also that, for languages (Python, Javascript, etc.) that lack an efficient `switch` statement, table-based is likely to beat function-call-based code)

ufo 2y ago
Needing two tokens of lookahead is fairly common. For example, in Lua "local IDENTIFIER" is a local variable declaration and "local function" is a private function declaration.