Передача дополнительного состояния через синтаксический анализатор в Scala

Я дам вам 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"
)

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

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

Использование комбинаторов синтаксического анализатора с немного изменяемым состоянием

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

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 выше, но без изменяемого состояния.

Что я пробовал

Я пытаюсь максимально приблизиться к решению Parsec, используя преобразователь монад состояний 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)
}

Это работает, и это не намного менее кратко, чем версия с изменяемым состоянием или версия Parsec.

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

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