Подтвердить что ты не робот

Включение дополнительного состояния через парсер в 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 также будут полезны и оценены.

4b9b3361

ОТВЕТЫ

Ответ 1

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

Я предлагаю решение, используя ScalaZ State где каждый наш результат не является значением типа Parse[X], а значением типа Parse[State[Stream[Char],X]] (с псевдонимом ParserS[X]). Таким образом, общий анализируемый результат не является значением, а является значением монадического состояния, которое затем запускается на некотором Stream[Char]. Это почти монодальный трансформатор, но мы должны делать подъем/размыкание вручную. Это делает код немного уродливым, так как нам нужно иногда поднимать значения или использовать 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 `return` for States
  def toState[S,X](x: X): State[S,X] = gets(_ => x)

  // Haskell `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 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 использует аналогичный подход, состояние/монада находится внутри парсера).