[Haskell-cafe] Hierachical abstraction

Nils Anders Danielsson nad at Cs.Nott.AC.UK
Fri Jan 29 12:46:21 EST 2010

On 2010-01-29 01:09, Edward Kmett wrote:
> 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.

If you restrict the amount of coinduction that you allow, then you can
guarantee termination of parsing:



More information about the Haskell-Cafe mailing list