7

マッピングによってこれらの値に依存するパーサーのリストを作成できる値のリストがあります（例を参照）。次に、パーサーのリストを連結によって単一のパーサーに変換します。

1つの可能性はとを使用することfoldLeftです~：

parsers.foldLeft(success(Nil)){case (ps,p) => rs ~ p ^^ {case xs ~ x => x ::xs}} ^^ (_.reverse)

これは効率的ですか？

コンビネーターパーサーがどのように機能するかわかりません。リストの長さの深さのコールスタックはありますか？したがって、非常に長い連結でSOエラーが発生する可能性がありますか？

もっといい方法

より読みやすい別の方法はありますか？

例

2行のファイルがあるとします。最初の行には、x_1からx_nまでのn個の整数が含まれています。2行目には、1行目のグループに属するx_1 + x_2 +...x_n整数が含まれています。最初の行から整数のシーケンスを取得し、n個のパーサーp_1からp_nを作成します。ここで、p_iはx_i整数を解析します。

l = List(1,2,3)最初の行の整数のリストがあるとします。整数ごとに、整数nを解析するパーサーを作成しnますparsers = l.map(repN(_,integer))。

4

2 に答える 2

7

あなたが記述しているもの (および and を使用して実装で多かれ少なかれ再発明したものfoldLeft)~は、基本的にはモナドの Haskell のsequenceものです (実際にはアプリケーション ファンクターのみが必要ですが、それはここでは関係ありません)。sequence単項値のリストを取り、値の単項リストを返します。Parserはモナドなので、sequenceforは aを a にParser変更します。List[Parser[A]]Parser[List[A]]

Scalazは を提供しますが、私の頭の中で、 に必要なインスタンスsequenceを取得する良い方法があるかどうかはわかりません。幸いなことに、非常に簡単に独自のロールを作成できます ( Haskell の定義を直接翻訳しています)。ApplicativeParser

import scala.util.parsing.combinator._

object parser extends RegexParsers {
  val integer = """\d+""".r

  val counts = List(1, 2, 3)
  val parsers = counts.map(repN(_, integer))

  val line = parsers.foldRight(success(Nil: List[List[String]])) {
    (m, n) => for { x <- m ; xs <- n } yield (x :: xs)
  }

  def apply(s: String) = parseAll(line, s)
}

これにより、必要に応じてList(List(1), List(2, 3), List(4, 5, 6))が得parser("1 2 3 4 5 6")られます。

(RegexParsersここでは便利な完全な例として使用していますが、このアプローチはより一般的に機能することに注意してください。)

理解を脱糖すると、何が起こっているのかが少し明確になるかもしれませんfor:

val line = parsers.foldRight(success(Nil: List[List[String]])) {
  (current, acc) => current.flatMap(x => acc.map(x :: _))
}

flatMap次のようにinto書くことができmapます^^：

val line = parsers.foldRight(success(Nil: List[List[String]])) {
  (current, acc) => current into (x => acc ^^ (x :: _))
}

これは、反転ではなく右折を使用していることと、~s を構築および分解していないことを除いて、あなたの定式化からそれほど離れていません。

効率性について: どちらの実装も不快なコール スタックが発生します。私の経験では、これは Scala のパーサー コンビネータを使用した場合の現実です。たとえば、別の Stack Overflow answerを引用するには:

Scala のパーサー コンビネーターはあまり効率的ではありません。彼らはそうなるように設計されていませんでした。比較的小さな入力で小さなタスクを実行するのに適しています。

私のsequence-y アプローチは、質問の「より読みやすい」部分に対処し、ほぼ間違いなく、Scala のパーサー コンビネーターで問題を解決する最もクリーンな方法です。実装よりもわずかに効率的であり、数千程度のグループには問題ありません。それ以上を処理する必要がある場合は、 の外を見る必要がありますscala.util.parsing.combinator。次のようなものをお勧めします。

def parse(counts: Seq[Int], input: String): Option[Seq[Seq[Int]]] = {
  val parsed = try {
    Some(input.split(" ").map(_.toInt))
  } catch {
    case _ : java.lang.NumberFormatException => None
  }

  parsed.flatMap { ints =>
    if (ints.length != counts.sum) None
    else Some(counts.foldLeft((Seq.empty[Seq[Int]], ints)) {
      case ((collected, remaining), count) => {
        val (m, n) = remaining.splitAt(count)
        (m.toSeq +: collected, n)
      }
    }._1.reverse)
  }
}

保証はありませんが、私のシステムでは、100k 整数グループの行でオーバーフローしません。

于 2011-10-15T20:17:38.333 に答える
1

RegexParsers(in )の使用を検討しましたscala.util.parsing.combinatorか? 次に、正規表現をパーサーとして使用できます。これは非常に高速に計算され、簡単に記述できます。

たとえば、パーサー コンビネーターを使用して AST を単純な算術演算用に解析している場合、正規表現を使用してオブジェクトを参照するトークンを解釈し、 のような式を解析できるようにすることができますappleList.size + 4。

これはかなり些細な例ですが、パーサー コンビネーターによって正規表現を組み合わせる方法を示しています。

object MyParser extends RegexParsers {
  val regex1 = """[abc]*""".r
  val regex2 = """[def]*""".r
  val parse = regex1 ~ regex2

  def apply(s: String) = parseAll(parse, s)
}
于 2011-10-09T18:06:42.677 に答える