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

Question

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

scalaparsingfunctional-programmingparser-combinators

4

我尝试使用Scala的Packrat解析器（scala-parser-combinators）将布尔表达式解析成Expr树。

  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会尝试所有四个选项：and/or/parensExpr将失败，但term将只需使用Term("aaa")就能成功。

然后，root的phrase会启动并检查是否还有剩余输入需要消耗，但会失败，因为有：" and 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定义不应该是等价的吗？这些解析器不具有引用透明性吗？

更重要的是，我该如何修复这个问题？

- dcastro

虽然不熟悉Packrat，但Scala有一个非常棒的解析库fastparse，其语法类似。如果重构工作量不大，请尝试使用它。它有更好的文档，可能会为您节省一些麻烦。顺便说一句，这个问题可以在那里得到解决。 - lprakashv

1

@lprakashv 当我开始尝试实现这个时，我实际上正在使用fastparse，但后来意识到fastparse不适用于这些语法。我需要语法是左结合的（即x and y and z应被解析为(x and y) and z而不是x and (y and z)），而fastparse在左递归语法上无限递归，并且溢出堆栈。另一方面，Packrat解析器使用记忆化来避免堆栈溢出，并且非常适合左递归语法。 - dcastro

2

这里有一个和我一样遇到 fastparse->packrat 解析器问题的人：https://users.scala-lang.org/t/with-input-from-string/4737/20 - dcastro

我认为左递归语法可以通过一系列步骤进行转换以消除左递归，但我也不确定如何做:/ - dcastro

这是一个消除左递归的逐步算法：https://en.wikipedia.org/wiki/Left_recursion#Removing_left_recursion 注意：在您的情况下，这可能会导致树结构稍微难看一些（因为您提到了左相关性）。 - Bengt

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lprakashv · 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`

可能是库版本问题？