Chomsky階層のタイプクラスと文法レベルの対応

Question

私の質問は、一方ではApplicativeとMonadタイプのクラス、もう一方はChomsky階層の文脈自由文法と文脈依存文法のレベルです。

私は、タイプクラスと文法レベルの間には対応があると聞いています。この対応はどのくらい正確ですか？

つまり、すべての文脈自由文法は、Applicative combinatorsよりも強力なものを使用して解析することはできません。また、文脈自由なApplicative combinatorsより強力なものを使用して解析できる文法はすべてありますか？つまり、Applicative型クラスは文脈自由文法に完全に対応していますか？

「context-sensitive」と「Monad」によるApplicativeで置き換えられた「context-free」を除いて同じ質問。

---

バウンティ清澄：型クラス（ES）を行うには、レベルを文法に対応しますか？たとえば、 には、正規表現の言語に必要なすべての操作を提供する型クラスのセットがあります。

質問の動機は、私がパーサーに取り組んでいて、私が使用したコンビネータに基づいて、実装がどの文法レベルであったかを知りたいということです。これは可能ですか？

Answer 1

誰もがこの正式にこれを示しているとは思わない。その理由は、申請者もモナドも、それ自体で何かの多くを解析することができないからです。むしろ、あなたも

1. を必要とする選択肢（MonadPlusの、オルタナティブ）
2. 再帰

（非決定性）の選択および（任意）再帰で、Applicativeのパーサは、本質的に正確にするためのインタフェースを一致させる、と述べていますBNF（そしてすべてのCFLを解析することができます）、モナドは任意の文脈依存操作を提供することができます。