Is it possible to construct a parser combinator library that reads like a BNF grammar? I don't know of any, so I started wondering if there are reasons it's impossible or undesirable to do so. It seems to me it would be the best of both worlds.

Functional languages such as F# allow operator overloading. Is it just a matter of providing the right syntax, or is there more to it?

  • Take a look at Boost Spirit (boost-spirit.com), where something similar was done using C++ templates and operator overloading. Feb 16 '12 at 21:06
  • Have you had a look at AntlrWorks? Feb 16 '12 at 21:07
  • I haven't looked at Boost Spirit or AntlrWorks. Do they fit what I'm describing? I guess my question is: since BNF is more declarative and easier to read, if it's easy to make a parser combinator look like BNF, why don't more of them?
    – Daniel
    Feb 16 '12 at 21:34
  • Maybe because it isn't easy. Feb 16 '12 at 21:41
  • 1
    @RobertHarvey: That's what I'm asking: why aren't parser combinators built this way? If the answer is "because it's hard" I'd like to know why.
    – Daniel
    Feb 16 '12 at 21:53

The various versions of Parsec / AttoParsec, for the Haskell programming language, are pretty close: a Parsec parser definition looks almost like BNF, with a few minor differences (where BNF uses |, Parsec has <|>; BNF := is = in Parsec; Parsec adds error reporting and the try function for arbitrary look-ahead).

  • Yes, you could argue they look similar, but can equivalent parsers look the same in BNF and Parsec? I've yet to see a non-trivial example of such a thing.
    – Daniel
    Feb 16 '12 at 21:22
  • @Daniel: What problem are you trying to solve? Feb 16 '12 at 21:41
  • @RobertHarvey: None. I'm just curious.
    – Daniel
    Feb 16 '12 at 21:52
  • They won't look exactly the same - after all, we're still talking about a programming language that is bound to practical constraints. If you want exact BNF, IIRC there are parser generators that take BNF as input and produce parser source code.
    – tdammers
    Feb 17 '12 at 6:27

You should be looking at Scala's Parser combinator. It's built ground up to match BNF's syntax.

  • Is the syntax BNF-like, or can the same BNF grammar be represented similarly as a parser combinator? That's an important distinction, I think.
    – Daniel
    Feb 17 '12 at 15:32
  • It's BNF-like, sorry that might not help. It's pretty hard for a programming language to parse a space " " as a "followed by" token. Scala uses ~ instead of space. Feb 20 '12 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.