48 ms·

Parsers don't have to be complicated

58 points by signa11 3mo ago

mrkeen 2mo ago
If you draw a line from 'ad-hoc byte-wrangling nonsense' to 'parser combinators', this can't be more than 20% along it. Looking at the linked URL parser, why doesn't it look like url = do scheme authority path query fragment where scheme = ... authority = ... etc. It looks totally ad-hoc.
Retr0id 2mo ago
> 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 end of a malformed line” unrepresentable rather than merely unlikely. I don't really see what makes it "unrepresentable", and this reads more like "if you used the right scanning logic, you can't have used the wrong scanning logic".
- inigyou 2mo ago
  Sure, start with \r\n, split on \n, now you have a stray \r at the end of every input.
  - Retr0id 2mo ago
    But the preceding clause says it handles \r\n. If you're already handling \r\n, what remaining sources of \r are there, that you'd actually want to silently ignore?
    - inigyou 2mo ago
      Someone else (possibly you) already split on \n.
      - Retr0id 2mo ago
        Fair point. I think if something is getting mangled like that I'd rather fail loudly, but it depends on the use case I suppose.
  - HackerThemAll 2mo ago
    \r\n?|\n handles all EOL sequences without backtracking. Or write a non-regex equivalent of that.
    - inigyou 2mo ago
      I'm sure every time you split something on newlines you remember to use a regex.
      - HackerThemAll 2mo ago
        I tend not to, because it's an overkill, but this regex nicely sums what needs to be done.
- thesz 2mo ago
  End of line on Classic Mac is \r.
- dspillett 2mo ago
  > Is there a common source of extra \r in malformed inputs, beyond those existing as part of \r\n? 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.
f311a 2mo ago
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::]/
- meindnoch 2mo ago
  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:b487:e57d:193e:550e::] $5 (path) = / Seems correct to me. [1] https://datatracker.ietf.org/doc/html/rfc3986#appendix-B https://datatracker.ietf.org/doc/html/rfc3986#appendix-B [2] https://regexr.com/8nqop https://regexr.com/8nqop
  - quuxplusone 2mo ago
    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/0b001f5f36579e8aea07efa5af139ca18dad9505/src/url.cpp#L48-L123 https://github.com/bkaradzic/bx/blob/0b001f5f36579e8aea07efa...
    - meindnoch 2mo ago
      >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.
  - f311a 2mo ago
    Regexes are pretty slow, though.
speedgoose 2mo ago
I now use nom to write my parsers. Once you understand it, it’s simple and parsing complex data becomes a _fun_ puzzle. I recommend it. https://github.com/rust-bakery/nom https://github.com/rust-bakery/nom
imoverclocked 2mo ago
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 can look progressively more like JSON… and on and on.
- simonask 2mo ago
  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.
  - haileys 2mo ago
    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.
    - mhast 2mo ago
      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.
      - srean 2mo ago
        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.
        2mo ago
tomashubelbauer 2mo ago
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.
- estebank 2mo ago
  I will provide some context from having done a lot of that work. The Rust grammar is actually quite regular, that's why we have things like the turbofish for type parameters (`binding.method::<Type>()`): it makes the grammar unambiguous (a naïve parser would with a complicated grammar that accepts chained comparisons would have to deal with differentiating between `binding.method < value > ()` and `binding.method<Type>()`). But that doesn't mean the rustc parser doesn't do the work of supporting some the more complex grammar in order to provide better diagnostics. I like to say that rustc actually knows about meta-Rust, a daughter language that goes crazier in its features. I also joke that rustc isn't done until you can paste code from another language and following the suggestions you end up with valid Rust code without loss of the user's intent. Part of the problem is that the places where incorrect code can fail is in more places than the parser. The chained comparisons example is one that is easy for Rust (as it doesn't support them), so the parser itself can produce a "missing turbofish" suggestion with high certainty, but for truly ambiguous expressions, the errors will happen later, during name resolution ("expected a value and found a type") or when checking the number of arguments. A production compiler needs to account for not only the original error, but also silence every knock-down error too. The simplest strategies are to just stop if at the end of a given stage there are errors (which leads to the "wave of errors" experience of fixing the "last" error leading to a ton of new ones) or fully replacing entire blocks of code that had a parse error with an AST node that acts as a tombstone marking that that later stages need to ignore it. The first option leads to a bad experience, and the latter is insufficient. A recent example of looking at this is https://github.com/rust-lang/rust/pull/159689 https://github.com/rust-lang/rust/pull/159689, where `Arc::new(RwLock::new(HashMap<i32, i64>::default()));` currently produces error[E0423]: expected value, found struct `HashMap` --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:34 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^^^^^ | --> $SRC_DIR/std/src/collections/hash/map.rs:LL:COL ::: $SRC_DIR/std/src/collections/hash/map.rs:LL:COL | = note: `HashMap` defined here error[E0423]: expected value, found builtin type `i32` --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:42 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^ not a value error[E0423]: expected value, found builtin type `i64` --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:47 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^ not a value error[E0425]: cannot find external crate `default` in the crate root --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:53 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^^^^^ not found in the crate root error[E0061]: this function takes 1 argument but 2 arguments were supplied --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:22 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^^^^^^^^^ --------------- unexpected argument #2 of type `bool` | note: associated function defined here --> $SRC_DIR/std/src/sync/poison/rwlock.rs:LL:COL help: remove the extra argument | LL - let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); LL + let _ = Arc::new(RwLock::new(HashMap<i32)); | This is because the expression is syntactically correct as RwLock::new( HashMap < i32, i64 > ::default() ); ^^^^^^^^^^^^ ------- - ---^ --- - ----------- ^ | | | | | | | | | | | | | | | a function call to `default` in the crate root | | | | | | a more than binop | | | | | a value to be compared | | | | the separator of the second argument to `RwLock::new()` | | | a value to be compared | | a less than binop | a value to be compared an associated function call but after that PR it would only be the following, even though the parser hasn't changed: error: can't compare two types --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:24:41 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^ ^ these are parsed as "less than" and "greater than" | help: you likely intended to write type `HashMap` with type parameters, but type parameters in expression contexts require the use of the "turbofish" `::<>` | LL | let _ = Arc::new(RwLock::new(HashMap::<i32, i64>::default())); | ++ I think that there's a lot of work needed in the parser itself to produce good diagnostics. There are other strategies, like performing multiple parses at a given point when you've reached a known bad state (you've seen a flag-post that shouldn't be there, but that is a signal for a handful of other known cases), or fully consuming the rest of a block when an unrecoverable parse occurred (we're half-way through parsing function arguments, but failed? consume the rest of the statement or of the parent block, accounting for sub-scopes). The latter can cause the rest of the file to be consumed, but that's an edge-case that in practice is much better than a deluge of irrelevant errors. Another added complexity is how some easy-to-hit errors occur during lexing, which means the compiler has barely any information about the user's code. Mismatched braces/parens is one of those. rustc tries to provide context by keeping a queue of seen open delimiters to point at, and explicitly checking for their indentation level as a heuristic to detect where the user's intent diverged from the code, but that's overly reliant on the code being sanely formatted (thanks to rustfmt-on-save, that's a good bet for many users). For an example of the things rustc can do even in the lexer, you can look at https://github.com/rust-lang/rust/pull/160592 https://github.com/rust-lang/rust/pull/160592.
jdw64 2mo ago
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
- conartist6 2mo ago
  I'll just drop this here for you and anyone else who wants it: https://github.com/bablr-lang/language-en-regex-vm-pattern/blob/trunk/lib/grammar.js https://github.com/bablr-lang/language-en-regex-vm-pattern/b... No codegen, just function calling.
r3d 2mo ago
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.
- jrimbault 2mo ago
  Can you feel the irony when typing this? "Simple readable C code" itself not being able to be parsed by "simple readable C code".
  - r3d 2mo ago
    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.
- tester756 2mo ago
  Why care about lang which doesnt really support strings well?
  - r3d 2mo ago
    What do you think the libraries you use to parse these things are doing under the hood? Maybe you don't care? Fair enough.
    - tester756 2mo ago
      use 10 meters of wrappers around C and its quirks? :P
  - mrkeen 2mo ago
    In C's defence, you only have forward-compatability of string handling to the extent that your string type will not change in the future. Byte arrays are great for this. All string encodings in the foreseeable future can be encoded in bytes. You do not need to recompile coreutils once someone invents utf8-plus. 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.
alexjurkiewicz 2mo ago
> if (!line.accept('[').isEmpty() ) // [section] header. Is this really ergonomic?
- roaringrocky 2mo ago
  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...".
- derdi 2mo ago
  It's not, and the article's attempt at putting lipstick on this pig is nonsensical: > StringView has no operator bool, so a successful match reads as !scanner.accept('=').isEmpty(). Noisier than returning a bool, but the matched text comes back with the answer instead of requiring a second call to go get it. Clearly there is a second call, it's the call to isEmpty. Plus, the actual text is lost in this particual example (though we know what it was). An actual ergonomic way of using this would set things up so that the INI parser's inner code could be written something like this: bool success = (name = trim(acceptUntil('='))) && accept('=') && accept(Space) && (property = acceptAll());
chrisjj 2mo ago
Nice, but > trims the stray trailing \r that malformed input likes to leave behind how does this distinguisg the non-stray variety?
zabzonk 2mo ago
FORTH parsers are ultra simple - get the next space-separated token, if it is a number, push it on the stack, otherwise it's a word - look it up in the dictionary and (if it exists there) execute it.
- roaringrocky 2mo ago
  Even simpler is you go the colorforth route, part of the source code is "pre parsed" by the editor, a prefix byte is added to each word (which is shown as different colors), then a simple dispatch loop with that prefix as a sort of opcode.
  - conartist6 2mo ago
    This feels like a precursor to the project I'm doing, which I us to make an editor whose state and output are expressed as such "pre-parsed" syntax trees. I'm trying to make mine fully language agnostic though
langbn 2mo ago
A parser/compiler could obviously be improved with an LLM (AI!) to suggest improvements to invalid input. That is actually a super good use case of LLM/AI. Having clang/gcc, or any other parser, implement that is of course impossible, they are too conservative and would rather die than to implement modern helpful tools.
- derdi 2mo ago
  You're presumably using an LLM to drive the compiler, and your LLM should be just as capable of reading the compiler's error message and fixing the problem. So why double the work?
aappleby 2mo ago
If this is "simple", then I don't think the author has tried a good parser combinator library yet.

58 points by signa11 3mo ago

If you draw a line from 'ad-hoc byte-wrangling nonsense' to 'parser combinators', this can't be more than 20% along it. Looking at the linked URL parser, why doesn't it look like url = do scheme authority path query fragment where scheme = ... authority = ... etc. It looks totally ad-hoc.

Retr0id 2mo ago

> 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 end of a malformed line” unrepresentable rather than merely unlikely. I don't really see what makes it "unrepresentable", and this reads more like "if you used the right scanning logic, you can't have used the wrong scanning logic".

inigyou 2mo ago
Sure, start with \r\n, split on \n, now you have a stray \r at the end of every input.
- Retr0id 2mo ago
  But the preceding clause says it handles \r\n. If you're already handling \r\n, what remaining sources of \r are there, that you'd actually want to silently ignore?
  - inigyou 2mo ago
    Someone else (possibly you) already split on \n.
    - Retr0id 2mo ago
      Fair point. I think if something is getting mangled like that I'd rather fail loudly, but it depends on the use case I suppose.
- HackerThemAll 2mo ago
  \r\n?|\n handles all EOL sequences without backtracking. Or write a non-regex equivalent of that.
  - inigyou 2mo ago
    I'm sure every time you split something on newlines you remember to use a regex.
    - HackerThemAll 2mo ago
      I tend not to, because it's an overkill, but this regex nicely sums what needs to be done.
thesz 2mo ago
End of line on Classic Mac is \r.
dspillett 2mo ago
> Is there a common source of extra \r in malformed inputs, beyond those existing as part of \r\n? 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.

f311a 2mo ago

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::]/

meindnoch 2mo ago
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:b487:e57d:193e:550e::] $5 (path) = / Seems correct to me. [1] https://datatracker.ietf.org/doc/html/rfc3986#appendix-B https://datatracker.ietf.org/doc/html/rfc3986#appendix-B [2] https://regexr.com/8nqop https://regexr.com/8nqop
- quuxplusone 2mo ago
  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/0b001f5f36579e8aea07efa5af139ca18dad9505/src/url.cpp#L48-L123 https://github.com/bkaradzic/bx/blob/0b001f5f36579e8aea07efa...
  - meindnoch 2mo ago
    >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.
- f311a 2mo ago
  Regexes are pretty slow, though.

speedgoose 2mo ago

I now use nom to write my parsers. Once you understand it, it’s simple and parsing complex data becomes a _fun_ puzzle. I recommend it. https://github.com/rust-bakery/nom https://github.com/rust-bakery/nom

imoverclocked 2mo ago

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 can look progressively more like JSON… and on and on.

simonask 2mo ago
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.
- haileys 2mo ago
  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.
  - mhast 2mo ago
    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.
    - srean 2mo ago
      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.
      - 2mo ago

tomashubelbauer 2mo ago

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.

estebank 2mo ago
I will provide some context from having done a lot of that work. The Rust grammar is actually quite regular, that's why we have things like the turbofish for type parameters (`binding.method::<Type>()`): it makes the grammar unambiguous (a naïve parser would with a complicated grammar that accepts chained comparisons would have to deal with differentiating between `binding.method < value > ()` and `binding.method<Type>()`). But that doesn't mean the rustc parser doesn't do the work of supporting some the more complex grammar in order to provide better diagnostics. I like to say that rustc actually knows about meta-Rust, a daughter language that goes crazier in its features. I also joke that rustc isn't done until you can paste code from another language and following the suggestions you end up with valid Rust code without loss of the user's intent. Part of the problem is that the places where incorrect code can fail is in more places than the parser. The chained comparisons example is one that is easy for Rust (as it doesn't support them), so the parser itself can produce a "missing turbofish" suggestion with high certainty, but for truly ambiguous expressions, the errors will happen later, during name resolution ("expected a value and found a type") or when checking the number of arguments. A production compiler needs to account for not only the original error, but also silence every knock-down error too. The simplest strategies are to just stop if at the end of a given stage there are errors (which leads to the "wave of errors" experience of fixing the "last" error leading to a ton of new ones) or fully replacing entire blocks of code that had a parse error with an AST node that acts as a tombstone marking that that later stages need to ignore it. The first option leads to a bad experience, and the latter is insufficient. A recent example of looking at this is https://github.com/rust-lang/rust/pull/159689 https://github.com/rust-lang/rust/pull/159689, where `Arc::new(RwLock::new(HashMap<i32, i64>::default()));` currently produces error[E0423]: expected value, found struct `HashMap` --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:34 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^^^^^ | --> $SRC_DIR/std/src/collections/hash/map.rs:LL:COL ::: $SRC_DIR/std/src/collections/hash/map.rs:LL:COL | = note: `HashMap` defined here error[E0423]: expected value, found builtin type `i32` --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:42 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^ not a value error[E0423]: expected value, found builtin type `i64` --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:47 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^ not a value error[E0425]: cannot find external crate `default` in the crate root --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:53 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^^^^^ not found in the crate root error[E0061]: this function takes 1 argument but 2 arguments were supplied --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:11:22 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^^^^^^^^^^^ --------------- unexpected argument #2 of type `bool` | note: associated function defined here --> $SRC_DIR/std/src/sync/poison/rwlock.rs:LL:COL help: remove the extra argument | LL - let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); LL + let _ = Arc::new(RwLock::new(HashMap<i32)); | This is because the expression is syntactically correct as RwLock::new( HashMap < i32, i64 > ::default() ); ^^^^^^^^^^^^ ------- - ---^ --- - ----------- ^ | | | | | | | | | | | | | | | a function call to `default` in the crate root | | | | | | a more than binop | | | | | a value to be compared | | | | the separator of the second argument to `RwLock::new()` | | | a value to be compared | | a less than binop | a value to be compared an associated function call but after that PR it would only be the following, even though the parser hasn't changed: error: can't compare two types --> $DIR/suggest-turbofish-parsed-as-comparisons.rs:24:41 | LL | let _ = Arc::new(RwLock::new(HashMap<i32, i64>::default())); | ^ ^ these are parsed as "less than" and "greater than" | help: you likely intended to write type `HashMap` with type parameters, but type parameters in expression contexts require the use of the "turbofish" `::<>` | LL | let _ = Arc::new(RwLock::new(HashMap::<i32, i64>::default())); | ++ I think that there's a lot of work needed in the parser itself to produce good diagnostics. There are other strategies, like performing multiple parses at a given point when you've reached a known bad state (you've seen a flag-post that shouldn't be there, but that is a signal for a handful of other known cases), or fully consuming the rest of a block when an unrecoverable parse occurred (we're half-way through parsing function arguments, but failed? consume the rest of the statement or of the parent block, accounting for sub-scopes). The latter can cause the rest of the file to be consumed, but that's an edge-case that in practice is much better than a deluge of irrelevant errors. Another added complexity is how some easy-to-hit errors occur during lexing, which means the compiler has barely any information about the user's code. Mismatched braces/parens is one of those. rustc tries to provide context by keeping a queue of seen open delimiters to point at, and explicitly checking for their indentation level as a heuristic to detect where the user's intent diverged from the code, but that's overly reliant on the code being sanely formatted (thanks to rustfmt-on-save, that's a good bet for many users). For an example of the things rustc can do even in the lexer, you can look at https://github.com/rust-lang/rust/pull/160592 https://github.com/rust-lang/rust/pull/160592.

jdw64 2mo ago

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

conartist6 2mo ago
I'll just drop this here for you and anyone else who wants it: https://github.com/bablr-lang/language-en-regex-vm-pattern/blob/trunk/lib/grammar.js https://github.com/bablr-lang/language-en-regex-vm-pattern/b... No codegen, just function calling.

r3d 2mo ago

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.

jrimbault 2mo ago
Can you feel the irony when typing this? "Simple readable C code" itself not being able to be parsed by "simple readable C code".
- r3d 2mo ago
  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.
tester756 2mo ago
Why care about lang which doesnt really support strings well?
- r3d 2mo ago
  What do you think the libraries you use to parse these things are doing under the hood? Maybe you don't care? Fair enough.
  - tester756 2mo ago
    use 10 meters of wrappers around C and its quirks? :P
- mrkeen 2mo ago
  In C's defence, you only have forward-compatability of string handling to the extent that your string type will not change in the future. Byte arrays are great for this. All string encodings in the foreseeable future can be encoded in bytes. You do not need to recompile coreutils once someone invents utf8-plus. 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.

alexjurkiewicz 2mo ago

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

roaringrocky 2mo ago
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...".
derdi 2mo ago
It's not, and the article's attempt at putting lipstick on this pig is nonsensical: > StringView has no operator bool, so a successful match reads as !scanner.accept('=').isEmpty(). Noisier than returning a bool, but the matched text comes back with the answer instead of requiring a second call to go get it. Clearly there is a second call, it's the call to isEmpty. Plus, the actual text is lost in this particual example (though we know what it was). An actual ergonomic way of using this would set things up so that the INI parser's inner code could be written something like this: bool success = (name = trim(acceptUntil('='))) && accept('=') && accept(Space) && (property = acceptAll());

chrisjj 2mo ago

Nice, but > trims the stray trailing \r that malformed input likes to leave behind how does this distinguisg the non-stray variety?

zabzonk 2mo ago

FORTH parsers are ultra simple - get the next space-separated token, if it is a number, push it on the stack, otherwise it's a word - look it up in the dictionary and (if it exists there) execute it.

roaringrocky 2mo ago
Even simpler is you go the colorforth route, part of the source code is "pre parsed" by the editor, a prefix byte is added to each word (which is shown as different colors), then a simple dispatch loop with that prefix as a sort of opcode.
- conartist6 2mo ago
  This feels like a precursor to the project I'm doing, which I us to make an editor whose state and output are expressed as such "pre-parsed" syntax trees. I'm trying to make mine fully language agnostic though

langbn 2mo ago

A parser/compiler could obviously be improved with an LLM (AI!) to suggest improvements to invalid input. That is actually a super good use case of LLM/AI. Having clang/gcc, or any other parser, implement that is of course impossible, they are too conservative and would rather die than to implement modern helpful tools.

derdi 2mo ago
You're presumably using an LLM to drive the compiler, and your LLM should be just as capable of reading the compiler's error message and fixing the problem. So why double the work?

aappleby 2mo ago

If this is "simple", then I don't think the author has tried a good parser combinator library yet.