1
\$\begingroup\$

Yesterday, I decided to learn about scala's Parser-Combinator library. After a while, I was able to write a simple Tree parser and lexer which understands trees written like this:

a(b(c,d),e(,f))

The above tree is actually

    a
   / \
  b   e
 / \   \
c   d   f

Here is the code

trait TreeCommon { this: Parsers =>
    def node: Parser[NODE]
    def cleftBegin: Parser[TreeToken] = success(BEGIN_CH)
    def crightBegin: Parser[TreeToken] = success(SEP_CH)
    def cEnd: Parser[TreeToken] = success(END_CH)
}

/**
  * ==================================================================================
  *                                   Tree Lexer
  * ==================================================================================
  */

sealed trait TreeToken
case class NODE(value: String) extends TreeToken
case object BEGIN_CH extends TreeToken
case object SEP_CH extends TreeToken
case object END_CH extends TreeToken

object TreeLexer extends TreeCommon with RegexParsers {
    override def node: Parser[NODE] = "[^()]+?".r ^^ NODE
    override def cleftBegin: Parser[TreeToken] = "(" ^^ (_ => BEGIN_CH)
    override def crightBegin: Parser[TreeToken] = "," ^^ (_ => SEP_CH)
    override def cEnd: Parser[TreeToken] = ")" ^^ (_ => END_CH)

    /**
      * Repeatedly attempts to match any of the tokens listed. Match atleast one
      * @return The list of tokens found
      */
    def tokens: Parser[Seq[TreeToken]] = rep1(cleftBegin | crightBegin | cEnd | node)

    /**
      * The apply method allows us to create a list of tokens from a given string
      * @param tree The string to parse into tokens
      * @return A list of Treetoken
      */
    def apply(tree: String): Option[Seq[TreeToken]] = parseAll(tokens, tree) match {
        case Success(result, _) => Some(result)
        case NoSuccess(_, _) => None
    }
}

/**
  * ==================================================================================
  *                                   Tree Parser
  * ==================================================================================
  */
sealed trait TreeAST extends Positional
case class ROOT(value: String) extends TreeAST
case class JUSTLEFT(value: String, left: TreeAST) extends TreeAST
case class JUSTRIGHT(value: String, right: TreeAST) extends TreeAST
case class TREE(value: String, left: TreeAST, right: TreeAST) extends TreeAST

object TreeParser extends TreeCommon with Parsers {
    override type Elem = TreeToken
    override def node: Parser[NODE] = accept("node", { case n@NODE(_) => n })

    class TreeTokenReader(tokens: Seq[TreeToken]) extends Reader[TreeToken] {
        override def first: TreeToken = tokens.head
        override def rest: Reader[TreeToken] = new TreeTokenReader(tokens.tail)
        override def pos: Position = NoPosition
        override def atEnd: Boolean = tokens.isEmpty
    }

    def leftTree: Parser[TreeAST] = node ~ BEGIN_CH ~ treeLike ~ SEP_CH ~ END_CH ^^ {
        case NODE(value) ~ _ ~ tree ~ _ ~ _ => JUSTLEFT(value, tree)
    }

    def rightTree: Parser[TreeAST] = node ~ BEGIN_CH ~ SEP_CH ~ treeLike ~ END_CH ^^ {
        case NODE(value) ~ _ ~ _ ~ tree ~ _ => JUSTRIGHT(value, tree)
    }

    def treeLike: Parser[TreeAST] = leftTree | rightTree |
      (node ~ opt(BEGIN_CH ~ treeLike ~ SEP_CH ~ treeLike ~ END_CH)) ^^ {
          case NODE(value: String) ~ None => ROOT(value)
          case NODE(value) ~ Some(_ ~ left ~ _ ~ right ~ _) => TREE(value, left, right)
    }

    def apply(tokens: Seq[TreeToken]): Option[TreeAST] = {
        val reader = new TreeTokenReader(tokens)
        treeLike(reader) match {
            case Success(result, _) => Some(result)
            case NoSuccess(msg, _) => println(msg); None
        }
    }
}


/**
  * ==================================================================================
  *                                   Tree Compiler!
  * ==================================================================================
  */
object TreeCompiler {
    def apply(tree: String): Option[Tree[String]] = TreeLexer(tree).flatMap {
        tokens => TreeParser(tokens).map(unfurl)
    }

    private def unfurl(ast: TreeAST): Tree[String] = ast match {
        case JUSTLEFT(value, left) => TreeBranch(value, unfurl(left), TreeEmpty)
        case JUSTRIGHT(value, right) => TreeBranch(value, unfurl(right), TreeEmpty)
        case ROOT(value) => TreeLeaf(value)
        case TREE(value, left, right) => TreeBranch(value, unfurl(left), unfurl(right))
    }
}

A brief guide to help the reader,

a ~ b simply means to match the token represented by a followed by the token b

a | b means to match the a or b which ever matches first

a ^^ {} means to match a and return the extracted match via a function

So this nice, but I have encountered a problem. Today I want to support trees in this form Branch (a, Branch (b, Leaf(c), Leaf (d)), Branch (e, Empty, Leaf(f))).

This is pretty much the same as the above, but this time a slightly different syntax. I proceeded as usual like so:

object TreeLexer2 extends TreeCommon with RegexParsers {
    override def node: Parser[NODE] = "(?:Branch|Leaf)".r ~ "(" ~ "[^(),]+?".r ^^ {
        case _ ~ _ ~ value => NODE(value)
    }
    override def cleftBegin: Parser[TreeToken] = "," ^^ (_ => SEP_CH)
    override def crightBegin: Parser[TreeToken] = "," ^^ (_ => SEP_CH)
    override def cEnd: Parser[TreeToken] = ")" ^^ (_ => END_CH)
}

Now here is where I got stuck because this new syntax introduces the idea of Empty which is used to indicate that one of a branch's children is empty. I don't want to have to redesign my original parser, and instead would like to reuse the original one.

So first I ask that you guys look over my code and make any suggestions or improvements. Secondly, I would like to suggestions on how to either change the second syntax or to redesign any part of the code to be able to accommodate the new syntax.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.