Luke pretty much nailed the summary of what you can parse using Applicative means. I tend to consider them "codata CFGs", because they can have infinite breadth and depth. However, a 'codata CFG' can handle a much larger class of languages than CFGs. To that end, it is interesting to consider that to maximize the ability to successfully parse such degenerate grammars you are well served to use a traversal that can handle both of those cases. Such a traversal can be built out of Luke's Omega monad or a logic monad with fair conjunction/disjunction and provides a straightforward if inefficient 'top-down' parser.

http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html

On the other hand, I've had greater success by working with Applicatives to build a CFG with 'pure' nodes represented as epsilons, using evil StableName hackery to build bottom up parsers. Although, for that to work you basically need to give up the ability to encode arbitrary "codata CFGs" in order to let the grammar finish compiling. This limits my approach to handling true CFGs (or TIGs), with an extension that covers TAGs, but lets me build a much more efficient parser.

And yes, one of the major motivating ideas behind Arrows were the parsers of Swierstra and Duponcheel (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2446).

There are also compromise approaches. For instance Swierstra's uu-parsinglib internally uses both a monadic and applicative parser and a by virtue of a special bind operation that can glue them together yields a monad that can at least optimize the last run of applicative computations. 

http://www.cs.uu.nl/wiki/bin/view/HUT/ParserCombinators

-Edward Kmett

On Thu, Jan 28, 2010 at 6:22 PM, Sebastian Fischer <sebf@informatik.uni-kiel.de> wrote:
On Jan 28, 2010, at 9:31 PM, Luke Palmer wrote:
I don't remember the name, but there is a technique where you compose
the features you want and then take its fixed point to get your AST.
Did you think of "Data types à la carte" by Wouter Swierstra?
   http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf
 
You can make a typeclass for each feature that uses it on any data
structure in which it is present.

I don't fully understand this sentence but it reminds me of "Finally Tagless, Partially Evaluated" by Jacques Carette, Oleg Kiselyov and Chung-chieh Shan:
   http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf

Actually, it is quite the opposite of the Kiselyov Carette and Shan trick. interpreting an ADT is an initial algebraic construction, while the "Finally Tagless" is a final coalgebraic construction.

-Edward Kmett