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

为了更好地了解 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 但它似乎与论文中的实现有很大不同。

最佳答案

这里的重点是，这个 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)在“递归绑定(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 的实现。

关于parsing - 解析器组合器和 Packrat 算法之间的实现差异，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53419694/