Parsing logical predicates

[Nikos Katzouris]

Hi, I'm trying to write a parser for logical predicates. I need to parse "flat" atoms, like p(x, y, 2), but also nested ones, like p(q(r(1,2),x),y). So far, I've written a parser in Parboiled2 that works with expressions like p(q(1,2,3),2,3), ("inner" function terms are flat), but I cannot get it to work with terms like p(q(r(1,2),2,3)) (where functions have arbitrary "depth"). So far that's what I have 

def LogicalAtom = FunctSymbol ~ "(" ~ PredicateInnerTerms ~ ")" ~ EOI ~> ( (x, y) => Atom(functor = x, terms = y.elems))

def PredicateInnerTerms = rule { oneOrMore(FunctionTerm | Var | Cons).separatedBy(",") ~> ( x => ExpressionList(x.toList) ) }

def FunctionTerm = rule { FunctSymbol ~ "(" ~ InnerTerms ~ ")" ~> ((x, y) => Atom(functor = x, terms = y.elems)) }

def InnerTerms = rule { oneOrMore(Var | Const).separatedBy(",") ~> ( x => ExpressionList(x.toList) ) }

def FunctSymbol = rule { capture(LowerCaseString) ~> ((x: String) => x) }

def Var = rule { capture(UpperCaseWord) ~> ((x: String) => Variable(x)) }

def Const = rule { capture(LowerCaseWord) ~> ((x: String) => Constant(x)) }

def LowerCaseWord = rule { CharPredicate.LowerAlpha ~ zeroOrMore(CharPredicate.AlphaNum | "_") }

def number = rule { oneOrMore(CharPredicate.Digit) }

def UpperCaseWord = rule { CharPredicate.UpperAlpha ~ zeroOrMore(CharPredicate.AlphaNum | "_") }

where Atom, ExpressionList, Variable, Constant are custom case classes. Naturally, this gets me to p(q(x,y),z), but not to p(q(r(x),y),z)

With parser combinators arbitrary logical expressions like the ones above can be parsed by:

def atom: Parser[LogicExpr] = funct ~ innerTerms 

def innerTerms: Parser[List[LogicExpr]] = "(" ~> repsep(term, ",") <~ ")"

def term: Parser[LogicExpr] = atom | variable | constant

def variable: Parser[LogicExpr] = upperCaseWord

def constant: Parser[LogicExpr] = lowerCaseWord

def funct: Parser[LogicExpr] = lowerCaseWord

(note that the definitions of atom and term "co-depend" on each other). Is there a similar way to define the grammar in Parboiled2? I tried a few things in a effort to introduce a similar co-definition of atom and term in Parboiled2, but I cannot even get them to compile...

Thank you

Best regards

Nikos 

[Mathias Doenitz]

Hi Nikos,

pb2 and parser combinators are similarly expressive and very close in the class of languages they can parse.
So, you should be able to translate a parser combinator grammar to pb2 without a lot of problems.

One thing you might want to do is attach type annotations to your (critical) rules.
This will greatly help with debugging.

> I tried a few things in a effort to introduce a similar co-definition of atom and term in Parboiled2, but I cannot even get them to compile...

If you show what errors you get we might be able to support you in debugging your code.

Cheers,
Mathias

---
mat...@parboiled.org
http://www.parboiled.org

> --
> You received this message because you are subscribed to the Google Groups "parboiled2.org User List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to parboiled-use...@googlegroups.com.
> Visit this group at https://groups.google.com/group/parboiled-user.
> To view this discussion on the web visit https://groups.google.com/d/msgid/parboiled-user/1dac6371-22a4-4231-9ff6-b7e3e541bbbc%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Nikos Katzouris]

Hi Mathias, thanks a lot for your answer. It turns out I made a stupid mistake somewhere that messed up the result type of a recursive type, hence the compilation error. It is all ok now. Thanks again

Best regards

Nikos