Live data from Hacker News

Just Write the Parser

tiarkrompf.github.io

21–30 of 85 posts

Re: Just Write the Parser

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

Re: Just Write the Parser

#22
post #10

> Enter an expression on the left and see the parse tree change! I don't get it. The left input field is uneditable in Firefox, Edge and Chrome. Navigation is broken across the board. Even copying and pasting the quote above somehow included most of the page even though I only selected that one sentence. This looks very cool and I would love to try it out! :(

Yeah I think something is broken because at least in chrome when you try to type in the left box the following exception keeps being thrown in the console VM463:82 Uncaught TypeError: Cannot read property 'startContainer' of undefined at HTMLPreElement.eval (eval at run (eval at runScriptElement (octopus-2.js:525)), :82:40)

I just pushed a fix for Chrome (apparently it doesn't report affected selection ranges for input events). Hope it works now!

Re: Just Write the Parser

#23

Author here - happy to answer questions, as always. Thanks also for feedback on the format of the article. It's a bit of an experiment on how to present dense information effectively. Some more rationale here: https://tiarkrompf.github.io/notes/?/octopus-notes/

Octopus notes is an interesting idea. Thanks for the link on it.

And I do like to write a lot of little parsers. I worked with someone once who would somehow transform every business problem into “we need to write a compiler”. Sounds crazy but he achieved brilliant results and has gone on to great things.

Re: Just Write the Parser

#25

I don't want to be that guy but I originally thought the CSS was broken. Harsh black on harsh white, everything squeezed in to the left third of my screen, and an unused scrollbar on the bottom. That being said, I love the information. I don't care for the workflow that comes with the most popular parser generators and I inevitably want more control over my parser as I start adding error handling, etc. It's easier to…

I think the design is great. Simple and easy to read.

I'm not quite sure why they went with the borked "half the screen is empty" look. Ok, it's easier to read, but that negative space is bad design, regardless.

Re: Just Write the Parser

#26

I don't want to be that guy but I originally thought the CSS was broken. Harsh black on harsh white, everything squeezed in to the left third of my screen, and an unused scrollbar on the bottom. That being said, I love the information. I don't care for the workflow that comes with the most popular parser generators and I inevitably want more control over my parser as I start adding error handling, etc. It's easier to…

There are unused scrollbars everywhere. It's quite an interesting example of scrollbar blindness [1].

[1]:https://news.ycombinator.com/item?id=24293421

Re: Just Write the Parser

#27

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 ar…

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

Re: Just Write the Parser

#28
post #13

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

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.

Re: Just Write the Parser

#29
post #13

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

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 thems…

> > • 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!

Re: Just Write the Parser

#30
Considering that something as simple and limited as JSON has been a source of security vulnerabilities from ambiguities in the spec, thanks but nope. Declarative definitions of a grammar help identify those ambiguities... and if the grammar is defined separately from its interpretation, it opens the door to invisible ambiguities that can become another vector for vulnerabilities.

Unless you have provable implementations (great if you do!), declarative grammars meaningfully limit points of failure.

Post reply on HN