Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

utcc.utoronto.ca

Post reply on HN
Print view View original

71–80 of 89 posts

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

#71

Post by pratt4the_win »

randomNumber7 wrote: post #50

The paper "Top Down Operator Precedence" also called "Pratt's Paper" introduced a very elegant algorithm for recursive descent parsers in 1973. Is is also written in a badass style and argues that this is superior to parser generators. https://dl.acm.org/doi/pdf/10.1145/512927.512931

Pratt parsers are elegant. I really like them.

For those to whom they are new: I found them a little tricky to implement directly from Pratt's paper or even Crockford's javascript that popularized them.

So, through trial and error I figured out how to actually implement them in regular languages (i.e. not in Lisp).

If it helps, examples in C and Go are here:

https://github.com/glycerine/PrattParserInC

https://github.com/glycerine/zygomys/blob/master/zygo/pratt....

I find them easier to work with than the cryptic LALR(1) bison/yacc tools, but then I never really felt like I mastered yacc to begin with.

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

#72

Post by sparkie »

johnwbyrd wrote: post #70

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.

PEGs are closely related to recursive descent, and have some of the same problems.

A PEG is always unambiguous because it picks the first option - but whether that was the intended parse is not necessarily straightforward. In practice these problems don't usually show up, so they're fine to work with.

The advantage LR gives you is that it produces a parser where there are no ambiguities and every successful parse is the one intended. An LR grammar is a proof, as well as a means of producing a parser. A decent LR parser generator is like a simple proof assistant - it will find problems with your language before you do, so you can fix your syntax before putting it into production.

In "real-world" parsing tasks as you put it, the problems of LR parser generators is that they're not the best suited to parsing languages that have ambiguities, like C, C++ and many others. Some of the complaints about LR are about the workarounds that need to be done to parse these languages, where it's obviously the wrong tool for the job because those languages aren't described by proper LR grammars.

But if you're designing a new language from scratch, surely it's better to not repeat those mistakes? If you carefully design your language to be parsed by an LR grammar then other developers who come to parse your language won't encounter those issues. They won't need lexical tie-ins and other nonsense that complicates the process.

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

#73

Post by cxr »

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.

The post by Laurence Tratt, which this piece is a response to, argues for another approach and is mentioned in the first sentence.

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

#74

Post by JonChesterfield »

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…

The generated parser will match the grammar.

The hand rolled parser might do, but also might not, what with software being difficult and testing being boring and so forth.

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

#75

Post by kerkeslager »

pjc50 wrote: post #42
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…

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 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-... Personally I've also written a parser-generator f…

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.

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

#76

Post by kerkeslager »

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…

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.

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

#77

Post by maxbond »

kerkeslager wrote: post #76
maxbond wrote: post #22

Earlier quoted context omitted.

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

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.

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.

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

#78

Post by senkora »

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…

> It reminds me of my short stint writing C++ where I'd read undefined memory in release mode, but when I ran it under debug mode it just worked.

I assume it’s far too late at this point, but that almost always means that you’re invoking UB. Your next step should be enabling UBSan.

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

#79

Post by lanstin »

kerkeslager wrote: post #76
maxbond wrote: post #22

Earlier quoted context omitted.

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

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.

There is a great Steve Yegge post on how useful ad-hoc transformation of source code is: http://steve-yegge.blogspot.com/2007/06/rich-programmer-food...

The only time I have used this myself was an expat style transformer for terraform (HCL). We had a lot of terraform and they kept changing the language, so I would build a fixer to make code written for say 0.10 to work with 0.12 and then again for 0.14. It was very fun and let us keep updating to newer terraform versions. Pretty simple language except for distinguishing quoted blocks from non-quoted.

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

#80

Post by kerkeslager »

maxbond wrote: post #77
kerkeslager wrote: post #76

Earlier quoted context omitted.

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.

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

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

Post reply on HN