Lambda the Ultimate

inactiveTopic Combinator Parsers
started 1/24/2001; 12:49:17 AM - last post 1/27/2001; 4:24:03 AM
andrew cooke - Combinator Parsers  blueArrow
1/24/2001; 12:49:17 AM (reads: 1501, responses: 2)
Combinator Parsers
The link above is an introduction to combinator parsers; there's also a broader introduction.

If you're used to yacc-like parser generators then these seem rather quaint at first - the idea is to build functions from the bottom up, with basic functions identifying tokens (say), and more complex functions constructing a parse tree. A good combinator parser framework separates this into elegant functional chunks with higher order functions to "compose" sub-functions and a neat separation between syntax and semantics (the <@ operator in the main link). Broadly, it's the same approach shown in many posts here (most recently the Prolog regexps).

This implementation (using streams rather than monads) looks pretty good and more are listed here.

Finally, an interesting extrapolation.

(Apologies to those that have seen some of these links on c.l.misc and a discussion post I made here recently).
Posted to "" by andrew cooke on 1/24/01; 12:52:30 AM

Ehud Lamm - Re: Combinator Parsers  blueArrow
1/26/2001; 8:18:12 AM (reads: 1555, responses: 0)
How is this different from recursive descent parsing?

andrew cooke - Re: Combinator Parsers  blueArrow
1/27/2001; 4:24:03 AM (reads: 1533, responses: 0)
It's the same thing, or rather (AFAIK), combinators are an approach to recursive descent parsing. See

I'm just learning all this, so my terminology isn't very good - my general comments above concern recursive descent parsing, but the links are to combinator-related work.