haskell - 乔姆斯基层次结构中类型类和语法级别之间的对应关系

Question

我的问题一方面是关于 Applicative 和 Monad 类型的类，另一方面是关于 Chomsky 层次结构的上下文无关和上下文敏感的语法级别。

我听说类型类和语法级别之间存在对应关系。这种对应关系有多准确？

也就是说，是否可以使用不比 Applicative 组合子更强的任何东西来解析所有上下文无关语法，并且是否所有可以使用不比 Applicative 组合子更强大的东西来解析的语法都是上下文无关的？换句话说，Applicative 类型类是否完全对应于上下文无关文法？

和同样的问题，除了用“上下文敏感”代替“上下文无关”和 Monad 应用。

赏金说明:类型类是否对应于语法级别？例如，
是否有一组类型类提供表达式正则语言所需的所有操作，仅此而已？

这个问题的动机是我正在研究一个解析器，并且想根据我使用的组合器来确定我的实现处于哪个语法级别。这可能吗？

Answer 1

我认为没有人正式展示过这一点。原因是 applicative 和 monad 都不能自己解析很多东西。相反，您还需要

选择(MonadPlus，替代)

递归

也就是说，通过(非确定性)选择和(任意)递归，Applicative 解析器本质上与 BNF 的接口(interface)完全匹配(因此可以解析所有 CFL)，而 monad 可以提供任意上下文相关操作。