解析器组合器和 Packrat 算法之间的实现差异

Question

为了更好地了解 packrat，我尝试查看 the provided implementation coming with the paper（我主要关注 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))

对我来说，解析器组合器（例如 this simplified version of 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 是一个带有记忆部分的解析器生成器。可悲的是，这个概念似乎没有用在这个实现中。

解析器组合器和 Packrat 在实现层面的最大区别是什么？

PS: 我也看过Papillon，但是好像和论文中的实现有很大的不同。

Answer 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 结构的适当组件。

然后将这个递归结系在 "recursive tie-up function"（再次摘自 Ford 的论文）：

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 技巧发生的地方。重要的是要理解这个技巧不能在传统的解析器组合器库中以标准方式实现（至少在像 Haskell 这样的纯编程语言中），因为它需要知道语法的递归结构。对于使用语法递归结构的特定表示的解析器组合器库，有一些实验性方法，并且有可能提供 Packrat 的标准实现。比如我自己的grammar-combinators library (not maintained atm, sorry) offers an implementation of Packrat.

Answer 2

如其他地方所述，packrat 不是组合器的替代品，而是这些解析器中的一个实现选项。 Pyparsing 是一个组合器，它通过调用 ParserElement.enablePackrat() 提供可选的 packrat 优化。它的实现几乎是 pyparsing 的 _parse 方法（重命名为 _parseNoCache）的替代品，带有 _parseCache 方法。

Pyparsing 使用固定长度的 FIFO 队列作为其缓存，因为一旦组合器完全匹配缓存的表达式并继续通过输入流，packrat 缓存条目就会过时。自定义缓存大小可以作为整数参数传递给 enablePackrat()，或者如果传递 None，则缓存是无界的。对于提供的 Verilog 解析器，默认值为 128 的 packrat 缓存的效率仅比无界缓存低 2%，并显着节省内存。

解析器组合器和 Packrat 算法之间的实现差异

Implementation differences between parser combinators and packrat algorithm

parsing

haskell

parsec

parser-combinators

peg