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

31–40 of 89 posts

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

#31

Post by fuzztester »

jasperry wrote: post #9

> If I was routinely working in a language that had a well respected de facto standard parser generator and lexer, and regularly building parsers for little languages for my programs, it would probably be worth mastering these tools. In OCaml, a language highly suited for developing languages in, that de facto standard is the Menhir LR parser generator. It's a modern Yacc with many convenient features, including comb…

>In OCaml, a language highly suited for developing languages in,

What makes OCaml suited for that?

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

#32

Post by fuzztester »

derriz wrote: post #27
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.

>functional combinator libraries

By that, do you mean parser combinators?

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

#33

Post by sirwhinesalot »

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.

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

#34

Post by mjburgess »

fuzztester wrote: post #31
jasperry wrote: post #9

> If I was routinely working in a language that had a well respected de facto standard parser generator and lexer, and regularly building parsers for little languages for my programs, it would probably be worth mastering these tools. In OCaml, a language highly suited for developing languages in, that de facto standard is the Menhir LR parser generator. It's a modern Yacc with many convenient features, including comb…

>In OCaml, a language highly suited for developing languages in, What makes OCaml suited for that?

algebraic datatypes (tagged unions + pattern matching); compiled, garbage collected (you dont really need memory management for a compiler), statically typed with inference

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

#35

Post by greggyb »

fuzztester wrote: post #31
jasperry wrote: post #9

> If I was routinely working in a language that had a well respected de facto standard parser generator and lexer, and regularly building parsers for little languages for my programs, it would probably be worth mastering these tools. In OCaml, a language highly suited for developing languages in, that de facto standard is the Menhir LR parser generator. It's a modern Yacc with many convenient features, including comb…

>In OCaml, a language highly suited for developing languages in, What makes OCaml suited for that?

ML, the language heritage from which OCaml derives, was explicitly designed with interpreters and compilers in mind.

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

#36

Post by JonChesterfield »

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 implementations are from not doing that work, and using a hand rolled approximation to the parser you had in mind instead, because that's nicer/easier than the formal grammar.

The parser generators emit useless error messages, yes. So if you want nice user feedback, that'll be handrolled in some fashion. Sure.

Sometimes people write a grammar and use a hand rolled parser, hoping they match. Maybe with tests.

The right answer, used by noone as far as I can tell, is to 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. Never feed the parse tree from the hand rolled parser into the rest of the compiler, that way lies all the bugs.

As alternative phrasing, your linter and your parser don't need to be the same tool, even if it's convenient in some senses to mash them together.

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

#37

Post by da-bacon »

ogogmad wrote: post #23

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

For 2, I don’t think you can break ties however you like because this would give you random left or right associativity https://en.m.wikipedia.org/wiki/Operator_associativity For example 2-4-7 would be either (2-4)-7 or 2-(4-7), depending on how you broke the tie.

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

#38

Post by fuzztester »

keithnz wrote: post #5

recursive descent parsers are usually what I do for my little domain specific scripting languages. They are just easy and straightforward. I do like things like ANTLR, but most of the time it seems unnecessary.

Got any open source ones you can share links / code of?

I am interested in that area, and reading up and learning about it.

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

#39

Post by hibikir »

mjburgess wrote: post #34
fuzztester wrote: post #31

Earlier quoted context omitted.

>In OCaml, a language highly suited for developing languages in, What makes OCaml suited for that?

algebraic datatypes (tagged unions + pattern matching); compiled, garbage collected (you dont really need memory management for a compiler), statically typed with inference

Yeah, the same reasons Scala has a built in parser combinator module in the standard library: Just easy to use with those features in the language

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

#40

Post by derriz »

fuzztester wrote: post #32
derriz wrote: post #27

Earlier quoted context omitted.

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.

>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 generalization of list comprehensions had been taken up by Haskell or other languages. Haskell decided on the do notation while Python users these days seem to shun the feature.

Post reply on HN