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

41–50 of 89 posts

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

#41

Post by fuzztester »

derriz wrote: post #40
fuzztester wrote: post #32

Earlier quoted context omitted.

>functional combinator libraries By that, do you mean parser combinators?

Yes - but this was decades ago so my memory is hazy. It was with an early Haskell variant called Gofer - which had a nice feature which allowed using list comprehension notation with arbitrary monads - which for simple grammars produced very readable - even beautiful - parser code. But like with parser generators, once the grammar became complex, the beauty and simplicity disappeared. Actually I wish this generalizat…

Thanks.

On a side note, I do use Python list comprehensions, and like them.

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

#42

Post by pjc50 »

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…

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

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

#44

Post by jfyi »

paddim8 wrote: post #30
motorest wrote: post #25

Earlier quoted context omitted.

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

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.

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

#45

Post by ufo »

sirwhinesalot wrote: post #33
ufo wrote: post #6

A middle ground that I think is sometimes useful is to use an LR parser generator to check if the grammar is ambiguous, but use recursive descent for the actual implementation. Since we won't actually use any code from the LR parser generator, you can pick whatever one you prefer regardless of the programming language.

It's trivial to get a recursive descent parser without any ambiguities hidden in it if you don't go the PEG route (which is only unambiguous because you always pick the first choice, which might not be what you want). Just always branch on the current token. No way to have an ambiguity like that.

I disagree. When writing recursive descent by hand, it's easy to miss an ambiguity because of miscomputed FIRST and FOLLOW sets.

In practice most recursive descent parsers use if-else liberally. Thus, they effectively work like pegs where the first match wins (but without the limited backtracking of pegs). They are deterministic in the sense that the implementation always returns a predictable result. But they are still ambiguous in the sense that this behavior might not have been planned by the language designer, and the ambiguity may not have been resolved how the programmer expected.

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

#46

Post by themk »

derriz wrote: post #40
fuzztester wrote: post #32

Earlier quoted context omitted.

>functional combinator libraries By that, do you mean parser combinators?

Yes - but this was decades ago so my memory is hazy. It was with an early Haskell variant called Gofer - which had a nice feature which allowed using list comprehension notation with arbitrary monads - which for simple grammars produced very readable - even beautiful - parser code. But like with parser generators, once the grammar became complex, the beauty and simplicity disappeared. Actually I wish this generalizat…

ghc has the the MonadComprehension extension which does what you desire

https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/mona...

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

#47

Post by vidarh »

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…

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.

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

#48

Post by coldcode »

Funny, I wrote a recursive descent parser in 1982, in Fortran, to parse the syntax of the Jovial programming language. That was my first ever professional programming project, with no university degree in CS, or job experience. Note, Fortran (78) is a terrible language to write a parser in.

I wish I could have save the source. It would be fun to see it.

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

#49

Post by masklinn »

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.

Pratt parsers are really fun if slightly mind-bending, their ability to handle odd associativities, precedences, and arities is basically unmatched making them really useful to embed inside recursive descent for when you reach expressions. If you need infix and mixfix operators anyway.

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

#50

Post by randomNumber7 »

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

Post reply on HN