SystemsBioinformatics / parcr

Construct parser combinators in R
Other
3 stars 0 forks source link

Parser `zero_or_one()` is not greedy #12

Closed douwe closed 6 months ago

douwe commented 6 months ago

Parser zero_or_one is not greedy, meaning that it sometimes does not parse input that it should be able to parse.

The reason for this bug is that zero_or_one(p) is defined as exactly(0,p) %or% exactly(1,p) which first tries to parse 0 times, and if it does, continues, even though it could have parsed once as well.

Example. We define a parser ABblock

ABblock <- function() {zero_or_one(literal("A")) %then% literal("B")}

and we apply this one or more times on the input c("A","B","B")

one_or_more(ABblock())(c("A","B","B"))

which leads to parse failure, whereas it should parse because we have: [one A then B] then [zero A then B]

douwe commented 6 months ago

This is resolved by defining zero_or_one as exactly(1,p) %or% exactly(0,p), i.e. by first testing whether p can parse once. Additionally, the example that fails has been added as a test in the package.