Можно ли эффективно смотреть вперед более чем на одного Чара в Аттопарсек?

Question

Я пытаюсь дополнить библиотеку синтаксического анализатора Attoparsec на Haskell функцией

takeRegex :: Regex -> Parser ByteString

используя одну из реализаций регулярного выражения.

(Мотивация: Хорошие библиотеки регулярных выражений могут обеспечить производительность, линейную по отношению к длине ввода, в то время как attoparsec необходимо откатить назад. Часть моего ввода особенно поддается анализу с использованием регулярных выражений, и даже библиотека обратного отслеживания Text.Regex.PCRE помогает мне 4-кратное ускорение по сравнению с кодом attoparsec для этой части.)

Аттопарсек раньше имел getInput :: Parser ByteString функция для получения (без потребления) оставшегося ввода; это, вероятно, было бы совершенно идеально для моих целей, так как мой ввод не является инкрементным, строгим и достаточно небольшим - я запускаю парсер для строки файла журнала одновременно. С этим, кажется, я мог бы сделать что-то вроде

takeRegex re = do
  input <- getInput
  m <- matchM re input
  take $ length m

К сожалению, в последних версиях attoparsec отсутствует эта функция. Есть ли способ добиться того же? Почему функция была удалена?

Теперь есть takeByteString :: Parser ByteString функция, которая принимает и потребляет остальную часть ввода. Если бы существовала функция, которая пыталась разобрать и получить результат, фактически ничего не потребляя, это можно было бы использовать вместе с этим, но я не могу найти (или выяснить, как реализовать) такую ​​функцию.

Есть ли способ достичь этого с текущей версией attoparsec?

Answer 1

Есть несколько решений для этого, но ни один не является хорошим....

---

Метод 1- Быстро внедрить, но не так быстро запустить

Ну, (в соответствии с http://hackage.haskell.org/package/attoparsec-0.10.1.1/docs/Data-Attoparsec-ByteString.html), attoparsec всегда возвращает назад при сбое, так что вы всегда можете сделать что-то вроде этого:

parseLine1 = do
  line <- takeTill (== '\n')
  char '\n'
  case <some sort of test on line, ie- a regex> of
    Just -> return <some sort of data type>
    Nothing -> fail "Parse Error"

потом многие из них будут работать как положено

parseLine = parseLine1 <|> parseLine2

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

---

Метод 2- Традиционный метод

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

Например, предположим, что у вас есть правило создания грамматики

pet = "dog" | "dolphin"

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

pet => "ca" halfpet
halfpet => "g" | "lphin"

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

---

Способ 3- правильный путь, но необходимо написать.

Истинный способ сделать это - напрямую скомпилировать регулярное выражение в комбинатор синтаксического анализатора.... Как только вы скомпилируете любой обычный язык, результирующему алгоритму всегда нужен только один символ предпросмотра, поэтому результирующий код attoparsec должен быть довольно простым (как и в методе 1 для чтения одного символа), но работа будет заключаться в компиляции регулярного выражения.

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

(Я написал библиотеку, которая автоматически "оставляет факторы" во многих случаях в контекстно-свободных грамматиках, превращая практически любую контекстно-свободную грамматику в линейный синтаксический анализатор, но я еще не сделал ее доступной… однажды, когда я ее очистил до я буду).