Why I write recursive descent parsers, despite their issues (2020) • Hacker News Board

Re: Why I write recursive descent parsers, despite their issues (2020)

#21

Post by kerkeslager » Mon, Jul 28, 2025, 3:35 AM UTC

o11c wrote: post #13

nicoburns wrote: post #8

I wonder who it is that likes other kinds of parser. Over the last ~10 years or so I've read several articles arguing that recursive descent parsers are in fact great on HN. And they seem to be both the easiest to get started with and what almost all production-grade systems use. I've seen very little in the way of anything arguing for any other approaches.

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). I am assuming you're willing to put up with the insanity of grammar rewriting, one way or another. LR however is more powerful, though this mostly matters if you don't have access to automatic grammar rewriting for your LL. Mo…

> 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".

Re: Why I write recursive descent parsers, despite their issues (2020)

#22

Post by maxbond » Mon, Jul 28, 2025, 3:54 AM UTC

kerkeslager wrote: post #21

o11c wrote: post #13

Earlier quoted context omitted.

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). I am assuming you're willing to put up with the insanity of grammar rewriting, one way or another. LR however is more powerful, though this mostly matters if you don't have access to automatic grammar rewriting for your LL. Mo…

> 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 o…

> [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

> 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

Re: Why I write recursive descent parsers, despite their issues (2020)

#23

Post by ogogmad » Mon, Jul 28, 2025, 4:31 AM UTC

Have people heard of the following top-down parsing algorithm for mathematical expressions:

  1. Replace any expression that's within parentheses by its parse tree by using recursion
  2. Find the lowest precedence operator, breaking ties however you'd like. Call this lowest precedence operator OP.
  3. View the whole unparsed expression as `x OP y`
  4. Generate a parse tree for x and for y. Call them P(x) and P(y).
  5. Return ["OP", P(x), P(y)].

It's easy to speed up step 2 by keeping a table of all the operators in an expression, sorted by their precedence levels. For this table to work properly, the positions of all the tokens must never change.

Re: Why I write recursive descent parsers, despite their issues (2020)

#24

Post by mpyne » Mon, Jul 28, 2025, 4:41 AM UTC

maxbond wrote: post #22

kerkeslager wrote: post #21

Earlier quoted context omitted.

> 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 o…

> [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 > 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 gra…

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.

Re: Why I write recursive descent parsers, despite their issues (2020)

#25

Post by motorest » Mon, Jul 28, 2025, 4:48 AM UTC

kerkeslager wrote: post #21

o11c wrote: post #13

Earlier quoted context omitted.

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). I am assuming you're willing to put up with the insanity of grammar rewriting, one way or another. LR however is more powerful, though this mostly matters if you don't have access to automatic grammar rewriting for your LL. Mo…

> 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 o…

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

Re: Why I write recursive descent parsers, despite their issues (2020)

#26

Post by UncleOxidant » Mon, Jul 28, 2025, 4:56 AM UTC

chadcmulligan wrote: post #20

fwiw LLM's seem very good at writing recursive descent parsers, at least for the small experiments I've done (wrote a Lua parser in Delphi).

Agreed. I recently had Gemini write a recursive descent parser for a specified subset of C in C and it did quite well. I've tried similar with Claude 4 and Qwen3 Coder and again, both did quite well.

Re: Why I write recursive descent parsers, despite their issues (2020)

#27

Post by derriz » Mon, Jul 28, 2025, 5:34 AM UTC

marssaxman wrote: post #14

I have never found parser generators to be worth the hassle. Recursive descent with a little Pratt-style precedence climbing is all you need.

Agree completely and I’ve used a bunch of them and also functional combinator libraries. I‘d go further and say the recursive descent and Pratt approach is the way if you want to offer useful error messages and feedback to the user. They’re also trivial to debug and test unlike any generation based approach.

Re: Why I write recursive descent parsers, despite their issues (2020)

#28

Post by fjfaase » Mon, Jul 28, 2025, 6:08 AM UTC

ufo wrote: post #4

fjfaase wrote: post #2

I recently wrote a small C compiler that uses a recursive decent parser while this should not be possible if you just look at the syntax grammar. Why, because it looks at some semantic information about the class of identifiers, whether they are variables of typedefs for example. On the otherhand this is not very surprising, because in the days C was developed, easy parsing was a practical implication of it not being…

It sounds like you're describing the Lexer Hack[1]. That trick works just the same in an LR parser, so I wouldn't count it as an advantage of recursive descent. [1] https://en.wikipedia.org/wiki/Lexer_hack

Yes, it is basically this. I feel that writing a recursive descent parser with recursive functions is a bit easier than using an LR parser generator or a back-tracking PEG parser from my experience. It also does not requirer any third party tools or libraries, which I see as advantage.

Re: Why I write recursive descent parsers, despite their issues (2020)

#29

Post by raincole » Mon, Jul 28, 2025, 6:47 AM UTC

motorest wrote: post #25

kerkeslager wrote: post #21

Earlier quoted context omitted.

> 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 o…

> 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 e…

[flagged]

Re: Why I write recursive descent parsers, despite their issues (2020)

#30

Post by paddim8 » Mon, Jul 28, 2025, 7:00 AM UTC

motorest wrote: post #25

kerkeslager wrote: post #21

Earlier quoted context omitted.

> 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 o…

> 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 e…

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