Различия в реализации между комбинаторами парсера и алгоритмом упаковки

Чтобы лучше понять упаковку, я попытался взглянуть на предоставленную реализацию, поставляемую вместе со статьей (я сосредотачиваюсь на 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, со значительной экономией памяти.

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