Соответствие между классами типов и уровнями грамматики в иерархии Хомского

Мой вопрос касается классов типов Applicative и Monad, с одной стороны, и контекстно-свободных и контекстно-зависимых уровней грамматики иерархии Хомского, с другой.

Я слышал, что существует соответствие между классами типов и уровнями грамматики. Насколько точно это соответствие?

То есть, могут ли все контекстно-свободные грамматики быть проанализированы, не используя ничего более сильного, чем Applicative комбинаторы, и все ли грамматики, которые могут быть проанализированы, не используя ничего более сильного, чем Applicative комбинаторы, контекстно-свободными? Другими словами, точно ли класс типа Applicative соответствует контекстно-свободным грамматикам?

И тот же вопрос, за исключением того, что «контекстно-свободный» заменен на «контекстно-зависимый» и «Аппликативный» - от Monad.

Разъяснение о награде: соответствуют ли классы типов грамматическим уровням? Например, существует ли набор классов типов, которые обеспечивают все операции, необходимые для регулярных языков выражений, и не более того?

Мотивация вопроса заключается в том, что я работал над синтаксическим анализатором и хотел определить, на каком уровне грамматики находилась моя реализация, на основе комбинаторов, которые я использовал. Это возможно?


typeclass haskell grammar monads applicative
person Matt Fenwick    schedule 17.05.2013    source источник
comment
Я думаю, что ваша посылка здесь неполная. Applicative сам по себе не продвинется далеко, так как вы не можете ни возвращаться, ни выбирать продукцию на основе ввода. Типичный API комбинатора синтаксического анализатора опирается на Alternative вместе с Applicative.   -  person C. A. McCann    schedule 17.05.2013
comment
@ C.A.McCann да, это правда, спасибо, что указали на это. Alternative соответствует ли обычным грамматикам? Я хотел добавить это, но не знал, что делать с ограничением Applicative. Есть ли другие классы типов, соответствующие обычным грамматикам?   -  person Matt Fenwick    schedule 17.05.2013
comment
Я не уверен. На самом деле я не уверен, что связь здесь идет глубже, чем общая способность Monad выражать причинно-следственные связи, которые Applicative не могут, потому что я не понимаю, как какие-либо естественные ограничения (т. Е. Не придуманные для этой цели) комбинаторов синтаксического анализатора даст возможность определять только менее выразительные грамматики.   -  person C. A. McCann    schedule 17.05.2013
comment
При дальнейшем рассмотрении мне также не ясно, что комбинаторы монадического синтаксического анализатора ограничены только контекстно-свободными языками, если мы предполагаем, что отклонение всего примитивного доступно, поскольку он может выполнять произвольные вычисления, прежде чем решить, следует ли возвращаться в любой момент.   -  person C. A. McCann    schedule 17.05.2013
comment
Вероятно, вам стоит прочитать это: byorgey.wordpress .com / 2012/01/05 /   -  person Luis Casillas    schedule 18.05.2013

Ответы (1)


arrow_upward
4
arrow_downward

Я не думаю, что кто-то показал это формально. Причина в том, что ни аппликатив, ни монада не в состоянии разбирать большую часть чего-либо самостоятельно. Скорее вам также понадобится

  1. Выбор (MonadPlus, Альтернатива)
  2. Рекурсия

при этом с (недетерминированным) выбором и (произвольной) рекурсией парсеры Applicative по существу точно соответствуют интерфейсу для BNF (и поэтому могут анализировать все CFL), в то время как монады могут обеспечивать произвольные контекстно-зависимые операции.

person Philip JF    schedule 17.05.2013