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

Question

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?

score 3 · Accepted Answer · edited May 23 '17 at 10:24

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.

For the Scalaz example you provide, I get some compile errors. I am using Scala 2.11 and Scalaz 7.0.6. Only difference between yours and mine is that I am using a `class` instead of an `object`, not sure that should matter though? The compile errors I see are: — adamretter, Jun 21 '14 at 08:59
Error:(14, 71) Implicit not found: scalaz.Unapply[scalaz.Applicative, TestParser.this.Parser[T]]. Unable to unapply type `TestParser.this.Parser[T]` into a type constructor of kind `M[_]` that is classified by the type class `scalaz.Applicative`. Check that the type class is defined by compiling `implicitly[scalaz.Applicative[type constructor]]` and review the implicits in object Unapply, which only cover common type 'shapes.' def combine[T](parsers: List[Parser[T]]): Parser[List[T]] = parsers.sequenceU ^ — adamretter, Jun 21 '14 at 09:00
Error:(14, 71) not enough arguments for method sequenceU: (implicit G: scalaz.Unapply[scalaz.Applicative,TestParser.this.Parser[T]])G.M[List[G.A]]. Unspecified value parameter G. def combine[T](parsers: List[Parser[T]]): Parser[List[T]] = parsers.sequenceU ^ — adamretter, Jun 21 '14 at 09:01
The non-Scalaz one does seem to compile fine though, so I may well use that for now. Although the code-base is already using Scalaz in places, so I would be interested to get the Scalaz example you posted working too. — adamretter, Jun 21 '14 at 09:04
@adamretter: That error actually is because you're using a class instead of an object—see my update for a workaround. — Travis Brown, Jun 21 '14 at 13:54

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

1 Answers1