4 ms·

> Recursive descent is fine if you trust that you won't write buggy code. If you implement a generator for it (easy enough), this may be a justifiable thing to

> Recursive descent is fine if you trust that you won't write buggy code. If you implement a generator for it (easy enough), this may be a justifiable thing to trust (though this is not a given). The idea that you're going to hand-roll a parser generator and then use that to generate a parser and the result is going to be less buggy than just hand-rolling a recursive descent parser, screams "I've never written code outside of an academic context".

maxbond 1y ago
> [It] screams "I've never written code outside of an academic context". SQLite, perhaps the most widely deployed software system, takes this approach. https://sqlite.org/lemon.html https://sqlite.org/lemon.html > The Lemon LALR(1) Parser Generator > The SQL language parser for SQLite is generated using a code-generator program called "Lemon". > ... > Lemon was originally written by D. Richard Hipp (also the creator of SQLite) while he was in graduate school at Duke University between 1987 and 1992. Here are the grammars, if you're curious. https://github.com/sqlite/sqlite/blob/master/src/parse.y https://github.com/sqlite/sqlite/blob/master/src/parse.y
- mpyne 1y ago
  SQLite is kind of cheating here, you won't catching me writing my own source control management system either. But I do think the wider point is still true, that there can be real benefit to implementing 2 proper layered abstractions rather than implementing 1 broader abstraction where the complexity can span across more of the problem domain.
- kerkeslager 1y ago
  Yeah, let me know when you're writing the next SQLite. For your average parser, you're not writing the SQLite parser, you don't have the SQLite parser's problems, and you don't need SQLite's solutions.
  - maxbond 1y ago
    Most people aren't writing something as complex as SQLite, but most people aren't writing parsers either. Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. SQLite isn't some kind of universal template, I'm not saying people should copy it or that recursive descent is a bag choice. But empirically parser generators are used in real production systems. SQLite is unusual in that they also wrote the parser generator, but otherwise is in good company. Postgres uses Bison, for example. Additionally, I think that Lemon was started as a personal learning project in grad school (as academic a project as it gets) and evolved into a component of what is probably the most widely deployed software system of all time shows this distinction between what is academic and what is practical isn't all that meaningful to begin with. What's academic becomes practical when the circumstances are right. Better to evaluate a technique in the context of your problem than to prematurely bin things into artificial categories.
    - kerkeslager 1y ago
      > Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. Sure, but adding the complexity of a parser generator doesn't help with that complexity in most cases. [General purpose] programming languages are a quintessential example. Yes, a compiler or an interpreter is a very complex program. But unless your programming language needs to be parsed in multiple languages, you definitely do not need to generate the parser in many languages like SQLite does. That just adds complexity for no reason. You can't just say "it's complex, therefore it needs a parser generator" if adding the parser generator doesn't address the complexity in any way.
      - maxbond 1y ago
        I'm not saying everyone or even anyone in particular needs a parser generator. I'm saying real, widely deployed projects - as far as you can get from academic - empirically find it useful. Creating abstractions does decrease complexity if one (or more) of the following is true: - The abstraction generates savings in excess of it's own complexity - The abstraction is shared by enough projects to amortize the cost of writing/maintaining it to a tolerable level - There are additional benefits like validating your grammars are unambiguous or generating flow charts of your syntax in your documentation, amortizing the cost across different features of the same project It's up to you as the implementer to weigh the benefits and costs. If you choose to use recursive descent, more power to you. (For what it's worth, I personally use parser combinators to split the difference between writing grammars and hand-rolling parsers. But I've used parser generators before and found them helpful.)
motorest 1y ago
> The idea that you're going to hand-roll a parser generator and then use that to generate a parser and the result is going to be less buggy than just hand-rolling a recursive descent parser, screams "I've never written code outside of an academic context" Your comment is quite funny as hand-rolling a recursive descent parser is the kind of thing that is often accused of being a) bug-prone, b) only done in academic environments.
- raincole 1y ago
  [flagged]
- paddim8 1y ago
  What? Accused of only being done in academic environments? Never heard that. Academics seem to spend 99% of their time talking about parser generators and LR parsing for some reason while most production compilers have handwritten recursive descent parsers...
  - jfyi 1y ago
    Same here, recursive descent is what I have run into in the real world. I'm just happy when parsing isn't being done with some absurdly long regex with no documentation.
- vidarh 1y ago
  Having written several parser generators, all my production parsers are hand-written - either pure recursive descent or a combination of recursive descent and operator precedence parsing. The reason being that the reason there are so many parser generators is largely that we keep desperately looking for a way of writing one that isn't sheer pain in production use.
pjc50 1y ago
One of the smartest projects I've ever seen was a tool that took the human-readable tables of the HEVC and AV1 specs, used them as input to https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta parser-generator, and then output both HEVC parsers in a variety of languages and also auto-fuzzers for test coverage. Ended up at https://www.graphcore.ai/posts/graphcore-open-sources-argon-streams-av1-video-decoder-verification-tool https://www.graphcore.ai/posts/graphcore-open-sources-argon-... Personally I've also written a parser-generator for XML in C# to overcome some of the odd limitations of Microsoft's one when used in AOT contexts. Hand-rolling is easy if the grammar is small. The larger it gets (and video codecs are huge!) the more you want something with automatic consistency.
- kerkeslager 1y ago
  Sure, if you need parsers in a dozen languages, then a parser generator might to make sense because you're not writing one parser, you're writing a dozen. But, the vast majority of parsers I've written didn't have this requirement. I needed to write one parser in one language.

maxbond 1y ago

> [It] screams "I've never written code outside of an academic context". SQLite, perhaps the most widely deployed software system, takes this approach. https://sqlite.org/lemon.html https://sqlite.org/lemon.html > The Lemon LALR(1) Parser Generator > The SQL language parser for SQLite is generated using a code-generator program called "Lemon". > ... > Lemon was originally written by D. Richard Hipp (also the creator of SQLite) while he was in graduate school at Duke University between 1987 and 1992. Here are the grammars, if you're curious. https://github.com/sqlite/sqlite/blob/master/src/parse.y https://github.com/sqlite/sqlite/blob/master/src/parse.y

mpyne 1y ago
SQLite is kind of cheating here, you won't catching me writing my own source control management system either. But I do think the wider point is still true, that there can be real benefit to implementing 2 proper layered abstractions rather than implementing 1 broader abstraction where the complexity can span across more of the problem domain.
kerkeslager 1y ago
Yeah, let me know when you're writing the next SQLite. For your average parser, you're not writing the SQLite parser, you don't have the SQLite parser's problems, and you don't need SQLite's solutions.
- maxbond 1y ago
  Most people aren't writing something as complex as SQLite, but most people aren't writing parsers either. Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. SQLite isn't some kind of universal template, I'm not saying people should copy it or that recursive descent is a bag choice. But empirically parser generators are used in real production systems. SQLite is unusual in that they also wrote the parser generator, but otherwise is in good company. Postgres uses Bison, for example. Additionally, I think that Lemon was started as a personal learning project in grad school (as academic a project as it gets) and evolved into a component of what is probably the most widely deployed software system of all time shows this distinction between what is academic and what is practical isn't all that meaningful to begin with. What's academic becomes practical when the circumstances are right. Better to evaluate a technique in the context of your problem than to prematurely bin things into artificial categories.
  - kerkeslager 1y ago
    > Those writing parsers are disproportionately writing things like programming languages and language servers that are quite complex. Sure, but adding the complexity of a parser generator doesn't help with that complexity in most cases. [General purpose] programming languages are a quintessential example. Yes, a compiler or an interpreter is a very complex program. But unless your programming language needs to be parsed in multiple languages, you definitely do not need to generate the parser in many languages like SQLite does. That just adds complexity for no reason. You can't just say "it's complex, therefore it needs a parser generator" if adding the parser generator doesn't address the complexity in any way.
    - maxbond 1y ago
      I'm not saying everyone or even anyone in particular needs a parser generator. I'm saying real, widely deployed projects - as far as you can get from academic - empirically find it useful. Creating abstractions does decrease complexity if one (or more) of the following is true: - The abstraction generates savings in excess of it's own complexity - The abstraction is shared by enough projects to amortize the cost of writing/maintaining it to a tolerable level - There are additional benefits like validating your grammars are unambiguous or generating flow charts of your syntax in your documentation, amortizing the cost across different features of the same project It's up to you as the implementer to weigh the benefits and costs. If you choose to use recursive descent, more power to you. (For what it's worth, I personally use parser combinators to split the difference between writing grammars and hand-rolling parsers. But I've used parser generators before and found them helpful.)

motorest 1y ago

> The idea that you're going to hand-roll a parser generator and then use that to generate a parser and the result is going to be less buggy than just hand-rolling a recursive descent parser, screams "I've never written code outside of an academic context" Your comment is quite funny as hand-rolling a recursive descent parser is the kind of thing that is often accused of being a) bug-prone, b) only done in academic environments.

raincole 1y ago
[flagged]
paddim8 1y ago
What? Accused of only being done in academic environments? Never heard that. Academics seem to spend 99% of their time talking about parser generators and LR parsing for some reason while most production compilers have handwritten recursive descent parsers...
- jfyi 1y ago
  Same here, recursive descent is what I have run into in the real world. I'm just happy when parsing isn't being done with some absurdly long regex with no documentation.
vidarh 1y ago
Having written several parser generators, all my production parsers are hand-written - either pure recursive descent or a combination of recursive descent and operator precedence parsing. The reason being that the reason there are so many parser generators is largely that we keep desperately looking for a way of writing one that isn't sheer pain in production use.

pjc50 1y ago

One of the smartest projects I've ever seen was a tool that took the human-readable tables of the HEVC and AV1 specs, used them as input to https://en.wikipedia.org/wiki/OMeta https://en.wikipedia.org/wiki/OMeta parser-generator, and then output both HEVC parsers in a variety of languages and also auto-fuzzers for test coverage. Ended up at https://www.graphcore.ai/posts/graphcore-open-sources-argon-streams-av1-video-decoder-verification-tool https://www.graphcore.ai/posts/graphcore-open-sources-argon-... Personally I've also written a parser-generator for XML in C# to overcome some of the odd limitations of Microsoft's one when used in AOT contexts. Hand-rolling is easy if the grammar is small. The larger it gets (and video codecs are huge!) the more you want something with automatic consistency.

kerkeslager 1y ago
Sure, if you need parsers in a dozen languages, then a parser generator might to make sense because you're not writing one parser, you're writing a dozen. But, the vast majority of parsers I've written didn't have this requirement. I needed to write one parser in one language.