Понимание многих в Мегапарсеке
Я пытаюсь понять поведение many в библиотеке Megaparsec для Haskell. Я бы подумал, что many возвращает пустой список, когда его анализатор ввода дает сбой, но, похоже, это не так.
В частности, меня озадачивает следующий минимальный код:
import Text.Megaparsec (Parsec, many, parseTest)
import Text.Megaparsec.Char (string)
import Data.Void
test :: Parsec Void String [String] -> String -> IO ()
test = parseTest
main = do
test (many (string "a" >> string "b")) "ac" -- error
test (many (string "a" <> string "b")) "ac" -- error
test (many (string "ab")) "ac" -- []
Его вывод следующий:
1:2:
|
1 | ac
| ^
unexpected 'c'
expecting 'b'
1:2:
|
1 | ac
| ^
unexpected 'c'
expecting 'b'
[]
Я не понимаю, почему первые два теста терпят неудачу, а третий нет.
Разве он также не зависает, когда пытается проанализировать string "ab" на "ac"?
Разница в том, что string "a" потребляет входные данные при успехе, и невозможно отменить их использование, если вы не обернете их в try.
Что мне кажется очень странным, так это то, что Парсек и Мегапарсек ведут себя в этом отношении по-разному. Например, «тот же» код с использованием Parsec main = (parseTest (many (string "a" >> string "b")) "ac") >> (parseTest (many (string "a" <> string "b")) "ac") >> (parseTest (many (string "ab")) "ac") выдает три ошибки.
где код предыдущего комментария импортирует Parsec, many и parseTest из Text.Parsec и string из Text.Parsec.Char.
В Parsec string использует соответствующий префикс, вам следует использовать string'.
Ответы 1
Нет никакой разницы в том, что будут анализировать парсеры string "a" >> string "b" и string "a" <> string "b", есть только разница в том, что они возвращают в случае успешного анализа (то есть "b" для первого и "ab" для второго), поэтому неудивительно, что первые два случая ведут себя одинаково ( то есть оба терпят неудачу).
Причина их неудачи в том, что парсер many p запускает парсер p до тех пор, пока он не выйдет из строя. Если сбой p не потребляет входные данные, то many p завершается успешно и возвращает список результатов успешных запусков синтаксического анализатора p до его сбоя. Если сбой p потребляет входные данные, то many p завершается сбоем по той же «причине», что и окончательный сбой синтаксического анализатора p.
Когда парсер string "a" >> string "b" работает с входными данными "ac", парсер string "a" успешно анализирует "a", а затем парсер string "b" не может проанализировать "c", не обрабатывая входные данные. Это приводит к сбою всего синтаксического анализатора string "a" >> string "b" из-за использования входных данных (вводных данных, потребляемых string "a", даже несмотря на то, что синтаксический анализ, вызвавший сбой string "b", сам не потреблял никаких входных данных).
Соберите все это вместе и many (string "a" >> string "b") запускает парсер string "a" >> string "b" до тех пор, пока он не выйдет из строя, что происходит при самом первом приложении по той причине, что парсер string "b" ожидал "b", но получил "c". Поскольку этот сбой потребляет входные данные ( "a" потребляется string "a"), весь синтаксический анализатор many (string "a" >> string "b") выходит из строя по той же «причине».
Парсер string "ab" немного отличается, и его поведение различается в Parsec и версиях Megaparsec начиная с 4.4.0 (см. документацию для токенов ).
В Parsec синтаксический анализатор string "ab", примененный к входным данным "ac", обрабатывает "a", а затем дает сбой на "c", поэтому он завершается с ошибкой после обработки входных данных. Вероятно, это плохая идея, поэтому Parsec представил string' в версии 3.1.16.0. Парсер string' "ab" поступает более разумно: он либо потребляет все "ab", либо терпит неудачу, не потребляя ничего. В частности, когда он применяется к входным данным "ac" и не может использовать "ab", он терпит неудачу, не потребляя входные данные.
В Мегапарсеке string изначально вел себя как string Парсека, но когда они исправили этот недостаток конструкции, вместо введения нового комбинатора string' они просто внесли несовместимое изменение в string, поэтому string "ab" в Мегапарсеке, как string' "ab" в Парсеке, либо потребляет весь "ab", либо терпит неудачу, ничего не потребляя.
(Чтобы еще больше запутать, у Megaparsec также есть комбинатор string', но это версия string без учета регистра и поэтому не имеет ничего общего с версией string' Parsec.)
Большое спасибо за ваш ответ. Объяснение string и string' особенно поучительно. Я использую Haskell в основном для небольших проектов и не особо забочусь об эффективности (в некоторой степени, конечно). Я хотел бы иметь комбинатор синтаксического анализатора звезды Клини, который никогда не подвел бы и не делал бы различия между eerr и cerr. Мне кажется, можно было бы определить kleene p = many (try p), но интересно: есть ли уже подобный оператор в mega.parsec?
Я взглянул на библиотеку ReadP, очень маленькую по сравнению с Parsec, которая не делает различия между пустыми ошибками и потребляемыми ошибками. Однако его many не жрёт и параллельно сохраняет все возможные префиксы. У них есть термин munch, который выглядит так, как я хочу, но в качестве входных данных он не принимает ReadP a, а только Char -> Bool. Есть ли способ заполучить пылкую звезду Клини, которая никогда не подведет?
Ваше определение kleene кажется подходящим, и я не думаю, что существует какая-либо подобная функция. Что касается вашего ReadP вопроса, возможно, лучше задать его как новый вопрос. У меня есть возможный ответ, но у кого-то другого вполне может быть лучший ответ.
Парсер сначала обрабатывает
"a", а это означает, что теперь он пытается проанализироватьstring "a" >> string "b"илиstring "a" <> string "b"и поэтому застревает. Вам следует добавитьtry, чтобы этого не произошло.