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

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

#61

Post by sirwhinesalot » Mon, Jul 28, 2025, 5:19 PM UTC

ufo wrote: post #58

sirwhinesalot wrote: post #56

Earlier quoted context omitted.

Don't compute first and follow sets. Just branch on the current token. It is trivially unambiguous since 1 token = 1 branch. Expressions can be dealt with using precedence climbing / pratt, which still just amounts to branching on the current token after the "lhs" has been computed. If the language doesn't fit this LL1 + operator precedence mold then I would not use a recursive descent parser.

The whole issue is that, without computing first and follow sets, it's easy to make a mistake and think that the grammar is LL(1) when it actually isn't. When that happens, the if statement does you no good. It'll be deterministic, but will silently mask the ambiguity.

The only case I can think of is something like the dangling else problem or similar, which is very easy to detect.

You need to have a recursive call to the same rule or a "parent" rule, followed by an optional token match (note that this is already more than a simple branch on the current token since it is effectively a 1 token backtrack).

If there's any extra token match inbetween (like mandatory {}) you've already dodged the problem.

So I agree a mistake is possible, but "easy" I would not call it. It only appears in very specific conditions. The issue is way more prevalent in general PEGs.

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

#62

Post by somat » Mon, Jul 28, 2025, 5:19 PM UTC

zahlman wrote: post #12

> But in practice I bounce back and forth between two languages right now (Go and Python, neither of which have such a standard parser ecology) https://pypi.org/project/pybison/ , or its predecessors such as https://pypi.org/project/ply/ ? But yes, the decidedly non-traditional https://github.com/pyparsing/pyparsing/ is certainly more popular.

To add to your survey, I have been reading the lark documentation https://github.com/lark-parser/lark and like the cut of it's jib, I have not used it yet as I don't really have any projects that need a full parser.

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

#63

Post by pklausler » Mon, Jul 28, 2025, 5:49 PM UTC

Recursive descent is a cleaner way to go when the language cannot be lexed without feedback from the parser and semantics, like Fortran. And parser combinators make RD straightforward to code.

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

#64

Post by nrds » Mon, Jul 28, 2025, 6:11 PM 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…

> ambiguities

It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed (unless that language is not well-specified, but then all bets are off and it is meaningless to speak of parsing), because they can be eliminated by side-conditions.

For example, one famous ambiguity is the dangling 'else' problem in C. But this isn't an actual ambiguity in the C language: the language has a side-condition which says that 'else' matches to the closest unmatched 'if'. This is completely unambiguous and so a recursive descent parser for C simply doesn't encounter this problem. It is only because parser generators, at least in their most academic form, lack a way to specify this side-condition that their proponents have to come up with a whole theory of "ambiguities". (Shockingly, Wikipedia gets this exactly right in the article on dangling else which I just thought to look up: "The dangling else is a problem in programming of parser generators".)

Likewise goes the problem of left-recursion. Opponents of recursive descent always present left-recursion as a gotcha which requires some special handling. Meanwhile actual programmers writing actual recursive descent parsers don't have any idea what these academics are talking about because the language that they're parsing (as it exists in their mind) doesn't feature left-recursion, but instead iteration. Left-recursion is only introduced in service of restricted formal grammars in which recursion is the only available primitive and iteration either doesn't exist or is syntactic sugar for recursion. For the recursive descent user, iteration is a perfectly acceptable primitive. The reason for the discrepancy goes back to side-conditions: iteration requires a side-condition stating how to build the parse tree; parser generators call this "resolving the ambiguity" because they can't express this in their restricted grammar, not because the language was ambiguous.

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

#65

Post by favorited » Mon, Jul 28, 2025, 7:21 PM UTC

Which mainline compilers or runtimes use a generated parser? I know that CRuby does, though they've recently standardized on Prism as their public AST, and it's possible that they'll switch to Prism for parsing eventually. I know that Go used to, as well as ancient versions of GCC.

It seems that, from the outside looking in, ~all significant PL projects end up using a hand-written recursive descent parser, eventually.

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

#66

Post by layer8 » Mon, Jul 28, 2025, 7:24 PM UTC

favorited wrote: post #65

Which mainline compilers or runtimes use a generated parser? I know that CRuby does, though they've recently standardized on Prism as their public AST, and it's possible that they'll switch to Prism for parsing eventually. I know that Go used to, as well as ancient versions of GCC. It seems that, from the outside looking in, ~all significant PL projects end up using a hand-written recursive descent parser, eventually…

The problem remains how to verify that the hand-written parser matches the purported grammar, and that the grammar isn’t ambiguous in the first place.

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

#67

Post by layer8 » Mon, Jul 28, 2025, 7:32 PM UTC

nrds wrote: post #64

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…

> ambiguities It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed (unless that language is not well-specified, but then all bets are off and it is meaningless to speak of parsing), because they can be eliminated by side-conditions. For example, one famous ambiguity…

> They do not actually exist in the language to be parsed (unless that language is not well-specified

How do you specify your language “well” when you don’t know if your grammar is unambiguous? Determining whether a grammar is ambiguous is famously undecidable in the general case. So how do you decide, if you don’t restrict your grammar to one of the decidable forms checkable by parser generators? You can add some disambiguation rules, but how do you know they cover all ambiguities?

We use formal systems exactly to make sure that the language is well-defined.

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

#68

Post by o11c » Mon, Jul 28, 2025, 8:24 PM UTC

nrds wrote: post #64

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…

> ambiguities It's important to note that ambiguities are something which exist in service of parser generators and the restricted formal grammars that drive them. They do not actually exist in the language to be parsed (unless that language is not well-specified, but then all bets are off and it is meaningless to speak of parsing), because they can be eliminated by side-conditions. For example, one famous ambiguity…

Dangling "else" isn't actually a problem for parser generators. All you have to do is either:

* use proper rules rather than cramming everything into "statement", or

* specify explicit precedence rules, which is just a shortcut for the above (also skipping useless reductions)

Doing this is ubiquitous with parser generators when dealing with vaguely Algol-like languages, and is no different than the fact that you have to do the same thing for expressions.

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

#69

Post by 8n4vidtmkvmk » Mon, Jul 28, 2025, 10:01 PM UTC

mrkeen wrote: post #55

JonChesterfield wrote: post #36

Pet subject of the week here. Big choices are handrolled recursive decent vs LALR, probably backed by bison or lemon generator and re2c for a lexer. Passing the lalr(1) check, i.e. having bison actually accept the grammar without complain about ambiguities, is either very annoying or requires thinking clearly about your language, depending on your perspective. I claim that a lot of the misfires in language implementa…

> parse with the lalr generated parser, then if that rejects your string because the program was ill formed, call the hand rolled one for guesswork/diagnostics This feels like a recipe for disaster. If the hand-rolled parser won't match a formal grammar, why would it match the generated parser? The poor programmer will be debugging the wrong thing. It reminds me of my short stint writing C++ where I'd read undefined…

There's risk, but it seems like you could run both parsers against the same unit tests to help mitigate.

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

#70

Post by johnwbyrd » Mon, Jul 28, 2025, 10:07 PM UTC

I'm surprised, and a little disappointed, that no one in this thread has mentioned parsing expression grammars (https://en.wikipedia.org/wiki/Parsing_expression_grammar) which are a much more human-friendly form of grammar for real-world parsing tasks.