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

Question

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

IЯ в замешательстве, потому что до этого я думал, что большая разница в том, что packrat был генератором парсера с частью для запоминания.К сожалению, кажется, что эта концепция не используется в этой реализации.

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

PS: я также взглянул на Papillon но, похоже, он сильно отличается от реализации, прилагаемой к статье.

Answer 1

Как указано в другом месте, packrat не является альтернативой комбинаторам, но является вариантом реализации в этих синтаксических анализаторах.Pyparsing - это комбинатор, который предлагает дополнительную оптимизацию пакета путем вызова ParserElement.enablePackrat().Его реализация - это почти полная замена метода _parse pyparsing (переименованного в _parseNoCache) с методом _parseCache.

Pyparsing использует очередь FIFO фиксированной длины для своего кэша, так как packratзаписи в кэше устаревают, когда комбинатор полностью совпадает с кэшированным выражением и перемещается по входному потоку.Пользовательский размер кэша может быть передан как целочисленный аргумент enablePackrat(), или, если передано значение None, кэш неограничен.Пакетный кэш со значением по умолчанию 128 был только на 2% менее эффективен, чем неограниченный кэш, по сравнению с поставляемым анализатором Verilog со значительной экономией памяти.

Answer 2

Дело в том, что на самом деле эта библиотека комбинатора синтаксического анализатора 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

Эти фрагментыдействительно, где трюк с пакратом происходит.Важно понимать, что этот прием не может быть реализован стандартным способом в традиционной библиотеке комбинатора синтаксического анализатора (по крайней мере, на чистом языке программирования, таком как Haskell), потому что он должен знать рекурсивную структуру грамматики.Существуют экспериментальные подходы к библиотекам комбинаторов синтаксического анализатора, которые используют конкретное представление рекурсивной структуры грамматики, и там можно обеспечить стандартную реализацию Packrat.Например, моя собственная библиотека грамматических комбинаторов (не поддерживается atm, извините) предлагает реализацию Packrat .