4 ms·

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 de

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...
seanmcdirmid 10y ago
> 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.
chubot 10y ago
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/ 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/ 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.
- xenadu02 10y ago
  Swift uses a hand-written parser.
- parrt 10y ago
  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-commercial-compilers-why-not/16503455#16503455 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 http://www.antlr.org/papers/allstar-techreport.pdf Excellent discussion!

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

seanmcdirmid 10y ago

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

chubot 10y ago

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

xenadu02 10y ago
Swift uses a hand-written parser.
parrt 10y ago
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-commercial-compilers-why-not/16503455#16503455 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 http://www.antlr.org/papers/allstar-techreport.pdf Excellent discussion!