7 ms·

I last played around with ANTLR in 2012 (when it was version 3) and I discovered that there's a "bigger picture" to the parser generator universe that most tuto

by jasode 10y ago

I last played around with ANTLR in 2012 (when it was version 3) and I discovered that there's a "bigger picture" to the parser generator universe that most tutorials don't talk about: 1) ANTLR is a good tool for generating "happy path" parsers. With a grammar specification, it easily generates a parser that accepts or rejects a piece of source code. However, it's not easy to use the hooks to generate high quality diagnostic error messages. 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. The common theme to the 2 bullet points above is that a high quality compiler written by hand will hold multiple "states" of information and an ANTLR grammar file doesn't really have an obvious way to express that knowledge. A pathological example would be the numerous "broken HTML" pages being successfully parsed by browsers. It would be very hard to replicate how Chrome/Firefox/Safari/IE doesn't choke on broken HTML by using ANTLR to generate an HTML parser. 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. Lastly, the lexing (creating the tokens) and parsing (creating the AST) is a very tiny percentage of the total development of a quality compiler. Therefore, ANTLR doesn't save as much time as one might think. I welcome any comments about v4 that makes those findings obsolete.

reacweb 10y ago
I think most of the creators of quality compilers have written huge numbers of toys (or experimental) compilers before.
pjmlp 10y ago
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?
- 01928301 10y ago
  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.
  - rbehrends 10y ago
    ANTLR isn't LL(k), it's predicated LL(*). Also, there can be advantages to having a top-down parser for semantic actions.
  - pjmlp 10y ago
    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.
_pmf_ 10y ago
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)?
- vidarh 10y ago
  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.
edko 10y ago
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.
corndoge 10y ago
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).
- jasode 10y ago
  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-reference https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-re... [2] https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
Matthias247 10y ago
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.
cityhall 10y ago
This was my experience too. Did you find any standard cost-based robust parsers or are we still stuck rolling our own?
bd82 10y ago
> 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 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.

by jasode 10y ago

reacweb 10y ago

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

pjmlp 10y ago

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?

01928301 10y ago
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.
- rbehrends 10y ago
  ANTLR isn't LL(k), it's predicated LL(*). Also, there can be advantages to having a top-down parser for semantic actions.
- pjmlp 10y ago
  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.

_pmf_ 10y ago

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

vidarh 10y ago
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.

edko 10y ago

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.

corndoge 10y ago

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

jasode 10y ago
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-reference https://pragprog.com/book/tpantlr2/the-definitive-antlr-4-re... [2] https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

Matthias247 10y ago

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.

cityhall 10y ago

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

bd82 10y ago

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