FParsec backtracking in nested parser

Question

I want to parse expressions that are constructed like: a is x or y or z or b is z or w, so basically I have the same separator for different rules in my grammar.

I already succeed parsing such expressions with Antlr since it can backtrack quite nicely. But now I want to parse it with FParsec and I don't get the inner parser to not be greedy. My current parsers look like this:

let variable = // matches a,b,c,...

// variables ::= variable { "or" variable }+ ;
let variables =
    variable .>>? keyword "or" .>>.? (sepBy1 variable (keyword "or"))

let operation =
    variable .>>? keyword "is" .>>.? variables

// expression ::= operation { "or" operation }+ ;
let expression =
    operation .>>? keyword "or" .>>.? (sepBy1 variable (keyword "or"))

In my example the variables parser consumes x or y or z or b and the whole thing fails at is. This means I need to make that variables parser less greedy or make it backtrack correctly.

I found a similar question where they make a backtracking version of sepBy1, but using that still does not solve my problem. I guess that is because I want to backtrack into a nested parser.

So what is the correct way to make FParsec accept my input?

I feel like the root cause of your issue is that the keyword or has two different meanings. If I'm parsing your example expression correctly, you want it to parse like (a is (x or y or z)) or (b is (z or w)), right? So the same keyword or means "Alternatives for a single is match" and also means "Either of these expressions could be true". If you switched your "Alternatives for a single is match" to be something else, like | for example, then you might have less difficulty. I've also come up with another idea, which I'll write in an answer since it's rather long. — rmunn

rmunn rmunn · Accepted Answer · 2018-06-29T02:17:49

Besides switching one of the meanings of or to | as I mentioned in a comment, you could also use notFollowedBy (keyword "is") as follows:

let variables =
    variable .>>? keyword "or" .>>.? (sepBy1 (variable .>> (notFollowedBy (keyword "is"))) (keyword "or"))

I'm not really enthusiastic about this solution because it doesn't generalize easily. Are there other keywords besides is that could appear after a variable? E.g., do you have a syntax like b matches x or y, or anything similar? If so, then you'd need to write something like (notFollowedBy ((keyword "is") <|> (keyword "matches"))) and it can quickly get complicated. But as long as the keyword is is the only one that is throwing off your parser, using (notFollowedBy (keyword "is")) is probably your best bet.

FParsec backtracking in nested parser

1 Answers