Parsing invalid input

[darichey]

One attractive feature of rnix-parser is, through its use of rowan, it is able to recover from errors and provide partial parses for input. This is especially useful in the context of editor tooling where the code is frequently invalid while it is being edited. How does nixel/santiago stack up in this respect?

[kamadorueda]

We don't support that at the moment

Do you know if there is literature explaining how to extend the Earley Parser to that use case?

[darichey]

Unfortunately I'm not very familiar with the Earley algorithm (or really parsing in general beyond recursive descent). I had a quick look, but I can't immediately find any explanation on how rowan accomplishes this beyond "a special effort of continuing the parsing if an error is detected" here.

In that document, rowan refers to the desired properties as "lossless" and "resilient":

• Parsing is lossless (even if the input is invalid, the tree produced by the parser represents it exactly).
• Parsing is resilient (even if the input is invalid, parser tries to see as much syntax tree fragments in the input as it can).

But I couldn't immediately find any literature explaining the technique. I'll keep looking :)

[darichey]

Small update: I misunderstood how rowan plays in here. It is not responsible for producing the lossless syntax trees, but representing them. Therefore, the techniques we're looking for (not for Earley, but just to get a general idea of what's going on) are actually found in the users of rowan like rnix-parser and rust-analyzer.

[darichey]

I was reminded of this in the rnix matrix channel today. I'd like to just dump some links I found in case anyone wants to continue investigating:

• Parser Generator in C# details a parser generator based on the Earley algorithm with error recovery (see section 4.2.5). Two citations in that section are probably of interest:
  • D. Grune and C. J. H. Jacobs, Parsing Techniques: A Practical Guide (Monographs in Computer Science). Springer, 2007, p. 662
  • A. W. Appel, Modern Compiler Implementation in C. Cambridge University Press, 2004, p. 556.
• Locally Least-Cost Error Recovery in Earley's Algorithm
• https://github.com/vnmakarov/yaep is a C implementation of Earley which supports error recovery by requiring explicit error branches in the grammar (like yacc)
• Q: How to do error recovery? ollef/Earley#34: error recovery has not been implemented in this Haskell earley parser

Feel free to close if this isn't something you're interested in pursuing. It seems like it would be a lot of work.

[kamadorueda]

Actually, is not much work now that we use GNU Bison as a parser generator (since nixel 5.0), it would be just a matter of using: https://www.gnu.org/software/bison/manual/bison.html#Error-Recovery

I'm happy to receive contributions for it, I think the sensible places to recover from errors would be between containers, like '(' error ')', or in unfinished bindings like binds attrpath '=' error and so on

[kamadorueda]

Closing in favor of #3