Creating a recursive data structure using parser combinators in scala

Question

I start working at scala, working on S99 to learn scala. One problem is converting from a string to a tree data structure. I can do it "manually", I also want to see how to do it using the Scala combiner library.

Tree data structure

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

And the input should be a string, for example: a(b(d,e),c(,f(g,)))

I can parse the string using something like

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

But how can I use the parsing library to build a tree? I know that I can use ^^ to convert, for example, some string to an integer. My confusion arises from the need to “know” the left and right subtrees when creating an instance of Node . How can I do this, or is it a sign that I want to do something else?

I better take what the parser returns ( (((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) for the example above), and create a tree on it rather than using parsers like ^^ or ^^^ to directly build a tree

Answer 1

This can be done with ^^ , and you're close enough:

 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 } 

And now:

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

In my opinion, the easiest way to approach this problem is to type the parser methods with the desired results, and then add the appropriate matching operations with ^^ until the compiler is happy.