News for hackers. Stuff that matters.
Re:Why not to use (f)lex, yacc or bison by kqr on Thursday March 05, 2020 @03:31AM (#22491898)
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.
Re:Why not to use (f)lex, yacc or bison by ltratt on Thursday March 05, 2020 @04:32AM (#22492181)
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!
Re:Why not to use (f)lex, yacc or bison by rurban on Thursday March 05, 2020 @02:07PM (#22496896)
For YACC/bison yes, but for peg parser generators not. They also don't need a lexer.
Re:Why not to use (f)lex, yacc or bison by neel_k on Thursday March 05, 2020 @06:20AM (#22492626)
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".

Re:Why not to use (f)lex, yacc or bison by atombender on Thursday March 05, 2020 @12:36PM (#22495846)
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?

Re:Why not to use (f)lex, yacc or bison by minieggs on Thursday March 05, 2020 @02:18PM (#22497026)
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.

Re:Why not to use (f)lex, yacc or bison by atombender on Thursday March 05, 2020 @02:27PM (#22497134)
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.
Re:Why not to use (f)lex, yacc or bison by minieggs on Thursday March 05, 2020 @02:37PM (#22497249)
Very true and agree. Parser is in good shape.
Re:Why not to use (f)lex, yacc or bison by 0xjnml on Saturday March 07, 2020 @09:15AM (#22511607)
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.
Re:Why not to use (f)lex, yacc or bison by EdwardCoffin on Thursday March 05, 2020 @02:29PM (#22497157)
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

Re:Why not to use (f)lex, yacc or bison by hercynium on Thursday March 05, 2020 @10:39AM (#22494419)
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/

Re:Why not to use (f)lex, yacc or bison by pansa2 on Thursday March 05, 2020 @03:46AM (#22491972)
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

Re:Why not to use (f)lex, yacc or bison by regularfry on Thursday March 05, 2020 @04:21AM (#22492128)
Ruby's yacc parser is my usual go-to for telling people how not to do it. That thing's terrifying.
Re:Why not to use (f)lex, yacc or bison by jknoepfler on Thursday March 05, 2020 @09:41AM (#22493849)
To be fair, ruby is not a fun language to machine-parse.
Re:Why not to use (f)lex, yacc or bison by regularfry on Thursday March 05, 2020 @11:27AM (#22494980)
Oh absolutely. As a user, I love the ruby syntax. As a potential contributor to the codebase? NOPENOPENOPE.
Re:Why not to use (f)lex, yacc or bison by chrisseaton on Thursday March 05, 2020 @04:32AM (#22492176)
Ruby doesn’t use yacc as intended though - it’s definitely not a good advert for yacc.
Re:Why not to use (f)lex, yacc or bison by bd82 on Thursday March 05, 2020 @10:52AM (#22494567)
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

Re:Why not to use (f)lex, yacc or bison by rajnathani on Thursday March 05, 2020 @03:46AM (#22491974)
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...

Re:Why not to use (f)lex, yacc or bison by lloydatkinson on Thursday March 05, 2020 @04:05AM (#22492063)
> 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.

Re:Why not to use (f)lex, yacc or bison by jakoblorz on Thursday March 05, 2020 @04:12AM (#22492092)
Also note the amazing architecture behind the Golang template parser/lexer A talk by Rob Like: https://talks.golang.org/2011/lex.slide
Re:Why not to use (f)lex, yacc or bison by jakoblorz on Thursday March 05, 2020 @07:32AM (#22492995)
Re:Why not to use (f)lex, yacc or bison by commandlinefan on Thursday March 05, 2020 @10:13AM (#22494137)
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.
Re:Why not to use (f)lex, yacc or bison by ftomassetti on Friday March 06, 2020 @03:19AM (#22501842)
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

Re:Why not to use (f)lex, yacc or bison by bmn__ on Friday March 06, 2020 @04:38AM (#22502230)
> 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.

Re:Why not to use (f)lex, yacc or bison by ftomassetti on Friday March 06, 2020 @09:55AM (#22503998)
you can contact me at federico -> tomassetti.me
Re:Why not to use (f)lex, yacc or bison by cube2222 on Thursday March 05, 2020 @12:38PM (#22495876)
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...

Re:Why not to use (f)lex, yacc or bison by imtringued on Thursday March 05, 2020 @06:00AM (#22492548)
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.
Re:Why not to use (f)lex, yacc or bison by tonyarkles on Friday March 06, 2020 @08:45AM (#22503454)
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...

Re:Why not to use (f)lex, yacc or bison by ftomassetti on Friday March 06, 2020 @03:32AM (#22501906)
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

Re:Why not to use (f)lex, yacc or bison by jrandm on Thursday March 05, 2020 @11:06AM (#22494733)
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