Scala The parser combinator did not back down, as I would have thought ...

Question

I looked at myself blindly at this issue, and I guess this is likely to be a real stupid question. But I have to learn my pride.

I have this combinatorial analyzer that does not back down as I thought. I reduce it to a small example without completely removing the context. It looks like the foobar examples are just harder to read. Here I go:

@RunWith(classOf[JUnitRunner]) class ParserBacktrackTest extends RegexParsers with Spec with ShouldMatchers { override def skipWhitespace = false lazy val optSpace = opt(whiteSpace) lazy val number = """\d+([\.]\d+)?""".r lazy val numWithOptSpace = number <~ optSpace private def litre = numWithOptSpace <~ ("litre" | "l") def volume = litre ^^ { case _ => "volume" } private def namedPieces = numWithOptSpace <~ ("pcs") ^^ { case _ => "explPcs" } private def implicitPieces = number ^^ { case _ => "implPcs" } protected def unitAmount = namedPieces | implicitPieces def nameOfIngredient = ".*".r def amount = volume | unitAmount // def amount = unitAmount protected def ingredient = (amount <~ whiteSpace) ~ nameOfIngredient describe("IngredientParser") { it("should parse volume") { shouldParse("1 litre lime") } it("should parse explicit pieces") { shouldParse("1 pcs lime") } it("should parse implicit pieces") { shouldParse("1 lime") } } def shouldParse(row: String) = { val result = parseAll(ingredient, row) result match { case Success(value, _) => println(value) case x => println(x) } result.successful should be(true) } } 

So what happens is that the third test fails:

 (volume~lime) (explPcs~lime) [1.4] failure: string matching regex `\s+' expected but `i' found 1 lime ^ 

So, it seems that the litre-parser consumed l, and then it failed when he could not find any place. But I would have thought that he would come back and try the next production rule. Obviously, the implicitPieces parser parses this line, because if I delete the previous volume analyzer (delete the comment), it will succeed

 (implPcs~litre lime) (explPcs~lime) (implPcs~lime) 

Why no amount backtracking? What? I do not understand?

Answer 1

He does not return, because for 1 lime

• ingredient starts with amount
• amount starts with volume
• volume starts with litre and
• litre successfully consumes 1 l 1 lime

So litre , volume and amount were successful! That is why then everything continues with the second part of the ingredient , namely whiteSpace .

NTN!

Answer 2

I just want to post a minimal example illustrating my misunderstanding. I thought this would be successful:

  def foo = "foo" | "fo" def obar = "obar" def foobar = foo ~ obar describe("foobar-parser") { it("should parse it") { shouldParseWith(foobar, "foobar") } } 

but rollback by | does not work. The disjunctive parser consumes "foo" and never returns it.

It must be normalized so that the disjunction is transferred to the upper level:

 def workingFooBar = ("foo" ~ obar) | ("fo" ~ obar)