search

leadzen / blog

博客
15 stars 1 forks source link

Packrat 解析： 简单，强大，惰性，线性时间 #10

Open leadzen opened 7 years ago

leadzen commented 7 years ago

0. 摘要

Packrat 解析是一种用惰性函数编程语言来实现解析器的新技术。Packrat 解析器提供了回溯和无限向前看能力的自顶向下解析的功能和灵活性，但仍然能保证线性时间解析。除了常规线性时间算法不支持的部分语言之外，由 LL(k) 或 LR(k) 文法定义的任何语言，都可以由 Parkrat 解析器识别。这种额外的功能可用于简化处理普通语法语言中常见但却麻烦的最长匹配规则，可以使用语法和语义断言策略来消除复杂的二义性，从而提供更好的文法组合特性，并且可将词法分析无缝地整合到语法解析过程中。除这些能力之外，Packrat 依旧保持了递归下降解析算法的简单和优雅；事实上通常只需涉及相当简单的结构调整，就可将可回溯递归下降解析器，转换为线性时间的 Packrat 解析器。本文通俗介绍 Packrat 解析，强调其在实际应用中的使用，并探讨其相对于其他常规的替代方案的优缺点。

1. 简介

有很多方法都可以在函数式编程语言中实现解析器。最简单和最直接的方法是自顶向下或递归下降解析，其中语言文法的组成部分，被或多或少地直接转换成一组相互递归的函数。自顶向下的解析器又可以分为两类。预测解析器试图通过“向前看”输入流中的有限个的符号来预测在给定点处期望什么类型的语言结构。回溯解析器通过连续尝试不同的替代式，来推测性地做出决策：如果一个替代式不能匹配，则解析器“回溯”到原始输入位置，并再尝试另一个。预测解析器是快速的，并且能保证线性时间复杂度的解析，而回溯解析器在概念上更简单和强大，但却需要指数复杂度的运行时间。

本文展示了一个可以避免在预测和回溯之间进行选择的自顶向下的解析策略。Packrat 解析提供了回溯模型的简单性、优雅性和通用性，但通过保存所有已计算的中间解析结果，来确保结果不会被多次解析，从而消除了超出线性解析时间的风险。这种算法的理论基础早在 20 世纪 70 年代已经出现，但由于当时的计算机内存大小的限制，线性时间版本从未在实际中应用。然而，在现代计算机中，该算法的存储成本对于许多应用却都是合理的。此外，这种专用的存储结构可以用现代惰性函数编程语言非常优雅和有效地实现，不需要散列表或其他显式查找数据结构。将这种被忽视的经典线性时间解析算法与现代函数式编程的结合，是本文的主要技术贡献。

Packrat 解析是非常强大的，但却能保证线性时间解析。可以很容易地构造 Packrat 解析器用于处理 LL(k) 或 LR(k) 文法描述的任何语言，以及需要无限向前看能力的非 LR 语言。这种灵活性消除了 YACC 系统的解析生成器带来的许多麻烦的限制。Packrat 解析器也比自底向上的 LR 解析器更容易构建，并可以实现解析器的手动构建。本文重点探讨手动构建方法，虽然自动构建 Packrat 解析器的是未来很有前途的工作方向。

Packrat 解析器直接有效地实现了诸如最长匹配和后续真假断言等，消除二义性的通用规则，这些都是在上下文无关语法中难以明确表达，或在常规线性时间解析器中难以实现的。例如，在词法分析期间识别标识符或数字，以类 C 语言解析 if-then-else 语句，以及处理 Haskell 中的do、let 和 lambda 表达式，都会涉及使用最长匹配来消除二义性问题。Packrat 解析器比 LR 解析器更加简洁和自然，更适合处理动态或可扩展语法。最后，词法和语法层面的解析都可以无缝整合为单一的 Packrat 解析器，词法和语法甚至可以混合在一起，来处理带有嵌入表达式的字符串字面量或结构化文档标记的字面量注释。

Packrat 解析的主要缺点是它的空间消耗。虽然其在最坏情况也与常规算法一样，保持与输入大小的线性关系， 即空间使用量是与输入大小成正比，而不是与最大递归深度成正比，但 Packrat 解析可能在空间使用的数量级有不同。然而，对于现代优化编译器的许多应用，Pacrkat 解析器的存储成本可能小于后续处理阶段的成本。因此，这种成本的代价是对有线性时间的无限向前看解析的功率和灵活性的合理权衡。

本文的其余部分探讨 Packrat 解析，已便在需要时，提供一个如何实现的实用方法。假定你已基本熟悉上下文无关语法和自顶向下解析。为了简洁和清楚的呈现，在文本中仅包括少量摘录的示例代码。然而，本文中描述的所有示例都是可用的，完整和可运行的 Haskell 代码在：

http://pdos.lcs.mit.edu/~baford/packrat/icfp02

本文组织如下： 第 2 节 介绍 Packrat 解析，以传统的递归下降解析作为起点，描述它是如何工作的。 第 3 节 介绍了对基本算法的有用扩展，例如支持左递归，词法分析和 Monad 解析。 第 4 节 更详细地探讨了 Packrat 解析器与传统线性时间解析器的识别能力的对比。 第 5 节 讨论了 Packrat 解析的三个主要实际限制：确定性，无状态和空间消耗。 第 6 节 介绍一些实验结果，以展示 Packrat 解析实际语言的实用性。 第 7 节 讨论相关工作。 第 8 节 指出未来探索的方向。 第 9 节 总结。

2. 构建解析器

Packrat 解析本质上是一个自上而下的解析策略，因此 Packrat 解析器与递归下降解析器密切相关。 因此，我们将首先为一个简单的语言构建一个递归下降解析器，然后将其转换成一个 Packrat 解析器。

2.1 递归下降解析

考虑构造递归下降解析器的标准方，法用于解析一般文法，例如图 1 所示的示意算术表达式语言。

Additive  ←  Multitive ‘+’ Additive | Multitive
Multitive ←  Primary ‘*’ Multitive | Primary
Primary   ← ‘(’ Additive ‘)’ | Decimal
Decimal   ← ‘0’ | ... | ‘9’

图 1. 示意文法

我们定义了四个函数，其中的每个都用于处理规则左侧的非终结符。每个函数接受要解析的字符串，尝试将输入字符串的某些前缀识别为相应非终结符的推导，并返回“成功”或“失败”的结果。成功时，函数返回紧接在识别部分之后的剩余输入字符串，以及从识别部分计算的语义值。每个函数可以递归调用自身和其他函数，以便识别在其对应语法规则右侧的非终结符。

要在Haskell中实现这个解析器，我们首先需要一个描述解析函数的结果的类型：

data Result v = Parsed v String
              | NoParse

为了使此类型可通用于不同的解析函数，以产生不同种类的语义值，Result 类型采用类型参数 v 表示相关语义值的类型。成功的结果由 Parsed 构造函数创建，其包含语义值（ 类型 v ）和剩余部分的输入文本（ 类型 String ）。失败的结果由简单的 NoParse 表示。在这个特定的解析器中，四个解析函数中的每个都需要一个 String 参数，并产生一个带有 Int 类型语义值的 Result 结果：

pAdditive  :: String -> Result Int
pMultitive :: String -> Result Int
pPrimary   :: String -> Result Int
pDecimal   :: String -> Result Int

这些函数的定义具有以下一般结构，并直接将文法表达的相互递归映射为图 1：

pAdditive  s = ... (calls itself and pMultitive) ...
pMultitive s = ... (calls itself and pPrimary) ...
pPrimary   s = ... (calls pAdditive and pDecimal) ...
pDecimal   s = ...

例如，pAdditive 函数可以仅使用原生的 Haskell 模式匹配结构来编写：

-- Parse an additive-precedence expression
pAdditive :: String -> Result Int
pAdditive s = alt1 where
    -- Additive <- Multitive ’+’ Additive
    alt1 = case pMultitive s of
              Parsed vleft s’ ->
                  case s’ of
                      (’+’:s’’) ->
                          case pAdditive s’’ of
                              Parsed vright s’’’ ->
                                  Parsed (vleft + vright) s’’’
                              _ -> alt2
                          _ -> alt2
                      _ -> alt2
    -- Additive <- Multitive
    alt2 = case pMultitive s of
              Parsed v s’ -> Parsed v s’
              NoParse -> NoParse

要计算 pAdditive 的结果，我们首先计算 alt1 的值，其代表此文法规则的第一个替代式。这个替代式又调用 pMultitive 来识别乘法优先级表达式。如果 pMultitive 成功，则返回该表达式的语义值 vleft 和输入识别部分之后的剩余输入 s'。然后，我们在位置 s' 检查 '+' 运算符，如果成功则产生表示在 '+' 运算符之后的剩余输入字符串 s''。最终，我们递归调用 pAdditive 自身来识别位于 s'' 处的另一加性优先表达式，如果成功，则产生右侧结果 vright 和最终剩余字符串 s'''。如果所有这三项都匹配成功，那么我们将结果返回给最初调用的 pAdditive，得到加法的语义值 vleft + vright 以及最后剩余的字符串 s'''。如果这些匹配中的任何一个失败，我们回到第二个替换式 alt2，它只尝试识别在原始输入位置 s 的单个乘法优先表达式，并逐字返回该结果，无论成功还是失败。

其他三个解析函数类似地构造，都与文法直接对应。当然，通过使用一个合适的辅助函数库或组合，可以以更简单和更简洁的方法来编写这些解析函数。这些技术将在 3.3 节稍后讨论，但为了清楚起见，我们现在将依旧使用简单的模式匹配。

2.2 回溯与预测

上面开发的解析器是一个回溯解析器。例如，如果 pAdditive 函数中的 alt1 失败，则解析器有效地“回溯”到原始输入位置，从第二替代式 alt2 中的原始输入字符串 s 开始，而不管第一替代式在其第一、第二或第三阶段是否匹配失败。注意，如果输入只包含一个乘法表达式，那么 pMultitive 函数将在同一个字符串上调用两次：在第一个替代式中，尝试匹配一个不存在的 '+' 运算符时，调用将失败；然后在第二个替代式中再次调用并成功匹配。这种对解析函数的回溯和冗余求值，将导致解析时间与输入的大小成指数增长，而这正是为什么这种“原始”回溯策略从未在需要于处理大量输入的实际解析器中使用的主要原因。

设计实用的自顶向下解析器的标准策略是，在实际进行任何递归调用之前，可“预测”使用哪个替代式规则。以这种方式，可以保证解析函数从不被冗余调用，并且任何输入可以在线性时间内被解析。例如，尽管图 1 中的语法不能直接用于预测解析器，但通过对 Additive 和 Multitive 非终结符进行“左因子分解，以提供一个用于预测的向前看符号，就可将其转换为如下的 LL(1) 文法：

Additive        ←  Multitive AdditiveSuffix
AdditiveSuffix  ←  ‘+’ Additive | ϵ
Multitive       ←  Primary MultitiveSuffix
MultitiveSuffix ←  ‘*’ Multitive | ϵ

现在，在进行任何递归调用之前，可以通过检查下一个输入字符是否为 ‘+’，来确定 AdditiveSuffix 的两个替代式。然而，因为预测机制只能依靠“原始”输入记号（这里是字符）来工作，并且自身必须在恒定时间内操作，所以这类可预测解析的文法有很大的限制性。还必须小心保持预测机制与语法一致，这难以做到手工实现和做到语言全局性质的高度灵活。例如，如果向语言添加了较高优先级幂运算符 ‘**’，则必须调整 MultitiveSuffix 的预测机制; 否则，幂运算符将错误地触发乘法表达式的预测，并导致解析器在有效输入上出错。

某些自顶向下的解析器可对大多数决策使用预测机制，但是当需要更多的灵活性时，却转而使用完全回溯。这种策略通常可在实践中提供灵活性和性能的较好结合，但仍然会遇到随之而来的预测复杂性，并且它需要解析器设计者准确地知道在哪里可以使用预测以及何时需要回溯。

2.3 表格自顶向下解析

正如 Birman 和 Ullman 所指出的，可以使 2.1 节中提到的自顶向下的回溯解析器在线性时间内运作，而不会增加复杂性或预测的约束。回溯解析器超出线性时间的基本原因是，对相同输入子串的相同解析函数的冗余调用，而这些冗余调用可以通过记忆来消除。

示例中的每个解析函数仅依赖于其单个参数，即输入字符串。每当解析函数对自身或另一个解析函数进行递归调用时，总是提供给出的相同输入字符串（例如，对于 pAdditive 到 pMultitive 的调用），或者是原始输入字符串的后缀（例如， 对于 pAdditive 在匹配 '+' 运算符之后的递归调用）。如果输入字符串的长度为 n，则可能只有 n + 1 个不同的后缀用于这些递归调用，包括原始输入字符串本身和空字符串。既然只有四个解析函数，所以解析过程可能最多需要 4 ( n + 1 ) 个不同的中间结果。

我们可以通过将任何中间结果存储在表中，来避免多次计算任何这些结果。该表对于四个解析函数中的每个都有对应的行，对于输入字符串中的每个不同位置都有对应的列。我们在表中填入每个输入位置的每个解析函数的结果，从输入字符串的右侧开始，逐列向左工作。在每一列中，我们从最底部的单元格开始向上工作。在我们计算给定单元格的结果时，相应的解析函数中所有可能的递归调用的结果将被计算并记录在表格的某个地方；我们只需要查找和使用适当的结果。

2 图 2. 字符串 ‘2*(3+4)’ 解析结果矩阵

图 2 列示了输入字符串 '2 * ( 3 + 4 )' 部分完成的结果表。为简洁起见，解析结果表示为 (v，c)，其中 v 是语义值，c 是相关联的剩余后缀开始的列数。列表示为 C1，C2 等，以避免与整数语义值混淆。NoParse 结果在单元格中用 X 表示。要填充的下一个单元格是在列 C3 处的 pPrimary 单元格，用带圆圈的问号表示。

Primary 表达式的规则有两个替换式：带括号的 Additive 表达式或 Decimal 数字。如果我们以文法中表达的顺序尝试每个替代式，pPrimary 将首先检查带括号的 Additive 表达式。为此，pPrimary 首先尝试匹配列 C3 中的 左括号 '(' ，成功后产生从列 C4 开始的输入后缀作为其剩余字符串，即 '3 + 4 '。在简单的递归下降解析器中，pPrimary 将在这个剩余字符串上递归调用 pAdditive。然而，因为我们有表，我们可以简单地在表中的 C4 列查找 pAdditive 的结果，即 (7, C7)。该项给出了语义值 7（加法表达式 '3 + 4' 的结果），以及从 C7 开始的剩余后缀 ')' 。既然这个匹配是成功的，pPrimary 最终尝试匹配位置 C7 处的右括号，成功后产生空字符串 C8 作为剩余字符串。 因此，在列 C3 处的 pPrimary 的最终结果就是 (7, C8)。

虽然，对于长输入字符串和复杂语法，这个结果表可能很大，但是假设语法具有固定数量的非终结符，那么其大小只会随着输入大小线性增长。此外，只要文法仅使用标准的 BNF (Backus-Naur Form) 运算符，则只需要访问矩阵中的固定数量的前面记录的单元即可计算新结果。因此，假设查表时间是恒定的，则整体的解析过程将在线性时间内完成。

由于嵌在结果表中的“前向指针”，计算给定结果时可以检查在矩阵中间隔很大的单元。例如，计算上述 C3 处的 pPrimary 的结果时，使用了来自列 C3、C4 和 C7 的结果。这种在进行解析决策时跳过任意距离的能力，是此算法可以无限向前看的根源，这种能力使得该算法比线性时间预测解析器或 LR 解析器更强大。

2.4 Packrat 解析

上面的表格右到左解析算法的一个明显的实际问题，就是其计算了从不需要的许多结果。另外一个不便之处是，我们必须仔细确定计算特定列结果的顺序，以便让依赖于同列其他结果的解析函数（例如 pAdditive 和pMultitive）可以正确工作。

Packrat 解析本质上是解决这两个问题的表格式算法的惰性化版本。Packrat 解析器只在需要时才计算结果，但顺序上与原始递归下降解析器相同。然而，一旦第一次计算出结果，其将被存储以便将来调用时使用。

非严格函数式编程语言，比如 Haskell，为 Packrat 解析器提供了理想的实现平台。事实上，在 Haskell 中的 Packrat 解析特别有效，因为它不需要数组或除了语言的普通代数数据类型之外的任何其他显式查找结构。

首先，我们需要一个新类型来表示解析结果矩阵的单个列，我们将其称为 Derivs（推导）。此类型只不过是带有一个分量的元组，用于文法中每个非终结。每个分量的类型就是相应的解析函数的结果类型。Derivs 类型还包含一个附加分量，我们称之为 dvChar，表示输入字符串的“原始”字符，就像它们本身就是解析函数的结果一样。在Haskell中，很容易将我们的示例解析器的 Derivs 类型声明如下：

data Derivs = Derivs {
        dvAdditive  :: Result Int,
        dvMultitive :: Result Int,
        dvPrimary   :: Result Int,
        dvDecimal   :: Result Int,
        dvChar      :: Result Char}

此 Haskell 语法声明类型 Derivs 具有一个构造函数，也称为 Derivs，其含有指定类型的五个分量。该声明还自动为每个分量创建相应的数据访问器函数：dvAdditive 可用作类型 Derivs -> Result Int 的函数，该函数提取 Derivs 元组的第一个分量，依此类推。

接下来，我们修改 Result 类型，使成功结果的 “剩余” 分量不是纯 String，而是 Derivs 的实例：

data Result v = Parsed v Derivs
              | NoParse

Derivs 和 Result 类型现在就是相互递归的：一个 Derivs 实例的成功结果将充当到其他 Derivs 实例的连接。这些结果值事实上提供了我们在解析结果矩阵中的不同列之间需要的唯一连接。

现在，我们将修改原始递归下降解析函数，使得每个函数都使用 Derivs 而不是 String 作为其参数：

pAdditive  :: Derivs -> Result Int
pMultitive :: Derivs -> Result Int
pPrimary   :: Derivs -> Result Int
pDecimal   :: Derivs -> Result Int

无论哪一个原解析函数直接检查到输入字符，新的解析函数都会引用 Derivs 对象的 dvChar 分量。只要原始函数中的一个对其自身或另一个解析函数进行递归调用，以匹配文法中的非终结符，新的解析函数将使用对应使用于该非终结符的 Derivs 访问器函数。终结符和非终结符序列将按照成功结果链，匹配到多个 Derivs 实例。例如，新的 pAdditive 函数将使用 dvMultitive、dvChar 和 Additive 访问器，而不进行任何直接递归调用，如下所示：

-- Parse an additive-precedence expression
pAdditive :: Derivs -> Result Int
pAdditive d = alt1 where
    -- Additive <- Multitive ’+’ Additive
    alt1 = case dvMultitive d of
             Parsed vleft d’ ->
                 case dvChar d’ of
                     Parsed ’+’ d’’ ->
                         case dvAdditive d’’ of
                             Parsed vright d’’’ ->
                                 Parsed (vleft + vright) d’’’
                             _ -> alt2
                     _ -> alt2
             _ -> alt2
    -- Additive <- Multitive
    alt2 = dvMultitive d

最后，我们创建一个特殊的“顶层”解析函数，以产生 Derivs 类型的实例，并“绑定”所有单独的解析函数之间的递归：

-- Create a result matrix for an input string
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 解析器的“魔法”就在这个双递归函数中。第一层递归是由 case 语句内的 parse 函数引用自身产生的。这种相对常规的递归形式用在输入字符串上逐字符地迭代，为每个输入位置产生一个 Derivs 实例。最终的 Derivs 实例，是一个空字符串，并带有 dvChar 结果 NoParse，其有效地终止结果矩阵中的那些列。

第二层递归是通过符号 d 产生的。此标识符命名要由解析函数构造和返回的 Derivs 实例，而且也是每个独立解析函数的参数。这些解析函数依次产生其余的分量形成每个 Derivs 对象。

当然，这种形式的数据递归仅在非严格语言下工作，其允许在相同对象的其他部分可用之前就访问对象的一些分量。例如，在由上述函数创建的任何 Derivs 实例中，可以在元组的任何其他分量可用之前访问 dvChar 组件。视图访问此元组的 dvDecimal 分量将引发 pDecimal 调用，而后者又使用 dvChar 分量，但不需要任何其他“更高层”的分量。访问 dvPrimary 分量将类似地调用 pPrimary，其可能访问 dvChar 和 dvAdditive。虽然在后的情况下，pPrimary 正在访问一个“更高层”的分量，但在这种情况下并不会创建一个循环依赖，因为它只是在一个不同的 Derivs 对象上调用 dvAdditive，即，在左括号后面位置的那个 Derivs 对象。可以用这种方式来延迟求值由解析产生的每个 Derivs 对象的每个分量。

3 图 3. 解析字符串 ‘2*(3+4)’ 产生的 Derivs 数据结构示意图

图 3 展示了解析器针对示例输入文本 ‘2 * ( 3 + 4 )’ 产生的数据结构，在完全聚集每个单元之后其将出现在现代功能计算机的内存中。每个垂直列表示带有五个 Result 分量的 Derivs 实例。对于形如 'Parsed v d' 的结果中，语义值 v 显示在适当的单元格中，并带有一个表示通向矩阵中另一个 Derivs 实例的“剩余”部分的指针箭头。在任何允许求值期间适当地保留共享关系的现代惰性语言实现中，图中的箭头将完全对应于堆中的指针，并且结构中的给定单元将永远不被求值两次。阴影框表示，在最左列 dvAdditive 结果是应用程序最终需要的唯一值的情况，下永远不会被求值的单元格。

此图可清楚说明为什么此算法在惰性求值下，对长度为 n 的输入字符串能在 O(n) 的时间内运行。顶层解析函数是创建 Derivs 类型实例的唯一函数，它总是创建正好 n + 1 个实例。解析函数只访问此结构中的项，而不是直接相互调用，并且每个函数在计算给定结果时最多检查固定数量的其他单元格。由于延迟求值确保每个单元格最多被求值一次，因此可提供关键的存储特性并且保证线性解析时间，即使求值这些结果的顺序可能完全不同于之前的表格化、从右到左、自底而上等算法。

3. 扩展算法

上一节提供了创建 Packrat 解析器所需的基本原理和工具，但为实际应用程序构建解析器涉及许多其他细节，其中一些细节受 Packrat 解析范式的影响。在本节中，我们将探讨一些更重要的实际问题，同时，将上面开发的示例基础上，逐步构造 Packrat 解析器。我们首先检查左递归这种恼人但又必须直面的问题。然后，我们解决词法分析的问题，将该任务无缝集成到 Packrat 解析器中。最后，我们探讨使用 Monad 组合器来更简洁地表达 Packrat 解析器。

3.1 左递归

与其他自顶向下解析方案一样，Packrat 解析也存在一个限制，即它不能直接支持左递归。例如，假设我们要对上面的例子添加一个减法运算符，并且加法和减法应该是正确的左相关。自然的方法是将 Additive 表达式的文法规则修改如下，并相应地改变解析器：

Additive  ←  Additive ‘+’ Multitive
          |  Additive ‘-’ Multitive
          |  Multitive

在此文法的递归下降解析器中，pAdditive 函数将用相同输入递归调用其自身，因此会陷入无限递归循环。在此文法的 Packrat 解析器中，pAdditive 将试图访问自己的 Derivs 元组的 dvAdditive 分量，即，其应该计算的同一个分量，从而形成了循环数据依赖。在任一解析器失败的情况下，尽管 Packrat 解析器的失败模式可能表现稍微“友好”些，因为现代懒惰求值机制经常会在运行时检测到循环数据依赖，但却无法检测到无限递归。

幸运的是，左递归文法总是可以被重写为等价的右递归文法，并且通过使用高阶函数作为中间解析器结果，可以很容易地重建期望的左相关语义行为。例如，为了使 Additive 表达式在示例解析器中为左相关，我们可以将这个规则分成两个非终结，Additive 和 AdditiveSuffix。pAdditive 函数识别单个 Multitive 表达式，后跟AdditiveSuffix：

pAdditive :: Derivs -> Result Int
pAdditive d = case dvMultitive d of
                Parsed vl d’ ->
                    case dvAdditiveSuffix d’ of
                        Parsed suf d’’ ->
                            Parsed (suf vl) d’’
                        _ -> NoParse
                _ -> NoParse

pAdditiveSuffix 函数采集中缀运算符和右侧操作数，并构建类型为 ‘Int → Int’ 的语义值，它接受左侧操作数并产生结果：

pAdditiveSuffix :: Derivs -> Result (Int -> Int)
pAdditiveSuffix d = alt1 where
    -- AdditiveSuffix <- ’+’ Multitive AdditiveSuffix
    alt1 = case dvChar d of
             Parsed ’+’ d’ ->
               case dvMultitive d’ of
                 Parsed vr d’’ ->
                   case dvAdditiveSuffix d’’ of
                     Parsed suf d’’’ ->
                       Parsed (\vl -> suf (vl + vr))
                              d’’’
                       _ -> alt2
                 _ -> alt2
             _ -> alt2
    -- AdditiveSuffix <- <empty>
    alt3 = Parsed (\v -> v) d

3.2 集成词法分析

传统的解析算法通常假定“原始”输入文本已经被单独的词法分析器部处理为符号流。然后，语法解析器将这些符号视为原子单位，即使每个符号可能表示多个连续的输入字符。这种分离通常是必要的，因为常规的线性时间解析器只能在其向前看决策中使用原始终结符，并且不能引用更高层的非终结符。这个限制在 2.2 节的自顶向下预测解析器中解释过，但是自底向上的 LR 解析器也依赖于类似的向前看符号机制，因此也有相同的问题。如果解析器只是在其向前看决策中使用原子符号，那么若这些符号表示所有关键字、标识符和字面量而不只是原始字符，则解析会变得更容易。

然而，Packrat 解析没有这样的向前看的限制。因为， Packrat 解析器体现了真正的回溯模型，所以在解析函数中选择替代式的决策，可取决于由其他解析函数产生的完整结果。因此，词法分析可以无缝集成到 Packrat 解析器中，而无须特殊处理。

要将 Packrat 解析器示例扩展为支持“实际的”词法分析，我们向 Derivs 类型添加一些新的非终结符：

data Derivs = Derivs {
                -- Expressions
                dvAdditive :: Result Int,
                ...
                -- Lexical tokens
                dvDigits :: Result (Int, Int),
                dvDigit :: Result Int,
                dvSymbol :: Result Char,
                dvWhitespace :: Result (),
                -- Raw input
                dvChar :: Result Char}

pWhitespace 解析函数会消耗可分隔词法符号的任何空格：

pWhitespace :: Derivs -> Result ()
pWhitespace d = case dvChar d of
                  Parsed c d’ ->
                    if isSpace c
                    then pWhitespace d’
                    else Parsed () d
                  _ -> Parsed () d

在一个更完善的语言中，此函数也可以带上吃掉注释的任务。由于 Packrat 分析的所有能力都可用于词法分析，因此注释也可有自身的复杂分层结构，诸如嵌套或字面量标记编程。由于未将语法识别分离为单向流水线，词法构造甚至可以“向上”引用为更高层次的语法元素。例如，语言的语法可以允许标记嵌入在注释中的标识符或代码片段，因此解析器可以找到并将其作为实际表达式或语句进行分析，从而使智能软件工程工具更有效。类似地，字符串字面量中的转义序列可以包含表示静态或动态替换的通用表达式。

pWhitespace 示例还说明了在 Packrat 解析器中如何方便地实现常见的最长匹配消出二义性规则，这些都难以在纯粹的上下文无关文法中表示。更复杂的决策和消除二义性策略也很容易实现，包括通用的语法断言，可基于不实际消耗输入文本的向前看信息，来影响语法解析决策。例如，使用 followed-by 和 notflowed-by 规则，仅当匹配其他任意非终结符后面的文本匹配（或不匹配）后跟规则时，才使用该替代式来解析。这类语法断言通常需要无限向前看，因此，超出了大多数其他线性时间解析算法的能力。

继续词法分析示例，函数 pSymbol 识别由运算符字符后跟可选空格组成的“运算符符号”：

-- Parse an operator followed by optional whitespace
pSymbol :: Derivs -> Result Char
pSymbol d = case dvChar d of
              Parsed c d’ ->
                if c ‘elem‘ "+-*/%()"
                then case dvWhitespace d’ of
                       Parsed _ d’’ -> Parsed c d’’
                       _ -> NoParse
                else NoParse
              _ -> NoParse

现在我们修改表达式的高层解析函数，使用 dvSymbol 而不是 dvChar 来扫描运算符和括号。例如，pPrimary 可以实现如下：

-- Parse a primary expression
pPrimary :: Derivs -> Result Int
pPrimary d = alt1 where

    -- Primary <- ’(’ Additive ’)’
    alt1 = case dvSymbol d of
             Parsed ’(’ d’ ->
               case dvAdditive d’ of
                 Parsed v d’’ ->
                   case dvSymbol d’’ of
                     Parsed ’)’ d’’’ -> Parsed v d’’’
                     _ -> alt2
                 _ -> alt2
             _ -> alt2

    -- Primary <- Decimal
    alt2 = dvDecimal d

此函数演示了解析决策不仅取决于在给定的位置是否存在非终结符（例如 Symbol ）的匹配，而且还取决于与该非终结符相关联的语义值。在这种情况下，即使所有符号记号被解析在一起并由 pSymbol 统一处理，其他规则（如 pPrimary）仍然可以区分特定符号。在更复杂的包含多字符运算符、标识符和保留字的语言中，由记号解析器产生的语义值可以是 String 而不一定是 Char，但是这些值可以相同的方式匹配。语法对语义值的依赖性，被称为语义断言，其在实践中提供了非常强大和有用的功能。与语法断言一样，语义断言通常需要无限向前看能力，而且不能通过常规解析算法来实现，除非放弃其线性时间保证。

3.2 Monad 式 Parkrat 解析

在 Haskell 等功能语言中构建解析器熟知的方法是使用 Monad 组合器。不幸的是，Monad 通常会带来性能损失，让 Packrat 解析难以权衡。目前描述的 Packrat 解析器的实现，是假设可以静态地知道一组非终结符及其对应的结果类型，因此将其绑定在单个固定元组中，以形成 Derivs 类型。通过组合从其他 Packrat 解析函数动态构造整个 Packrat 解析器，需要 Derivs 类型的动态查找结构，以便将一组可变的非终结符与相应的结果关联。这种方法会更慢，空间效率更低。

有个更实用的策略，可提供最便利的组合器且没有明显的性能损失，就是使用 Monad 来定义 Packrat 解析器中的各个解析函数，同时保持之前的 Derivs 类型和静态实现的“顶层”递归。

既然我们想直接使用组合器来构建解析函数，明显的方法就是让组合器用一个简单的类型别名来处理：

type Parser v = Derivs -> Result v

不幸的是，为了利用 Haskell 的有用的 do 语法，组合器必须使用特殊类 Monad 的类型，而简单别名不能指定类的型类。我们必须将解析函数包装成一个“真正的”用户定义类型：

newtype Parser v = Parser (Derivs -> Result v)

现在，我们可以实现具有 Haskell 标准的数列 (>> =)、产生结果 (return) 和产生错误功能的组合器：

instance Monad Parser where
        (Parser p1) >>= f2 = Parser pre
                where pre d = post (p1 d)
                      post (Parsed v d’) = p2 d’
                        where Parser p2 = f2 v
                      post (NoParse) = NoParse
        return x = Parser (\d -> Parsed x d)
        fail msg = Parser (\d -> NoParse)

最终，我们需要一个交替组合器来解析：

(<|>) :: Parser v -> Parser v -> Parser v
(Parser p1) <|> (Parser p2) = Parser pre
                where pre d = post d (p1 d)
                      post d NoParse = p2 d
                      post d r = r

除了用于识别特定字符的这些组合器之外，在原来 Packrat 解析器示例中的 pAdditive 函数可以写为如下形式：

Parser pAdditive =
            (do vleft <- Parser dvMultitive
                char ’+’
                vright <- Parser dvAdditive
                return (vleft + vright))
        <|> (do Parser dvMultitive)

很容易为更高层次的子句构建额外的组合器，例如，反复和中缀表达式。然而，在 Packrat 解析函数内使用迭代组合器违反了这样的假设：一旦来自其所依赖的任何其他单元的结果可用，则应该在恒定时间内计算结果矩阵中的每个单元。迭代组合器有效地创建了“隐藏”递归，其中间结果并未记忆在结果矩阵中，潜在地导致解析器超出线性时间运行。第 6 节中的结果将表明，这一问题在实践中并不严重，但在使用迭代组合器时应该考虑到这一点。

本文的在线示例包括一个全功能的 Monad 组合器库，可以方便地构建大型 Packrat 解析器。这个库基本上受到 PARSEC 的启发，不过 Packrat 解析组合器简单得多，因为它们不必实现单独的词法分析或传统自顶向下解析器的向前看一个符号的预测机制。完整的组合器库提供了各种“安全”的恒定时间组合器，以及一些“危险”的迭代器，不一定要用，但却可以方便构造解析器。此组合器库可以与具有不同 Derivs 类型的多个解析器同时使用，并且支持用户友好的错误检测和报告。

4. 与 LL 和 LR 解析的对比

前面的章节作为一个如何构建 Packrat 解析器的教程，接下来，我们转向 Packrat 解析在实践中的使用问题。本节将通俗地更深入探讨 Packrat 解析的语言识别能力，并阐明其与传统的线性时间算法如 LL(k) 和 LR(k) 的关系。

虽然 LR 解析通常被看作比有限向前看的自顶向下或 LL 解析“更强大”，但这些解析器可以识别的语言类是相同的。正如 Pepper 指出的那样，LR 解析可以被简单地视为经过重写语法的 LL 解析，以消除左递归和尽量推迟所有重要的解析决策。结果是 LR 提供了更多表达文法方式的灵活性，但并未增加实际语言识别能力。为此，我们将 LL 和 LR 解析器看作基本上是相等。

4.1 向前看机制

Packrat 解析和 LL / LR 解析之间最关键的实际差异是向前看机制。Packrat 解析器可基于直到输入字符串结束的所有文本中的任意点进行决策。虽然解析矩阵中的单个结果的计算，只能执行恒定数量的“基本操作”，但是在解析矩阵中包含了这些基本操作可追寻的前向指针，每个指针都可以一次跳过大量的文本。因此，LL 和 LR 解析器只能向前看输入中恒定数量的终结符，但是 Packrat 解析器可按任何组合方式来向前看恒定数量的终结符和非终结符。解析决策可使用任意非终结符的能力，就赋予了 Packrat 解析无限向前看的能力。

为了阐明语言识别能力的差异，下列 k 为任意值的非 LR(k) 文法，对 Packrat 解析器来说根本不是问题：

S ←  A | B
A ←  x A y | x z y
B ←  x B y y | x z y y

一旦 LR 解析器在上述语言的字符串中遇到 'z' 和第一个随后的 'y'，它必须立即决定是否通过非终结符 A 或 B 开始规约，但在遇到更多 'y' 之前，根本无法做出这个决定，因为左侧有 ‘x’。而 Packrat 解析器基本上以推导方式操作，在扫描输入时同步为非终结符 A 和 B 产生推导。A 和 B 之间的最终决定被有效地推迟到整个输入字符串被解析，其中该决定仅仅是检查哪个非终结符在该位置具有成功结果的问题。从左到右镜像交换上述文法也不会改变这一情况，这清楚地表明，区别不仅仅是 LR 从左到右扫描输入的某些副作用，而 Packrat 解析似乎是反向操作。

4.2 文法对比

当为实际语言设计解析器时，常常会感觉到 LR 解析因固定数目向前看机制的限制，并且这些限制事实上源于 LL 和 LR 语法不是完全可组合的。例如，下列表示的表达式和赋值的简单语言的文法，只允许赋值左侧的简单标识符：

S ←  R | ID ‘=’ R
R ←  A | A EQ A | A NE A
A ←  P | P ‘+’ P | P ‘-’ P
P ←  ID | ‘(’ R ‘)’

若符号ID、EQ和NE是终结符，即，由独立词法分析阶段产生的原子符号，则 LR(1) 解析器处理该文法就不会有麻烦。但是，如果我们尝试使用以下更简单规则，以符号化过程集成到解析器本身中，则不再是 LR(1) 的文法：

ID ←  ’a’ | ’a’ ID
EQ ←  ’=’ ’=’
NE ←  ’!’ ’=’

问题是，在扫描标识符之后，LR 解析器必须立即决定其是一个主表达式还是一个赋值的左侧，却只能仅仅基于紧接其后的符号。但是，若这个符号是 '='，解析器就无法知道它是一个赋值运算符还是一个 '==' 运算符的前半部分。在这种特定情况下，文法只能用 LR(2) 解析器解析。实践中，k>1 的 LR(k) 甚至LALR(k) 解析器并不常见。最近开发的对传统的从左至右解析算法的某些扩展，稍微改善了这种情况，但是它们仍然无法提供无限向前看能力，还要同时保证线性时间的运行。

即使当词法分析与解析分离时，LR 解析器的限制也通常在其他实际情况中频繁出现，其结果却是文法演进中看似无害的改变。例如，假设我们要向上述语言添加简单的数组索引，以便数组索引运算符可以出现在赋值的左侧或右侧。可能的方法是添加一个新的非终结符 L 来表示左侧或“左值”表达式，并将数组索引运算符合并到两种类型的表达式中，如下所示：

S ←  R | L ‘=’ R
R ←  A | A EQ A | A NE A
A ←  P | P ‘+’ P | P ‘-’ P
P ←  ID | ‘(’ R ‘)’ | P ‘[’ A ‘]’
L ←  ID | ‘(’ L ‘)’ | L ‘[’ A ‘]’

即使再次将 ID、EQ 和 NE 符号当作终结符，该文法也不是 k 为任意值的 LR(k) ，因为在解析器看到标识符之后，它必须立即决定它是 P 还是 L 表达式的一部分，但直到后面任意数组索引运算符被完全解析之前，都没有办法知道这一点。然而，Packrat 解析器对于该文法却没有问题，因为它有效地 “同步” 求值 P 和 L 替代式，并且在需要做出关键判定时有完整的推导（或知道缺少推导）。

总之，Packrat 解析器的文法是可组合的，因为 Packrat 解析器在替代式之间做出决策时，可考虑向前看任意非终结符，诸如第一个例子中的 EQ 或第二个例子中的 P 和 L。由于 Packrat 解析器不会像 LL 或 LR 解析器那样，给“原始”语法结构（终结符）赋予了任何特殊含义，因此，出现在文法中的任何终结符或固定的终结符序列都可以用非终结符替换，而不会“破坏”解析器。这种替换能力使 Packrat 解析具有更大的组合灵活性。

4.3 识别限制

假设 Packrat 解析器可以在线性时间内识别比 LL(k) 或 LR(k) 算法更广泛的语言类型，那么，什么样类型的文法不能由 Packrat 解析器识别呢？虽然此算法理论上的精确能力还没有被彻底地表征，但是下面这个平常和无二义性的上下文无关文法的示例，对 Packrat 解析器以及对同样的 LL 或 LR 解析器来说，都证明是有问题的：

S ←  x S x | x

几种解析器处理这种文法的问题是，在扫描字符串中的那些 ‘x’ 时（LR 是从左至右，Packrat 是从右至左）， 该算法必须以某种方式提前“知道”字符串的中间位置在哪，以便可在该位置应用第二个替代式，然后对于输入流的其余部分使用第一个替代式来“另外构建”。然而由于输入流是完全同质的，所以解析器没有办法找到中间位置，直到整个输入被解析。因此，该文法给出的示例（尽管是故意设计的），需要更通用的非线性时间的 CFG 解析算法。

5. 实际问题和限制

虽然 Packrat 解析对于许多应用程序是强大和有效的，但在某些情况下并不适合，主要有三个问题。首先，Packrat 解析只能用于构造确定性解析器：解析器最多只能产生一个结果。其次，Packrat 解析器的效率取决于它几乎或完全是无状态的。最后，由于它需要依靠存储空间，Packrat 解析本质上是空间密集型的。本节将讨论这三个问题。

5.1 确定性解析

我们到目前为止的一个重要假设是，构建 Packrat 解析器的每个相互递归的解析函数，将确定性地返回最多一个结果。如果在用来构建解析的文法中有任何二义性问题，那么解析函数必须要能够自行在本地解决。在本文开发的示例解析器中，多个替代式通常按其测试顺序隐式地消除了二义性：第一个成功匹配的就是要使用的替代式，而不管任何其他后续替代式是否也可匹配成功。这种行为既容易实现也有助于执行最长匹配和其他的显式局部消除二义性规则。解析函数甚至可以尝试所有可能的替代式，并且如果多于一个替代式匹配，则产生失败结果。Packrat 解析器中的解析函数做不到返回多个结果，以用在随后的全局策略中同步处理和消除二义性。

在设计给机器使用的语言中，多个匹配替代式在本地消除二义性的要求，在实践中并不是很大的问题，首先由于二义性通常是不期望的，并且本地消除二义性规则往往优选于全局消除二义性规则，因为这对于人类更容易理解。然而，对于解析自然语言或其他期望全局模糊性的文法，Packrat 解析可能用处不大。尽管在经典的非确定性自顶向下的解析器中，解析函数返回的结果列表也可用类似的方式被记忆，但是所得到的解析器将不是线性时间的，这更应该与处理二义性的上下文无关文法的表格解析算法去比较。由于非确定性解析在计算复杂性上等同于布尔矩阵乘法，因此不太可能找到对这个更一般问题的线性时间处理的解决方案。

5.2 无状态解析

Packrat 解析的第二个限制是其从根本上就是面向无状态的解析。Packrat 解析器的记忆系统假定每个非终结符的解析函数仅依赖于输入字符串，而不依赖于在解析过程中累积的任何其他信息。

虽然纯粹的上下文无关语法是定义为无状态的，但是许多实际语言在解析时需要状态的概念，因而也不是真正的上下文无关。例如，C 和 C ++ 要求解析器在声明类型时逐渐构建类型名称的表，因为解析器必须能够区分类型名称与其他标识符，以便正确解析后续文本。

传统的自顶向下 (LL) 和自底向上 (LR) 解析器在解析时保持状态并没有什大麻烦。由于其仅仅对输入执行单一的从左到右扫描，并且从不向前看超过一个或至多几个标记，因此当发生状态改变时什么也没有“丢失”。相反，Packrat 解析器为了其无限向前看能力的效率，需要依赖无状态性。虽然可以构造有状态的 Packrat 解析器，但是解析器必须在每次解析状态改变时，开始构建新的结果矩阵。由于这个原因，如果状态变化频繁发生，则有状态的 Packrat 解析可能是不切实际的。有关带状态的 Packrat 解析的详细信息，请参考我的硕士论文。

5.3 空间消耗

可能 Packrat 解析器最显着的特性是，它确实储存了其已经计算的关于输入文本的一切，包括整个输入文本自身。因此，Packrat 解析存储的需求总是等于输入大小常数倍的一些可能的用量。相比之下，LL(k)、LR(k) 和简单回溯解析器可以设计为空间消耗仅随着输入中出现的语法结构的最大嵌套深度而增长，这在实践中通常小于文本的总大小。尽管 LL(k) 和 LR(k) 解析器在用于任意不规则语言的在最坏情况下，仍然有线性空间的要求，但是这种“平均情况”的差异在实践中可能是重要的。

减少推导结构空间需求的一种方法是，将 Derivs 类型拆分为多个级别，特别是在有许多非终结符文法的语法解析器中。例如，假设一种语言的非终结符可以被分组成若干大类，诸如词法记号、表达式、语句和声明。这时，Derivs 元组本身除了 dvChar 之外可能只有四个分量，每个非终结符类别一个。这些分量中的每一个又是包含该类别中的所有非终结符结果的元组。对于表示“在符号之间”的字符位置的大多数 Derivs 实例，将不会对表示非终结符类别的分量进行求值，因此只有小的顶级对象和未求值其分量的闭包会占用空间。即使对于对应符号开始的 Derivs 实例，通常仅需要来自一个或两个类别的结果，这取决于在那个位置处是什么类型的语言结构。

即使用了这种优化策略，Packrat 解析器也将消耗比原始输入文本大小多许多倍的工作存储。因此，在某些应用程序领域，Packrat 解析可能不是最好的选择。例如解析 XML 数据流时，其解析结构相当简单但通常会编码大量相对平坦的机器生成的数据，就不需要 Packrat 解析的能力和灵活性，因其存储成本并不合理。

另一方面，为了解析复杂的现代编程语言，其源代码通常由人写，语言的能力和表现力是最高优先级，Packrat 解析的空间成本可能是合理的。标准编程实践包括将大型程序分解成大小可管理的可独立编译的模块，并且在解析时展开典型的 10-100KB 源文件时，现代机器的主内存大小至少应保留有三个数量级的余量。即使在解析更大的源文件时，由于实际语言强结构的局部性特点，工作集仍可能相对较小。最后，由于在解析完成后可以丢弃整个推导结构，因而，如果其结果被馈送到需要与 Packrat 解析器使用一样多的空间的某些其他复杂计算，例如全局优化器，解析器的空间消耗可能是无关紧要的。第 6 节将证明这种空间消耗在实践中是合理的。

6. 性能效果

虽然详细分析 Packrat 解析的经验超出了本文的范围，但在提交新的和不熟悉的解析范式之前，了解 Packrat 解析器在实践中的表现如何，可能会很有帮助。

6.1 空间效率

第一组测试测量 Packrat 解析器处理 Java 编程语言的空间效率。我为这个实验选择 Java，是因为它有一个丰富而复杂的文法，但是仍然采用了相当干净的语法范式，不需要像 C 和 C++ 解析器那样保持关于声明类型的状态，也不需要像 Haskell 的布局方案那样，要求在词法和层次之间执行特殊解析。

实验采用了两个不同版本的 Java 解析器。除了规范换行符和 Java 的 Unicode 转义序列的简单预处理阶段，两个解析器的词法分析都是完全集成的，如第 3.2 节所述。一个解析器在其词法分析函数中使用 Monad 组合器，而另一个解析器仅依赖于原始的模式匹配。两个解析器都使用 Monad 组合器来构造所有更高阶的解析函数。两个解析器还使用了第 5.3 节中描述的将 Derivs 元组分成两级的技术，以便增加模块性和减少空间消耗。解析器使用 Glasgow Haskell 编译器的 5.04 版本进行编译，并打开了优化和分析。GHC 的堆分析系统用于测量活堆利用率，排除未使用的堆空间和可收集的垃圾。

测试套件包括 Cryptix 库的 60 个未修改的 Java 源文件，因为其包括大量相对较大的 Java 源文件。Java 源文件平均较小，因为编译模型鼓励程序员将每个类定义在单独的文件中。

4 图 4. 最大堆大小与输入大小关系图

图 4 展示了每个解析器的最大活堆大小与要解析的输入文件大小的关系图。由于解析一些较小的源文件如此迅速，垃圾回收从未发生，堆分析机制没有产生任何样本，因此该图只包含完全 Monad 解析器的 45 个数据点，和直接模式匹配词法分析的混合解析器的 31 个数据点。整个测试套件平均情况下，完全 Monad 解析器对每个输入字节使用 695 字节的活堆，而混合解析器对每个输入字节只使用 301 字节的堆。结果是令人鼓舞的：虽然 Packrat 解析会消耗大量的空间，拥有 128KB 以上 RAM 的典型现代机器解析 100-200KB 的源文件应该没有问题。此外，即使两个解析器用了一些迭代 Monad 组合器，这在理论上可以破坏线性时间和空间保证，但是解析器的空间消耗还是表现为线性地增长。

使用 Monad 组合器显然在空间效率方面具有实质性的损失。修改解析器以使用直接模式匹配可以有进一步的改善，由于词法分析的成本往往把持解析器的其余部分，其改善程度难以预测。混合解析器的词法分析部分大约等效于 Monad 解析器部分的两倍，其暗示虽然单独使用模式匹配来编写 Packrat 解析器在某种程度上是比较笨的，但在效率很重要时也不是不合理。

6.2 解析性能

第二个实验测量两个 Packrat 解析器的绝对执行时间。对于这个测试，解析器由 GHC 5.04 编译优化，但关闭分析，并在运行 Linux 2.4.17 的 1.28GHz AMD Athlon 处理器上计时。在此测试中，我只使用测试套件中大于 10KB 的 28 个源文件，因为较小的文件被解析太快，以至于超出 Linux 时间命令计时精度。

5 图5. 运行时间与输入大小关系图 图 5 展示了根据源文件大小绘制的执行时间结果。在这些输入上，完全 Monad 解析器平均为 25.0KB/s，标准偏差为 8.6KB/s，而混合解析器平均为 49.8KB/s，标准偏差为 16KB/s。

为了提供 Packrat 解析和更传统的线性时间算法之间合理的性能比较，我将 Java 免费可用的 YACC 文法转换为 Happy（一个 Haskell 的 LR 解析生成器）的文法。不幸的是，GHC 无法编译由这种文法产生的 230KB Haskell 源文件，而且是在未做优化并有 1GB 内存的机器上。 这些困难又提高了之前建议的可信度：在现代编译器中，Packrat 解析器的临时存储成本很可能被后续阶段的存储成本所超过。然而，生成的 LR 解析器却能在 Haskell 的 Hugs 解释器下工作。因此，为了提供粗略的性能比较，我在 80MB 大小的堆的 Hugs 下 用 LR 和 Packrat解析器分别执行五个较大的 Java 源文件的解析。为了公平起见，我只将 LR 解析器与较慢完全 Monad 的 Packrat 解析器进行对比，因为 LR 解析器使用了从后面的 Packrat 解析器导出的 Monad 词法分析器。这样，词法分析性能应该是可比较的，而且只有解析算法才是最重要的。

在 Hugs 下，LR 解析器始终执行约两倍的减少数量，并分配55％的总堆存储量。我找不到一种方式来配置在 Hugs 下的活堆利用率，而不是总分配量。然而，实际执行时间的差异很大：LR 解析器在较小的文件上花费了将近两倍的时间，但是在最大的文件上执行大约相同的时间。这种差异的一个可能原因是受垃圾回收的影响。由于随着时间的推移，运行的 Packrat 解析器自然会具有比 LR 解析器高得多的数据垃圾比率，而且当存在更多的实时数据时，垃圾收集开销增加了成本并且降低了有效性（释放更少的空间），当源文件大小增长时，垃圾收集对 Packrat 解析器的打击可能比对 LR 解析器更大。仍然，令人鼓舞的是，Packrat 解析器能够在除最大的 Java 源文件之外的所有其他文件解析上胜过 LR 解析器。

7. 相关工作

本节简要回顾 Packrat 解析的前期工作。关于 Packrat 解析与其他算法相比的更多细节，请参考我的硕士论文。

Birman 和 Ullman 最首开​​发了具有回溯确定性解析算法形式上的特征。这项工作由 Aho 和 Ullman 继续完善，并被归类为“自顶向下有限回溯解析”，参考每个解析函数可以产生至多一个结果的限制，从此回溯可被本地化。他们展示了这种解析器，正式名为广义自顶向下解析语言（GTDPL）解析器，相当强大。GTDPL 解析器可以模拟任何下推自动机，从而可识别任何 LL 或 LR 语言，甚至可以识别一些不是上下文无关的语言。然而，由左递归导致的所有“失败”是可以检查和从 GTDPL 文法中消除的，从而确保算法是良好的。Birman 和 Ullman 也指出了通过表格结构来构造线性时间 GTDPL 解析器的可能性，但是这种线性时间算法显然从未投入实践，毫无疑问，因为主内存在当时更加有限，编译器不得不像流式过滤器那样操作，以在接近恒定空间中运行。

最近， Adams 在认识到 GTDPL 与 LR 算法相比有更出色的可组合性自后，将 GTDPL 解析复活为模块化语言原型框架的一个组件。此外，许多实用的自顶向下的解析库和工具包，包括流行的 ANTLR 和 Haskell 的 PARSEC 组合器库，也提供了类似的有限回溯能力，以便解析器设计者可以选择性地调用来克服预测解析的限制。然而，所有这些解析器都以没有记忆的传统递归-下降方式来实现回溯，最坏情况解析将产生指数时间的危险，并且由此使得依赖回溯作为预测的替代或者集成词法分析与解析成为不切实际的方案。

唯一有效支持集成词法分析或“无扫描器解析”的线性时间解析算法是 NSLR(1) 算法，其最初由 Tai 创建的，并且由 Salomon 和 Cormack 有目的地投入实践。通过增加基于非终结符来做出向前决策的有限支持，该算法扩展了传统的 LR 类算法。Packrat 解析相对于 NSLR(1) 的能力并不清楚：Packrat 解析对右侧向前看限制较少，而 NSLR(1) 也可以考虑左侧上下文。实际上，NSLR(1) 可能更节省空间，但 Packrat 解析更简单明了。最近的其他无扫描器解析器都是放弃线性时间确定性的算法，偏爱虽然更通用但却很慢的，可容忍二义性的 CFG 解析。

8. 未来的工作

虽然，这里给出的结果展示了 Packrat 解析的强大功能和实用性，但需要更多的实验来评估其在更多种语言上的灵活性、性能和空间消耗。例如，广泛依赖解析器状态的语言（诸如 C 和 C++）以及布局敏感的语言（诸如ML和Haskell），这可能让 Packrat 解析器的有效地处理变得更加困难。

另一方面，实际语言的语法通常是考虑用特定的解析技术而设计的。出于这个原因，一个同样引人注目的问题是，使用 Packrat解析“自由”的无限向前看和无限制的文法组合能力，可能创造设计出什么样的新语法。第 3.2 节提出了一些依赖于集成词法分析的简单扩展的建议，但在文法组合灵活性很重要的语言中，Packrat 解析可能更有用。

虽然 Packrat 解析简单到足以用惰性函数语言手工实现，但是在 C 语言中的 YACC 或 Haskell 中的 Happy 和 M'ımico 的语法编译器中仍然有实际的好处。除了解析函数本身，语法编译器可以自动生成静态“推导”元组类型和顶层递归“绑定”函数，消除了第 3.3 节中讨论的 Monad 表示的问题。编译器还可以将诸如流行的 '+' 和 '*' 重复操作符的迭代记号降级为仅使用原始固定实践操作的低层次文法，从而保持线性解析时间。 最后，编译器可以重写左递归规则，使其更容易在文法中表达左相关结构。

一个让 Packrat 解析可能有难度但很值得进一步研究的实用领域是解析交互流。例如，语言解释器中的 REPL (read-eval-print-loop)，通常期望解析器在每行结束时检测是否需要更多的输入来完成当前语句，而这种要求违反了 Packrat 算法的假设：整个输入流应该是预先可用的。类似的开放问题是，在什么条件下 Packrat 解析可能适合于解析无限流。

9. 总结

Packrat 解析是一个简单而优雅的方式，将非严格函数式编程语言实现的回溯递归下降解析器，转换为线性时间解析器，同时并未无限向前看的能力。该算法依赖于非严格函数语言直接表达具有复杂依赖性的递归数据结构的能力的简单性，并且其实际效率依赖于惰性求值。Packrat 解析器可以识别用于常规确定性线性时间算法可的任何语言及其任何不能适用的语言，可提供较好的组合特征，并允许将词法分析和语法解析进行集成。该算法的主要限制是，其仅支持确定性解析，以及需要考虑较多的（渐近线性）存储空间。

leadzen commented 7 years ago

累死我啦 ...