スカラーのパーサーコンビネーターを使用した再帰的なデータ構造の作成

Question

私はスカラーの初心者で、S99のスカラーを学ぼうとしています。問題の1つは、文字列からツリーデータ構造に変換することです。手動で行うこともできます。Scalaのパーサーコンビネータライブラリを使用してそれを行う方法も見たいと思っています。

ツリーのデータ構造は

sealed abstract class Tree[+T] 
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] { 
    override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")" 
} 
case object End extends Tree[Nothing] { 
    override def toString = "." 
} 
object Node { 
    def apply[T](value: T): Node[T] = Node(value, End, End) 
}  

され、入力は次のように、文字列であると考えられる。a(b(d,e),c(,f(g,)))

私は

trait Tree extends JavaTokenParsers{ 
    def leaf: Parser[Any] = ident 
    def child: Parser[Any] = node | leaf | "" 
    def node: Parser[Any] = ident~"("~child~","~child~")" | leaf 
} 

のようなものを使用して文字列を解析することができます

しかし、私はツリーを構築するために解析ライブラリを使うことができますか？私は^^を使用して、たとえば、いくつかの文字列を整数に変換できることを知っています。私の混乱は、Nodeのインスタンスを作成するときに左右のサブツリーを「知る」必要があるからです。どうすればいいのですか、それとも何か違うことをしたいという兆候でしょうか？

は、私はオフより良いものパーサ戻る（上の例入力用(((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~))）を取って、それに基づいてツリーを構築しています、直接ではなく、ツリーを構築するために^^または^^^のようなパーサの演算子を使用しますか？

Answer 1

^^できれいにこれを行うことが可能である、とあなたはかなり近いです：

object TreeParser extends JavaTokenParsers{ 
    def leaf: Parser[Node[String]] = ident ^^ (Node(_)) 
    def child: Parser[Tree[String]] = node | leaf | "" ^^ (_ => End) 
    def node: Parser[Tree[String]] = 
    ident ~ ("(" ~> child) ~ ("," ~> child <~ ")") ^^ { 
     case v ~ l ~ r => Node(v, l, r) 
    } | leaf 
} 

そして今：私の意見で

scala> TreeParser.parseAll(TreeParser.node, "a(b(d,e),c(,f(g,)))").get 
res0: Tree[String] = T(a T(b T(d . .) T(e . .)) T(c . T(f T(g . .) .))) 

この種の問題にアプローチする最も簡単な方法コンパイラが満足するまで、適切なマッピング操作を^^で追加します。