Dam ci ll dr

Próbuję użyć stanowego transformatora monadowego wScalaz 7 wątku dodatkowego stanu przez parser i mam problem z robieniem niczego użytecznego bez pisanialos zt m a -> t m b wersjem a -> m b metody.

Przykładowy problem z analizą

Załóżmy, że mam ciąg zawierający zagnieżdżone nawiasy z cyframi w nich:

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

Mam też strumień nowych nazw zmiennych (w tym przypadku znaków):

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

Chcę pobrać nazwę z górnej części strumienia i przypisać ją do każdego wyrażenia w nawiasie, gdy ją analizuję, a następnie odwzorować tę nazwę na ciąg reprezentujący zawartość nawiasów, z zagnieżdżonymi wyrażeniami w nawiasach (jeśli istnieją) zastąpionymi przez ich imiona.

Aby uczynić to bardziej konkretnym, oto, jak chciałbym, aby wyjście wyglądało tak, jak w powyższym przykładzie:

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

Na danym poziomie może występować ciąg cyfr lub dowolnie wiele podwyrażeń, ale te dwa rodzaje treści nie będą mieszane w jednym wyrażeniu w nawiasie.

Aby zachować prostotę, przyjmiemy, że strumień nazw nigdy nie będzie zawierał ani duplikatów, ani cyfr, i że zawsze będzie zawierał wystarczającą liczbę nazw dla naszych danych wejściowych.

Używanie kombinatorów parsera z nieco zmiennym stanem

Powyższy przykład jest nieco uproszczoną wersją problemu parsowania wto pytanie o przepełnienie stosu. jaodpowiedział na to pytanie z rozwiązaniem, które wyglądało mniej więcej tak:

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

Nie jest tak źle, ale wolałbym unikać zmiennego stanu.

Czego chcę

HaskellaParsec biblioteka sprawia, że ​​dodawanie stanu użytkownika do parsera jest trywialnie proste:

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

Jest to dość proste tłumaczenie mojego parsera Scala powyżej, ale bez stanu zmiennego.

Co próbowałem

Staram się zbliżyć do rozwiązania Parsec, ponieważ mogę użyć transformatora monadowego Scalaza, więc zamiastParser[A] Pracuję zStateT[Parser, Stream[Char], A]. Mam „rozwiązanie”, które pozwala mi napisać:

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

Działa to i nie jest mniej zwięzłe niż wersja ze zmiennym stanem lub wersja Parsec.

Ale mójExtraStateParsers jest brzydki jak grzech - nie chcę więcej próbować cierpliwości niż ja, więc nie włączę go tutaj (chociażoto link, jeśli naprawdę tego chcesz). Musiałem pisać nowe wersje każdegoParser iParsers metody używam powyżej dla mojejExtraStateParsers iESP typy (rep1, ~>, <~, i|, w przypadku, gdy liczysz). Gdybym potrzebował użyć innych kombinatorów, musiałbym również napisać ich nowe wersje na poziomie transformatorów państwowych.

Czy jest na to czystszy sposób? Chciałbym zobaczyć przykład monadowego transformatora stanu Scalaz 7, który był używany do tworzenia wątków za pomocą parsera, ale przykłady Scalaz 6 lub Haskell byłyby również przydatne i doceniane.