"try-parse" functionality / improving BACKTRACK

[NaridaL]

I've got a situation where I want "try parsing rule X, and if that doesn't work parse rule Y". This is currently supported with the BACKTRACK functionality. The issue with that (correct me if I'm mistaken) is that in the following case withEqualsStatement (and all side effects) get called twice.

      $.OR([
        // both statements have the same prefix which may be of "infinite" length, this means there is no K for which
        // we can build an LL(K) parser that can distinguish the two alternatives.
        {
          GATE: $.BACKTRACK($.withEqualsStatement),
          ALT: () => {
            $.SUBRULE($.withEqualsStatement)
          }
        },
...
])

It seems the simplest fix here would be to have BACKTRACK save the result of the subrule, and have SUBRULE check if the last call to BACKTRACK was for the same rule it wants to parse, and if so, just return that.

[bd82]

It seems the simplest fix here would be to have BACKTRACK save the result of the subrule, and have SUBRULE check if the last call to BACKTRACK was for the same rule it wants to parse, and if so, just return that.

That could work, although you will need to save a stack like information about backtracking, as withEqualsStatement could internally also call BACKTRACK.

backtracking is generally best avoided, it does not play well with other features (e.g error recovery).
and reduces performance, and not only by a constant factor it could be by an order of magnitude
if we have a chain of backtracking nested rules.

In Chevrotain backtracking is used as very naïve "advanced" lookahead which tries to parse the entire rule
and returns a boolean if the rule matched.

• chevrotain/packages/chevrotain/src/parse/parser/traits/recognizer_api.ts

  Lines 682 to 706 in e3e2068

  	BACKTRACK<T>(
  	this: MixedInParser,
  	grammarRule: (...args: any[]) => T,
  	args?: any[]
  	): () => boolean {
  	return function () {
  	// save org state
  	this.isBackTrackingStack.push(1)
  	const orgState = this.saveRecogState()
  	try {
  	grammarRule.apply(this, args)
  	// if no exception was thrown we have succeed parsing the rule.
  	return true
  	} catch (e) {
  	if (isRecognitionException(e)) {
  	return false
  	} else {
  	throw e
  	}
  	} finally {
  	this.reloadRecogState(orgState)
  	this.isBackTrackingStack.pop()
  	}
  	}
  	}

But more efficient lookahead logic could be implemented, for example in the Java-Parser package
There are custom "lookahead rules" that only search "deep" enough ahead to determine the choice.
These rules even disable the construction of the output structure (CST).

• https://github.com/jhipster/prettier-java/blob/3dfeef40ac3df34ce01a03b5c9db23d0347079a2/packages/java-parser/src/parser.js#L92-L112
• https://github.com/jhipster/prettier-java/blob/3dfeef40ac3df34ce01a03b5c9db23d0347079a2/packages/java-parser/src/productions/classes.js#L126-L150

You can find more details about that here: https://github.com/jhipster/prettier-java/blob/main/packages/java-parser/docs/design.md

[bd82]

From a library API perspective I'm not sure if Chevrotain should provide complex backtracking capabilities.
Simply because there may be multiple scenarios and backtracking does not play well with error recovery / partial CST building
which I consider to be more important features of Chevrotian.

Beyond that:

• I am also worried about the support/maintenance overhead of advanced backtracking capabilities.
• For most parsers I've implemented I have managed to either:
  • Avoid backtrakcing.
  • Only use it in very specific positions in the grammar, so the performance hit was not large.
  • Implement a more efficient backtracking logic (Java-Parser).
• I am also perfectly fine with Chevrotain not being able to parse all languages as it is primarily an LL(K) parser.

In regards to your suggestion:
Although I believe you can implement the flow you described as an end user if you modify the code links above:

1. Implement your custom backtrack logic but:

• Return the rule's result instead of boolean
• Avoid reloading the original parser state if the backtracking succeeded.

2. Call the backtrack logic before the gate (like in the Java-Parser).
3. Skip the rest of the current rule (if/else) if the backtracking succeeded.
   • Note you will have to ensure this does not conflict with grammar recording

To be honest, I would personally prefer to optimize the lookahead like in the Java-Parser
so each phase is clearly distinct (LOOKAHEAD / Parsing) as this will reduce complexity even if is not the most performant.

[NaridaL]

Some general info:

I started off with the CST-Parser but dropped it in favor the embedded actions parser and am currently creating my own AST/CST. This is mainly because I'm parsing left-associative structures and that would have required an extra step after parsing to "fix" the CST. (Maybe that would have been simpler, but the current solution also works fine). Also being explicit with the AST generation allows TypeScript to typecheck if everything is correct too.

In general I have been rewriting rules to avoid backtracking as much as possible but the specific case isn't that simple. Concretely, for GLSL ( https://www.khronos.org/registry/OpenGL/specs/es/3.0/GLSL_ES_Specification_3.00.pdf ) f[index_or_size /* usually one token but could be more */] could be the start of an expression f[index] = val or a declaration f[size] ff = ... which would be different AST nodes.

I've considered some custom backtracking logic but the current public API is quite limited in that regard. Fields used in the Java Parser such as isBackTrackingStack are not declared. There is also no field for example to check if the parser is currently backtracking.

I think the fix as I've suggested it doesn't actually need a stack: If withEqualsStatement internally also calls BACKTRACK, then it would set the "lastBacktrackResult" field, which might be used by another nested subrule, but as soon as the "top-level" BACKTRACK returns, it would overwrite the field (with null if it fails), and the next SUBRULE would only see the result of the BACKTRACK immediately preceding it.

In general this isn't a huge issue for me, as you've noted there are a number of workaround but it seems like an easy fix/improvement. Let me know if you're open to a PR.

[bd82]

In general I have been rewriting rules to avoid backtracking as much as possible but the specific case isn't that simple. Concretely, for GLSL ( https://www.khronos.org/registry/OpenGL/specs/es/3.0/GLSL_ES_Specification_3.00.pdf ) f[index_or_size /* usually one token but could be more */] could be the start of an expression f[index] = val or a declaration f[size] ff = ... which would be different AST nodes.

can there be only one closing square bracket on the left side of the = ? or more than one?

I've considered some custom backtracking logic but the current public API is quite limited in that regard. Fields used in the Java Parser such as isBackTrackingStack are not declared. There is also no field for example to check if the parser is currently backtracking.

That may be a good place to improve on, as it would enable consumers to implement their own solutions more easily.

I think the fix as I've suggested it doesn't actually need a stack

Possibly, the call stack may suffice. Although I needed a stack for some state management during backtracking.

In general this isn't a huge issue for me, as you've noted there are a number of workaround but it seems like an easy fix/improvement. Let me know if you're open to a PR.

I'd rather not change the backtracking capabilities at this time as I'm not sure what is the long term goal there in terms of APi.
Particularly when it is relatively simple for a consumer to modify the behavior
But I will reference this discussion if/when I have time and decide to invest in #856 . 👍

[bd82]

related to #856

[bd82]

@NaridaL just pinging in case you missed this issue being moved to a discussion

[matthew-dean]

Incidentally, Less and Sass also have this problem, where rule starts are entirely ambiguous, and thus entire paths have to be tried before trying a different one. I'm currently trying to figure out the least expensive way to do this in Chevrotain.

[matthew-dean]

Btw, just thought I'd jot some notes that I had while trying a similar approach. I think that GATEs / BACKTRACK are not the right approach here for a performant solution.

It occurred to me that, since I noticed that all GATEs are evaluated before choosing an ALT, then probably caching a BACKTRACK and returning it during a SUBRULE is still too low in performance, because you'd be evaluating GATEs that wouldn't apply. Instead, probably the better approach would be to set an option on the OR call, like CONTINUE_ON_ERROR that has behavior more like this:

1. Chevrotain evaluates an OR and, because of the index of the token stream, determines there are 2 or more possible ALTs that match.
2. Chevrotain tries each valid ALT, and if CONTINUE_ON_ERROR is true, errors are not thrown and are reset, along with position (like current backtracking).
3. If all valid ALTs throw errors, then a no viable alt error is thrown.

By doing the above, you get an effect like backtracking, but not EVERY Backtrack gate would be tried before choosing an ALT.

[matthew-dean]

Note: this is very much how the current Less parser works today.