adamretter
adamretter

Reputation: 3517

What would be the function to dynamically combine Scala's parser combinators?

I am looking for a function to dynamically combine Scala Parser Combinators. For example, if I want to do it statically I can write:

def aDirective: Parser[String] = "a" ^^ { case _ => "a" }
def bDirective: Parser[String] = "b" ^^ { case _ => "b" }

def combinedDirective: Parser[List[String]] =
  aDirective ~ bDirective ^^ { case a ~ b => List(a, b) }

However rather than coding this statically I want to be able to do this dynamically, for the purposes of generating combinations of parsers.

For example:

def aDirective: Parser[String] = "a" ^^ { case _ => "a" }
def bDirective: Parser[String] = "b" ^^ { case _ => "b" }

def combinedDirective: Parser[List[String]] =
  combine(List(aDirective, bDirective))

def combine(parsers: List[Parser[T]): Parser[List[T]] = ???

I think I need to go from a List of parsers to a Parser of List of Results. So I have attempted to write a signature for a function named combine.

At the moment I cannot figure out how to implement the combine function. Whichever way I attempt it, it seems to be fraught with problems that I cannot think how to solve at the moment. For example how do I construct an initial parser for a fold? I have tried to experiment with various foldLeft and reduceLeft constructs, but cannot seem to quite get there.

I am using Scala 2.11. Any ideas?

Upvotes: 3

Views: 615

Answers (1)

Travis Brown
Travis Brown

Reputation: 139058

This is a sequencing operation, and Scalaz provides a shortcut (normally you wouldn't need the explicit instance definition boilerplate with Scalaz, but this is a special case):

import scala.util.parsing.combinator.RegexParsers
import scalaz._, Scalaz._

object MyParser extends RegexParsers {
  implicit val pm = std.util.parsing.combinator.parser.parserMonad(this)

  def aDirective: Parser[String] = "a" ^^ { case _ => "a" }
  def bDirective: Parser[String] = "b" ^^ { case _ => "b" }

  def combine[T](parsers: List[Parser[T]]): Parser[List[T]] = parsers.sequenceU

  def combinedDirective: Parser[List[String]] =
    combine(List(aDirective, bDirective))
}

And then:

scala> MyParser.parseAll(MyParser.combinedDirective, "ab")
res0: MyParser.ParseResult[List[String]] = [1.3] parsed: List(a, b)

You can also define it yourself with a fold:

import scala.util.parsing.combinator.RegexParsers

object MyParser extends RegexParsers {
  def aDirective: Parser[String] = "a" ^^ { case _ => "a" }
  def bDirective: Parser[String] = "b" ^^ { case _ => "b" }

  def combine[T](parsers: List[Parser[T]]): Parser[List[T]] =
    parsers.foldRight(success(List.empty[T])) {
      case (p, acc) => for {
        pRes   <- p
        accRes <- acc
      } yield pRes :: accRes
    }

  def combinedDirective: Parser[List[String]] =
    combine(List(aDirective, bDirective))
}

And it'll work exactly the same. The trick is just getting the base right—it needs to be a parser that always succeeds with the empty list as its value.


Update: if you're defining a class, not an object, the Scalaz approach above won't work (for a number of weird reasons—in short the this isn't stable enough). You can define your own monad instance pretty easily, though:

class MyParser extends RegexParsers {
  implicit val pm = new Monad[Parser] {
    def point[A](a: => A): Parser[A] = success(a)
    def bind[A, B](fa: Parser[A])(f: A => Parser[B]): Parser[B] = fa flatMap f
  }

  def aDirective: Parser[String] = "a" ^^ { case _ => "a" }
  def bDirective: Parser[String] = "b" ^^ { case _ => "b" }

  def combine[T](parsers: List[Parser[T]]): Parser[List[T]] = parsers.sequenceU

  def combinedDirective: Parser[List[String]] =
    combine(List(aDirective, bDirective))
}

You actually don't need a monad instance here to use sequence, just an applicative functor, but the definition is actually a little more convenient and the monad instance may be useful in other cases.

Upvotes: 3

Related Questions