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

31–40 of 77 posts

Re: Parsers don't have to be complicated

#31

Post by r3d »

f311a wrote: post #4

Unfortunately, simple URL parsing breaks on so many things. There is a reason on why every URL parsing library is at least a few thousand LOCs. One common way to test it is just to pass ipv6 url: http://[f021:d981:b487:e57d:193e:550e::]/

Yeah it's complicated, and that's the thing about parsing anything, the more complicated and unpredictable the input and the harder it is to parse.

Does it need to be human readable, does it need to work across all platforms. Does the it need to be secure. These things change everything. Speed, reliability, security pick one.

Your point about being compliant with the real spec is the difference between a 20 line scannf and and a 1000 line function. Yeah. Ha.

Re: Parsers don't have to be complicated

#32

Post by srean »

mhast wrote: post #27
haileys wrote: post #17

Earlier quoted context omitted.

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.

I think the point was that even if you managed to make a O(n*2) parser it will ve fast enough for human entered problems.

Not for C++ code generated by whole program optimizing compilers. Your "human entered" is doing the heavy lifting. Now that AI is writing code your assertion might be on shaky ground.

Re: Parsers don't have to be complicated

#33

Post by spockz »

tomashubelbauer wrote: post #12

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…

Doaitse Swierstra’s parser combinators have included this for a while. I seem to recall them also having optional support for self-healing such as adding missing commas, parentheses, etc. I’m sure other parser combinators have this as well by now.

Re: Parsers don't have to be complicated

#34

Post by spockz »

tgv wrote: post #29
iainmerrick wrote: post #25

Earlier quoted context omitted.

It actually does touch on this: Built-in line and column tracking. Any movement across a newline updates the line number, including a backwards seek. getLine and getColumn are always available and both are one-based, which makes decent error messages nearly free. That doesn't sound like much, but having hand-written plenty of recursive descent parsers, it's most of what you need for good error messages. Just being ab…

I don't really agree. Many top-down parsers find an error at an unexpected token. That token is often not the error. Quite often something is missing at that point, or there has been a mistake some way back. Translating e.g. "unexpected semicolon" into "keyword 'if' should be the identifier 'f'" is not easy.

I think it becomes easier if you have some oracle, like a compiler, available to check whether the end result (after introducing suggestions) is viable.

I say it like this because to me the only valid way to come to the latter class of error messages (containing constructive suggestions) is by first coming up with possible edits and then checking whether they make the whole parse and compile.

Re: Parsers don't have to be complicated

#35

Post by meindnoch »

quuxplusone wrote: post #30
meindnoch wrote: post #21

Earlier quoted context omitted.

Is that so? RFC 3986 Appendix B [1] "Parsing a URI Reference with a Regular Expression": The following line is the regular expression for breaking-down a well-formed URI reference into its components. ^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))? scheme = $2 authority = $4 path = $5 query = $7 fragment = $9 Let's test your URI with this regex, shall we? [2] $2 (scheme) = http $4 (authority) = [f021:d981:b…

Hm, but I think he's right. The problem comes when you try to break down the authority portion into host and port; TFA's parser treats the first colon as introducing the port, which is wrong. https://github.com/bkaradzic/bx/blob/0b001f5f36579e8aea07efa...

>The problem comes when you try to break down the authority portion into host and port

That's a problem orthogonal to URI parsing.

You parse the URI with the RFC 3986 regex, which gives you the components: scheme, authority, path, query, fragment.

You're then free to parse any of the components according to your own bespoke rules, e.g. the query string often follows the key=value&key=value&... pattern.

Re: Parsers don't have to be complicated

#36

Post by nly »

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…

It's "fine" is you ignore adversarial situations.

If someone is taking malicious stabs at your API then you have a problem

Re: Parsers don't have to be complicated

#37

Post by nly »

haileys wrote: post #17
simonask wrote: post #11

Earlier quoted context omitted.

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.

Recursive descent isnt guaranteed linear time

In the face of backtracking the time depends on the complexity of the grammar, since it's basically a brute force search through all the rules.

Re: Parsers don't have to be complicated

#39

Post by roaringrocky »

alexjurkiewicz wrote: post #15

> if (!line.accept('[').isEmpty() ) // [section] header. Is this really ergonomic?

Yeah those all read a bit brain teasy to me.

"if not accept this character, so this is skipping the match, oh wait, if the result of trying to match is empty, no wait again, it was not empty, i.,e we ARE matching...".

Re: Parsers don't have to be complicated

#40

Post by whstl »

iainmerrick wrote: post #25
tomashubelbauer wrote: post #12

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…

It actually does touch on this: Built-in line and column tracking. Any movement across a newline updates the line number, including a backwards seek. getLine and getColumn are always available and both are one-based, which makes decent error messages nearly free. That doesn't sound like much, but having hand-written plenty of recursive descent parsers, it's most of what you need for good error messages. Just being ab…

What I normally do is: only storing the byte position during the parsing itself, and then extracting the line + column when/if displaying an error.

This allows the error report mechanism to be decoupled, and the hot path of the parser has a bit less code to manage.

Post reply on HN