通过Scala的解析器线程额外的状态(Threading extra state through a

我给你的文艺青年最爱的前面

我想使用的状态单子转换Scalaz 7通过一个分析器，线程额外的状态，我在做什么有用的东西，而无需编写了很多麻烦tma -> tmb版本的ma -> mb方法。

一个例子解析问题

假设我有一个包含与它们内部数字嵌套的括号的字符串：

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

我也有新鲜的变量名（字符，在这种情况下）流：

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

我想拉一个名字的料流的顶部，并将其分配给每个括号表达式作为我解析它，然后将该名称映射到表示括号中的内容的字符串，与嵌套括号表达式（如果有的话）所取代他们的名字。

为了使这更具体，这里有我想要的输出看起来像上面的例子中输入的内容：

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

有可能在给定的电平是A的位数的字符串或任意许多子表达式，但是这两种类型的内容将不会在一个单一的括号表达式混合。

为了简单起见，我们假设名称的流永远不会包含任何重复或数字，而且它总是包含我们的输入足够的名字。

使用解析器组合有位可变状态

上面的例子是解析问题的以稍微简化的版本这个堆栈溢出问题。我回答这个问题，有一个看起来大致是这样的解决方案：

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的秒差距库使得添加用户状态解析器很轻松：

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)))"

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

我已经试过

我试图得到尽可能接近秒差距的解决方案，我可以使用Scalaz的状态单子转换，所以不是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)
}

这工作，这是不是更简洁比任何可变状态版本或秒差距版本。

但我的ExtraStateParsers是丑陋的罪过，我不想尝试，比我已经有你的耐心多，所以我不会在这里包括它（尽管这里有一个链接，如果你真的想要的话）。我已经写的每一个新版本的Parser和Parsers方法上面我用我的ExtraStateParsers和ESP类型（ rep1 ， ~> ， <~和| ，如果你正在计算）。如果我需要使用其他组合程序，我不得不写他们的新的国家变压器级的版本。

是否有一个更清洁的方式做到这一点？我喜欢看到正在使用Scalaz 7的状态单子变压器的一个例子通过一个分析器，线程状态，但Scalaz 6或Haskell的例子也将是有用的和理解。

也许最普遍的解决办法是重写Scala的解析库，以适应一元计算，在解析（如你做部分），但是这将是一个相当艰苦的任务。

我建议使用一个解决方案ScalaZ的国家，每个我们的结果是不是类型的值Parse[X]但类型的值Parse[State[Stream[Char],X]]别名为ParserS[X] ）。所以整体的解析结果不是价值，而是一个单子状态值，然后在运行一些Stream[Char] 。这几乎是一个单子转换，但我们必须做手工升/ unlifting。这使得代码有点难看，因为我们需要有时举起值或使用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的秒差距采取了类似的做法，国家/单子是分析器内）。