26

我会给你前面的 tl;dr

我正在尝试使用Scalaz 7中的状态单子转换器通过解析器线程化额外的状态，并且在不编写大量方法t m a -> t m b版本的情况下做任何有用的事情时遇到了麻烦m a -> m b。

示例解析问题

假设我有一个包含嵌套括号的字符串，其中包含数字：

val input = "((617)((0)(32)))"

我还有一个新的变量名流（在这种情况下是字符）：

val names = Stream('a' to 'z': _*)

我想从流的顶部提取一个名称，并在解析它时将其分配给每个括号表达式，然后将该名称映射到表示括号内容的字符串，并将嵌套的括号表达式（如果有）替换为他们的名字。

为了使这一点更具体，这是我希望上面示例输入的输出看起来像的样子：

val target = Map(
  'a' -> "617",
  'b' -> "0",
  'c' -> "32",
  'd' -> "bc",
  'e' -> "ad"
)

在给定的级别上，可能存在一串数字或任意多个子表达式，但这两种内容不会混合在一个括号表达式中。

为简单起见，我们假设名称流永远不会包含重复项或数字，并且始终包含足够的名称供我们输入。

使用带有一些可变状态的解析器组合器

上面的例子是这个 Stack Overflow question中解析问题的一个稍微简化的版本 。我用一个大致如下的解决方案回答了这个问题：

import scala.util.parsing.combinator._

class ParenParser(names: Iterator[Char]) extends RegexParsers {
  def paren: Parser[List[(Char, String)]] = "(" ~> contents <~ ")" ^^ {
    case (s, m) => (names.next -> s) :: m
  }

  def contents: Parser[(String, List[(Char, String)])] = 
    "\\d+".r ^^ (_ -> Nil) | rep1(paren) ^^ (
      ps => ps.map(_.head._1).mkString -> ps.flatten
    )

  def parse(s: String) = parseAll(paren, s).map(_.toMap)
}

这还不错，但我更愿意避免可变状态。

我想要的是

Haskell 的Parsec库使将用户状态添加到解析器变得非常容易：

import Control.Applicative ((*>), (<$>), (<*))
import Data.Map (fromList)
import Text.Parsec

paren = do
  (s, m) <- char '(' *> contents <* char ')'
  h : t  <- getState
  putState t
  return $ (h, s) : m
  where
    contents
      =  flip (,) []
     <$> many1 digit
     <|> (\ps -> (map (fst . head) ps, concat ps))
     <$> many1 paren

main = print $
  runParser (fromList <$> paren) ['a'..'z'] "example" "((617)((0)(32)))"

这是我上面的 Scala 解析器的一个相当简单的翻译，但没有可变状态。

我试过的

我正在尝试使用 Scalaz 的状态单子转换器尽可能接近 Parsec 解决方案，所以Parser[A]我正在使用StateT[Parser, Stream[Char], A]. 我有一个“解决方案”，允许我编写以下内容：

import scala.util.parsing.combinator._
import scalaz._, Scalaz._

object ParenParser extends ExtraStateParsers[Stream[Char]] with RegexParsers {
  protected implicit def monadInstance = parserMonad(this)

  def paren: ESP[List[(Char, String)]] = 
    (lift("(" ) ~> contents <~ lift(")")).flatMap {
      case (s, m) => get.flatMap(
        names => put(names.tail).map(_ => (names.head -> s) :: m)
      )
    }

  def contents: ESP[(String, List[(Char, String)])] =
    lift("\\d+".r ^^ (_ -> Nil)) | rep1(paren).map(
      ps => ps.map(_.head._1).mkString -> ps.flatten
    )

  def parse(s: String, names: Stream[Char]) =
    parseAll(paren.eval(names), s).map(_.toMap)
}

这行得通，而且它并不比可变状态版本或 Parsec 版本简明多少。

但我ExtraStateParsers的丑陋如罪——我不想比我已经拥有的更多地尝试你的耐心，所以我不会在这里包含它（虽然这里有一个链接，如果你真的想要的话）。我必须为我的和类型（、、和，以防你计算）编写上面使用的每个Parser和方法的新版本。如果我需要使用其他组合器，我也必须编写它们的新状态转换器级版本。ParsersExtraStateParsersESPrep1~><~|

有没有更清洁的方法来做到这一点？我很想看到一个 Scalaz 7 的状态 monad 转换器用于通过解析器线程化状态的示例，但 Scalaz 6 或 Haskell 示例也将很有用和赞赏。

4

1 回答 1

11

可能最通用的解决方案是重写 Scala 的解析器库以在解析时适应单子计算（就像您部分所做的那样），但这将是一项相当费力的任务。

我建议使用ScalaZ的State的解决方案，其中我们的每个结果都不是 type 的值Parse[X]，而是 type 的值Parse[State[Stream[Char],X]]（别名为ParserS[X]）。所以整体解析结果不是一个值，而是一个单子状态值，然后在 some Stream[Char]. 这几乎是一个单子变压器，但我们必须手动进行提升/卸载。它使代码有点难看，因为我们有时需要提升值或在几个地方使用map/ flatMap，但我相信它仍然是合理的。

import scala.util.parsing.combinator._
import scalaz._
import Scalaz._
import Traverse._

object ParenParser extends RegexParsers with States {
  type S[X] = State[Stream[Char],X];
  type ParserS[X] = Parser[S[X]];


  // Haskell's `return` for States
  def toState[S,X](x: X): State[S,X] = gets(_ => x)

  // Haskell's `mapM` for State
  def mapM[S,X](l: List[State[S,X]]): State[S,List[X]] =
    l.traverse[({type L[Y] = State[S,Y]})#L,X](identity _);

  // .................................................

  // Read the next character from the stream inside the state
  // and update the state to the stream's tail.
  def next: S[Char] = state(s => (s.tail, s.head));


  def paren: ParserS[List[(Char, String)]] =
    "(" ~> contents <~ ")" ^^ (_ flatMap {
      case (s, m) => next map (v => (v -> s) :: m)
    })


  def contents: ParserS[(String, List[(Char, String)])] = digits | parens;
  def digits: ParserS[(String, List[(Char, String)])] =
    "\\d+".r ^^ (_ -> Nil) ^^ (toState _)
  def parens: ParserS[(String, List[(Char, String)])] =
    rep1(paren) ^^ (mapM _) ^^ (_.map(
        ps => ps.map(_.head._1).mkString -> ps.flatten
      ))


  def parse(s: String): ParseResult[S[Map[Char,String]]] =
    parseAll(paren, s).map(_.map(_.toMap))

  def parse(s: String, names: Stream[Char]): ParseResult[Map[Char,String]] =
    parse(s).map(_ ! names);
}

object ParenParserTest extends App {
  {
    println(ParenParser.parse("((617)((0)(32)))", Stream('a' to 'z': _*)));
  }
}

注意：我相信您的方法在StateT[Parser, Stream[Char], _]概念上并不正确。该类型表示我们正在构建一个给定状态（名称流）的解析器。因此，给定不同的流，我们可能会得到不同的解析器。这不是我们想要做的。我们只希望解析结果取决于名称，而不是整个解析器。这种方式Parser[State[Stream[Char],_]]似乎更合适（Haskell 的 Parsec 采用了类似的方法，state/monad 在解析器内部）。

于 2012-09-22T14:26:43.470 回答