Вопрос о классах типа Аппликация и тип Монады, с одной стороны, и контекстно-зависимых уровнях грамматики иерархии Хомского - с другой.Переписка между типами классов и уровнями грамматики в иерархии Хомского
Я слышал, что существует соответствие между типами классов и уровнями грамматики. Насколько точна эта переписка?
То есть, можно ли анализировать все контекстно-свободные грамматики, используя ничего более сильного, чем аппликативные комбинаторы, и все ли грамматики, которые могут быть проанализированы с использованием ничего более сильного, чем сопутствующие комбинаторы без контекста? Другими словами, класс Applicative type точно соответствует контекстно-свободным грамматикам?
И тот же вопрос, кроме как «контекстно-свободный», замененный «контекстно-зависимым» и аппликативным по Монаде.
Bounty уточнение: сделать тип класс (ы) соответствуют грамматике уровней? Например, есть набор классов типов, которые предоставляют все операции, необходимые для выражения регулярных языков и ничего более?
Мотивация вопроса заключается в том, что я работал над парсером и хотел определить, какой уровень грамматики был для моей реализации, на основе используемых множителей. Это возможно?
Я думаю, что ваше помещение здесь неполное. «Аппликативный» сам по себе не заставит вас очень далеко, так как вы не можете ни отступать, ни выбирать постановки на основе ввода. Типичный API-интерфейс комбинатора парсеров опирается на «Alternative» вместе с «Applicative». –
@ C.A.McCann да, это правда, спасибо, что указали это. Соответствует ли «Альтернатива» регулярным грамматикам? Я хотел добавить это, но не знал, что делать с ограничением «Аппликация». Есть ли еще один класс (ы) типа, соответствующий регулярным грамматикам? –
Я не уверен. Я на самом деле не убежден, что связь здесь глубже, чем общая способность «Монады» выражать причинно-следственные связи, которые «Аппликативные» не могут, потому что я не вижу, как любое естественное ограничение (т. Е. Не надуманное для этой цели) комбинаторных комбинаторов приведет к способности определять только менее выразительные грамматики. –