我会给你前面的 tl;dr
我正在尝试在 Scalaz 7 中使用状态单子(monad)变压器通过解析器线程化额外的状态,如果不编写大量 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"
)
在给定的级别上,可能存在一串数字或任意多个子表达式,但这两种内容不会混合在一个括号表达式中。
为简单起见,我们假设名称流永远不会
包含重复项或数字,并且它将始终包含足够的
我们输入的名称。
使用带有一些可变状态的解析器组合器
上面的例子是解析问题的一个稍微简化的版本
this Stack Overflow question .
我 answered that 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 的 state monad 转换器尽可能接近 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
丑得像罪——我不想比我已经拥有的更多地尝试你的耐心,所以我不会把它包括在这里(尽管 here's a link ,如果你真的想要的话)。我不得不为每个 Parser
编写新版本和 Parsers
我上面使用的方法对于我的
ExtraStateParsers
和 ESP
类型( rep1
、 ~>
、 <~
和 |
,以防您计算)。如果我需要使用其他组合器,我也必须编写它们的新状态转换器级版本。有没有更清洁的方法来做到这一点?我很想看到一个 Scalaz 7 的状态 monad 转换器用于通过解析器线程化状态的示例,但 Scalaz 6 或 Haskell 示例也将很有用和赞赏。
最佳答案
可能最通用的解决方案是重写 Scala 的解析器库以在解析时适应一元计算(就像您部分所做的那样),但这将是一项相当费力的任务。
我建议使用 ScalaZ 的解决方案的State我们的每个结果都不是 Parse[X]
类型的值, 但类型为 Parse[State[Stream[Char],X]]
的值(别名为 ParserS[X]
)。所以整体解析结果不是一个值,而是一个单子(monad)状态值,然后在一些 Stream[Char]
上运行.这几乎是一个单子(monad)变压器,但我们必须手动进行提升/卸载。它使代码有点难看,因为我们有时需要提升值或使用 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 采用类似的方法,状态/单子(monad)在解析器内部)。
关于scala - 通过 Scala 中的解析器线程化额外状态,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12487827/