Невозможно вычислить минимальную длину парсера - uu-parsinglib в Haskell

Давайте посмотрим на фрагмент кода:

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

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

РЕДАКТИРОВАТЬ

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

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

Я заметил, что добавление "addLength 1" перед оператором do решает проблему, но я не уверен, правильное ли это решение:

pSegmentBegin p i   = addLength 2 $ do
    j <- pIndentAtLast i
    (:) <$> p j <*> ((pEOL *> pSegments p j) <|> pure [])
Источник

3 ответа

Решение

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

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

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

expr: = "if" expr "тогда" expr "else" expr

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

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

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

Источник

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

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

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

Источник

У меня есть обходной путь, который я использую с монадическими парсерами в uuparsinglib. Здесь ответ на свой вопрос: монадический разбор с uu-parsinglib

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

Источник
Другие вопросы по тегам