Lambda the Ultimate

I'm aware of that paper and that suggestion, but it doesn't really address the issue I'm after. I'm concerned about the case where we have an input that clearly (and correctly) fails to parse in some portion. What we would then like to do is have a means to re-synchronize the parser so that subsequent, unrelated errors can be detected and reported in the same compile run.

I haven't seen anything in the mixfix/distfix literature that addresses this at all.

Perhaps an area to look is parallel parsers: for divide-and-conquer, theyl'll need to speculate how to jump in at any point anyways. I think I misunderstood the question however.

If you think of an error as punching a hole in a valid parse tree, I try to make that hole smaller so feedback on other code occurs sooner.

So basically, instead of backtracking on error and trying another rule, assume a syntax error and continue parsing with the current rule, placing an explicit syntax error node in the tree. Then collect the set of all parse trees, basically one per rule, and pick the one with the fewest number of errors.

For a successful parse, there will be a tree without errors. If no successful parse exists, the tree with the smallest number of errors is the program requiring the fewest number of changes to become syntactically correct.

That does sound optimal, albeit expensive, but it seems like a good place to start.

Edit: You could probably make this efficient by making parsing incremental. Only continue parsing with a given rule if the number of errors encountered so far is less than the number of errors encountered by the previously lowest error parse. This would require evaluating each rule in parallel until they start dropping off as they start accumulating errors. Some will come back into the running for unparseable programs as errors accumulate.

I tried something like this for a DSL parser some time ago.

The problem was how to re-synchronise when all parse trees had errors. I thought I was smart by giving each rule a re-sync symbol it could look ahead for. Sadly this didn't work unless all the current rules happened to have the same symbol. If the re-sync symbols were different (which was the case most of the time in the particular language) then each tree had to continue to be parsed to end of input and that became too expensive, especially where subsequent errors multiplied the numbers of trees.

Also when several rules had different causes of the error which one should be displayed to the user? Plain "syntax error" wasn't very helpful but "you have error abc or def" was worse :-)

Eventually gave up and failed on first error.

The problem was how to re-synchronise when all parse trees had errors.

What do you mean by "synchronization"? Following naaskings approach each branch of the parser always eats the same token. In that sense they are "synchronized" by default.

By synchronize I meant the rule to the token stream.

After a mismatch continuing to try to match subsequent tokens at the same place in the rule gave long strings of errors which wasn't very useful. The idea (not original) was to define a token or pattern that was very likely to indicate a specific point in the rule (eg the ';' as statement end in a C like language).

From this point any further mismatches are likely to be further syntax errors, not irrelevant consequent errors, so all tokens up to this point can be ignored.

I assume it is hard to find a dedicated checkpoint in a mixfix expression which can be arbitrary nested.

Have you tried to repair the token-stream?

Let's say the token-stream T is corrupted at index n. We build a new token-stream T' from T with the following properties:

1. The edit distance dist(T, T') must be minimal.
2. For a fixed k the stream T'[0..n+k] must represent a valid expression ( T[0..n-1] is valid by assumption ).

It is important to choose k not too small because otherwise we might run into consequent errors but also not too big because we don't want to detect new syntax errors at this point.

I assume it is hard to find a dedicated checkpoint in a mixfix expression which can be arbitrary nested.

Yes, informally the requirement for accuracy seemed to be that the sync pattern must be illegal either syntactically or semantically in any preceding nested expressions. Experience showed that a pattern was still useful if it rarely occurred in practice in preceding nested expressions.

Of course unless your language treats the whole input as one expression then there are parts of the syntax which can't occur in expressions (eg traditional statements). These are much better sync points, but the question was how to handle errors within the mixfix expressions. Still maybe the lesson is define your language so that in practice the mixfix expressions don't get too big and so they can be abandoned and then sync on the next thing thats not an expression.

Have you tried to repair the token-stream?

Not much, due to lack of time only a quick consideration was given to single token edits. But due to the ambiguity of the grammar it was not clear how to decide on a substitution or insert. Any guidance on recent literature welcome.

Instead as I said we abandoned expressions on the first error, skipped tokens until the first one that could not occur in an expression and continued from there.

Not much, due to lack of time only a quick consideration was given to single token edits. But due to the ambiguity of the grammar it was not clear how to decide on a substitution or insert.

That's not decidable upfront. As in naaskings approach the parser still has to handle multiple parses in the general case. It only removes the need for a "sync-point" to deal with consequent errors. However new errors might be introduced. For example inserting a bracket '[' might locally fix your expression but leads to a global imbalance. This doesn't reduce the value of the approach though because one still counts fixes and the parse with the least ones becomes the winner of the competition.

On this:

So basically, instead of backtracking on error and trying another rule, assume a syntax error and continue parsing with the current rule, placing an explicit syntax error node in the tree. [...] For a successful parse, there will be a tree without errors. If no successful parse exists, the tree with the smallest number of errors is the program requiring the fewest number of changes to become syntactically correct.

After several attempts with other approaches (including the obvious stop-on-first error), I've implemented exactly what naasking just described. And it works pretty fine, as far as friendly (say, not "totally dumb") multi-error reporting is concerned, I can confirm, at least with a PEG-based fluent interface like in this.

However, I confirm, too, it's not especially cheap, clearly, but I haven't tried the rest of naasking's suggestion (the incremental parsing part), though.

My .02

I'll cry.

Hey! My Pet language uses make a lot. *laughing out loud and returning to his own corner*