41–50 of 77 posts
Earlier quoted context omitted.
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.
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…
> 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.
In my experience having access to the appropriate place where the parser failed is necessary but wholly insufficient for good diagnostics.
> 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…
Old Macs and some other systems use \r as their EOL, I still sometimes see that with string values in CSV files y code has to deal with (though I don't think I've seen it as an EOL marker in the format itself for a _long_ time).
Sometimes incorrect cleaning steps can leave them behind, such as replacing \r\n with \n but that replacement not being global: it tests fine on strings with zero or one \r\n but subsequent ones will retain their \r. Also code splitting on \n assuming it will always see just that as EOLs will leave trailing \r characters in place. Also, code cleaning EOLs from strings that are supposed to be one-line-only may replace \n (or \n or \r\n, ignoring the possibility of just \r) with a space or a comma and a space, that could be where the \r characters in certain string values I see in files from clients are coming from.
I suspect that off-by-one errors caused by character counting bugs in UTF8/UTF16 handling may cause splitting on EOLs to be a bit off in some cases, though here you will probably be seeing other data corruption at the same time and an errant \r is one of your smaller problems.
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 descenrs parsers are not linear.
They are generally O(n^2) and can even can go exponential with some grammars if written naively.
It can be pretty easy to do adverserival attacks on most naive descent parser and bring it to its knees.
Packrat parser [^1] are linear, but they are by no means "trivial 200 lines" type of parsers.
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…
Earlier quoted context omitted.
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.
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.
Why care about lang which doesnt really support strings well?
If you wrote your standard lib in whatever was better-than-C at the time, you might have settled for sized strings (who needs strings longer than 65535 bytes?) instead of \0, and you might have had utf32 or some kind of wide char representation.
Earlier quoted context omitted.
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.
I'd be quite surprised if an optimizing compiler generated C++ code somewhere in its pipeline!
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…
It's "fine" is you ignore adversarial situations. If someone is taking malicious stabs at your API then you have a problem
What good is a perfect linear-time constant-space parser if the next thing the system does is to allocate hundreds of megabytes of objects representing some deserialized data structure?
The parser is usually the least interesting part.