Scala Packrat 解析器、错误消息和引用透明性

Question

我正在尝试将 bool 表达式解析为 Expr树使用来自 scala-parser-combinators 的 Scala 的 Packrat 解析器.

  sealed trait Expr
  case class Term(term: String) extends Expr
  case class And(x: Expr, y: Expr) extends Expr
  case class Or(x: Expr, y: Expr) extends Expr

aaa and bbb          --> And(Term(aaa),Term(bbb))
aaa and bbb or ccc   --> Or(And(Term(aaa),Term(bbb)),Term(ccc))
aaa and (bbb or ccc) --> And(Term(aaa),Or(Term(bbb),Term(ccc)))

这个语法似乎工作得很好:

object Parsing extends RegexParsers with PackratParsers {

  override val skipWhitespace = false

  val validIdentifiers = List("aaa", "bbb", "ccc", "ddd")

  lazy val term: PackratParser[Term] = """\s*""".r ~> """\w+""".r flatMap { identifier =>
    if (validIdentifiers.contains(identifier))
      success(Term(identifier))
    else
      err(s"expected one of: $validIdentifiers")
  }

  lazy val and: PackratParser[And] =
    expr ~ """\s+and\s+""".r ~ (term | parensExpr) ^^ { case e1 ~ _ ~ e2 => And(e1, e2) }

  lazy val or: PackratParser[Or] =
    expr ~ """\s+or\s+""".r ~ (term | parensExpr) ^^ { case e1 ~ _ ~ e2 => Or(e1, e2) }

  lazy val parensExpr: PackratParser[Expr] = """\s*\(""".r ~> expr <~ """\s*\)""".r

  lazy val expr: PackratParser[Expr] =
    term ||| and ||| or ||| parensExpr

  lazy val root: PackratParser[Expr] =
    phrase(expr)

  def parseExpr(input: String): ParseResult[Expr] =
    parse(root, new PackratReader(new CharSequenceReader(input)))
}

但错误信息有时.... 不好。
如果解析器在 and 的左侧发现无效标识符，它会正确地告诉我们。

println(parseExpr("invalidIdentifier and aaa"))


[1.18] error: expected one of: List(aaa, bbb, ccc, ddd)
invalidIdentifier and aaa
                 ^

但是如果它在 上发现一个无效的标识符右 -手边 and ，它会给我们这个误导性的错误信息。

println(parseExpr("aaa and invalidIdentifier"))

[1.4] failure: end of input expected
aaa and invalidIdentifier
   ^

我很确定这是因为 expr将尝试所有 4 个选项: and/ or/ parensExpr会失败，但是 term只需 Term("aaa") 即可成功.

然后， root的 phrase将启动并检查是否还有任何输入要消耗，并失败，因为有:“和 invalidIdentifier”。

所以我想，我会推 phrase低一级。换句话说，我改变了这个:

  lazy val expr: PackratParser[Expr] =
    term ||| and ||| or ||| parensExpr

  lazy val root: PackratParser[Expr] =
    phrase(expr)

进入这个:

  lazy val expr: PackratParser[Expr] =
    term ||| and ||| or ||| parensExpr

  lazy val root: PackratParser[Expr] =
    phrase(term) ||| phrase(and) ||| phrase(or) ||| phrase(parensExpr)

现在，所有 4 个选项都应该失败，但我们应该看到 and的错误消息，因为 and比其他 3 个选项消耗更多的输入

我现在收到了更好的错误消息，但令我惊讶的是，一些以前有效的输入现在无效!

println(parseExpr("aaa or bbb"))

[1.4] failure: string matching regex '\s+and\s+' expected but ' ' found
aaa or bbb
   ^

println(parseExpr("aaa and bbb or ccc"))

[1.12] failure: end of input expected
aaa and bbb or ccc
           ^

我不明白为什么。

事实上，即使只是一个更简单、微不足道的更改，例如:

  // before
  lazy val root: PackratParser[Expr] =
    phrase(expr)

  // after
  lazy val root: PackratParser[Expr] =
    phrase(term ||| and ||| or ||| parensExpr)

...打破以前有效的输入。

怎么来的？ root的这两个定义不应该吗？是等价的？这些解析器不是引用透明的吗？

更重要的是，我应该如何解决这个问题？

Answer 1

我在您发布的确切代码中遇到以下错误，我相信这些是预期的错误消息？:

@ println(Parsing.parseExpr("invalidIdentifier and aaa"))
[1.18] error: expected one of: List(aaa, bbb, ccc, ddd)

invalidIdentifier and aaa
                 ^


@ println(Parsing.parseExpr("aaa and invalidIdentifier"))
[1.26] error: expected one of: List(aaa, bbb, ccc, ddd)

aaa and invalidIdentifier
                         ^

我将 ammonite repl 与 ivy 导入的 Scala Parser Combinators 库一起使用:

import $ivy.`org.scala-lang.modules::scala-parser-combinators:1.1.2`

也许是库版本问题？