Proposals for parsing error handling

[gwhitney]

Beyond fixing the bug detailed in #544, some further thought and experimentation has led to a couple of reasonably specific proposals for making the parse error generation from ohm grammars more useful:

(A) Don't record (just?) the start position of a failure of a non-terminal, record the end position of its partial match.

Without this, a described rule that matches a lot of the input but doesn't manage to succeed (or only manages to succeed by matching much less input, via fewer instances of an iteration, for example), loses a great deal of its "credit" in terms of being highlighted as the "likely" parse for the input that went astray. It really does mean something when a partial match of a (described) rule gets farther along in the input.

For concrete examples:

(1) consider the language of the initial post of issue 302. It would be much more helpful to the person who wrote the erroneous ? in the middle of an otherwise correct "BlockExpression" to hear that "?" isn't an "Expression" than to hear that there shouldn't be any stuff after a valid empty program. In other words, the parse path that got all the way to accepting the "1" and only died on the "?" should take priority in terms of reporting over the path that accepted no characters at all and then was upset that there was any input after that. (After all, that's the original rationale of "rightmost failure".) But with the current accounting of failure position, both parse paths fail "at position 0" and so they are considered equally (and then bug #544 suppresses the BlockExpression one altogether, leaving just the "I parsed nothing as a Program and then was shocked to see another character" one).

In other words, this example has a unique rightmost failure -- parse as an ExpressionList of one BlockExpression, starting with block { and then an ExpressionList with the first Expression being a "1" and then unparseable stuff -- and that should remain the rightmost failure regardless of whether rules are described or not. So failures (whether named or not) should be primarily indexed by how far they got into the input, not by where they started.

Note that I say this principle should hold for non-terminals. I believe that typically when parsing a terminal like "while" the fact that it gets three characters into "which" is pretty irrelevant -- for the sake of parsing, "while" has no more to do with "which" than it has to do with "for," say. So I think terminals should continue to be primarily indexed by their start position.

(2) Consider the quoted string language of #542. In reporting on the difficulty with parsing "\uD8" it seems more useful to focus on the missing hex digits of a possible unicodeEscape than just to say that after an escape slash, there should be a literal "n," "t," slash, quote, or unicodeEscape -- there already was the proper "\u" for a unicodeEscape, and so the important information is that then the unicodeEscape was malformed. That's what would happen if the last match position of a partial match was used instead of the start -- then the unicodeEscape failure would be the sole rightmost failure and would be reported on its own.

(3) Consider the example language of #482. The poster/grammar author there is clearly more interested in telling their users what is wrong with the function definition that the example input started than that if the empty program was intended, it shouldn't be followed by anything else. Again, if the Fun parse path that consumed the first 10 characters of the input got "credit" for that, rather than just being a rule that tried to apply starting from the beginning of the input and eventually failed, then the error reporting would focus on that path as the rightmost failure, as desired.

---

(B) In the Failure object, make available (at least) both the rightmost "lexical" expectation/failure and its innermost enclosing named rule, or the "lexical" expectation and just the innermost enclosing syntactic rule if there is no enclosing named rule. I think that both are needed to produce the kind of syntax error message that a "real" programming language would. In the same three examples from (A), you would like to:

(1) tell the user that a digit or "block" was expected, because you are trying to assemble a BlockExpression;
(2) tell the user that a hexDigit is expected, because you are trying to read a unicodeEscape.
(3) tell the user that a Statement is expected because you are trying to parse Statements.

Right now with the failuresInfo (that had been pushed onto the stack when a described rule is commenced) being popped and completely thrown away when a rule fails, the second "because" part of each of these "ideal" syntax error messages is (modulo #544) being kept around to be used in a message, but the first part of each -- what actually ended up going wrong, or rather what character/terminal-item possibilities would have worked, is being thrown away and can't be used to generate something helpful for the person trying to use the language defined by the grammar.

Of course, if it's simply/conveniently possible to just capture the whole parse stack at the point of a Failure and make it available in the Failure object, a grammar writer would be able to analyze it afterward to generate the most apt error message. So that approach would be fine as well.