I'll give you the tl;dr up front

Я пытаюсь использовать монадный преобразователь состояния вСкалаз 7 пропустить дополнительное состояние через анализатор, и у меня возникают проблемы с выполнением чего-либо полезного без написанияlot изt m a -> t m b версииm a -> m b методы.

An example parsing problem

Предположим, у меня есть строка, содержащая вложенные скобки с цифрами внутри:

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

У меня также есть поток свежих имен переменных (в данном случае символов):

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

Я хочу вытащить имя из верхней части потока и назначить его для каждой скобки выражение, как я анализирую его, а затем сопоставить это имя с строкой, представляющей содержимое скобок, с вложенными выражениями в скобках (если они есть), замененными их имена.

Чтобы сделать это более конкретным, вот то, что я хотел бы, чтобы выходные данные были похожи на приведенный выше пример ввода:

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

На данном уровне может быть либо строка цифр, либо произвольно много подвыражений, но эти два вида контента не будут смешиваться в одном выражении в скобках.

Для простоты мы предположим, что поток имен никогда не будет содержать или дубликаты или цифры, и что он всегда будет содержать достаточно имена для нашего ввода.

Using parser combinators with a bit of mutable state

Приведенный выше пример является несколько упрощенной версией проблемы синтаксического анализа в этот вопрос переполнения стека. I ответил на этот вопрос с решение, которое выглядело примерно так:

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

Это не так уж плохо, но я предпочитаю избегать изменчивого состояния.

What I want

Haskell & APOS; sпарсек библиотека делает добавить пользовательское состояние в синтаксический анализатор тривиально просто:

import Control.Applicative ((*>), (<
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)))"
gt;), (<*))
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 (,) []
     <
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)))"
gt; many1 digit
     <|> (\ps -> (map (fst . head) ps, concat ps))
     <
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)))"
gt; many1 paren

main = print $
  runParser (fromList <
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)))"
gt; paren) ['a'..'z'] "example" "((617)((0)(32)))"

Это довольно простой перевод моего парсера Scala выше, но без изменяемого состояния.

What I've tried

Я пытаюсь максимально приблизиться к решению Parsec, используя преобразователь монад состояния Scalaz, поэтому вместоParser[A] Я работаю сStateT[Parser, Stream[Char], A]. I have a "solution" that allows me to write the following:

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 а такжеParsers метод, который я использую выше для меняExtraStateParsers а такжеESP типы (rep1, ~>, <~, а также|в случае, если вы считаете). Если бы мне нужно было использовать другие комбинаторы, мне пришлось бы также написать их новые версии на уровне преобразователя состояния.

Есть ли более чистый способ сделать это? Я хотел бы видеть пример преобразователя монады состояний Scalaz 7, используемого для потоковой обработки состояния через анализатор, но примеры Scalaz 6 или Haskell также были бы полезны и оценены.