3 ms·

Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. "I feel that CFGs more naturally represent how w

Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. "I feel that CFGs more naturally represent how we think" but "All this doesn't apply to situations where you trying to parse some language, whose specification explicitly says that the language is based on PEG formalism" A terrible context free grammar (with left and right recursion, not a small feat) is presented. "I blindly converted grammar above to Haskell code" "I accidentally discovered my grammar was ambiguous!" "All this gave me psychological trauma (figuratively speaking). I will never use Parsec (and PEG parsers) anymore." Denial that an ambiguous grammar is a defect, denial that the ambiguity has to be resolved, refusal to use parser combinators to resolve the ambiguity in the correct way. It's also strange to see someone react to a modest, non-shameful failure (guess what, parsing is difficult is language design is even more difficult) that should be a nice learning opportunity (elegant context free grammars are usually insufficient in practical usage) with anger and radicalization far beyond an acceptable level of blaming the tools. The other post in the blog, however, follows a similar general pattern: never use a popular technique (de Bruijn indices rather than parser combinators), because they advocate another technique (expressing lambda calculus terms with randomly generated globally unique identifiers for all bound variables rather than pure context free grammars) because that's what they like.

just_mc 2y ago
Well said.
eslaught 2y ago
So, I agree with your take as a reaction to this article specifically. However, I also think that there is a legitimate point here. Which is that parser combinators, even in languages like Haskell, are shockingly tricky to use correctly. In particular, they violate the usual Haskell principle that "if it compiles, then it will probably run correctly". Having written multiple parsers in multiple languages with multiple parsing frameworks (including direct recursive descent), using Parsec in Haskell was the only time I had to write a test suite for the parser specifically. And that's because there were so many footguns that I was repeatedly making mistakes despite the fact that this was a port of a parser I'd already written (and therefore, ought to know backward and forward). (For the record, this was not my first Haskell project either, which is why I was so shocked it went so poorly.) I'm sure it's possible to make mistakes in CFGs too, but practically speaking I can't remember running into that situation myself. Whereas with Parsec I ran into it repeatedly.
- HelloNurse 2y ago
  PEG parsing is likely to squash some grammar ambiguities in unexpected ways, making a test suite a very good idea; but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification, so the work of taming PEG precedence or combinator behaviour is not an additional burden of the technology but an additional tool to correct the grammar to become less ambiguous, an alternative to rewriting it in unnatural, verbose and complex ways.
  - yatac42 2y ago
    > but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification I don't think that's true. The following CFG is unambiguous: S ::= A S | A A ::= 'a' | 'a' 'b' Yet if we translate this 1-to-1 to a PEG (without changing the order of the alternatives), it's not going to match any input with 'b's in it, so it doesn't match the same language.
    - HelloNurse 2y ago
      This grammar is difficult to adapt to ordered choice, having 4 possible variants that mostly define different languages from each other and from the "same" grammar with traditional parsing. It's a formally very different problem from spontaneously and arbitrarily disambiguating an ambiguous grammar, but in practice it causes the same kind of suffering and it's likely to be a more common issue.
- rowanG077 2y ago
  I have written a simple compiler in Haskell using parser combinators for parsing. And I couldn't disagree more with you. It was super straightforward writing the parser and it worked immediately. Why do say they are tricky?
  - HelloNurse 2y ago
    What language did you compile? Some languages can be much more manageable than others. Did you adapt an existing CFG, or another parser combinator implementation, or did you start from scratch? The first case is more treacherous.
paulddraper 2y ago
> Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. Ah, an S-expr enjoyer I see
kragen 2y ago
it's important to read your comment in the context that we have established in https://news.ycombinator.com/item?id=40582885 https://news.ycombinator.com/item?id=40582885 that you wrote it before finding out what pegs were i'm curious if you change your mind once you understand peg's limited backtracking semantics
aranchelk 2y ago
> I feel that CFGs more naturally represent how we think Author could have replaced the “we” with “I” and made it into a mildly interesting diary entry.

just_mc 2y ago

Well said.

eslaught 2y ago

So, I agree with your take as a reaction to this article specifically. However, I also think that there is a legitimate point here. Which is that parser combinators, even in languages like Haskell, are shockingly tricky to use correctly. In particular, they violate the usual Haskell principle that "if it compiles, then it will probably run correctly". Having written multiple parsers in multiple languages with multiple parsing frameworks (including direct recursive descent), using Parsec in Haskell was the only time I had to write a test suite for the parser specifically. And that's because there were so many footguns that I was repeatedly making mistakes despite the fact that this was a port of a parser I'd already written (and therefore, ought to know backward and forward). (For the record, this was not my first Haskell project either, which is why I was so shocked it went so poorly.) I'm sure it's possible to make mistakes in CFGs too, but practically speaking I can't remember running into that situation myself. Whereas with Parsec I ran into it repeatedly.

HelloNurse 2y ago
PEG parsing is likely to squash some grammar ambiguities in unexpected ways, making a test suite a very good idea; but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification, so the work of taming PEG precedence or combinator behaviour is not an additional burden of the technology but an additional tool to correct the grammar to become less ambiguous, an alternative to rewriting it in unnatural, verbose and complex ways.
- yatac42 2y ago
  > but we shouldn't forget that this kind of failure can only happen starting from an ambiguous grammar specification I don't think that's true. The following CFG is unambiguous: S ::= A S | A A ::= 'a' | 'a' 'b' Yet if we translate this 1-to-1 to a PEG (without changing the order of the alternatives), it's not going to match any input with 'b's in it, so it doesn't match the same language.
  - HelloNurse 2y ago
    This grammar is difficult to adapt to ordered choice, having 4 possible variants that mostly define different languages from each other and from the "same" grammar with traditional parsing. It's a formally very different problem from spontaneously and arbitrarily disambiguating an ambiguous grammar, but in practice it causes the same kind of suffering and it's likely to be a more common issue.
rowanG077 2y ago
I have written a simple compiler in Haskell using parser combinators for parsing. And I couldn't disagree more with you. It was super straightforward writing the parser and it worked immediately. Why do say they are tricky?
- HelloNurse 2y ago
  What language did you compile? Some languages can be much more manageable than others. Did you adapt an existing CFG, or another parser combinator implementation, or did you start from scratch? The first case is more treacherous.

paulddraper 2y ago

> Parsing is an application domain where I'd expect more hard logic and less soft feelings than in this article. Ah, an S-expr enjoyer I see

kragen 2y ago

it's important to read your comment in the context that we have established in https://news.ycombinator.com/item?id=40582885 https://news.ycombinator.com/item?id=40582885 that you wrote it before finding out what pegs were i'm curious if you change your mind once you understand peg's limited backtracking semantics

aranchelk 2y ago

> I feel that CFGs more naturally represent how we think Author could have replaced the “we” with “I” and made it into a mildly interesting diary entry.