26

前もって 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"
)

所定のレベルで、数字の文字列または任意の数の部分式のいずれかが存在する可能性がありますが、これら 2 種類のコンテンツが 1 つの括弧内の式に混在することはありません。

簡単にするために、名前のストリームには重複や数字が含まれることはなく、常に入力に十分な名前が含まれていると仮定します。

少し変更可能な状態でパーサーコンビネーターを使用する

上記の例は、この Stack Overflow 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 のステート モナド トランスフォーマーを使用して、可能な限り 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は罪のように醜いです—私はすでに持っている以上にあなたの忍耐を試したくないので、ここには含めません (ただし、本当に必要な場合はリンクがあります)。上記のand型 ( 、、、および、数えている場合は )に使用するすべてのParserandParsersメソッドの新しいバージョンを作成する必要がありました。他のコンビネータを使用する必要があった場合、それらの新しい状態トランスフォーマー レベルのバージョンも作成する必要がありました。ExtraStateParsersESPrep1~><~|

これを行うためのよりクリーンな方法はありますか？Scalaz 7 のステート モナド トランスフォーマーを使用してパーサーを介して状態をスレッド化する例を見たいと思っていますが、Scalaz 6 または Haskell の例も有用であり、高く評価されます。

4

1 に答える 1

11

おそらく最も一般的な解決策は、Scalaのパーサーライブラリを書き直して、構文解析中のモナディック計算に対応することです（部分的に行ったように）が、それは非常に骨の折れる作業です。

ScalaZのStateを使用した解決策を提案します。ここで、各結果はtypeの値ではなく、typeParse[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'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も同様のアプローチを取り、状態/モナドはパーサー内にあります）。

于 2012-09-22T14:26:43.470 に答える