3 ms·

Never listen to anyone who tells you that parsers are easy. Parsers that work on simple input are easy. Parsers that get all the edge cases and diabolical inp

Never listen to anyone who tells you that parsers are easy. Parsers that work on simple input are easy. Parsers that get all the edge cases and diabolical input right are stupidly difficult.

tomjakubowski 11y ago
> Parsers that work on simple input are easy. Parsers that get all the edge cases and diabolical input right are stupidly difficult. Not to mention parsers which work on a vague and totally unspecified grammar - like "real world" HTTP and HTML parsers, which have to account for misbehaving clients and servers or malformed web pages (is this what you meant by 'diabolical input'?).
- haberman 11y ago
  > is this what you meant by 'diabolical input' Not exactly what I meant, but that's a good point too! By diabolical input, I mean things specifically designed to stress the parser, like ("{" * 100000) in JSON.
eru 11y ago
Parsers can be simple, if the language you are parsing is simple. That's why you should make your languages / protocols as `weak' as possible. Prefer a finite language over a regular language over a context free language, and avoid context sensitive languages like the plague.
tikhonj 11y ago
Parsers are easy. It's the grammars that are complicated. Seriously: seemingly simple things designed and described informally, in prose, can easily be incredibly complex when you expand all their details. That says a lot about those things, a little bit about the process and mindset that went into them and virtually nothing about parsing in general.
- haberman 11y ago
  > Parsers are easy. It's the grammars that are complicated. What is this supposed to mean? It sounds something like "Programming is easy. It's the classes/objects that are complicated."
  - tikhonj 11y ago
    What I'm saying is that parsing is not inherently hard. But, just like anything else that isn't inherently hard, you can make it as hard as you like by making the input arbitrarily complex and convoluted. Given a grammar, making a parser is largely trivial. A computer could do it. Making a fast parser, or one with good error messages, or one that's modular and composable are all harder, but still generally not hard. The problem comes up when you have a bad, overly complex, ill-thought-out, incomplete or vague specification. But anything would be hard with a specification like that, not just parsing. (This feels like something standards bodies seem to enjoy producing though.) Perhaps it's a bit like saying "programming is easy, the world is complicated" except that the world could be so much less complicated if relevant formal languages were simpler and better-defined.
    - haberman 11y ago
      > The problem comes up when you have a bad, overly complex, ill-thought-out, incomplete or vague specification. But anything would be hard with a specification like that, not just parsing. Nearly nearly every real text format in the world would fall under your definition of "bad, overly complex, ill-thought-out", thanks to practical considerations always leading to some amount of complexity. You may wish that languages could be nice and clean, but in practice they rarely end up that way. But aside from that, your statement isn't true. Serialization is an order of magnitude easier than parsing, because for a serializer all you have to do is emit something that stays within the lines delimited by the spec. For a parser, you have to correctly and safely handle absolutely any construct or variation allowed by the spec.

Never listen to anyone who tells you that parsers are easy. Parsers that work on simple input are easy. Parsers that get all the edge cases and diabolical input right are stupidly difficult.

tomjakubowski 11y ago

> Parsers that work on simple input are easy. Parsers that get all the edge cases and diabolical input right are stupidly difficult. Not to mention parsers which work on a vague and totally unspecified grammar - like "real world" HTTP and HTML parsers, which have to account for misbehaving clients and servers or malformed web pages (is this what you meant by 'diabolical input'?).

haberman 11y ago
> is this what you meant by 'diabolical input' Not exactly what I meant, but that's a good point too! By diabolical input, I mean things specifically designed to stress the parser, like ("{" * 100000) in JSON.

eru 11y ago

Parsers can be simple, if the language you are parsing is simple. That's why you should make your languages / protocols as `weak' as possible. Prefer a finite language over a regular language over a context free language, and avoid context sensitive languages like the plague.

tikhonj 11y ago

Parsers are easy. It's the grammars that are complicated. Seriously: seemingly simple things designed and described informally, in prose, can easily be incredibly complex when you expand all their details. That says a lot about those things, a little bit about the process and mindset that went into them and virtually nothing about parsing in general.

haberman 11y ago
> Parsers are easy. It's the grammars that are complicated. What is this supposed to mean? It sounds something like "Programming is easy. It's the classes/objects that are complicated."
- tikhonj 11y ago
  What I'm saying is that parsing is not inherently hard. But, just like anything else that isn't inherently hard, you can make it as hard as you like by making the input arbitrarily complex and convoluted. Given a grammar, making a parser is largely trivial. A computer could do it. Making a fast parser, or one with good error messages, or one that's modular and composable are all harder, but still generally not hard. The problem comes up when you have a bad, overly complex, ill-thought-out, incomplete or vague specification. But anything would be hard with a specification like that, not just parsing. (This feels like something standards bodies seem to enjoy producing though.) Perhaps it's a bit like saying "programming is easy, the world is complicated" except that the world could be so much less complicated if relevant formal languages were simpler and better-defined.
  - haberman 11y ago
    > The problem comes up when you have a bad, overly complex, ill-thought-out, incomplete or vague specification. But anything would be hard with a specification like that, not just parsing. Nearly nearly every real text format in the world would fall under your definition of "bad, overly complex, ill-thought-out", thanks to practical considerations always leading to some amount of complexity. You may wish that languages could be nice and clean, but in practice they rarely end up that way. But aside from that, your statement isn't true. Serialization is an order of magnitude easier than parsing, because for a serializer all you have to do is emit something that stays within the lines delimited by the spec. For a parser, you have to correctly and safely handle absolutely any construct or variation allowed by the spec.