3 ms·

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:

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

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