Hacker News Reader

Comment by kqr | Hacker News Reader

Is it not the case that most serious parser implementations are hand-written? In part because it makes it so much easier to provide good diagnostic messages. I feel like every other project moves from parser-generators to hand-rolled parsers and levels.

View on HN

Community wisdom has long held that good error recovery is impossible for automatically generated parsers and I unquestioningly accepted that wisdom for years. When I was building a Yacc system in Rust, I eventually investigated further, and found that there's loads of work in this area over several decades. None of it ever found its way into real parsers, probably because it was too slow. I extended some of that work a bit, made it more efficient, and took advantage of the speed of modern machines and now have an approach to automatic error recovery that you have to do quite a lot of work to beat with a hand-rolled parser. More at https://softdevteam.github.io/grmtools/master/book/errorreco... if you're interested!

For YACC/bison yes, but for peg parser generators not. They also don't need a lexer.

Both go and OCaml use LR parser generators, precisely because they make it easy to give excellent error messages.

Basically the key insight is that you can use the parsing automaton state to classify syntax errors, which makes it as easy as falling off a log to produce good messages. The paper originating this technique is Clinton Jeffery's TOPLAS 2003 paper “Generating LR Syntax Error Messages from Examples.” This is what go uses, and OCaml uses a more advanced version of this technique introduced by Francois Pottier in his CC 2016 paper "Reachability and Error Diagnosis in LR(1) Parsers".

Go doesn't use a generated parser. Both the parser and the lexer are hand-written:

https://github.com/golang/go/blob/master/src/go/parser/parse...

https://github.com/golang/go/blob/master/src/go/scanner/scan...

Why did you think it was generated?

If you look closely at the Go code you'll see it was once C code generated by some parser generater (which I assume was Bison). Believe it was Russ Cox that wrote a program that transformed the generated C code into Go.

Edit: I forked the compiler a while ago to add maybe types (a la Rust result). Looks like the compiler code has changed quite a bit from when I was playing w/ it.

That's a long time ago. You can see vestiges of it here and there (mostly in deeper areas of the compiler, which goes all the way back to Plan 9), but the parser now looks very clean.

Very true and agree. Parser is in good shape.

FTR: The go/parser package was _never_ used by the Go compiler. It used to be a yacc generated one when the compiler itself was in C. Then it was all mechanically translated to Go. And finally, a hand written lexer and parser were adopted, but different from the ones in the stdlib.

Guy Steele said this in the Dynamic Languages Wizards series, in the panel on language design [1]:

Be sure that your language will parse. It seems stupid to sit down and start designing constructs and not worry how they will fit together. You can get a language that's difficult if not impossible to parse, not only for a computer, but for a person. I use YACC constantly as a check of all my language designs, but I very seldom use YACC in the implementation. I use it as a tester, to be sure that it's LR(1) ... because if a language is LR(1) it's more likely that a person can deal with it.

[1] https://youtu.be/agw-wlHGi0E?t=4145

I've had great success with a parser-generator known as "Marpa" [1]. One of the things I particularly liked about it is how simple it made to emit accurate and useful error messages when parsing complex languages. In addition, it can handle anything that can be expressed in BNF, and it's quite fast.

[1] https://jeffreykegler.github.io/Marpa-web-site/

For general-purpose languages, yes, but there are some exceptions. Ruby uses yacc, and Python uses a custom LL(1)-ish parser generator, which is in the process of being replaced by a custom PEG parser generator [0].

[0] https://github.com/gvanrossum/pegen

Ruby's yacc parser is my usual go-to for telling people how not to do it. That thing's terrifying.

To be fair, ruby is not a fun language to machine-parse.

Oh absolutely. As a user, I love the ruby syntax. As a potential contributor to the codebase? NOPENOPENOPE.

Ruby doesn’t use yacc as intended though - it’s definitely not a good advert for yacc.

Even the Antlr FAQ mentions that "almost no one uses parser generators to build commercial compilers."

* https://github.com/antlr/antlr4/blob/master/doc/faq/general....

* See: "What do you think are the problems people will try to solve with ANTLR4?" question

I've used several different parser generators in the past. But I've also transitioned to hand-rolled recursive decent parsers, being Lazy I've created a library to assist in hand-rolling a recursive decent parser: https://github.com/SAP/chevrotain

This is actually pretty true based upon what I've personally observed too. While Apache Spark [0] and Presto [1] use ANTLR to implement their parsers, when I searched about TypeScript's parser and noticed that they implement their own parser [2] (in TypeScript itself), the reason I was able to find was that the nuanced error messages which a language like TypeScript has to provide is only feasible by hand-writing the parser.

[0] https://github.com/apache/spark/blob/master/sql/catalyst/src...

[1] https://github.com/prestodb/presto/blob/master/presto-parser...

[2] https://github.com/microsoft/TypeScript/blob/master/src/comp...

> the nuanced error messages which a language like TypeScript has to provide is only feasible by hand-writing the parser.

I wonder if this is relevant to how bad the error messages generally are in Typescript.

Also note the amazing architecture behind the Golang template parser/lexer A talk by Rob Like: https://talks.golang.org/2011/lex.slide

- Video of the talk: https://www.youtube.com/watch?v=HxaD_trXwRE

- Grammar documentation: https://golang.org/pkg/text/template/

- Code: https://golang.org/src/text/template/parse/lex.go

Edit: His name is Rob Pike

That’s what I expected this article to be about - it looks like it’s actually a long-form sales pitch for ANTLR training (but still worth a read). I’ve never been fortunate (or unfortunate) enough to be called on to put together a real compiler since school, but I’ve spent a lot of time working with “lite” parsers like JAXB and Hibernate (or variants thereof), and I’ve come to the same conclusion: I’m better off just hand-rolling my unmarshalling code than dealing with the gaps left by code generators.

In my professional experience I build parsers, like at least 10 per year and 99% are written using ANTLR. I did not find a language that I was not able to parse with it, so far.

I think it does make sense to write manually parsers for performance and error messages, but it should be clear that this means raising cost by ~10 times. It is worth the effort if you are building a compiler for Java, for example, probably not if you want to process some DSL you developed.

Disclaimer: I am the brother of the author of this article

> I did not find a language that I was not able to parse with [ANTLR], so far.

I have plenty. Publish contact info on your HN profile and I can send some.

you can contact me at federico -> tomassetti.me

You can check out how CockroachDB uses special error symbols with goyacc to provide good error messages for SQL passing. It’s a very interesting read really.

https://github.com/cockroachdb/cockroach/tree/master/pkg/sql...

The reasoning is pretty simple. Writing a parser for a sane language won't take significantly more than a month for your average developer. If you have a whole team working on the same compiler for decades then the pay off becomes pretty obvious.

One of the subtle things hidden in your statement (which I do somewhat agree with) is “sane language”.

One of the more memorable parsers I’ve worked on was a parser for SPICE netlists. I started out believing that it wasn’t going to be too big of a deal, and ended up sinking a ton of time into it. Ultimately the company (as far as I know) ended up just buying a $40k license to some obscure company that had one, because there was a constant cat-and-mouse game of getting it working right and then discovering a customer who did even more strange stuff that was somehow accepted by the 3rd-party SPICE sim, but wouldn’t be accepted by ours.

I’m assuming that PHP has evolved a ton since I encountered this, but IIRC at one point you couldn’t do `$foo[$baz]($zap)` to call an anonymous function stored in an array, rather you had to `$t = $foo[$baz]; $t($zap)`. At the time (young and naive), I just couldn’t comprehend how a sane parser wouldn’t parse the first form, and then I started looking at how it was implemented...

I think that hand-rolled parsers are good if: 1) You have a team that knows well what they are doing 2) You have a lot of resources 3) Your language is stable

I would argue that parser-generators are what made those projects to be started and prosper in the first place. Then once one is successful a custom solution could make sense but in my experience it is more expensive and potentially less maintanable, unless you know very welll your way around parsers and language tooling

For some definition of "serious" I think the gains from a readable implementation in your working language far outweigh performance or correctness concerns.

To put it another way, I'm rarely parsing data for it to be directly optimized into a machine language. I'm parsing data to extract parts I care about and then work with those parts. The more consistent this process is the easier it is to debug and fix. If my whole parsing/using-the-parsed-data pipeline is in the same language, say Javascript, then I am still only ever debugging the same language and runtime environment (eg: node v12 on whatever \*nix).

In a practical example, YARA[0] is (confusingly) used as both a format[1] and specific implementation[2] for sharing malware detection rules. ClamAV[3] is a popular open source antivirus engine that added YARA-the-format support a few years ago[4]. If you look at their grammar[5] file as well, you can see that one uses GNU Bison 3.0.4 the other uses 3.0.5. One is 3754 lines long, the other is 1849. We can expect these to behave differently. At a certain point, say because of how regular expressions are handled[6], it becomes easier to maintain your own parser than to deal with quirks/whims of someone else's implementation (generated or not).

[0]: https://en.wikipedia.org/wiki/YARA

[1]: https://yara.readthedocs.io/en/latest/writingrules.html

[2]: https://github.com/VirusTotal/yara/blob/master/libyara/hex_g...

[3]: https://www.clamav.net

[4]: https://blog.clamav.net/2015/06/clamav-099b-meets-yara.html

[5]: https://github.com/Cisco-Talos/clamav-devel/blob/898c08f08b5...

[6]: "In previous versions of YARA, external libraries like PCRE and RE2 were used to perform regular expression matching, but starting with version 2.0 YARA uses its own regular expression engine. This new engine implements most features found in PCRE, except a few of them" from https://yara.readthedocs.io/en/latest/writingrules.html#regu... ; if the regular expression grammar and/or symbol set isn't consistent the things parsing the files won't necessarily be either

Reply on news.ycombinator.com