[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Hierachical abstraction

Subject: Re: [Haskell-cafe] Hierachical abstraction
From: Nils Anders Danielsson
Date: Fri, 29 Jan 2010 17:46:21 +0000
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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

<Prev in Thread] Current Thread [Next in Thread>