4 ms·

> Why simpler is better and why you don't need a parser generator. As far as I can see, this isn't fully answered, unless the claim is strictly limited to the

by ben509 6y ago

> Why simpler is better and why you don't need a parser generator. As far as I can see, this isn't fully answered, unless the claim is strictly limited to the question of need. In my case, I certainly want a parser generator. I'm working on a language, and I did a very early version using a hand-rolled recursive descent parser. Then I realized I wanted a syntax that was human friendly, so I graduated to megaparsec. That worked, it's an elegant way to describe a parser, but as a language gets complex you have to work in implicit orderings (magic, frankly) to handle the limits of recursive descent. Finally, I realized I needed a spec and an implementation in sync with that spec, so I went with BNFC[2], and it even generates some pretty documentation[1] for me. This is the classic debate over using a domain specific language vs. a general purpose language, so there's no hard answer one way or the other. For me, the deciding factor was I didn't want to write, test, etc. my own parser, and I think there being a canonical way for others to parse my language (in other languages as well) is helpful. [1]: https://tenet-lang.org/spec-syn.html https://tenet-lang.org/spec-syn.html [2]: https://bnfc.digitalgrammars.com/ https://bnfc.digitalgrammars.com/

dfabulich 6y ago
Right below the line you quote, the author makes three arguments: > • It’s highly instructive, in a way that using a parser generator is not. To quote Feynman: “What I cannot create, I do not understand” > • It’s an important skill: most real-world compilers use hand-written parsers because they provide more control over error handling, significant whitespace, etc. > • It’s not actually difficult! The exercises themselves are meant to justify these arguments. I think the exercises conclusively demonstrate that #1 and #3 are true. If you can easily follow these exercises, and if, by the end, you feel like you've learned something useful, then it follows that hand-rolling a parser is instructive and not too difficult. I strongly agree with the author that if you're developing a language for the first time, you shouldn't use a parser generator at first. You should hand-roll a parser first, and then, when you see the limitations of your hand-rolled parser, adopt a parser generator, now with full understanding of what the generator is doing for you (and not doing for you). As for #2, the article demonstrates how to do error handling in a manner that would be a head-scratcher in Yacc. You claim here that it was easier to develop a "human friendly" syntax with megaparsec than it was to do that in a hand-rolled recursive-descent parser. That could be true, but that's not my experience. To be convincing, you'd need to do what the author did, (even though you say the author didn't): you'd need to justify your argument with specific examples.
- avmich 6y ago
  > > • It’s highly instructive, in a way that using a parser generator is not. Top-down parsers are nice, but even better would be not to have to write them each time you need to parse something. Also top-down parsers don't handle (well) some of useful grammar constructs, and it's tedious to remember always formulate grammars in a certain way. Next, grammars are for many people more convenient to work with than actual parser code. So parser generators have their place. > To quote Feynman: “What I cannot create, I do not understand” And this can be true for parser generators. After you've figured how to do that you could be tempted to never use external tools, and have a nice jump from, say, arbitrary CFG to a generalized LR, while controlling all the parts in between. > • It’s not actually difficult!
- ben509 6y ago
  I know people often read headlines and then instantly comment, but I really did read most of the post. What I realized after writing most of my comment was that the author was primarily interested in explaining a recursive descent parser, and the arguments you quoted were simply a hook to get people interested. That's why I phrased my objection to not _fully_ answering the question. And it's a good question, so I thought the other side deserved some exploration. > You should hand-roll a parser first, and then, when you see the limitations of your hand-rolled parser, adopt a parser generator, now with full understanding of what the generator is doing for you (and not doing for you). Writing your own recursive descent parser only teaches you recursive descent. So, sure, you'll have a clear idea of what a parsec derivative is doing since that's also RD, but it won't help you understand what a LALR parser generated by yacc is doing. The other problem is for someone to use your parser in another language, they have to port the whole thing and maintain that port as your language changes. Talking about "the first time you write it" and pedagogical uses is entirely fair, but it's only the beginning of the story. > To be convincing, you'd need to do what the author did, (even though you say the author didn't): you'd need to justify your argument with specific examples. Nope, never said the author didn't provide examples. To be clear, it's an excellent tutorial on how to write a RD parser. I'm not prepared to rewrite a bunch of code in two styles, but you're welcome to take a look at the expression parser[1]. In this case, I didn't want to write a whole precedence scanner for expressions, and I wanted precedence to be clear to a reader. So there's some nuance I didn't capture: in Haskell parsing, writing your own RD parser starts to look like parsec because it's such a natural expression of the problem. If I was going to write my own parsec, I could still probably use an existing combinator[3] because the parsec model is so generic. That's why I wanted to use that to do a more human readable, and thus more complex, syntax. But, as I mentioned above, recursive descent kinda sucks. As an example, take the parsing for the left-hand side of an assignment[2]. Sometimes I have 'try' calls, other times I don't. Sometimes the ordering around alternatives (the <|> operator) matters, sometimes it doesn't. I know in abstract why it works one way or another. But, honestly, most of that is in there because it got tests to pass. My interest is in writing a language, not a parser. And that's really why I switched from megaparsec to a parser generator. Once I got my grammar to be (reasonably) unambiguous, my source was just the plain, trivially readable BNF rules, and I nuked those stupid tests. [1]: https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c7591d3e0228f455b765e944c61563e1964b/library/Tenet/Parsing/Expr.hs#L51 https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c... [2]: https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c7591d3e0228f455b765e944c61563e1964b/library/Tenet/Parsing/Lhs.hs#L24 https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c... [3]: https://hackage.haskell.org/package/parser-combinators-1.2.1/docs/Control-Monad-Combinators-Expr.html https://hackage.haskell.org/package/parser-combinators-1.2.1...
hardwaregeek 6y ago
How do you handle good error messages or error recovery? I've played around with parser generators but I never figured out how to do either in a satisfactory fashion. Granted, my hand written parser doesn't do error recovery very well either.
- ben509 6y ago
  I'm not entirely settled on that. My working approach is if you're writing a compiler, it wants to have an unambiguous grammar and shouldn't even attempt recovery. If input doesn't parse, the compiler can recommend (or just run) the linter. That keeps the common case fast and simple. The linter/fixer can have a relaxed syntax specifically designed to handle messy code and suggest corrections. That comes from a philosophy of treating error correction and user assistance as a separate task. But that's an approach I'm taking because I want to get a reference implementation together as quickly as possible. It's definitely not how modern IDEs work. JetBrains GrammarKit uses a PEG[1] because they need strong support for error recovery[2] using hints. Another interesting library is Tree-sitter[3]; it does incremental parsing keeping an AST constantly up to date for you. Relevant to this whole discussion, GvR wrote a series on PEG parsers[4] in which he starts out by writing one by hand and then shows how to write one that accepts a grammar. [1]: https://github.com/JetBrains/Grammar-Kit https://github.com/JetBrains/Grammar-Kit [2]: https://github.com/JetBrains/Grammar-Kit#attributes-for-error-recovery-and-reporting https://github.com/JetBrains/Grammar-Kit#attributes-for-erro... [3]: https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/ [4]: https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...
- ltratt 6y ago
  Alas, most parser generators don't have very good error recovery (and some have such terrible error recovery that I think it's worse than not having any!). It turns out that this isn't inevitable: there's been a long strand of research on decent error recovery for LR parsers, at least, but it needed a bit of a refresh to be practical. If you'll forgive the blatant self promotion, we tackled this problem in https://soft-dev.org/pubs/html/diekmann_tratt__dont_panic/ https://soft-dev.org/pubs/html/diekmann_tratt__dont_panic/ which is implemented in our Rust parsing system https://github.com/softdevteam/grmtools/ https://github.com/softdevteam/grmtools/. It won't beat the very best hand-written error recovery routines, but it's often not far behind.
mannykannot 6y ago
Once, I wanted a parser, and being the sort of person who thinks there is value in seeing what other people have done before, I took a look at parser generators. The learning curve seemed long and steep, much more than seemed necessary for my modest requirements, so I rolled my own. I got a parser out of the exercise, but also an appreciation for why the tools exist, and a new-found motivation for learning how to use them.

by ben509 6y ago

dfabulich 6y ago

Right below the line you quote, the author makes three arguments: > • It’s highly instructive, in a way that using a parser generator is not. To quote Feynman: “What I cannot create, I do not understand” > • It’s an important skill: most real-world compilers use hand-written parsers because they provide more control over error handling, significant whitespace, etc. > • It’s not actually difficult! The exercises themselves are meant to justify these arguments. I think the exercises conclusively demonstrate that #1 and #3 are true. If you can easily follow these exercises, and if, by the end, you feel like you've learned something useful, then it follows that hand-rolling a parser is instructive and not too difficult. I strongly agree with the author that if you're developing a language for the first time, you shouldn't use a parser generator at first. You should hand-roll a parser first, and then, when you see the limitations of your hand-rolled parser, adopt a parser generator, now with full understanding of what the generator is doing for you (and not doing for you). As for #2, the article demonstrates how to do error handling in a manner that would be a head-scratcher in Yacc. You claim here that it was easier to develop a "human friendly" syntax with megaparsec than it was to do that in a hand-rolled recursive-descent parser. That could be true, but that's not my experience. To be convincing, you'd need to do what the author did, (even though you say the author didn't): you'd need to justify your argument with specific examples.

avmich 6y ago
> > • It’s highly instructive, in a way that using a parser generator is not. Top-down parsers are nice, but even better would be not to have to write them each time you need to parse something. Also top-down parsers don't handle (well) some of useful grammar constructs, and it's tedious to remember always formulate grammars in a certain way. Next, grammars are for many people more convenient to work with than actual parser code. So parser generators have their place. > To quote Feynman: “What I cannot create, I do not understand” And this can be true for parser generators. After you've figured how to do that you could be tempted to never use external tools, and have a nice jump from, say, arbitrary CFG to a generalized LR, while controlling all the parts in between. > • It’s not actually difficult!
ben509 6y ago
I know people often read headlines and then instantly comment, but I really did read most of the post. What I realized after writing most of my comment was that the author was primarily interested in explaining a recursive descent parser, and the arguments you quoted were simply a hook to get people interested. That's why I phrased my objection to not _fully_ answering the question. And it's a good question, so I thought the other side deserved some exploration. > You should hand-roll a parser first, and then, when you see the limitations of your hand-rolled parser, adopt a parser generator, now with full understanding of what the generator is doing for you (and not doing for you). Writing your own recursive descent parser only teaches you recursive descent. So, sure, you'll have a clear idea of what a parsec derivative is doing since that's also RD, but it won't help you understand what a LALR parser generated by yacc is doing. The other problem is for someone to use your parser in another language, they have to port the whole thing and maintain that port as your language changes. Talking about "the first time you write it" and pedagogical uses is entirely fair, but it's only the beginning of the story. > To be convincing, you'd need to do what the author did, (even though you say the author didn't): you'd need to justify your argument with specific examples. Nope, never said the author didn't provide examples. To be clear, it's an excellent tutorial on how to write a RD parser. I'm not prepared to rewrite a bunch of code in two styles, but you're welcome to take a look at the expression parser[1]. In this case, I didn't want to write a whole precedence scanner for expressions, and I wanted precedence to be clear to a reader. So there's some nuance I didn't capture: in Haskell parsing, writing your own RD parser starts to look like parsec because it's such a natural expression of the problem. If I was going to write my own parsec, I could still probably use an existing combinator[3] because the parsec model is so generic. That's why I wanted to use that to do a more human readable, and thus more complex, syntax. But, as I mentioned above, recursive descent kinda sucks. As an example, take the parsing for the left-hand side of an assignment[2]. Sometimes I have 'try' calls, other times I don't. Sometimes the ordering around alternatives (the <|> operator) matters, sometimes it doesn't. I know in abstract why it works one way or another. But, honestly, most of that is in there because it got tests to pass. My interest is in writing a language, not a parser. And that's really why I switched from megaparsec to a parser generator. Once I got my grammar to be (reasonably) unambiguous, my source was just the plain, trivially readable BNF rules, and I nuked those stupid tests. [1]: https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c7591d3e0228f455b765e944c61563e1964b/library/Tenet/Parsing/Expr.hs#L51 https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c... [2]: https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c7591d3e0228f455b765e944c61563e1964b/library/Tenet/Parsing/Lhs.hs#L24 https://gitlab.com/contravariance/tenet-haskell/-/blob/0640c... [3]: https://hackage.haskell.org/package/parser-combinators-1.2.1/docs/Control-Monad-Combinators-Expr.html https://hackage.haskell.org/package/parser-combinators-1.2.1...

hardwaregeek 6y ago

How do you handle good error messages or error recovery? I've played around with parser generators but I never figured out how to do either in a satisfactory fashion. Granted, my hand written parser doesn't do error recovery very well either.

ben509 6y ago
I'm not entirely settled on that. My working approach is if you're writing a compiler, it wants to have an unambiguous grammar and shouldn't even attempt recovery. If input doesn't parse, the compiler can recommend (or just run) the linter. That keeps the common case fast and simple. The linter/fixer can have a relaxed syntax specifically designed to handle messy code and suggest corrections. That comes from a philosophy of treating error correction and user assistance as a separate task. But that's an approach I'm taking because I want to get a reference implementation together as quickly as possible. It's definitely not how modern IDEs work. JetBrains GrammarKit uses a PEG[1] because they need strong support for error recovery[2] using hints. Another interesting library is Tree-sitter[3]; it does incremental parsing keeping an AST constantly up to date for you. Relevant to this whole discussion, GvR wrote a series on PEG parsers[4] in which he starts out by writing one by hand and then shows how to write one that accepts a grammar. [1]: https://github.com/JetBrains/Grammar-Kit https://github.com/JetBrains/Grammar-Kit [2]: https://github.com/JetBrains/Grammar-Kit#attributes-for-error-recovery-and-reporting https://github.com/JetBrains/Grammar-Kit#attributes-for-erro... [3]: https://tree-sitter.github.io/tree-sitter/ https://tree-sitter.github.io/tree-sitter/ [4]: https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...
ltratt 6y ago
Alas, most parser generators don't have very good error recovery (and some have such terrible error recovery that I think it's worse than not having any!). It turns out that this isn't inevitable: there's been a long strand of research on decent error recovery for LR parsers, at least, but it needed a bit of a refresh to be practical. If you'll forgive the blatant self promotion, we tackled this problem in https://soft-dev.org/pubs/html/diekmann_tratt__dont_panic/ https://soft-dev.org/pubs/html/diekmann_tratt__dont_panic/ which is implemented in our Rust parsing system https://github.com/softdevteam/grmtools/ https://github.com/softdevteam/grmtools/. It won't beat the very best hand-written error recovery routines, but it's often not far behind.

mannykannot 6y ago

Once, I wanted a parser, and being the sort of person who thinks there is value in seeing what other people have done before, I took a look at parser generators. The learning curve seemed long and steep, much more than seemed necessary for my modest requirements, so I rolled my own. I got a parser out of the exercise, but also an appreciation for why the tools exist, and a new-found motivation for learning how to use them.