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.

I often use parser combinator libraries, but I've never written one. What are good resources for getting started? In case it matters, I'm using Julia, a functional (but not lazy) language.

share|improve this question

closed as not constructive by gnat, Martijn Pieters, MichaelT, Dynamic, Kilian Foth May 17 '13 at 6:35

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

    
How about basing the design off one of the libraries you've used? –  ChaosPandion Apr 16 '13 at 20:28
    
You do not need any laziness for a combinator library. –  SK-logic Apr 17 '13 at 9:10
    
Yeah, this actually ended up being much easier than I thought. –  dan Apr 17 '13 at 15:56
    
"What are good resources..." -- resource requests are not quite welcome at Programmers. As far as I understand, one would rather present an underlying problem instead - a problem that was intended to be solved with particular resource requested –  gnat May 16 '13 at 21:32

2 Answers 2

This one is in Haskell (which is Lazy), but has some nice ideas:

http://eprints.nottingham.ac.uk/237/1/monparsing.pdf

The Boost.Spirit website has very nice ideas about implementing parser combinators too. Boost.Spirit uses Boost.Phoenix extensively, which is a library of lazy containers (so it's effectively lazy code too):

http://boost-spirit.com/home/

share|improve this answer

I was working on a simple parser combinator library in C++. I think the following functions are all you really need as a foundation for a library. I couldn't quickly tell if Julia has anything like generics but it will be very helpful if it does.

template<typename R, typename U>
auto Zero() -> ParserType(R, U)
{
    return [] (State<U> state) -> Result<R>
    {
        return Result<R>();
    };
}

template<typename R, typename U>
auto Return(R value) -> ParserType(R, U)
{
    return [value] (State<U> state) -> Result<R>
    {
        return Result<R>(value);
    };
}

template<typename R1, typename R2, typename U>
auto Bind(
    function<Result<R1>(State<U>)> parser,
    function<function<Result<R2>(State<U>)>(R1)> continuation
    ) -> ParserType(R2, U)
{
    return [parser, continuation] (State<U> state) -> Result<R2>
    {
        auto r = parser(state);
        if (r.Code == ResultCode::Failure)
            return Result<R2>();
        return continuation(r.Value)(state);
    };
}
share|improve this answer

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