Search code examples
scalagrammarbnfebnf

Grammars, Scala Parsing Combinators and Orderless Sets

I'm writing an application that will take in various "command" strings. I've been looking at the Scala combinator library to tokenize the commands. I find in a lot of cases I want to say: "These tokens are an orderless set, and so they can appear in any order, and some might not appear".

With my current knowledge of grammars I would have to define all combinations of sequences as such (pseudo grammar):

command = action~content
action = alphanum
content  = (tokenA~tokenB~tokenC | tokenB~tokenC~tokenA | tokenC~tokenB~tokenA ....... )

So my question is, considering tokenA-C are unique, is there a shorter way to define a set of any order using a grammar?

Solution

  • There are ways around it. Take a look at the parser here, for example. It accepts 4 pre-defined numbers, which may appear in any other, but must appear once, and only once.

    OTOH, you could write a combinator, if this pattern happens often:

    def comb3[A](a: Parser[A], b: Parser[A], c: Parser[A]) =
  a ~ b ~ c | a ~ c ~ b | b ~ a ~ c | b ~ c ~ a | c ~ a ~ b | c ~ b ~ a