Using a scala combinator to parse propositional logic

Question

I've been set a homework task for an assignment at university to use Scala combinators to parse propositional logic and I'm about to tear my hair out as I've been working on this for several hours and can't even get past the first stage.

The initial part is to build a recogniser that builds the recognition types (types are already provided separately) that conforms to the EBNF form given. ([] implies 0 or one, + implies one or more and * implies zero or more)

prop  ::=  equiv

equiv ::=  impl biArrow impl
                                   p <=> q   becomes  Equivalent (P, Q)
                                   p <+> q   becomes  Not (Equivalent (P, Q))
impl  ::=  disj [impls]
impls ::=  (rightArrow disj)+
                                   p => q    becomes  Implies (P, Q)
        |  (leftArrow disj)+
                                   p => q    becomes  Implies (Q, P)
disj ::=  conj (disjOp conj)*
                                   p | q    becomes  Or (P, Q)
conj ::=  neg (conjOp neg)
                                   p & q    becomes  And (P, Q)
neg  ::=  negs | pos
negs ::=  negOp neg
                                   ~ p      becomes  Not (P)
pos  ::=  ident | "(" prop ")"
                                   ident   becomes  Literal (true, ident)

The scala code we're given in the combinator provides a lazy defintion of prop that is an error. I've started filling in the classes to match the above code like so, but even if I implement it, I don't catch the correct errors, I think it is actually that I do not understand how you specify to catch a value on the parsers

trait PropRecognizer extends RegexParsers {

  val ident = """[a-zA-Z]\w*""".r

  val biArrow = "<=>" | "<+>"
  val rightArrow = "=>"
  val leftArrow = "<="
  val disjOp = "|"
  val conjOp = "&"
  val negOp = "~"
  lazy val pos = ident | "("~prop~")"
  lazy val negs: Parser[Any] = negOp~neg
  lazy val neg = negs | pos
  lazy val conj = neg~(conjOp~neg).* | neg
  lazy val disj = conj~(disjOp~conj).* | conj
  lazy val impls = (rightArrow~disj).+ | (leftArrow~disj).+ | disj
  lazy val impl = disj~impls.? | impls
  lazy val equiv = impl~biArrow~impl | impl
  lazy val prop: Parser[Any] = rep(equiv)
}

Any help, form a hint to a better outlining of the syntax would be of incredible help, I've been reading through the documentation and still cannot seem to have it click in my head. I understand this is a fairly easy problem to those who are used to propositional logic and parsers but I've been scratching my head for hours now and am getting close to just hacking my way through it bit by bit.

EDIT: UPDATE The syntax given was wrong by one item so I tweaked it, now works perfectly:

lazy val prop: Parser[Any] = rep(equiv)
lazy val equiv: Parser[Any] = impl~(biArrow~impl).?
  lazy val impl = disj~impls.?
  lazy val impls: Parser[Any] = (rightArrow~disj).+ | (leftArrow~disj).+
  lazy val disj = conj~(disjOp~conj).*
  lazy val conj: Parser[Any] = neg~(conjOp~neg).* 
  lazy val neg: Parser[Any] = negs | pos
  lazy val negs: Parser[Any] = negOp~neg 
  lazy val pos = ident | "("~prop~")" 

Answer 1

You need to convert the parsed expressions into the representation classes using the ^^ operator/method. For example:

lazy val conj: Parser[And] = neg~conjOp~neg ^^ {case p1~_~p2 => And(p1,p2)}

This assumes that neg is of type Parser[Proposition], which is a super class for representing any formula and And takes two propositions as arguments. You need to know that a Parser[T] will parse some input and return a value of type T as its result.

Also Parser is covariant, so you can use a Parser[And] where you require to parse any proposition.

Have a look at this example for a parser for propositional logic.