parsimmon: p.or and p.alt wont backtrack
I’ve these two examples which fails
// Input
var input = "hello hello";
// Parser
var hello = p.string("hello");
var hellos = p.sepBy(hello, p.whitespace);
// Examples
console.info(p.alt(hello, hellos).parse(input));
console.info(hello.or(hellos).parse(input));
// Output
{ status: false,
index: { offset: 5, line: 1, column: 6 },
expected: [ 'EOF' ] }
{ status: false,
index: { offset: 5, line: 1, column: 6 },
expected: [ 'EOF' ] }
I was expecting both to try the first parser hello and on failure backtrack and continue with hellos. How come this isn’t possible and how would I solve this without having to reimplement the different parsers?
Real world use case: In my application I’ve have created different isolated parsers which initially overlap. Here is some example input (:highlights in vim):
var example1 = "SpellLocal xxx ctermbg=14 gui=undercurl"
var example2 = "rubyEval xxx links to Statement"
var example3 = "rubyKeywordAsMethod xxx cleared"
Each line represents a different parser, but happens to look the same in the beginning. Each example have it’s own parser. A line can only be mapped to one parser. I was hoping to do something like below as this would allow me keep the parsers independent.
var input = [example1, example2, example3].sample();
exampleParser1.or(exampleParser2).or(exampleParser3).parse(input)
About this issue
- Original URL
- State: closed
- Created 8 years ago
- Comments: 19 (3 by maintainers)
Alternation in parser combinators is not generally commutative - the only requirement is that it’s associative -
alt(a, alt(b, c)) == alt(alt(a, b), c), which it is in this case. Parsec’s alternation (the<|>operator, or thechoicefunction) is also not commutative.Just so you know,
x.or(y)is just defined asP.alt(x, y), so the results of those should never be different.The error in your parser is that you need to put the longer of two parsers first when they start with the same prefix.
The documentation gives an example of this limitation and how to work around it.