5 ms·

I'm curious about this chapter: "Why not a parser generator" Seemse like the way to go these days? Why write it yourselve if you can generate it from EBNF not

by TeeWEE 7y ago

I'm curious about this chapter: "Why not a parser generator" Seemse like the way to go these days? Why write it yourselve if you can generate it from EBNF notation?

misternugget 7y ago
Author here. I'm going to be super shameless here and quote myself in that chapter: > [...] we are here to learn, we want to understand how parsers work. And it’s my opinion that the best way to do that is by getting our hands dirty and writing a parser ourselves. Also, I think it’s immense fun. In other words: use a parser generator when you need a working parser, quick. But if you want to learn how parsers work, what ASTs are, what "top-down parsing" means, etc. then I recommend you write your own. It's not that hard once the concept "clicked" and, again, it's a ton of fun :)
- alexgmcm 7y ago
  Yeah, I did the Nand2Tetris course which culminates in writing a toy compiler and the philosophy there is the same as yours. I really like that philosophy - as Feynman said: "What I cannot build I do not understand"
  - tom_mellior 7y ago
    > "What I cannot build I do not understand" This is true, but it provides no guidance on the question whether you need to understand it. If you don't want to build a web browser, you don't need to understand how web browsers are built. That doesn't mean that it is dishonorable for you to use a web browser. So do you need to understand how generated parsers work? I think that's a matter of preference that Feynman doesn't help you decide.
    - macintux 7y ago
      If you’re designing a language, it’s not a stretch to assume that understanding how parsers work would be useful.
      - tom_mellior 7y ago
        I think "you plug a grammar into a generator, and you get back a function that maps character sequences to a syntax tree" can be enough understanding for a lot of use cases. Maybe you're more interested in any of the many other aspects that go into designing and implementing an interpreted language -- type checking, garbage collection, an efficient bytecode format and interpreter for example. But maybe you aren't, in which case I agree that case a hand-written parser might be right up your alley! There's no one size fits all.
        greenshackle2 7y ago
        You need a little bit more than that, cause if that is the limit of your understanding, you will have a bad time when the generator spits back an error message about reduce/reduce conflicts or whatever instead of a function.
- pizza234 7y ago
  > use a parser generator when you need a working parser, quick. Not necessarily. Use it also when you need a more correct one :-) The way the book presents the parsing subject leaves the impression that a handcrafted parser is generally preferrable. I have experience with a project that was based on that book, and there were (and probably, are) a lot of bugs in the parsing code, that wouldn't have been there if a parser generator was used. I don't camp for using parser generator at all costs, however, presenting both sides of the coin would allow readers to make a (more) informed choice.
  - misternugget 7y ago
    > I have experience with a project that was based on that book, and there were (and probably, are) a lot of bugs in the parsing code, that wouldn't have been there if a parser generator was used. I think I need to a add a big "do. not. use. in. production!" disclaimer then :) The parser we build in the book is, of course, not a battle-tested, industrial-grade parser that can survive every fuzzer you throw at it. Far from it, but that's fine, since that was never the goal. The goal was always to learn. So, yes, I agree. If you do need a production-ready, stable parser: use a mature parser generator or, maybe, invest more time in getting good at writing parsers than it takes to read and work through the ~100 pages I wrote on the subject.
    - bigtunacan 7y ago
      Since you have written a book in the subject you obviously are much more of an expert than I am. After reading your book what materials would you recommend for someone wanting to reach the stage is bring able to implement their on "production grade" parsers?
wyufro 7y ago
In my experience the hardest part of using parser generators is to have them create understandable errors. Also it's questionable that they add very much. Parsing text isn't all that difficult. The hard part is to get the tree structure of the AST right. All in all the parsing is a quite small part of a compiler. I've converted from a parser generated to manual code in two different projects and they actually ended up with less lines of code after the conversion, if just barely.
tom_mellior 7y ago
I think the conventional wisdom is that parser generators make it hard(er) to produce useful error messages for users. There are some exceptions, for example: http://pauillac.inria.fr/~fpottier/slides/fpottier-2015-11-oups.pdf http://pauillac.inria.fr/~fpottier/slides/fpottier-2015-11-o... (don't be put off by the French title, the rest is in English).
- pizza234 7y ago
  An interesting argument against that is: > There’s also some argument made by GCC and Clang teams that they can hand-tune a hand written- parser to get better error messages. I believe they can do such hand tuning and probably have. But that argument does not stop you from customizing the grammar for generated parser to do essentially the same thing, so I don’t buy it as a differentiator. This is an excerpt from an interesting Quora reply on the subject: https://www.quora.com/Are-there-many-established-programming-languages-that-use-a-handcrafted-parser-Why/answer/Ira-Baxter https://www.quora.com/Are-there-many-established-programming...
  - tom_mellior 7y ago
    Yes, given a sufficiently powerful parser generator (more powerful than Yacc), you can do that. That's also the point of the talk I linked. Ira Baxter makes a living out of selling proprietary technology based on GLR parsing. His opinion matters, but if there is no open source GLR parser generator available (is there? I don't know), the point he makes cannot apply to GCC or Clang.
    - mjos 7y ago
      I believe GNU Bison parser generator is capable of generating GLR parsers: https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html https://www.gnu.org/software/bison/manual/html_node/GLR-Pars...
      - thosakwe 7y ago
        Oh wow, that's pretty cool, wish I had known about it before. Unfortunately flex and bison, when used together in C++, cause a lot of headache (unless you create an "adapter" class that wraps your Flex parser and pass that to Bison). :/
spinningslate 7y ago
He discussed that on the Corecursive podcast episode [0]. > Why not a parser generator IIRC it was about "minimising magic" - showing what's actually involved in native code. Bob Nystrom makes the same decision in "Crafting Interpreters [1]. Quoting [2]: "Many other language books and language implementations use tools like Lex and Yacc, “compiler-compilers” to automatically generate some of the source files for an implementation from some higher level description. There are pros and cons to tools like those, and strong opinions—some might say religious convictions—on both sides. We will abstain from using them here. I want to ensure there are no dark corners where magic and confusion can hide, so we’ll write everything by hand. As you’ll see, it’s not as bad as it sounds and it means you really will understand each line of code and how both interpreters work." [0] https://corecursive.com/037-thorsten-ball-compilers/ https://corecursive.com/037-thorsten-ball-compilers/ [1] https://craftinginterpreters.com/ https://craftinginterpreters.com/ [2] https://craftinginterpreters.com/introduction.html#the-code https://craftinginterpreters.com/introduction.html#the-code
azhenley 7y ago
The C# and Go parsers do not use a parser generator, iirc.
- weberc2 7y ago
  I believe you are correct about Go. The rationale I recall was that generated parsers were slower and afforded less control over error reporting. Notably wrt performance, fast compilation was a major goal for Go from the beginning.
chrisseaton 7y ago
> Seems like the way to go these days? No I think people use parser generators less these days. > Why write it yourselves if you can generate it from EBNF notation? Can you write EBNF for it? Can you generate a parser from the EBNF? EBNF and most parser generators are designed for context-free languages. Most languages are context-sensitive. You can see where things start to go wrong...
azhenley 7y ago
One of the C# developers commented [1] on HN that they use a hand written parser for three reasons: incremental re-parsing, better error reporting, and resilient parsing (i.e., you still get a syntax tree even if something doesn't parse). [1] https://news.ycombinator.com/item?id=13915150 https://news.ycombinator.com/item?id=13915150
MrBuddyCasino 7y ago
If you are super familiar with EBNF notation, it may be the fastest way. Otherwise I like parser combinators for their simplicity, you just need to understand the host language.

by TeeWEE 7y ago

I'm curious about this chapter: "Why not a parser generator" Seemse like the way to go these days? Why write it yourselve if you can generate it from EBNF notation?

misternugget 7y ago

Author here. I'm going to be super shameless here and quote myself in that chapter: > [...] we are here to learn, we want to understand how parsers work. And it’s my opinion that the best way to do that is by getting our hands dirty and writing a parser ourselves. Also, I think it’s immense fun. In other words: use a parser generator when you need a working parser, quick. But if you want to learn how parsers work, what ASTs are, what "top-down parsing" means, etc. then I recommend you write your own. It's not that hard once the concept "clicked" and, again, it's a ton of fun :)

alexgmcm 7y ago
Yeah, I did the Nand2Tetris course which culminates in writing a toy compiler and the philosophy there is the same as yours. I really like that philosophy - as Feynman said: "What I cannot build I do not understand"
- tom_mellior 7y ago
  > "What I cannot build I do not understand" This is true, but it provides no guidance on the question whether you need to understand it. If you don't want to build a web browser, you don't need to understand how web browsers are built. That doesn't mean that it is dishonorable for you to use a web browser. So do you need to understand how generated parsers work? I think that's a matter of preference that Feynman doesn't help you decide.
  - macintux 7y ago
    If you’re designing a language, it’s not a stretch to assume that understanding how parsers work would be useful.
    - tom_mellior 7y ago
      I think "you plug a grammar into a generator, and you get back a function that maps character sequences to a syntax tree" can be enough understanding for a lot of use cases. Maybe you're more interested in any of the many other aspects that go into designing and implementing an interpreted language -- type checking, garbage collection, an efficient bytecode format and interpreter for example. But maybe you aren't, in which case I agree that case a hand-written parser might be right up your alley! There's no one size fits all.
      - greenshackle2 7y ago
        You need a little bit more than that, cause if that is the limit of your understanding, you will have a bad time when the generator spits back an error message about reduce/reduce conflicts or whatever instead of a function.
pizza234 7y ago
> use a parser generator when you need a working parser, quick. Not necessarily. Use it also when you need a more correct one :-) The way the book presents the parsing subject leaves the impression that a handcrafted parser is generally preferrable. I have experience with a project that was based on that book, and there were (and probably, are) a lot of bugs in the parsing code, that wouldn't have been there if a parser generator was used. I don't camp for using parser generator at all costs, however, presenting both sides of the coin would allow readers to make a (more) informed choice.
- misternugget 7y ago
  > I have experience with a project that was based on that book, and there were (and probably, are) a lot of bugs in the parsing code, that wouldn't have been there if a parser generator was used. I think I need to a add a big "do. not. use. in. production!" disclaimer then :) The parser we build in the book is, of course, not a battle-tested, industrial-grade parser that can survive every fuzzer you throw at it. Far from it, but that's fine, since that was never the goal. The goal was always to learn. So, yes, I agree. If you do need a production-ready, stable parser: use a mature parser generator or, maybe, invest more time in getting good at writing parsers than it takes to read and work through the ~100 pages I wrote on the subject.
  - bigtunacan 7y ago
    Since you have written a book in the subject you obviously are much more of an expert than I am. After reading your book what materials would you recommend for someone wanting to reach the stage is bring able to implement their on "production grade" parsers?

wyufro 7y ago

In my experience the hardest part of using parser generators is to have them create understandable errors. Also it's questionable that they add very much. Parsing text isn't all that difficult. The hard part is to get the tree structure of the AST right. All in all the parsing is a quite small part of a compiler. I've converted from a parser generated to manual code in two different projects and they actually ended up with less lines of code after the conversion, if just barely.

tom_mellior 7y ago

I think the conventional wisdom is that parser generators make it hard(er) to produce useful error messages for users. There are some exceptions, for example: http://pauillac.inria.fr/~fpottier/slides/fpottier-2015-11-oups.pdf http://pauillac.inria.fr/~fpottier/slides/fpottier-2015-11-o... (don't be put off by the French title, the rest is in English).

pizza234 7y ago
An interesting argument against that is: > There’s also some argument made by GCC and Clang teams that they can hand-tune a hand written- parser to get better error messages. I believe they can do such hand tuning and probably have. But that argument does not stop you from customizing the grammar for generated parser to do essentially the same thing, so I don’t buy it as a differentiator. This is an excerpt from an interesting Quora reply on the subject: https://www.quora.com/Are-there-many-established-programming-languages-that-use-a-handcrafted-parser-Why/answer/Ira-Baxter https://www.quora.com/Are-there-many-established-programming...
- tom_mellior 7y ago
  Yes, given a sufficiently powerful parser generator (more powerful than Yacc), you can do that. That's also the point of the talk I linked. Ira Baxter makes a living out of selling proprietary technology based on GLR parsing. His opinion matters, but if there is no open source GLR parser generator available (is there? I don't know), the point he makes cannot apply to GCC or Clang.
  - mjos 7y ago
    I believe GNU Bison parser generator is capable of generating GLR parsers: https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html https://www.gnu.org/software/bison/manual/html_node/GLR-Pars...
    - thosakwe 7y ago
      Oh wow, that's pretty cool, wish I had known about it before. Unfortunately flex and bison, when used together in C++, cause a lot of headache (unless you create an "adapter" class that wraps your Flex parser and pass that to Bison). :/

spinningslate 7y ago

He discussed that on the Corecursive podcast episode [0]. > Why not a parser generator IIRC it was about "minimising magic" - showing what's actually involved in native code. Bob Nystrom makes the same decision in "Crafting Interpreters [1]. Quoting [2]: "Many other language books and language implementations use tools like Lex and Yacc, “compiler-compilers” to automatically generate some of the source files for an implementation from some higher level description. There are pros and cons to tools like those, and strong opinions—some might say religious convictions—on both sides. We will abstain from using them here. I want to ensure there are no dark corners where magic and confusion can hide, so we’ll write everything by hand. As you’ll see, it’s not as bad as it sounds and it means you really will understand each line of code and how both interpreters work." [0] https://corecursive.com/037-thorsten-ball-compilers/ https://corecursive.com/037-thorsten-ball-compilers/ [1] https://craftinginterpreters.com/ https://craftinginterpreters.com/ [2] https://craftinginterpreters.com/introduction.html#the-code https://craftinginterpreters.com/introduction.html#the-code

azhenley 7y ago

The C# and Go parsers do not use a parser generator, iirc.

weberc2 7y ago
I believe you are correct about Go. The rationale I recall was that generated parsers were slower and afforded less control over error reporting. Notably wrt performance, fast compilation was a major goal for Go from the beginning.

chrisseaton 7y ago

> Seems like the way to go these days? No I think people use parser generators less these days. > Why write it yourselves if you can generate it from EBNF notation? Can you write EBNF for it? Can you generate a parser from the EBNF? EBNF and most parser generators are designed for context-free languages. Most languages are context-sensitive. You can see where things start to go wrong...

azhenley 7y ago

One of the C# developers commented [1] on HN that they use a hand written parser for three reasons: incremental re-parsing, better error reporting, and resilient parsing (i.e., you still get a syntax tree even if something doesn't parse). [1] https://news.ycombinator.com/item?id=13915150 https://news.ycombinator.com/item?id=13915150

MrBuddyCasino 7y ago

If you are super familiar with EBNF notation, it may be the fastest way. Otherwise I like parser combinators for their simplicity, you just need to understand the host language.