Replies: 7 comments 2 replies
-
That could work, although you will need to save a stack like information about backtracking, as backtracking is generally best avoided, it does not play well with other features (e.g error recovery). In Chevrotain backtracking is used as very naïve "advanced" lookahead which tries to parse the entire rule
But more efficient lookahead logic could be implemented, for example in the Java-Parser package
You can find more details about that here: https://github.com/jhipster/prettier-java/blob/main/packages/java-parser/docs/design.md |
Beta Was this translation helpful? Give feedback.
-
From a library API perspective I'm not sure if Chevrotain should provide complex backtracking capabilities. Beyond that:
In regards to your suggestion:
To be honest, I would personally prefer to optimize the lookahead like in the Java-Parser |
Beta Was this translation helpful? Give feedback.
-
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 ) 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 I think the fix as I've suggested it doesn't actually need a stack: If 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. |
Beta Was this translation helpful? Give feedback.
-
can there be only one closing square bracket on the left side of the
That may be a good place to improve on, as it would enable consumers to implement their own solutions more easily.
Possibly, the call stack may suffice. Although I needed a stack for some state management during backtracking.
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. |
Beta Was this translation helpful? Give feedback.
-
related to #856 |
Beta Was this translation helpful? Give feedback.
-
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. |
Beta Was this translation helpful? Give feedback.
-
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
By doing the above, you get an effect like backtracking, but not EVERY Backtrack gate would be tried before choosing an ALT. |
Beta Was this translation helpful? Give feedback.
-
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.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.
Beta Was this translation helpful? Give feedback.
All reactions