Scala parser combinator with recursive structures

Question

I'm a beginner with Scala, and now learning Scala parser combinator, writing "MiniLogicParser", a mini parser for propositional logic formula. I am successful for parsing it partly, but can not convert to case class. I tried some codes like below.

import java.io._
import scala.util.parsing.combinator._

sealed trait Bool[+A]
case object True extends Bool[Nothing]
case class Var[A](label: A) extends Bool[A]
case class Not[A](child: Bool[A]) extends Bool[A]
case class And[A](children: List[Bool[A]]) extends Bool[A]

object LogicParser extends RegexParsers {
  override def skipWhitespace = true

  def formula = ( TRUE | not | and | textdata )
  def TRUE  = "TRUE"
  def not : Parser[_] = NEG ~ formula  ^^ {case ( "!"  ~ formula) => Not(formula)}
  def and : Parser[_] = LPARENTHESIS ~ formula ~ opt(CONJUNCT ~ formula) ~ RPARENTHESIS
  def NEG = "!"
  def CONJUNCT = "&&"
  def LPARENTHESIS = '('
  def RPARENTHESIS = ')'
  def textdata = "[a-zA-Z0-9]+".r

  def apply(input: String): Either[String, Any] = parseAll(formula, input) match {
      case Success(logicData, next)        => Right(logicData)
      case NoSuccess(errorMessage, next) => Left(s"$errorMessage on line ${next.pos.line} on column ${next.pos.column}")
    }
}

but, the compilation failed with the following error message

[error] ... MiniLogicParser.scala:15 type mismatch;  
[error]  found : Any 
[error]  required: Bool[?]  
[error]  def not : Parser[_] = NEG ~ formula  ^^ {case ( "!"  ~ formula) => Not(formula)}

I can partly understand the error message; i.e., it means for line 15 where I tried to convert the result of parsing to case class, type mismatch is occurring. However, I do not understand how to fix this error.

vvg · Accepted Answer · 2016-05-05 10:24:51Z

I've adapted your parser a little bit.

import scala.util.parsing.combinator._
sealed trait Bool[+A]
case object True extends Bool[Nothing]
case class Var[A](label: A) extends Bool[A]
case class Not[A](child: Bool[A]) extends Bool[A]
case class And[A](l: Bool[A], r: Bool[A]) extends Bool[A]


object LogicParser extends RegexParsers with App {
  override def skipWhitespace = true

  def NEG = "!"
  def CONJUNCT = "&&"
  def LP = '('
  def RP = ')'

  def TRUE = literal("TRUE") ^^ { case _ => True }
  def textdata = "[a-zA-Z0-9]+".r ^^ { case x => Var(x) }

  def formula: Parser[Bool[_]] = textdata | and | not | TRUE
  def not = NEG ~ formula ^^ { case n ~ f => Not(f) }
  def and = LP ~> formula ~ CONJUNCT ~ formula <~ RP ^^ { case f1 ~ c ~ f2 => And(f1, f2) }

  def apply(input: String): Either[String, Any] = parseAll(formula, input) match {
    case Success(logicData, next) => Right(logicData)
    case NoSuccess(errorMessage, next) => Left(s"$errorMessage on line ${next.pos.line} on column ${next.pos.column}")
  }

  println(apply("TRUE"))            // Right(Var(TRUE))
  println(apply("(A && B)"))        // Right(And(Var(A),Var(B)))
  println(apply("((A && B) && C)")) // Right(And(And(Var(A),Var(B)),Var(C)))
  println(apply("!(A && !B)"))      // Right(Not(And(Var(A),Not(Var(B)))))
}

Kulu Limpa · Accepted Answer · 2016-05-05 10:06:26Z

0

The child of the Not-node is of type Bool. In line 15 however, formula, the value that you want to pass to Not's apply method, is of type Any. You can restrict the extractor (i.e., the case-statement) to only match values of formula that are of type Bool by adding the type information after a colon:

case ( "!"  ~ (formula: Bool[_]))

Hence, the not method would look like this:

def not : Parser[_] = NEG ~ formula  ^^ {case ( "!"  ~ (formula: Bool[_])) => Not(formula)}

However, now, e.g., "!TRUE" does not match anymore, because "TRUE" is not yet of type Bool. This can be fixed by extending your parser to convert the string to a Bool, e.g.,

def TRUE  = "TRUE" ^^ (_ => True)

answered May 5, 2016 at 10:06

Kulu Limpa

3,5411 gold badge24 silver badges31 bronze badges

Collectives™ on Stack Overflow

Scala parser combinator with recursive structures

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related