Hacker News Reader

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

Swift uses a hand-written parser.