Можно ли эффективно смотреть вперед более чем на одного Чара в Аттопарсек?
Я пытаюсь дополнить библиотеку синтаксического анализатора 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?
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 для чтения одного символа), но работа будет заключаться в компиляции регулярного выражения.
Компиляция регулярных выражений рассматривается во многих учебниках, поэтому я не буду вдаваться в подробности, но в основном это означает замену всех неоднозначных путей в автомате состояний регулярных выражений новыми состояниями. Или, иначе говоря, он автоматически "оставил факторы" во всех случаях, которые потребуют возврата.
(Я написал библиотеку, которая автоматически "оставляет факторы" во многих случаях в контекстно-свободных грамматиках, превращая практически любую контекстно-свободную грамматику в линейный синтаксический анализатор, но я еще не сделал ее доступной… однажды, когда я ее очистил до я буду).