Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
Take a look at Boost Spirit (boost-spirit.com), where something similar was done using C++ templates and operator overloading. –  kevin cline Feb 16 '12 at 21:06
    
Have you had a look at AntlrWorks? –  Robert Harvey 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. –  Robert Harvey 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
add comment

2 Answers

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

share|improve this answer
    
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? –  Robert Harvey 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
add comment

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

share|improve this answer
    
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. –  Enrico Susatyo Feb 20 '12 at 22:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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