Why not to use (f)lex, yacc or bison • Hacker News Board

Re: Why not to use (f)lex, yacc or bison

#31

Post by chrisseaton » Thu, Mar 05, 2020, 9:32 AM UTC

pansa2 wrote: post #22

kqr wrote: post #17

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.

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

#32

Post by ltratt » Thu, Mar 05, 2020, 9:32 AM UTC

kqr wrote: post #17

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.

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

#33

Post by brutuz » Thu, Mar 05, 2020, 9:49 AM UTC

I have seen multiple projects that run into maintenance problems due to the large grammar with thousands lines and antlr 3/4 incompatibility.

Generally parser generator adds a layer of complexity/constraint which may be significant if you need full control of lexing, parsing, semantic processing, error recovery of your language.

After working on a few language projects (including core language, web-based editor with syntax coloring and auto-completion) myself I would strongly suggest hand-rolled parser for any serous language endeavour(general purpose or DSL).

Re: Why not to use (f)lex, yacc or bison

#34

Post by acqq » Thu, Mar 05, 2020, 9:55 AM UTC

The paper:

https://www.antlr.org/papers/allstar-techreport.pdf

Has the important detail why it scored good in benchmarks against other parsers:

"7.3 Effect of lookahead DFA on performance

The lookahead DFA cache is critical to ALL(*) performance. To demonstrate the cache’s effect on parsing speed, we disabled the DFA and repeated our Java experiments. Consider the 3.73s parse time from Figure 9 to reparse the Java corpus with pure cache hits. With the lookahead DFA cache disabled completely, the parser took 12 minutes (717.6s)."

I'd still most probably hand-roll, at least when making something for a long-term project, and not some "demo" -- there the stability and ease of maintenance is more important than fast availability of initial results.

Re: Why not to use (f)lex, yacc or bison

#35

Post by a3n » Thu, Mar 05, 2020, 9:58 AM UTC

kyeb wrote: post #9

I tried to read this article, but unfortunately the lack of grammar was too distracting and I just couldn't get through it. A lot of these are things that Google Docs or Microsoft Word will notice and ask you to change. I highly recommend using one of those to write (especially if English is not your first language) and trying to understand the suggestions it makes. Your articles will come out much more readable to o…

Counterpoint: I used to "and I stopped reading" when I ran into grammar issues. I gradually realized that it's worth the effort to focus on the underlying ideas and evaluate that, rather than someone's 2nd language ability. People are smart, even when they talk funny, y'all.

(The worth/validity of the underlying ideas is a separate matter.)

Counterpoint 2: Automated grammar corrections are risky unless you're a native speaker. Ironic.

Re: Why not to use (f)lex, yacc or bison

#36

Post by grandinj » Thu, Mar 05, 2020, 10:16 AM UTC

brutuz wrote: post #33

I have seen multiple projects that run into maintenance problems due to the large grammar with thousands lines and antlr 3/4 incompatibility. Generally parser generator adds a layer of complexity/constraint which may be significant if you need full control of lexing, parsing, semantic processing, error recovery of your language. After working on a few language projects (including core language, web-based editor with…

Second this. Recursive descent parsers are much easier in the long run, even if you can't immediately see your grammar after they have grown for a while.

Re: Why not to use (f)lex, yacc or bison

#37

Post by nottorp » Thu, Mar 05, 2020, 10:58 AM UTC

"ANTLR instead is more actively developed. It has been re-written from scratch a few times during the years, so the code has is of good quality."

... rewrites improve code quality ... right ... right???

Re: Why not to use (f)lex, yacc or bison

#38

Post by imtringued » Thu, Mar 05, 2020, 11:00 AM UTC

kqr wrote: post #17

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.

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

#39

Post by adontz » Thu, Mar 05, 2020, 11:14 AM UTC

What I don't like about any of these parsers, including ANTLR is that for real languages you get not a clear EBNF grammar, but terrible mix of declarative and imperative statements. I was pretty sure PEG is the modern way to go, but looks like it's not. So, what is then?

Re: Why not to use (f)lex, yacc or bison

#40

Post by raverbashing » Thu, Mar 05, 2020, 11:20 AM UTC

grandinj wrote: post #36

brutuz wrote: post #33

I have seen multiple projects that run into maintenance problems due to the large grammar with thousands lines and antlr 3/4 incompatibility. Generally parser generator adds a layer of complexity/constraint which may be significant if you need full control of lexing, parsing, semantic processing, error recovery of your language. After working on a few language projects (including core language, web-based editor with…

Second this. Recursive descent parsers are much easier in the long run, even if you can't immediately see your grammar after they have grown for a while.

I would agree but...

From trying to understand parsing and RDPs I think I don't have the part of the brain required to understand it.

Not that it isn't simple, it is. But it seems examples (as usual) overexplain the simple things then overlook something that seems obvious but isn't.

The only time I managed to write a parser for simple math that wasn't an example was through the use of 'reverse production' parsing. Yes, it's the worse way, but it worked for me (this was a long time ago though)