Tworzenie rekurencyjnej struktury danych za pomocą kombinatorów parsera w scala

Question

Jestem początkujący w scala, pracując nad S99, aby spróbować nauczyć się scala. Jednym z problemów jest konwersja z ciągu znaków na strukturę danych drzewa. Mogę to zrobić "ręcznie", a także chcę zobaczyć, jak to zrobić za pomocą biblioteki kombinatorów parsera Scali.

Struktura danych dla drzewa jest

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 wejście ma być ciągiem znaków, tak: a(b(d,e),c(,f(g,)))

mogę analizować ciąg przy użyciu coś jak

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

Ale jak mogę użyć biblioteki parsowania do zbudowania drzewa? Wiem, że mogę użyć ^^ do konwersji, na przykład, jakiegoś ciągu na liczbę całkowitą. Moje zamieszanie wynika z potrzeby "poznania" lewego i prawego poddrzewki podczas tworzenia instancji Node. Jak mogę to zrobić, czy jest to znak, że chcę zrobić coś innego?

jestem lepiej biorąc rzecz powraca parsera ((((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) na przykład wejście powyżej) i budowanie w oparciu o drzewo, że zamiast używać operatorów parsera jak ^^ lub ^^^ zbudować drzewo bezpośrednio?

Answer 1

Jest możliwe, aby to zrobić czysto z ^^, i jesteś dość blisko:

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 
} 

a teraz:

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

moim zdaniem najłatwiejszy sposób podejścia do tego rodzaju problemu jest wpisanie metod analizatora składni z żądanymi wynikami, a następnie dodanie odpowiednich operacji odwzorowania z ^^, dopóki kompilator nie będzie zadowolony.