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

Question

为了更好地了解 Packrat，我尝试查看 the provided implementation附带 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 结构的适当组件，表达式解析器对其自身的递归调用就被破坏了(以一种开放递归的方式)。

这个递归结然后被绑在“递归绑定(bind)函数”中(同样取自福特的论文):

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图书馆(不维护atm，抱歉)提供了 Packrat 的实现.