7 ms·
Why you should not use (f)lex, yacc and bison
- PaulHoule 5y agoI would have upvoted this article except for the fact that it popped up not one but two pop-up windows asking for my email address.
- mcguire 5y agoBoth of which were ads for ANTLR services, which is what they provide.
- criddell 5y agoOn other articles (like this [1]), they put a box at the bottom where you can submit your email address. It's far more respectful way to do it. [1]: https://tomassetti.me/working-with-excel-in-python/ https://tomassetti.me/working-with-excel-in-python/
- fjfaase 5y agoThe title should have been 'Why you should use ANTLR and not use (f)lex, yacc and bison' as if ANTLR is the only alternative.
- heythere22 5y agoPrevious discussion: https://news.ycombinator.com/item?id=22491536 https://news.ycombinator.com/item?id=22491536 (89 comments)
- quickthrower2 5y agoOh that was pretty recent I’d have held off submitting if I saw that.
- stephc_int13 5y agoI learned about the existence of Lex, Yacc, and Bison a bit more than 20 years while discussing the difficulties of debugging handwritten parsers with a friend. But I was quickly discouraged by the complexity of using these tools, they are more like a new language that you have to learn. Today I prefer writing parsers by hand, in C, like Fabrice Bellard, it is not super easy but manageable and I never encountered major issues. I think that Lex/Yacc and similar tools are a good illustration of the power and shortcomings of metaprogramming. There are some obvious use cases, but it is not always the best choice.
- 1vuio0pswjnm7 5y agoHow easy is it to make quick changes to hand-written parsers. Imagine, for example, that the input being parsed is not under the authors control and it suddenly changes. The parser must be changed.
- mateo411 5y agoThe input changing shouldn't matter. Maybe you could see a performance issue if you had to parse a really large file/files. The issue would be if the grammar to what you are parsing changes. If that changes, then no parser will work, correctly until it supports the new grammar. As a practical matter the grammar can act like a contract between the two systems. You don't have control of the input, but the input must follow the same grammar.
- 1vuio0pswjnm7 5y agoDoes the separation of the grammar into its own file, like a .y file for yacc, make it easier to modify the grammar at a later point. Similarly, is it easier to modify a parser later on, if the input changes, if the patterns to be searched in the input and the state machine are stored in a separate file, like an .l file for flex.
- mateo411 5y agoI would think so. I don't work on parsers and grammar day to day, so I might not be the best person to ask about this. I am interested in the subject though. I just don't get to work on this in my current day job.
- AshamedCaptain 5y agoGlad to hear the ANTLR vs Yacc holy way (a.k.a. LL vs LR) is still going strong. This one holy war may actually be older than emacs vs vi. Have the ANTLR guys dropped their Java credo or they're still thinking they are going to convince any C developer with a .jar?
- ksaj 5y agoThis is actually the first time I've even heard of ANTLR, which came about in the early 90's. But yacc/lex/vi/emacs, et al have been around since the 70's. The emacs vs. vi holy war was pretty much instant, but doomed every time one spoke of headless devices such as routers.
- deleted 5y ago[deleted]
- karmakaze 5y agoAntlr and LL(k) parsers in general are great when they fit the grammar you want to make well. I remember discovering it when it was called JavaCC a nod to yacc.
- AshamedCaptain 5y agoHeh. at my grad school we had a pccts fan (antlr before java even existed) and he actually tried to paint the LR vs LL war as a american vs european thing (this was in france).
- professoretc 5y agoI wrote a parser for a DSL using ANTLR about ten-ish years ago, and it was an incredibly painful experience. There's very little freely-available documentation for ANTLR, most of it is just "buy my book". ANTLR doesn't know anything about the language it's targeting (not even Java), so if you name a rule e.g., `while` the generated code will be filled with errors, because it names the parser functions after the rules. The graphical tools for building parsers are cool, except that many advanced things can only be done by adding actual code to the parser rules, which the graphical tool does not support (and how could it?) so you're back at square one.
- legulere 5y agoIf you push out enough grammars that makes writing lexers and parsers by hand more work than learning tools for that, you will soon have all kinds of other problems.
- quickthrower2 5y agoThe piece is written by a consulting company who by design are probably pushing out a lot of grammars but to different systems and companies.
- atomicnumber3 5y agoI used ANTLR to build a query language parser and interpreter for a past employer. They had a specialized use case. ANTLR was pretty pleasant to use. The solution ended up being a pretty small amount of code and enabled much more powerful searching in their internal data viewing tool. I still think fondly about the project from time to time, partly because it was the one project where my fellow devs were just as happy with the tool as the non-dev users were (this was a very common tool for both devs and non-devs to use).
- lallysingh 5y agoThe IDE and tree parser modes are pretty nice!
- Steve_Baker77 5y agoToo many pop-ups; I left the site.
- MaxBarraclough 5y agoHere's Outline's version: https://www.outline.com/gEuVje https://www.outline.com/gEuVje
- dmitrygr 5y agoThis reads more like an ad for ANTLR than a criticism of flex&bison. Very few criticisms are offered, and most of them are quite handwavy.
- truenindb 5y agoThe re-entrancy complaint seems legit if actually well founded, although I'd think that it probably says somewhere in Flex/bison docs that the generated parsers expect only to be entered from a single C process. It sounds to me like they were using Flex/Bison generated parsers inside of some huge messy corporate web codebase, probably for webscraping or some kind of semi-structured data cleaning, and the code clammed up in some way.
- dmitrygr 5y agoflex & bison use globals to report things per-rule. Of course they are not re-entrant. This is documented by virtue that those are globals.
- eqvinox 5y agoAnd the fix is to not use globals. cf. my toplevel post about "%option reentrant", "%lex-param" and "%parse-param". Globals are just the 80's setup, and flex/bison are supposed to be POSIX lex/yacc compatible, so I'm gonna count this as "shitty defaults due to compatibility with stone tablets".
- db48x 5y agoCorrect. It’s the default but it’s no longer necessary. Flex has had some work done to push it towards being able to generate Go and Rust code too, though this work isn’t finished. In principle it is now possible to generate any Algol–style language.
- truenindb 5y agoOkay, so yes it is good to note that the GNU lexical generator toolkit does not generate unicode parsers and isn't re-entrant. In general, parsing the same text from multiple threads seems like it could probably lead to more problems than just the fact that the parser generator toolkit for compiler writers isn't re-entrant, but that sounds more like a problem for the 'design' of these folk's client's codebases than anything else to me. It would be nice to see a simple LL(1) lexer/parser generator in C that handles unicode and re-entrancy, although again, the latter one seems like something of a complex concept to me. Having the library generate parsers which are stable across multiple threads using generated parsers to parse different things at once seems like the only stable notion that I'd care about, so I will assume that is what this fellow is talking about.
- lallysingh 5y agoConsider any server side query system. Parsing those queries in only one thread can be prohibitive.
- WesolyKubeczek 5y ago> flex uses a BSD license, while Bison uses the GPL. Bison waive the license for most generated parsers, but it can be a problem Now, this is one of the most atrocious handwavy kind of FUD that I've had a displeasure to see. If the parsers generated by bison are GPL-free, where is the problem? Can you even name the problem? Or you just see the word "GPL" and it's scaring you somehow?
- robocat 5y agoI am guessing that the author is referencing organisations that are pathologically allergic to GPL, where the legal department might not accept the exception. https://www.google.com/search?q=bison+gpl+exception https://www.google.com/search?q=bison+gpl+exception
- WesolyKubeczek 5y agoThe problem is that you have to guess what the problem is, exactly. The author might just as well put up a comparison chart: bison: PROBLEMATIC AND GPL ANTLR: does not have a problem* ---- * With yearly consulting contract from our company The message would be exactly the same.
- yjftsjthsd-h 5y ago"Incompetent legal dept" is not a bug in the product.
- pengwing 5y agoIt's 2021, why not use parsing expression grammar?
- bear8642 5y agoperhaps because you want LALR or other techniques? Can't remember why but my Compilers teacher (Adrian Johnstone, Royal Holloway) doesn't like PEGs - think due to parse forest not being generated?
- mbrodersen 5y agoI use PEG’s all the time. Works great.
- 1vuio0pswjnm7 5y agoEvery person who has compiled a Linux kernel by first typing "make menuconfig" has used a program created with flex and bison.
- eqvinox 5y agoA quick search for "reentrant flex bison" gets me this: https://stanislaw.github.io/2016/03/29/reentrant-parser-using-flex-and-bison.html https://stanislaw.github.io/2016/03/29/reentrant-parser-usin... which in turn links this: https://github.com/blynn/symple/tree/75aaea79141a18a234c94dc8a2a7277d42fe83aa https://github.com/blynn/symple/tree/75aaea79141a18a234c94dc... The magic flags are: %option reentrant and %lex-param { yyscan_t scanner } %parse-param { yyscan_t scanner } %parse-param { val_callback_t callback } ... so ... it seems a reentrant flex/bison parser is easily possible?
- donaldihunter 5y agoReentrancy is a problem for yacc. Bison can generate reentrant parsers https://www.gnu.org/software/bison/manual/bison.html#Pure-Decl https://www.gnu.org/software/bison/manual/bison.html#Pure-De...
- UncleEntity 5y agoI've found re2c + lemon to be a pretty good combination. re2c has good unicode support -- takes a while to compile if attempting TR31 "Unicode Identifier And Pattern Syntax" though. Haven't used lemon on anything too complicated, I basically just play with grammars for fun, but it works really well for my MiniScheme fork I like to poke at every once in a while. My new shiny is Coco/R which is a dream to use (once you get up the learning curve) but hasn't really been maintained for ages.
- egberts1 5y agoAntler doesn’t support C or C++. But they’ll use an obscure C##.
- kcartlidge 5y agoObscure? C#? Lots of people have opinions on the language (or Microsoft themselves) and it may not be up there with C++, Java, and Javascript in terms of adoption. However it's 20+ years old, massively used in enterprise, powers sites like StackOverflow, and is most definitely (by language rankings and surveys) a top tier ecosystem - often in the top 5.
- egberts1 5y agomany embedded systems could not use C++ namely because of lack of real-time capability caused by too-long pauses made by C++ garbage memory collection overhead.
- kcartlidge 5y ago(I presume you mean C#) You're right about embedded systems. Most ecosystems that use a GC would struggle there, including DotNet.
- chmaynard 5y agoSeems odd that the author uses grandiose titles like "The Story of Lex" and "The Story of Yacc" for a few paragraphs of unsubstantiated history. This type of exaggeration makes me skeptical about the accuracy of their claims.
- abss 5y agoFor c/c++ just use lemon: https://en.m.wikipedia.org/wiki/Lemon_(parser_generator) https://en.m.wikipedia.org/wiki/Lemon_(parser_generator) I think that lemon is comming from the same author as sqlite. I used it like 15 years ago ;) but i still remember lemon as high quality piece of software (Much better compared with flex, yacc, bison...)
- akimd 5y ago(I maintain Bison.) While I definitely agree that ANTLR is a great tool, I feel that many of the critics about Bison are somewhat unfair. First of all, many people like to tie Flex and Bison together, and that's wrong. You don't have to use Flex to feed tokens to your Bison parser. And my personal opinion is that Flex is badly maintained. Releases are infrequent, and issues keep on stacking. So please, stop putting Flex and Bison in the same bucket: they _can_ be used together, but they are not maintained by the same people. Second, many people seem to not know that Bison is way more than YACC. To name just a few features of Bison - it goes way beyond LALR(1): IELR(1), canonical LR(1), and GLR are supported - it generates parsers in C, C++, Java and D - it supports push and pull parsing - it supports customized error message generation - it can generate explicit counterexamples about conflicts (see https://en.wikipedia.org/wiki/GNU_Bison#Counterexample_generation https://en.wikipedia.org/wiki/GNU_Bison#Counterexample_gener... to see examples) - it perfectly supports reentrant parsers and it comes with several examples of such parsers (see https://github.com/akimd/bison/tree/master/examples/c https://github.com/akimd/bison/tree/master/examples/c) - and way more. The original article says: > Flex and Bison are very much stable software. They are maintained, but development of new features is limited, if not absent. Before emitting such strong statements about Bison, please at least look at its current state and to the NEWS file (https://git.savannah.gnu.org/cgit/bison.git/tree/NEWS https://git.savannah.gnu.org/cgit/bison.git/tree/NEWS). There were two major releases in 2018, three in 2019 and two in 2020. That's 29 releases in four years if you also count the bug fix releases. Therefore "development of new features is limited, if not absent" is pretty much false. Did the author actually studied Bison before writing all this?