Correspondence between type classes and grammar levels in the Chomsky hierarchy

Question

My question is about the Applicative and Monad type classes on the one hand, and the context-free and context-sensitive grammar levels of the Chomsky hierarchy on the other.

I've heard that there's a correspondence between the type classes and the grammar levels. How exact is this correspondence?

That is, can all context-free grammars be parsed using nothing stronger than Applicative combinators, and do are all grammars that can be parsed using nothing stronger than Applicative combinators context-free? In other words, does the Applicative type class exactly correspond to context-free grammars?

And the same question, except with 'context-free' substituted by 'context-sensitive' and Applicative by Monad.

---

Bounty clarification: do type class(es) correspond to grammar levels? For example, is there a set of type classes which provide all the operations required for expression regular languages and nothing more?

The motivation for the question is that I was working on a parser, and wanted to determine which grammar level my implementation was at based on the combinators I used. Is this possible?

Answer 1

I don't think anyone has shown this formally. The reason is that neither applicative nor monad is able to parse much of anything on its own. Rather, you also need

1. Choice (MonadPlus, Alternative)
2. Recursion

that said, with (non deterministic) choice and (arbitrary) recursion, Applicative parsers essentially exactly match the interface for BNF (and so can parse all CFLs), while monads can provide arbitrary context sensitive operations.