Improving MuSyntax backtracking performance
Project: | JNode Shell |
Component: | Code |
Category: | task |
Priority: | normal |
Assigned: | Stephen Crawley |
Status: | active |
Jump to:
Description
The time taken to parse a MuSyntax currently tends to exponential backtracking as Syntaxes get more complex. I currently kludge this by putting a limit on the number of cycles that the MuParser will perform.
Another possible way to address this would be to implement a "cut" primitive or something similar in the MuGrammar. The idea is that if the parse of symbols to the right of a cut fails, the parser will not backtrack and trying alternatives to the left of the cut. If used appropriately, this avoids trying alternatives that we know (at the Syntax level) cannot succeed.
Yet another idea is to see if we can use / adapt "Parsing Expression Grammars" as described here.
- Login to post comments
#1