Improving MuSyntax backtracking performance

Project:JNode Shell
Component:Code
Category:task
Priority:normal
Assigned:Stephen Crawley
Status:active
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.

#1

Title:Add support for 'cut' to the MuSyntax» Improving MuSyntax backtracking performance