Hacker News Reader

Comment by yanowitz | Hacker News Reader

They are used to build a number of tools you probably rely on or use regularly, including ruby, golang, bash, MySQL and postgresql.

View on HN

golang uses a handwritten recursive decent parser and handwritten lexer.

https://github.com/golang/gofrontend/blob/master/go/parse.cc https://github.com/golang/gofrontend/blob/master/go/lex.cc

I can't think of a single major tool that uses ANTLR or bison. I say that being a huge ANTLR fan. Parser/lexer generators are really easy to use for DSLs but for real languages and tools, they're too heavyweight and constraining.

PHP appears to. It was the first language that came up in my Github search, and I stopped looking there.

Does postgres count ? https://wiki.postgresql.org/wiki/Debugging_the_PostgreSQL_gr...

GCC used to use bison. I don't think GCC became a major project recently. But you're correct that recursive descent is more efficient. Not everything is efficiency though (parsers are usually 1% of compile time since they're dirt cheap compared to code generator and especially static analyzer and optimizer). Bison makes parsing extremely simple. I can't see why anyone would use recursive descent unless they're a super major project and need to squeeze every ms.

A big part of why tools move away from Bison and ANTLR isn’t performance, but UX (especially error reporting)

In my experience recursive descent doesn't have any better error reporting than Bison or ANTLR. Parser combinators are much better if error reporting is what you're aiming for. Also, for LALR/LR parsers like Bison/ANTLR, the canonical trick is to encode errors in your grammar, which really isn't a huge deal. E.g. in pseudocode

    suite: stmt ';' stmt {/* ok */}
         | one_line_stmt NEWLINE stmt {raise("you need a ';' there buddy");}
         | // other rules
         ;

obviously this won't be useful for every case in general, otherwise why use ';' at all, but in most cases it'll give a helpful error.

Some more powerful parsers like Earley Algorithm have much worse error reporting.

context sensitive grammars.

You can deal with context sensitive grammars with "lexer trick" or multiple pass parsers.

That's the gccgo frontend; the more usual Go compiler is here: https://github.com/golang/go/tree/master/src/cmd/compile/int...

It's still handwritten though so your point stands.

> Parser/lexer generators are really easy to use for DSLs but for real languages and tools, they're too heavyweight and constraining.

Haskell and OCaml are examples of real languages that use parser generators.

GHC: https://github.com/ghc/ghc/blob/master/compiler/parser/Parse...

Ocaml: https://github.com/ocaml/ocaml/blob/trunk/parsing/parser.mly

Golang also has its own linker and assembler (going as far as having different notation for asm instructions), it doesn't count in these comparisons.

Reply on news.ycombinator.com