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.htm... -- /NAD