Не удается вычислить минимальную длину парсер - УУ-parsinglib в Haskell

Question

Позволяет увидеть фрагмент кода:

pSegmentBegin p i = pIndentExact i *> ((:) <$> p i <*> ((pEOL *> pSegment p i) <|> pure [])) 

, если я изменю этот код в моем парсер:

pSegmentBegin p i = do 
    pIndentExact i 
    ((:) <$> p i <*> ((pEOL *> pSegment p i) <|> pure [])) 

У меня есть ошибка:

canot compute minmal length of a parser due to occurrence of a moadic bind, use addLength to override 

Я думал, что приведенный выше парсер должен вести себя одинаково. Почему эта ошибка может возникнуть?

EDIT

Приведенный выше пример является очень простой (для упрощения вопроса) и, как указано ниже, это не обязательно использовать делать обозначения здесь, но реальный случай, я хотел, чтобы использовать следующим образом:

pSegmentBegin p i = do 
    j <- pIndentAtLast i 
    (:) <$> p j <*> ((pEOL *> pSegments p j) <|> pure []) 

Я заметил, что добавление «addLength 1» до того, как сделать заявление, решает эту проблему, но я не уверен, если его правильное решение:

pSegmentBegin p i = addLength 2 $ do 
    j <- pIndentAtLast i 
    (:) <$> p j <*> ((pEOL *> pSegments p j) <|> pure []) 

Answer 1

Как я уже упоминал много раз, монадический интерфейс следует избегать, когда это возможно. позвольте мне попытаться объяснить, почему предпочтительным является аппликативный интерфейс.

Одна из отличительных особенностей моей библиотеки заключается в том, что она выполняет исправление ошибок, вставляя или удаляя проблемы. Конечно, мы можем взять здесь неограниченный взгляд, но это сделает процесс ОЧЕНЬ дорогим. Поэтому мы принимаем только ограниченный взгляд на три шага.

Теперь предположим, что мы должны вставить выражение и одно из выражений альтернатив:

выражение: = «если» выражение «то» выражение «другое» выражение

, то мы хотим, чтобы исключить этот вариант так как выбор этой альтернативы потребовал бы вставки другого выражения и т. д. Таким образом, мы выполняем абстрактную интерпретацию альтернатив и следим за тем, чтобы в случае ничьей (т. е. равные затраты для ограниченного взгляда) мы берем одну из нерекурсивных альтернатив.

К сожалению, эта схема разрушается при записи монадических парсеров, так как длина правой стороны связывания может зависеть от результата левой стороны.Поэтому мы выдаем сообщение об ошибке и запрашиваем некоторую помощь от программиста, чтобы указать количество токенов, которые может использовать этот вариант. Фактическое значение не имеет большого значения, если вы не предоставляете конечную длину для чего-то, что является рекурсивным и может привести к бесконечным вводам. Он используется только для выбора кратчайшей альтернативы при вставке.

Эта абстрактная интерпретация имеет некоторые издержки, и если вы напишете все свои синтаксические анализаторы в монадическом стиле, это неизбежно, что этот анализ повторяется снова и снова. поэтому: НЕ НАЙДИТЕ МОНАДИЧЕСКИХ ПАРАМЕТРОВ СТИЛЯ ПРИ ИСПОЛЬЗОВАНИИ ЭТОЙ БИБЛИОТЕКИ, ЕСЛИ ЕСТЬ ПРИМЕНЯЕМАЯ АЛЬТЕРНАТИВА.

Answer 2

Он пытается статически проанализировать, сколько входных данных нужно читать, чтобы оптимизировать производительность, но для такой оптимизации требуется статически известная структура парсера - тип, который может быть создан Applicative с, поскольку эффект парсера не может зависеть от анализатора стоимость такой, какой (>>=) делает.

Так вот что получается не так: при использовании do нотации он переводится на монадическое связывание, которое прерывает предиктор Applicative. Было бы неплохо, если бы библиотека открывала только один из двух интерфейсов, чтобы такая ошибка не могла произойти, но вместо этого существует некоторая несогласованность, если вы используете оба интерфейса вместе в одном и том же парсере.

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

Answer 3

У меня есть обходное решение, которое я использую с монадическими парсерами в uuparsinglib. Его само-ответ здесь: Monadic parse with uu-parsinglib

Вы можете найти полезным