20

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

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

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

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

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

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

4

1 回答 1

4

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

  1. 选择（MonadPlus，替代）
  2. 递归

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

于 2013-05-17T20:55:29.923 回答