Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Parsers don't have to be complicated

bkaradzic.github.io

Post reply on HN
Print view View original

11–20 of 77 posts

Re: Parsers don't have to be complicated

#11

Post by simonask »

imoverclocked wrote: post #8

The hardest thing about writing a parser is cognitively accepting what is going to be considered valid input. You can make the best parser that is fast and well specified but invariably someone will (ab)use it in an unexpected way. Famous examples: despite so many initial good intentions, html tags don’t need to be closed, JSON numbers are too often encoded as strings, YAML can look like what most people expect or it…

I think the second-hardest thing is to accept that CS spent decades optimizing parsing algorithms and grammars, and this is still a significant part of CS curricula in many places. But the practical reality is that parsing is almost never a bottleneck.

If what you're parsing is within the capacity of humans to interact with (so in the range of tens of kilobytes), a grammar that requires an O(N^2) parser is totally fine.

Re: Parsers don't have to be complicated

#12

Post by tomashubelbauer »

This post doesn't touch on something that makes parsers complicated no matter how simple the grammar: good error messages. Parsing a well formed input is the easy part, but not just spitting out a byte index but actually telling the user why their input is not good and what they could do to make it conform is super hard.

The Rust compiler is a common example of a compiler that does a good job here, and I think it is one of only a few.

Re: Parsers don't have to be complicated

#13

Post by jdw64 »

I'm going to collect this post after 24 hours, extract the methodologies from everyone's comments, and write them down in my notes. The reason I like HN is that people freely share their tips in the comments

Re: Parsers don't have to be complicated

#16

Post by jrimbault »

r3d wrote: post #14

If you created a format that is so difficult to parse that it cannot be parsed with simple readable C code then the problem is the format not the parser code.

Can you feel the irony when typing this? "Simple readable C code" itself not being able to be parsed by "simple readable C code".

Re: Parsers don't have to be complicated

#17

Post by haileys »

simonask wrote: post #11
imoverclocked wrote: post #8

The hardest thing about writing a parser is cognitively accepting what is going to be considered valid input. You can make the best parser that is fast and well specified but invariably someone will (ab)use it in an unexpected way. Famous examples: despite so many initial good intentions, html tags don’t need to be closed, JSON numbers are too often encoded as strings, YAML can look like what most people expect or it…

I think the second-hardest thing is to accept that CS spent decades optimizing parsing algorithms and grammars, and this is still a significant part of CS curricula in many places. But the practical reality is that parsing is almost never a bottleneck. If what you're parsing is within the capacity of humans to interact with (so in the range of tens of kilobytes), a grammar that requires an O(N^2) parser is totally fi…

An O(n^2) parser is not fine for the mere reason that I don't know how one would make such a mess of the job in the first place.

A simple recursive-descent parser is easy to write by hand and runs in linear time.

Re: Parsers don't have to be complicated

#18

Post by r3d »

jrimbault wrote: post #16
r3d wrote: post #14

If you created a format that is so difficult to parse that it cannot be parsed with simple readable C code then the problem is the format not the parser code.

Can you feel the irony when typing this? "Simple readable C code" itself not being able to be parsed by "simple readable C code".

Yeah, I agree. But C code parsing is a common and solved problem. The myriad of things people want to store and recover is not though right.

Re: Parsers don't have to be complicated

#19

Post by conartist6 »

jdw64 wrote: post #13

I'm going to collect this post after 24 hours, extract the methodologies from everyone's comments, and write them down in my notes. The reason I like HN is that people freely share their tips in the comments

I'll just drop this here for you and anyone else who wants it: https://github.com/bablr-lang/language-en-regex-vm-pattern/b...

No codegen, just function calling.

Re: Parsers don't have to be complicated

#20

Post by HackerThemAll »

inigyou wrote: post #5
Retr0id wrote: post #3

> LineReader splits input into lines, handles \n and \r\n, and trims the stray trailing \r that malformed input likes to leave behind Is there a common source of extra \r in malformed inputs, beyond those existing as part of \r\n? Or is this just a dig at Windows-style line endings? If there's something weird going on I think I'd rather fail loudly. > Bounding the inner scanner to a single line makes “run past the en…

Sure, start with \r\n, split on \n, now you have a stray \r at the end of every input.

\r\n?|\n

handles all EOL sequences without backtracking. Or write a non-regex equivalent of that.

Post reply on HN