Различия в реализации между комбинаторами парсера и алгоритмом упаковки
Чтобы лучше понять упаковку, я попытался взглянуть на предоставленную реализацию, поставляемую вместе со статьей (я сосредотачиваюсь на bind
):
instance Derivs d => Monad (Parser d) where
-- Sequencing combinator
(Parser p1) >>= f = Parser parse
where parse dvs = first (p1 dvs)
first (Parsed val rem err) =
let Parser p2 = f val
in second err (p2 rem)
first (NoParse err) = NoParse err
second err1 (Parsed val rem err) =
Parsed val rem (joinErrors err1 err)
second err1 (NoParse err) =
NoParse (joinErrors err1 err)
-- Result-producing combinator
return x = Parser (\dvs -> Parsed x dvs (nullError dvs))
-- Failure combinator
fail [] = Parser (\dvs -> NoParse (nullError dvs))
fail msg = Parser (\dvs -> NoParse (msgError (dvPos dvs) msg))
Для меня это выглядит (без обработки ошибок) для комбинаторов синтаксического анализа (таких как эта упрощенная версия Parsec):
bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \s -> concatMap (\(a, s') -> parse (f a) s') $ parse p s
Я в замешательстве, потому что до этого я думал, что большая разница в том, что packrat был генератором парсера с частью для запоминания. К сожалению, кажется, что эта концепция не используется в этой реализации.
В чем большая разница между комбинаторами парсера и пакратом на уровне реализации?
PS: Я также взглянул на Papillon, но, похоже, он сильно отличается от реализации, прилагаемой к статье.
1 ответ
Дело в том, что эта библиотека комбинатора синтаксического анализатора Packrat не является полной реализацией алгоритма Packrat, а скорее похожа на набор определений, которые можно повторно использовать между различными синтаксическими анализаторами Packrat.
Реальная хитрость алгоритма packrat (а именно, запоминание результатов разбора) происходит в другом месте. Посмотрите на следующий код (взят из тезиса Форда):
data Derivs = Derivs {
dvAdditive :: Result Int,
dvMultitive :: Result Int,
dvPrimary :: Result Int,
dvDecimal :: Result Int,
dvChar :: Result Char}
pExpression :: Derivs -> Result ArithDerivs Int
Parser pExpression = (do char ’(’
l <- Parser dvExpression
char ’+’
r <- Parser dvExpression
char ’)’
return (l + r))
</> (do Parser dvDecimal)
Здесь важно заметить, что рекурсивный вызов синтаксического анализатора выражений сам по себе прерывается (в виде открытой рекурсии), просто проецируя соответствующий компонент структуры Derivs.
Этот рекурсивный узел затем связывается в "функции рекурсивного связывания" (снова взятой из тезиса Форда):
parse :: String -> Derivs
parse s = d where
d = Derivs add mult prim dec chr
add = pAdditive d
mult = pMultitive d
prim = pPrimary d
dec = pDecimal d
chr = case s of
(c:s’) -> Parsed c (parse s’)
[] -> NoParse
Эти фрагменты действительно там, где происходит трюк с пакратом. Важно понимать, что этот трюк не может быть реализован стандартным способом в традиционной библиотеке комбинатора синтаксического анализатора, потому что он должен знать рекурсивную структуру грамматики. Существуют экспериментальные подходы к библиотекам комбинатора синтаксического анализатора, которые используют конкретное представление рекурсивной структуры грамматики, и там можно обеспечить стандартную реализацию Packrat. Например, моя собственная библиотека грамматических комбинаторов (не поддерживается atm, извините) предлагает реализацию Packrat.
Как указано в другом месте, packrat не является альтернативой комбинаторам, но является вариантом реализации в этих синтаксических анализаторах. Pyparsing - это комбинатор, который предлагает дополнительную оптимизацию пакетов путем вызова ParserElement.enablePackrat()
, Его реализация является почти заменой для pyparsing _parse
метод (переименован в _parseNoCache
), с _parseCache
метод.
Pyparsing использует очередь FIFO с фиксированной длиной для своего кэша, поскольку записи кэша packrat устаревают, когда комбинатор полностью соответствует кэшированному выражению и перемещается по входному потоку. Пользовательский размер кэша может быть передан как целочисленный аргумент enablePackrat()
или, если None пропущен, кэш не ограничен. Пакетный кэш со значением по умолчанию 128 был только на 2% менее эффективен, чем неограниченный кэш по сравнению с поставляемым анализатором Verilog, со значительной экономией памяти.