7

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?

Improve this question
5
  • Take a look at Boost Spirit (boost-spirit.com), where something similar was done using C++ templates and operator overloading.
    – kevin cline
    Feb 16, 2012 at 21:06
  • Have you had a look at AntlrWorks?
    – Robert Harvey
    Feb 16, 2012 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, 2012 at 21:34
  • Maybe because it isn't easy.
    – Robert Harvey
    Feb 16, 2012 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, 2012 at 21:53

2 Answers 2

Reset to default
4

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).

Improve this answer
4
  • 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, 2012 at 21:22
  • @Daniel: What problem are you trying to solve?
    – Robert Harvey
    Feb 16, 2012 at 21:41
  • @RobertHarvey: None. I'm just curious.
    – Daniel
    Feb 16, 2012 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, 2012 at 6:27
0

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

Improve this answer
2
  • 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, 2012 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.
    – Enrico Susatyo
    Feb 20, 2012 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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