Hacker News Reader

The vast majority of the time it is totally okay to quit on a single syntax error. Not everybody -- most -- do not need "speculative parsing", we are not all designing HTML parsers and IDE assists. ANTLR / Bison are fantastic for parsing grammars and parsers written in them are a million times more maintainable than a 1000 line hand rolled parser in C that's ten years old and has been touched by 20 hands. You really can't out perform a parser generator unless you live in an ivory tower where no one will ever modify your code and you have unlimited time to reinvent every wheel that Bison / ANTLR have built in.

In short, ANTLR is great for prototyping a parser but any industrial-grade parser released into the wild with programmers' expectations of helpful error messages would require a hand-written parser.

What an odd statement, in light of the innumerable deployments of Bison / ANTLR parsers you certainly use at least once a day (if you spend any time at all in a terminal).

Your hostile tone means you misunderstood the intent of my message. I wasn't dismissing the usefulness of ANTLR. I was adding extra information on where ANTLR fits in the bigger universe of parsing. This is extra information that ANTLR tutorials never seem to mention.

For example, here's a blurb from ANTLR creator Terence Parr[1]: "Programmers run into parsing problems all the time. Whether it’s a data format like JSON, a network protocol like SMTP, a server configuration file for Apache, _a PostScript/PDF file_, or a simple spreadsheet macro language"

No... using ANTLR is the wrong tool for writing a parser of "PDF files". Parsing real-world PDF files is very similar to parsing wild HTML. PDF files are often broken and noncompliant. Is that the fault of ANTLR?!? Not really, but consumers don't care.

With all the dozens of PDF helper libraries out there, this is probably the #1 bug report transcript:

- programmer/customer: "Your PDF library can't open RealWorldBroken.pdf -- please fix it"

- vendor customer support: "We looked at the pdf file you're trying to open and it's invalid"

- programmer/customer: "Yes but Adobe Acrobat Reader opens it just fine."

- <Vendor of library then adds code workaround to open that invalid file and make customer happy and thereby reinvents Adobe Acrobat's permissive parser -- one bug report at a time>

That last step inside the <angle brackets> is the kind of "industrial grade" parsing that ANTLR grammar files are not good at expressing. By mentioning PDF files, it's misleading people about what ANTLR is really good for. ANTLR is a better lex/yacc. It's not better than a hand-written parser for things like PDF files!

If you have a well-defined parsing problem in the classic "Dragon" book[2] sense and want to skip the tedium of hand writing a parser... yes ANTLR is wonderful for that.

>You really can't out perform a parser generator unless you live in an ivory tower"

You can easily outperform ANTLR if your parsing domain is "messy" and programmers (users of compilers) are looking for more than a binary result of accept/reject of a source file with "invalid token" on line 5 of a 1000 line program. They often want insightful error messages from the compiler that "guesses" the programmer's intentions. For example, the C++ parsing error messages in Clang that's superior to GCC cannot be expressed in a ANTLR grammar file.

[1] https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-re...

[2] https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

> What an odd statement, in light of the innumerable deployments of Bison / ANTLR parsers you certainly use at least once a day (if you spend any time at all in a terminal).

Having worked in the industry for awhile, there are a lot of handwritten parsers out there, especially when you need to build an IDE with code completion. You are right that for small tool-based languages that don't need those things, a grammar-generated parser is completely sufficient, but if you go all in on a more general programming language, you are likely to wind up with a hand written parser eventually.

What an odd statement, in light of the innumerable deployments of Bison / ANTLR parsers you certainly use at least once a day (if you spend any time at all in a terminal).

Which ones? Awk is one; in fact Awk was almost co-developed with yacc. But it gives generally bad error messages. (There are multiple implementations, but most of them use a yacc-style LR(1) grammar and give bad error messages.)

I don't know of any others. Certainly ANTLR generates bad C/C++ code, so I would be very surprised if it's used in anything in a typical Unix/Linux terminal.

I have been blogging about Unix and parsing here, after writing a very complete bash parser by hand: http://www.oilshell.org/blog/

My conclusion is also that generic parser generators are not good enough for production quality parsers. This is borne out by evidence in the wild.

In other words, "real" languages don't use parser generators. Look at the top 10 languages, as well as emerging languages. Which one of them use parser generators?

Clang, GCC, v8, PHP, C# / Roslyn, Go, Perl, TypeScript, Dart, etc. all use hand-written parsers. Not sure about Rust and Swift, but I think they are hand-written. Java is an exception, but interestingly it has a "real" grammar, and then a LALR(1) optimized for parser generators:

http://trevorjim.com/is-java-context-free/

Python uses ITS OWN parser generator, not a generic one, which is a very important distinction.

I'm not sure about Ruby, I think it might be a yacc core with A LOT of ad-hoc parsing, so it may not count. Just like bash uses yacc for about 1/4 of the language, and ad hoc hand-written parsers for the other 3/4.

Anyway, I don't think parser generators are as widely used as you think, but I would be happy to be corrected.

Swift uses a hand-written parser.

Howdy! It is definitely the case that most production languages use handbuilt parsers. In talking with these compiler developers, they are obsessed with control (speed, error reporting, ...) and want very specific data structures built during the parse. They also tend to use existing lexer infrastructure that is baked into their development environments. I commented more on this topic here: http://stackoverflow.com/questions/16503217/antlr-for-commer...

The thing to remember is that the vast majority of parsers out there are not for these production language compilers. Compare the number of people you know that have built parsers for a DSL, data, documents, or whatever to the number of people you know that built compilers. ANTLR's niche is for your everyday parsing needs. It generates fast ALL(*) parsers in a multitude of languages and accepts all grammars without complaint, with the minor constraint that it cannot handle indirect left recursion. (Direct left recursion as an expressions is totally okay.) For a speed shootout with other tools, see OOPSLA paper http://www.antlr.org/papers/allstar-techreport.pdf

Excellent discussion!

Thanks for the response. Yes I think we are agreeing -- I have 2 of your books, and have read many of your ANTLR-related papers, and they were definitely the thing that taught me the most about top-down parsing. (I also used to share an office with Guido van Rossum and I remember he had your books too.)

I ported the POSIX shell grammar to both ANTLR v3 and v4 (which was basically changing yacc-style BNF to EBNF). But as mentioned, I discovered that the grammar only covers about 1/4 of the language. bash generates code with the same grammar using yacc, but fills in the rest with hand-written code. Every other shell I've encountered uses a hand-written parser. bash says they regret using yacc here:

http://www.aosabook.org/en/bash.html

I agree with you that there is a Pareto or long tail distribution in parser use cases. Most languages CAN use something like ANTLR or bison. But the parent was making a different claim:

What an odd statement, in light of the innumerable deployments of Bison / ANTLR parsers you certainly use at least once a day (if you spend any time at all in a terminal).

I would say that is FALSE, because most parsers that your fingers pass through are HAND-WRITTEN, because of the Pareto distribution. 99% of anyone's usage is of probably a dozen or so parsers, and they are either hand-written or generated by custom code generators, not general-purpose code generators like ANTLR or yacc.

-----

As feedback from a user of parsing tools, you might also be interested in my article here:

https://news.ycombinator.com/item?id=13628412

Someone is asking if there are any parsing tools that generate a "lossless syntax tree".

Also, based on my experience with ANTLR v3 vs. v4, I ask the question why use a concrete syntax tree at all? Nobody answered that question in the comments. I don't understand why that is a good representation, other than the fact that you might not want to clutter your grammar with semantic actions ("pure declarative syntax").

To me the parse tree / CST seems to be resource-heavy while containing unnecessary information, and also lacking some crucial information like where there's whitespace and comments.

To summarize my article, I'm researching code representations in the wild for both style-preserving source translation (like go fix, lib2to3 in Python) and auto-formatting (like go fmt).

It's definitely possible I misunderstood something since my experience was relatively limited, but I have read a lot of the docs and bought the books.

> why use a concrete syntax tree at all?

Do you mean instead of an AST? I find the syntax tree better for non-compiler applications like translators.

My claim is that neither the parse tree/CST or AST is good for applications like translators. Instead I defined another term Lossless Syntax Tree, which is the data structure I want:

http://www.oilshell.org/blog/2017/02/11.html

I researched "production" implementations, and found that they use something like a Lossless Syntax Tree (not an AST or CST):

https://github.com/oilshell/oil/wiki/Lossless-Syntax-Tree-Pa...

Examples: Clang, Microsoft's Roslyn platforms, RedBaron/lib2to3 for Python, scalameta, and Go. The defining property of the LST is that it can be round-tripped back to the source. This is called out in this C# design doc, along with some conventions for associating whitespace with syntax tree nodes:

https://github.com/dotnet/roslyn/wiki/Roslyn-Overview

What do you think of that claim? (If you prefer not to use this deep comment thread, feel free to contact me by e-mail instead at andychup@gmail.com.)

I've heard many compilers started with yacc/bison, but later went hand-written for better error messages.

Currently, jq (pretty much, awk for json https://stedolan.github.io/jq/) uses bison, but sometimes has unhelpful syntax error messages. I'm not the maintainer or anything, but trying to trigger error messages more precisely (i.e. diagnosis) was a nightmare.

While a generator can't match a custom parser for control, is it plausible to have arbitrarily precise hooks in ANTLR for diagnostic messages?

BTW unfortunately deadlink http://stackoverflow.com/questions/16503217/antlr-for-commer...

> Compare the number of people you know that have built parsers for a DSL, data, documents, or whatever

The vast majority of those people that I know of have not even been aware of tools like ANTLR, and usually resort to regexp-based abominations instead unless they happen to know about bison/yacc (slightly more likely than ANTLR).

I agree those are cases where a tool like ANTLR might very well be preferable to someone hacking together a regexp-driven mess, but my personal experience is that the people most likely to know about these tools are also the people most likely to know how to handwrite reasonably clean parsers.

Some subset certainly will opt for the tools some of the time (I have done that myself, even though I much prefer handwritten parsers; I've also written parser generation tools myself, out of frustration with the existing ones... Im still frustrated enough by my own tools to end up handwriting parsers... (EDIT: Clarified; I could use a good parser to check my English sometimes) ), but the parser-generation field is a peculiar one.

I have no doubt that sooner or later someone will crack this nut (maybe ANTLR will be that tool one day) and handwriting parsers will go the way of handwriting assembler and be something you do only in rare cases, but we're far from there still.

Note that I'm not saying ANTLR is a bad tool. I'm saying this is a space where a lot of the potential audience are a bunch of very difficult to convince and picky people (myself included...), and where a large other part of the audience doesn't know the field at all and are unaware of the tools.

Haven't looked at the ruby source in ages, but it definitely had a yacc grammar in there in, I guess the 1.8 days.

edit: of course there could be handwritten extensions, but I didn't dive that deep.

I had an interesting thread here with somebody who wrote a pretty complete Ruby parser in Ruby:

https://news.ycombinator.com/item?id=13041646

The "canonical" documentation of the Ruby parser is basically a 6000+ line Bison file where most of the linecount is taken up with handling exceptions... It's awful.

That sounds very like much like bash, where parse.y is 6227 lines. Almost of all of it is C code, it's not actually using very much of yacc...

That'd be me... Though with the caveat that my parser (part of this project[1] ) still has fairly substantial gaps, so it will grow, but certainly not to the size of MRI's parse.y.

It's actually worse these days it turns out parse.y for Ruby is 11348 lines [2], though for fairness it's worth noting that it's written in a quite "linefeed heavy" style, and this includes providing a Ruby API to the parser.

[1] http://hokstad.com/compiler

[2] https://github.com/ruby/ruby/blob/trunk/parse.y

Yikes! 11K lines is a lot. I guess my conclusion is the same as last time: human brains are good at parsing very elaborate languages. People like all that subtle "expressiveness".

I think my bash parser is pretty complete, and it's about 4K lines in Python now, including the lexer. Changing it to the lossless syntax tree vs AST blew it up by a few hundred lines.

However, it does more than the 6K lines in bash's parse.y, because it parses in a single pass. Bash does more parsing in the 9700 line file subst.c, so it's hard to count.

But yeah I'm about to write my Oil parser now, as opposed to the OSH parser... I really want to avoid writing another 4K lines of code!!! That might be the most practical way though. :-(

http://www.oilshell.org/blog/2017/02/05.html

I guess ANTLR should have some support for "outside of the happy path parsing": As far as I know it's also used as the parsing part of the XText framework, which allows to create custom languages and which will also create eclipse plugins for editing these. These plugins also need to be error tolerant for providing intellisense support during editing, and at least from a user point of view that seems to work.

> 2) ANTLR was not good for speculative parsing or probabilistic parsing which would be the basis of today's generation of tools such as "Intellisense" not giving up on parsing when there's an unclosed brace or missing variable declaration.

ANTLR does have some generic error recovery capabilities such as single token insertion/deletion or re-sync recovery.

There is a whole chapter describing the algorithms in the ANTLR book: http://media.pragprog.com/titles/tpantlr/errors.pdf (unfortunately this link does not contain the full content of the chapter).

These kinds of generic heuristics is not something that would be simple to implement in most hand build parsers as they require full knowledge of the entire grammar and that information is often "hard coded" as source code not as a separate data structure.

ANTLR has one of the best error handling strategies of the tools I've used; what do you use that is better in this regard (maybe I need to expand my horizon a bit)?

Most people use hand written parsers for this, for the lack of tools that are good enough. Part of the reason for the proliferation of of parser generation tools is that people tend to get disillusioned by the available tools in this space very quickly.

I tried some of the earlier versions of the JS target (v4). Like you say: the happy path works well. What I disliked is that, in unpredictable cases, there were nulls in the generated output. This made me feel doubtful about using it, so I wrote my own parser by hand. It turned out to be a good decision: it was fun, and I learned a lot.

Even so, ANTLR is a great productivity improvement (as other similar compiler generator tools), over those stuck on yacc/lex days.

Also many languages don't survive the prototyping phase into some kind of product, so why bother with premature optimizations?

I've asked this before, and I'll ask it again: How is ANTLR an improvement over menhir/ocamllex?

LR has fewer constraints than LL(n), menhir's documentation is better and splitting lexing/parsing IMO adds clarity.

ANTLR isn't LL(k), it's predicated LL(*).

Also, there can be advantages to having a top-down parser for semantic actions.

And I will answer again, it provides GUI tooling for several phases of compiler development, including debugging.

The technical aspect of how the grammar is parsed, is a matter of taking the effort to design it in a LL (*) compatible way.

This was my experience too. Did you find any standard cost-based robust parsers or are we still stuck rolling our own?

I think most of the creators of quality compilers have written huge numbers of toys (or experimental) compilers before.