4 ms·

> Basically no serious programming language uses bison or flex, https://en.wikipedia.org/wiki/GNU_Bison#Use https://en.wikipedia.org/wiki/GNU_Bison#Use: Ruby,

> Basically no serious programming language uses bison or flex, https://en.wikipedia.org/wiki/GNU_Bison#Use https://en.wikipedia.org/wiki/GNU_Bison#Use: Ruby, PHP, GCC until 2004, Go, Bash, PostgreSQL, MySQL, Perl. Can we stop with this "duh, real programmers write their own handwritten parsers"? Parser generators are awesome! They force you to write a declarative grammar which a human can understand. If you're designing a language this is very useful. With a handwritten parser you're very likely to encode some unintended behaviour in edge cases; using a parser generator early in this process will very quickly reveal the ambiguities. That doesn't mean that parser generators are always the best. There are many use cases where a handwritten parser is better. But the picture is way more nuanced than "no serious programming language uses bison or flex".

chrisseaton 7y ago
> They force you to write a declarative grammar which a human can understand. The problem is many languages' grammars are not declarative. They're full of completely uncontrolled side effects. So why are we trying to use a declarative tool for them? It's the wrong tool for the job.
- hasbot 7y ago
  How is that relevant to this thread in which I am saying that the parsing/lexing as described in the link is very outdated? Maybe you should start a separate discussion.
  - chrisseaton 7y ago
    > Maybe you should start a separate discussion. I started this one!
- judofyr 7y ago
  > It's the wrong tool for the job. Yes! We should have both handwritten parsers and parser generators in our toolkit and then depending on the language we want to parse we should choose the best tool for the job. My point about a declarative grammar was more that if the language permits it (e.g. is simple enough for Bison), it's so valuable to have a declarative grammar which serves as both specification and parser. It will be way less bug-prone than any handwritten parser. (From my experience handwritten parsers tends to have both weird crashes and unexpected handling of edge cases. But maybe I just suck at programming?) I've seen people using Bison on one complicated languages, given up, and then they bring the negative bias to other languages they want to parse — even when the other languages are very simple.
dbcurtis 7y ago
The problem with LALR parser generators is that you end up with an LALR parser. Which is fine as long as the input is error-free, but trying to get a reasonable error message out of any LALR parser is about as much fun as repeatedly poking yourself in the eye with a sharp stick. FLEX, on the other hand, is perfect for the job. I can't imagine why anyone would hand-write a lexer.
- jcranmer 7y ago
  > FLEX, on the other hand, is perfect for the job. I can't imagine why anyone would hand-write a lexer. Flex introduces a new dependency to your project, which involves generating source files at build time. This is a lot of complexity in your build system if this is the first time you need it. And it also by default uses a style that isn't really modern--it's more annoying to use if you want to use it in a multithreaded programming, or if you want to have multiple lexers in one program. (Or you're not even using C/C++ in the first place!). Furthermore, lexers are actually really easy to write. Most tokens [1] are recognizable within a character or two, and usually amount to a regex on the order of [a-z][a-z0-9_]+ or "([^\"]|\.)*" -- the sorts of regexes that have very trivial implementations to handcode. The lexer I wrote for a JSON-ish file format is 128 lines of code. Sure, it'd be more like 30 lines of code if I used an automatic generator, but running into any issues integrating the automatic generator into my workflow would toss out the benefits of saving 100 lines of code. [1] Excluding keywords, but keywords are usually implemented by parsing it as an identifier and looking for the identifier in a hashtable of known keywords.
- beagle3 7y ago
  In my experience, re2c is an improvement on lex/flex in most ways, but I agree - flex is indeed nicer than hand-rolled in every way (except if you are Arthur Whitney - his hand rolled lexers are a marvel)
jcranmer 7y ago
The current go compiler uses a hand-written parser, judging from it's source. The benefit of having a BNF grammar for your language is rightfully enormous, and all modern languages definitely lay out their lexing grammar and BNFs explicitly in their specification. But there are downsides. Debugging LALR grammars is painful; error conditions are almost uniformly painful. Many languages make tokenization dependent on the current context of a parse for language ergonomic reasons [1], and you might not be able to specify the action in the right place in your automated parser generator. Hell, the language might not even conform to the LL(k) or LALR(1) your parser generator translates. [1] I'd say this is context-sensitive lexing, but the resulting grammar isn't context-sensitive. Just somewhat more complicated than a naive translation of the grammar would indicate.
patrec 7y ago
I'm guilty of being overly hyperbolic, and you are right to correct me. But if your poster boys to illustrate the benefits of parser generators forcing you to write a declarative grammar which a human can understand are perl, bash or even postgresql, I'm not sure what to say ;) Apart from Go, (and maybe PHP, which I don't know well enough to judge) all the languages you list have pretty horrible syntax that probably few (ruby?) to basically none of its users (bash, perl, C++, postgresql) really understand.
- hasbot 7y ago
  > if your poster boys to illustrate the benefits of parser generators forcing you to write a declarative grammar which a human can understand are perl, bash or even postgresql, I'm not sure what to say ;) And that is a straw man argument because, of course, no one is saying that.
- hyperpape 7y ago
  Agreed. I'm not going to say whether Ruby syntax is nice or not, but its use of parser generators is not a model of simplicity: https://github.com/ruby/ruby/blob/master/parse.y https://github.com/ruby/ruby/blob/master/parse.y https://whitequark.org/blog/2013/04/01/ruby-hacking-guide-ch-11-finite-state-lexer/ https://whitequark.org/blog/2013/04/01/ruby-hacking-guide-ch... It also changes syntax in patch level versions: https://github.com/whitequark/parser https://github.com/whitequark/parser.
userbinator 7y ago
I can name just as many "serious programming language" implementations that use recursive descent or migrated to it because a parser generator turned out to be a bad idea after all: Java, MSVC, GCC (after 2004), Clang/LLVM, ICC, C#, PowerShell, V8(JavaScript). They force you to write a declarative grammar which a human can understand It's a separate language that also has to be learnt, an extra step in the compilation process, and the difficulty of debugging parser-generator-generated code cannot be overstated. A recursive-descent parser written in a programming language is easily understood, debuggable, and does not incur any extra complexity. Perhaps that is where the "no serious programming language" argument comes from --- the migration away from parser generators is a sign that the language has received enough attention such that the limitations of a generated parser become prominent.

chrisseaton 7y ago

> They force you to write a declarative grammar which a human can understand. The problem is many languages' grammars are not declarative. They're full of completely uncontrolled side effects. So why are we trying to use a declarative tool for them? It's the wrong tool for the job.

hasbot 7y ago
How is that relevant to this thread in which I am saying that the parsing/lexing as described in the link is very outdated? Maybe you should start a separate discussion.
- chrisseaton 7y ago
  > Maybe you should start a separate discussion. I started this one!
judofyr 7y ago
> It's the wrong tool for the job. Yes! We should have both handwritten parsers and parser generators in our toolkit and then depending on the language we want to parse we should choose the best tool for the job. My point about a declarative grammar was more that if the language permits it (e.g. is simple enough for Bison), it's so valuable to have a declarative grammar which serves as both specification and parser. It will be way less bug-prone than any handwritten parser. (From my experience handwritten parsers tends to have both weird crashes and unexpected handling of edge cases. But maybe I just suck at programming?) I've seen people using Bison on one complicated languages, given up, and then they bring the negative bias to other languages they want to parse — even when the other languages are very simple.

dbcurtis 7y ago

The problem with LALR parser generators is that you end up with an LALR parser. Which is fine as long as the input is error-free, but trying to get a reasonable error message out of any LALR parser is about as much fun as repeatedly poking yourself in the eye with a sharp stick. FLEX, on the other hand, is perfect for the job. I can't imagine why anyone would hand-write a lexer.

jcranmer 7y ago
> FLEX, on the other hand, is perfect for the job. I can't imagine why anyone would hand-write a lexer. Flex introduces a new dependency to your project, which involves generating source files at build time. This is a lot of complexity in your build system if this is the first time you need it. And it also by default uses a style that isn't really modern--it's more annoying to use if you want to use it in a multithreaded programming, or if you want to have multiple lexers in one program. (Or you're not even using C/C++ in the first place!). Furthermore, lexers are actually really easy to write. Most tokens [1] are recognizable within a character or two, and usually amount to a regex on the order of [a-z][a-z0-9_]+ or "([^\"]|\.)*" -- the sorts of regexes that have very trivial implementations to handcode. The lexer I wrote for a JSON-ish file format is 128 lines of code. Sure, it'd be more like 30 lines of code if I used an automatic generator, but running into any issues integrating the automatic generator into my workflow would toss out the benefits of saving 100 lines of code. [1] Excluding keywords, but keywords are usually implemented by parsing it as an identifier and looking for the identifier in a hashtable of known keywords.
beagle3 7y ago
In my experience, re2c is an improvement on lex/flex in most ways, but I agree - flex is indeed nicer than hand-rolled in every way (except if you are Arthur Whitney - his hand rolled lexers are a marvel)

jcranmer 7y ago

The current go compiler uses a hand-written parser, judging from it's source. The benefit of having a BNF grammar for your language is rightfully enormous, and all modern languages definitely lay out their lexing grammar and BNFs explicitly in their specification. But there are downsides. Debugging LALR grammars is painful; error conditions are almost uniformly painful. Many languages make tokenization dependent on the current context of a parse for language ergonomic reasons [1], and you might not be able to specify the action in the right place in your automated parser generator. Hell, the language might not even conform to the LL(k) or LALR(1) your parser generator translates. [1] I'd say this is context-sensitive lexing, but the resulting grammar isn't context-sensitive. Just somewhat more complicated than a naive translation of the grammar would indicate.

patrec 7y ago

I'm guilty of being overly hyperbolic, and you are right to correct me. But if your poster boys to illustrate the benefits of parser generators forcing you to write a declarative grammar which a human can understand are perl, bash or even postgresql, I'm not sure what to say ;) Apart from Go, (and maybe PHP, which I don't know well enough to judge) all the languages you list have pretty horrible syntax that probably few (ruby?) to basically none of its users (bash, perl, C++, postgresql) really understand.

hasbot 7y ago
> if your poster boys to illustrate the benefits of parser generators forcing you to write a declarative grammar which a human can understand are perl, bash or even postgresql, I'm not sure what to say ;) And that is a straw man argument because, of course, no one is saying that.
hyperpape 7y ago
Agreed. I'm not going to say whether Ruby syntax is nice or not, but its use of parser generators is not a model of simplicity: https://github.com/ruby/ruby/blob/master/parse.y https://github.com/ruby/ruby/blob/master/parse.y https://whitequark.org/blog/2013/04/01/ruby-hacking-guide-ch-11-finite-state-lexer/ https://whitequark.org/blog/2013/04/01/ruby-hacking-guide-ch... It also changes syntax in patch level versions: https://github.com/whitequark/parser https://github.com/whitequark/parser.

userbinator 7y ago

I can name just as many "serious programming language" implementations that use recursive descent or migrated to it because a parser generator turned out to be a bad idea after all: Java, MSVC, GCC (after 2004), Clang/LLVM, ICC, C#, PowerShell, V8(JavaScript). They force you to write a declarative grammar which a human can understand It's a separate language that also has to be learnt, an extra step in the compilation process, and the difficulty of debugging parser-generator-generated code cannot be overstated. A recursive-descent parser written in a programming language is easily understood, debuggable, and does not incur any extra complexity. Perhaps that is where the "no serious programming language" argument comes from --- the migration away from parser generators is a sign that the language has received enough attention such that the limitations of a generated parser become prominent.