7

我有一个值列表，我可以从中构造一个解析器列表，这些解析器通过映射依赖于这些值（参见示例）。然后我想要做的是通过连接将解析器列表变成一个解析器。

一种可能性是使用foldLeftand ~：

parsers.foldLeft(success(Nil)){case (ps,p) => rs ~ p ^^ {case xs ~ x => x ::xs}} ^^ (_.reverse)

这有效率吗？

我不知道组合解析器是如何工作的；会有一个列表长度深度的调用堆栈吗？因此，我可能会在很长的连接中遇到 SO 错误吗？

更好的方法

有没有更易读的不同方式？

例子

假设您有一个包含两行的文件。第一行包含 n 个整数 x_1 到 x_n。第二行包含根据第一行属于组的 x_1 + x_2 + ... x_n 整数。我想从第一行获取整数序列并创建 n 个解析器 p_1 到 p_n，其中 p_i 解析 x_i 整数。

假设我有l = List(1,2,3)第一行的整数列表。对于每个整数n，我创建一个解析n整数的解析器：parsers = l.map(repN(_,integer)).

4

2 回答 2

7

您所描述的（以及您在实现中或多或少用foldLeftand重新发明的~内容）本质上是 Haskell 的sequence单子（实际上您只需要一个应用函子，但这在这里无关紧要）。sequence接受一元值列表并返回一元值列表。Parser是一个单子，所以sequenceforParser会将 a 更改List[Parser[A]]为 a Parser[List[A]]。

Scalaz给了你sequence，但我不知道是否有一个很好的方法来获取必要的Applicative实例Parser。幸运的是，你可以很容易地自己动手（我直接翻译Haskell 定义）：

import scala.util.parsing.combinator._

object parser extends RegexParsers {
  val integer = """\d+""".r

  val counts = List(1, 2, 3)
  val parsers = counts.map(repN(_, integer))

  val line = parsers.foldRight(success(Nil: List[List[String]])) {
    (m, n) => for { x <- m ; xs <- n } yield (x :: xs)
  }

  def apply(s: String) = parseAll(line, s)
}

这为我们List(List(1), List(2, 3), List(4, 5, 6))提供parser("1 2 3 4 5 6")了所需的 。

（请注意，我在RegexParsers这里使用的是一个方便的完整示例，但该方法更普遍。）

如果我们对for理解进行去糖处理，发生的事情可能会更清楚一些：

val line = parsers.foldRight(success(Nil: List[List[String]])) {
  (current, acc) => current.flatMap(x => acc.map(x :: _))
}

我们可以写flatMapasinto和mapas ^^：

val line = parsers.foldRight(success(Nil: List[List[String]])) {
  (current, acc) => current into (x => acc ^^ (x :: _))
}

这与您的公式相差不远，除了我们使用正确的折叠而不是反转并且没有建立和分解~s。

About efficiency: Both of our implementations are going to result in unpleasant call stacks. In my experience this is just a fact of life with Scala's parser combinators. To quote another Stack Overflow answer, for example:

Scala's parser combinators aren't very efficient. They weren't designed to be. They're good for doing small tasks with relatively small inputs.

我的sequence-y 方法解决了您问题的“更具可读性”部分，并且几乎可以肯定是使用 Scala 的解析器组合器解决问题的最干净的方法。它比您的实施效率略高，对于几千组左右应该没问题。如果你需要处理更多的事情，你将不得不在scala.util.parsing.combinator. 我会推荐如下内容：

def parse(counts: Seq[Int], input: String): Option[Seq[Seq[Int]]] = {
  val parsed = try {
    Some(input.split(" ").map(_.toInt))
  } catch {
    case _ : java.lang.NumberFormatException => None
  }

  parsed.flatMap { ints =>
    if (ints.length != counts.sum) None
    else Some(counts.foldLeft((Seq.empty[Seq[Int]], ints)) {
      case ((collected, remaining), count) => {
        val (m, n) = remaining.splitAt(count)
        (m.toSeq +: collected, n)
      }
    }._1.reverse)
  }
}

没有保证，但在我的系统上，它不会在具有 100k 个整数组的行上溢出。

于 2011-10-15T20:17:38.333 回答
1

您是否考虑过使用RegexParsers(in scala.util.parsing.combinator)？然后你可以使用正则表达式作为解析器，它的计算速度非常快，并且易于编写。

例如，如果您使用解析器组合器来解析 AST 以进行简单的算术运算，您可能会使用正则表达式来解释引用对象的标记，以便您可以解析诸如appleList.size + 4.

这是一个相当简单的示例，但它显示了解析器组合器如何组合正则表达式。

object MyParser extends RegexParsers {
  val regex1 = """[abc]*""".r
  val regex2 = """[def]*""".r
  val parse = regex1 ~ regex2

  def apply(s: String) = parseAll(parse, s)
}
于 2011-10-09T18:06:42.677 回答