Parsing a string then converting to another format, in Scala

Question

I have a propositional formula, e.g., in this String format:

(~d \/ x) /\ (y \/ ~b) /\ (~y \/ a \/ b)

I wrote a parser like this:

import scala.util.parsing.combinator._

class CNFParser extends JavaTokenParsers with RegexParsers {
  def expr: Parser[Any] = term~rep("/\\"~term)
  def term: Parser[Any] = value~rep("\\/"~value)
  def value: Parser[Any] =  ident | "~"~ident | "("~expr~")"

}

object Test_02 extends CNFParser {
  def main(args: Array[String]): Unit = {

    println("input: " + "(~d \\/ x) /\\ (y \\/ ~b) /\\ (~y \\/ a \\/ b)")
    println(parseAll(expr, "(~d \\/ x) /\\ (y \\/ ~b) /\\ (~y \\/ a \\/ b)"))

  }
}

Well, the parsed output looks like:

[1.41] parsed: (((((~(((~~d)~List((\/~x)))~List()))~))~List())~List((/\~((((~((y~List((\/~(~~b))))~List()))~))~List())), (/\~((((~(((~~y)~List((\/~a), (\/~b)))~List()))~))~List()))))

I am trying several ways, by using the operations ^^, to get rid of these "extra" parentheses and stuff, but without success.

Actually, the result that I want to get is to convert the formula in a .dimacs format, where each letter/word is a number, the \/ operator becomes a space between the literals and the \/ becomes a newline (where a value 0 is inserted at the end of each line). Concretely, for my example here - if x = 1, y = 2, a = 3, b = 4, d = 5- then the resulting file must look like this:

c filename.cnf
p cnf 5 3
-5 1 0
2 -4 0
-2 3 4

Any hint how I can continue to achieve this is really welcomed! Thanks.

Alexey Romanov · Accepted Answer · 2017-02-20 11:03:51Z

1

You don't want to have Parser[Any]; instead, define a data type representing formulas:

sealed trait Formula
case class Variable(name: String) extends Formula {
  override def toString = name
}
case class And(left: Formula, right: Formula) {
  override def toString = s"($left /\ $right)"
}
// etc.

You can add any operations you end up needing to Formula (or to the companion object) as well.

Then define Parser[Formula] and work with Formulas, not with strings.

Formula is an example of an algebraic data type, and by searching for this term you can find a lot more information.

answered Feb 20, 2017 at 11:03

Alexey Romanov

172k38 gold badges329 silver badges509 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Parsing a string then converting to another format, in Scala

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related