3 ms·
An alternate title: "Just Shotgun Parse Your Inputs". This isn't bad advice across the board, but it is bad advice for many applications. This is how you end
by samatman 6y ago
An alternate title: "Just Shotgun Parse Your Inputs".
This isn't bad advice across the board, but it is bad advice for many applications.
This is how you end up with context-sensitive formats, or ones where the semantics of a particular particle require running the parser, or worse. It exposes a rich surface area for exploitation with adversarial inputs.
That said, the advantages cited at the front of the article are all real: error recovery and decent error messages are unsolved problems with existing parser generators, although ANTLR is pretty good at it.
But, especially if you're developing the data format rather than just implementing it, I strongly suggest using something like Instaparse which can generate a parser directly from a grammar. Once this is solidified, it's reasonable to hand-roll something, but even there, I suggest using a nice parser combinator library, like hammer or Nom.
This provides more discipline: as long as you're coloring inside the lines, you'll end up with a parser which actually implements your spec. When you start adding functions to provide context, recover from errors, and provide meaningful feedback in the form of error messages for unexpected inputs, you'll know what you're doing: a classic recursive-descent parser can't provide the same conceptual separation between the parsing logic and the logic to support ergonomics or one-pass compiling or whatever add-ons you're putting in there.
- specialist 6y ago"where the semantics of a particular particle require running the parser, or worse" Yup. Consider the much maligned (apache) httpd.conf and makefile. Their code was the source of truth for correctness. No matter horrible terrible their syntax, they would have been sufferable if they had grammars. Bespoke parsing of expressions benefits from having an implicit grammar, like this OC. But threshold for needing explicit grammars is pretty low. Prime examples are all the data exchange formats. Descriptions of JSON and CSV are short and naively reasonable, but insufficient. As we've seen, any ambiguity that can happen will happen.
- thequux 6y agoI agree with everything you say, except your advice to use a parser combinator library, because most implement PEGs. Hammer is, of course, an exception to this, as long as you call `h_compile` to tell it to use a different backend. Why not use PEGs? In short, they don't actually remove ambiguity from your grammar, but rather hide it in ways that are difficult to reason about. You're still dependent on code as a definition of the language that you accept, and worse, that code is very fragile in the face of refactoring. Further, the lexical analysis step is generally the source of most ambiguity, and most parser combinator libraries make it extremely inconvenient to parse something that isn't a character stream. (Hammer is actually worse than most here; it's not possible to use it to parse anything other than streams of bytes, though perhaps it can be excused because of the limitations of C)
- samatman 6y agoI firmly disagree about the value of PEGs (and hence combinators) as a formalism that's ambiguous or hard to reason about. PEGs are as well-specified as CFGs, they just work in a different way. One of the strengths of PEGs is that they're never ambiguous. That does mean that order of alternates is important, and sometimes you do have to fiddle with that order when translating something like ABNF. But what you get in return is never having to deal with a parse forest, let alone punting on that problem by just reifying the greedy parse as the correct one. I've written a tool that converts a declarative specification of a PEG grammar into a parser, although I haven't released it yet. It works great, I've used it on a number of real-world structured data formats. Edit: cut out the first paragraph after checking the user name. Hi TQ.
- tomp 6y ago"PEGs are never ambiguous" is equivalent to solving a problem by proclaiming the wrong solution to be correct. In that sense, LALR parser generators (e.g. yacc) are also never ambiguous, because even if your grammar is ambiguous in the formal sense, yacc will produce a working parser with well-defined resolution of conflicts... But the reality is, E = E `+` E is intrinsically ambiguous, no matter how you want to spin it... the only difference is, that LALR generators point that out, whereas PEG generators sweep it under the rug.
- samatman 6y agoI don't agree, as I've said, because PEG is a declarative formalism, and LALR is a parsing strategy. GLL implemented with graph-structured stacks can and will produce a parse forest for an ambiguous grammar, LALR will manifest one of those parses for the same grammar. To lean on that means you have hidden information: your grammar is BNF + LALR, or BNF + GLL, not just BNF. PEGs, by contrast, are always PEGs. What you see is what you get. A grammar in PEG format will always give you one parse, and which parse is predictable. If you want a different parse, you have to rewrite it. Indeed, as I'm sure you know, your example grammar isn't valid in the original PEG formalism, which prohibits immediate left recursion. Automatic rewrites into an intermediate rule are the leading method of allowing it. Ambiguity is a well-defined concept in grammars, and PEGs aren't. I've noticed that a lot of CFG enthusiasts don't like this about PEGs. They consider it inelegant, unprincipled. Some of that is aesthetic, some is unfamiliarity, and some is sunk cost: none of it actually engages with the formal expressive power of PEGs, nor their ergonomics as a practical tool for development.
- spullara 6y agoANTLR 4 is a joy to work with if folks on this thread haven't tried it.