[Haskell-cafe] Hierachical abstraction

[Nils Anders Danielsson]

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:

  http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.html

-- 
/NAD