4

我一直盯着自己的这个问题看,我想这可能是一个非常愚蠢的问题。但我必须吞下我的骄傲。

我有这个组合器解析器,它不会像我想象的那样回溯。我一直在将其简化为一个小例子,而没有完全删除上下文。感觉像“foobar”-示例更难阅读。我来啦:

@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)
  }
}

那么第三次测试失败了:

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

1 lime
   ^

所以似乎litre-parser消耗了 l 然后它在找不到任何空间时失败了。但我原以为它会回溯并尝试下一个生产规则。显然implicitPieces解析器会解析这一行,因为如果我删除前面的卷解析器(删除注释),它会成功

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

为什么不amount回溯?我有什么误解?

4

2 回答 2

4

我只想发布一个最小的例子来说明我的误解。我认为这会成功:

  def foo = "foo" | "fo"
  def obar = "obar"

  def foobar = foo ~ obar

  describe("foobar-parser") {
    it("should parse it") {
      shouldParseWith(foobar, "foobar")
    }
  }

但是回溯|不是那样工作的。析取解析器将消耗“foo”并且永远不会将其返回。

必须对其进行归一化,以便将析取移到顶层:

def workingFooBar = ("foo" ~ obar) | ("fo" ~ obar)
于 2012-02-08T16:42:54.860 回答
2

它不会回溯,因为对于1 lime

  • ingredient开始于amount
  • amount以。。开始volume
  • volumelitre和开头
  • litre1 l成功消耗1 lime

所以litrevolume并且amount都成功了!这就是为什么整个事情继续进行第二部分ingredient,即whiteSpace

于 2012-02-08T11:52:16.360 回答