How to force an error token if resync recovery fails?

[LordOfDragons]

I've got this parser definition: https://github.com/LordOfDragons/vscode-langext-dragonscript/blob/dd59509907d098a65796dc36ed2f16bd51da5547/server/src/parser.ts .

The problem happens with a script like this:

...
class A
   function void B()
      c = (d + e * )
   end
end

Chevrotail totally breaks down in this situation. The problem is the function call "*" is missing an argument and thus this rule can not be completed:
https://github.com/LordOfDragons/vscode-langext-dragonscript/blob/dd59509907d098a65796dc36ed2f16bd51da5547/server/src/parser.ts#L737

What happens is that all code after this line is dead. The re-sync travels all the way up to the top production rule instead of stopping at something simple like the ")" token closing an expression group.

Hence what happens is that Chevrotain fails to realize it could fix the problem by simply adding an error token in the OR() clause in this rule:
https://github.com/LordOfDragons/vscode-langext-dragonscript/blob/dd59509907d098a65796dc36ed2f16bd51da5547/server/src/parser.ts#L926

Is there a way to explicitly add a "ERROR()" production to this OR() clause to tell Chevrotain to inject exactly here an error token should it fail to complete this rule?

I also tried using "{resyncEnabled: false}" to stop the re-syncing bubbling up but to no avail. The breaking just is differently but prevents all kind of editor helps to be deduced which customers expect to be present.

[bd82]

Hello @LordOfDragons

For the https://github.com/LordOfDragons/vscode-langext-dragonscript/blob/dd59509907d098a65796dc36ed2f16bd51da5547/server/src/parser.ts#L926 I don't believe single token insertion recovery is applicable.

That type of error recovery only happens within the scope of the current grammar rule.
And in order to proceed the parser first has to decide between the 4 alternatives which triggers the re-sync.

I also suspect the recovery problem is related to the general structure / pattern of the binary expressions.
If you can create a minimal reproducing example:

1. Grammar with 3-4 levels of binary expressions.
2. Sample input where "too much" input was dropped due to re-sync.

I could try:

1. Verifying this is the expected behavior of the recovery logic.
2. Thinking of a workaround / better way to recover in that scenario.
   • No promises on succeeding here 😄

[LordOfDragons]

Getting a small reproducing example will be difficult. As a question in the mean time I've seen in the API documentation this: https://chevrotain.io/docs/tutorial/step4_fault_tolerance.html#embedded-actions-integration . A function "recoveryValueFunc" is mentioned which could be used to produce a token. I have though not figured out yet how this is supposed to work. What is the function returning? Is there some code example for the use of this function?

[bd82]

What is the function returning?

If I remember correctly this is meant to return a specific value when a grammar rule fails to parse successfully.
So for example if you have a grammar rule that parses a JSON object with 3 properties (name/age/address).
and the result of the parse is a JS Object with the following properties, e.g;

Input

name -> John
age -> 50
address -> NY

Output of this grammar rule:

{
  name : "John",
  age : 50,
  address: "NY"
}

The output of the recoveryValueFunc could be some N/A / Empty person, e.g.:

{
  name : "N/A",
  age : NaN,
  address: "N/A"
}

This API will not affect the recovery logic, only the returned value after the re-sync happened.
With a CST parser the returned value is normally a CST sub-tree so that API seems non-relevant in that case.

[LordOfDragons]

Are there any tips on how to best design a CST grammar or known situations where such problems occur? Maybe this helps me to figure out what could be the problem.

[bd82]

I needed to create a small grammar (XML) outputting a CST in the past.
There were a couple of cases where I disabled the single token deleteion recovery to improve the results of error recovery:

• https://github.com/SAP/xml-tools/blob/ce9aab3a21df94d54e5c9d34540c45e04a9a9a61/packages/parser/lib/parser.js#L102-L112
• https://github.com/SAP/xml-tools/blob/ce9aab3a21df94d54e5c9d34540c45e04a9a9a61/packages/parser/lib/parser.js#L144-L155

There was also a bug (fixed since) which was handled by overriding an internal Chevrotain function:

• https://github.com/SAP/xml-tools/blob/ce9aab3a21df94d54e5c9d34540c45e04a9a9a61/packages/parser/lib/parser.js#L183-L203

I suspect you will need to dive into the Chevrotain internals:

• Figure out if the default recovery logic is implemented correctly (is there a bug?).
• Figure out how to modify the recovery behavior for your use case (e.g overriding internals) (assuming its not a bug).
• Use the understanding you acquired in the above steps Consider re-factoring the grammar so the recovery would behave "better".
  • For example, due to performance reasons I tend to model binary expressions as a flat list (without precedence at the grammar level), e.g.:

    • chevrotain/examples/grammars/ecma5/ecma5_parser.js

      Lines 257 to 283 in 4a68802

      	$.RULE("BinaryExpression", () => {
      	$.SUBRULE($.UnaryExpression);
      	$.MANY(() => {
      	$.OR(
      	$.c3 ||
      	($.c3 = [
      	// flat list of binary operators
      	{ ALT: () => $.CONSUME(t.AbsAssignmentOperator) },
      	{ ALT: () => $.CONSUME(t.VerticalBarVerticalBar) },
      	{ ALT: () => $.CONSUME(t.AmpersandAmpersand) },
      	{ ALT: () => $.CONSUME(t.VerticalBar) },
      	{ ALT: () => $.CONSUME(t.Circumflex) },
      	{ ALT: () => $.CONSUME(t.Ampersand) },
      	{ ALT: () => $.CONSUME(t.AbsEqualityOperator) },
      	{ ALT: () => $.CONSUME(t.AbsRelationalOperator) },
      	{ ALT: () => $.CONSUME(t.InstanceOfTok) },
      	{ ALT: () => $.CONSUME(t.InTok) },
      	{ ALT: () => $.CONSUME(t.AbsShiftOperator) },
      	{
      	ALT: () => $.CONSUME(t.AbsMultiplicativeOperator),
      	},
      	{ ALT: () => $.CONSUME(t.AbsAdditiveOperator) },
      	]),
      	);
      	$.SUBRULE2($.UnaryExpression);
      	});
      	});

    • chevrotain/examples/grammars/ecma5/ecma5_parser.js

      Lines 41 to 48 in 4a68802

      	// A.3 Expressions
      	// Note that the binary expression operators are treated as a flat list
      	// instead of using a new rule for each precedence level.
      	// This is both faster and less verbose but it means additional logic must be used to re-order the flat list
      	// into a precedence tree.
      	// This approach was used in the swift compiler.
      	// https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Expressions.html#//apple_ref/doc/uid/TP40014097-CH32-ID383
      	// (scroll down to the note on binary expressions)

Would this pattern also affect the recovery behavior of binary expressions? I don't know...
That is why I recommended starting with a minimal reproducing example as it can simplify the understanding of the problem space.

[LordOfDragons]

I tried recreating the problem using https://chevrotain.io/playground/ but I always get

Errors during evaluation of the implementation: 
lexer.tokenize is not a function

Is the playground using an old chevrotain library? The strange thing is I do not use "tokenize" anywhere in the playground code so I have no idea where this one is coming from.

[LordOfDragons]

I see. I'll certainly opt for the alternative approach there as it does not require large code changes.

So if I understand correctly it is best to avoid AT_LEAST_ONE_SEP to achieve higher recovery rate?

[bd82]

it is best to avoid AT_LEAST_ONE_SEP to achieve higher recovery rate?

The answer is more nuanced:

There is a combination of factors:

1. AT_LEAST_ONE_SEP can throw an error which will trigger re-sync recovery.
2. resync recovery tries to sync to grammar rules farther up the rule stack, so it won't try to parse any of the rest of the grammar inside the current rule.

So, the same thing could happen with OR, it is not only about AT_LEAST_ONE_SEP.

Some thoughts on optimizing grammar for error recovery

Splitting into sub-rules

Splitting the part of the grammar which can throw an error into a sub-rule can assist in reducing the amount of grammar "skipped" on resync, e.g.:

// one big rule
this.RULE("statementCase", () => {
		this.CONSUME(DSLexer.tokenCase)
		this.AT_LEAST_ONE_SEP({
			SEP: DSLexer.tokenComma,
			DEF: () => this.SUBRULE(this.expression, {LABEL: "value"})
		})
		this.SUBRULE(this.endOfCommand)
		this.SUBRULE(this.statements)
	})


// with a sub-rule
this.RULE("statementCase", () => {
		this.CONSUME(DSLexer.tokenCase)
		this.SUBRULE(this.casesExpressions) // now an error in this sub-rule could "re-sync" recover to the next sub-rule.
		this.SUBRULE(this.endOfCommand)  // after successful re-sync parsing will continue here.
		this.SUBRULE(this.statements)
	})

this.rule("casesExpressions", () => {
		this.AT_LEAST_ONE_SEP({ // error could be thrown here is NOTHING is matched (not even once)
			SEP: DSLexer.tokenComma,
			DEF: () => this.SUBRULE(this.expression, {LABEL: "value"})
		})
    })

But there are likely other behaviors of the recovery algorithms which would work better with
more grammar "in-lined" into the rule.

For example, I vaguely recall single-token insertion and deletion have limits on the scope they work at.
It has been too many years since I implemented these algorithms for prefect recall.
I suspect you will need to dive into the logic itself to have the knowledge to manipulate the error recovery for optimal results.

• https://github.com/Chevrotain/chevrotain/blob/master/packages/chevrotain/src/parse/parser/traits/recoverable.ts

And in some cases you may even need to override/modify some built-in chevrotain methods.

Maybe you could even contribute a best practices for optimizing error recovery docs to share the lessons learned 😄

[LordOfDragons]

Actually the point about how recovery ends the rule and tries to recover the next higher up is the important information I think. From the documentation I did not get this kind of behavior to be done. This is what the documentation says:

Repetition re-sync recovery happens when:

    The parser is in a repetition(MANY/AT_LEAST_ONE/MANY_SEP/AT_LEAST_ONE_SEP).
    The parser has consumed the last iteration and is about to "exit" the repetition.
    The next token X is invalid right after the repetition ended.

In such a situation the parser will attempt to skip tokens until it detects the beginning of a another iteration of the repetition or the token it originally expected after the last iteration.

From this I concluded recovery is performed "in the rule that caused the exception" not the "parent rule". Adjusting the documentation in this regard might help.

[bd82]

Yeah that documentation is part of the tutorial, some more in-depth detailed docs could be useful...

For example, detailed docs for the grammar recording phase:

• https://chevrotain.io/docs/guide/internals.html#grammar-recording

[LordOfDragons]

I did now some first tests. Refactoring such problematic parts into subrules does help to reduce the amount of dropped tokens to a reasonable amount. There are still problematic cases but all in all this helps. Maybe outlining this recovery behavior and the possible solution for it would be a good idea.