4 ms·

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

by 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!
- chubot 10y ago
  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 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 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.
  - parrt 10y ago
scrame 10y ago
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.
- chubot 10y ago
  I had an interesting thread here with somebody who wrote a pretty complete Ruby parser in Ruby: https://news.ycombinator.com/item?id=13041646 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...
  - vidarh 10y ago
    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 http://hokstad.com/compiler [2] https://github.com/ruby/ruby/blob/trunk/parse.y https://github.com/ruby/ruby/blob/trunk/parse.y
    - chubot 10y ago
      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 http://www.oilshell.org/blog/2017/02/05.html

by chubot 10y ago

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!

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

scrame 10y ago

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.

chubot 10y ago
I had an interesting thread here with somebody who wrote a pretty complete Ruby parser in Ruby: https://news.ycombinator.com/item?id=13041646 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...
- vidarh 10y ago
  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 http://hokstad.com/compiler [2] https://github.com/ruby/ruby/blob/trunk/parse.y https://github.com/ruby/ruby/blob/trunk/parse.y
  - chubot 10y ago
    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 http://www.oilshell.org/blog/2017/02/05.html