Creating a recursive data structure using parser combinators in scala

Question

I'm a beginner in scala, working on S99 to try to learn scala. One of the problems involves converting from a string to a tree data structure. I can do it "manually", by I also want to see how to do it using Scala's parser combinator library.

The data structure for the tree is

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 is supposed to be a string, like this: 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 the tree? I know that I can use ^^ to convert, for example, some string into an integer. My confusing comes from needed to 'know' the left and the right subtrees when creating an instance of Node. How can I do that, or is that a sign that I want to do something different?

Am I better off taking the thing the parser returns ((((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) for the example input above), and building the tree based on that, rather than use parser operators like ^^ or ^^^ to build the tree directly?

Twomey

Answer 1

It is possible to do this cleanly with ^^, and you're fairly close:

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 kind of problem is to type the parser methods with the results you want, and then add the appropriate mapping operations with ^^ until the compiler is happy.

Physiologist

Hah, I thought JavaTokenParsers was some Java library. You came up with a better answer once again! – Consultant

You're right about never having T(. .). I left off the "" => (_ => End) bit. I removed my answer for clarity. – Consultant

Thanks for both the answer and the meta-answer about how to solve this type of problem. Now, I need to re-read the chapter on parsers in "Programming in Scala" to see what else I missed. – Twomey