65.9K
CodeProject 正在变化。 阅读更多。
Home

Loyc LL(k) 解析器生成器：第二部分

Qwertie
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.98/5 (19投票s)

2013年11月26日

LGPL3

33分钟阅读

viewsIcon

56427

downloadIcon

306

适用于 C# 的新解析器生成器：现已支持语法高亮显示。

引言

不熟悉 LLLPG？请从第 1 部分开始。

在本系列文章中，我将不仅教大家如何使用我的解析器生成器，还会讲解更广泛的知识，例如：有哪些类型的解析器生成器？什么是歧义，我们如何处理它？什么是终结符？因此，在本文中，我将从对解析术语和解析技术的通用讨论开始，然后向大家介绍 LLLPG 的一些有用的核心功能。

注意：如果您想知道如何配置 LLLPG 或如何组织您的源代码，请访问第 3 部分（“配置 LLLPG”，“样板代码”），然后再返回此处。

注意：语法高亮显示扩展是下载中的LLLPG.NET40\LoycSyntaxForVs.vsix。它支持LES (Loyc Expression Syntax) 和 增强型 C#，并在 Visual Studio 2010 到 2015 中运行。更重要的是，自定义工具 LoycFileGeneratorForVs.exe 支持 VS 2008 到 VS 2015，包括 Express 版本，如果您想知道它是如何制作的，我写了整篇文章。

今日目录

  1. 您真的需要解析器生成器吗？
  2. 解析术语：如果您已经了解了终结符和可空项等概念，请跳过此项。
  3. LL(k) 与竞争对手对比：在第 1 部分中，您对 LL(k) 的含义有了一定的了解（仅基于 k 个向前查看标记来选择语法路径，k >= 1）。这次我将比较 LL(k) 与 LALR(1) 和 PEG 等替代方法。如果您已经了解或不关心替代解析模型，请跳过此项。
  4. 学习 LLLPG，带数字示例：本节介绍语法谓词、语义谓词、门、下划线和波浪线，以及 [k] 属性。
  5. 总结.

您真的需要解析器生成器吗？

任何解析器生成器最常见的入门示例之一就是表达式解析器或计算器，就像上一篇文章中捆绑的这个计算器一样。

LLLPG parser(laType(int)) // LES version
{
    rule Atom()::double @[
        { result::double; }
        ( t:=id           { result = Vars[t.Value -> string]; }
        | t:=num          { result = t.Value -> double; } 
        | '-' result=Atom { result = -result; }
        | '(' result=Expr ')'
        | error           { result = 0; 
          Error(InputPosition, "Expected identifer, number, or (stuff)"); }
        )
        { return result; }
    ];
    rule MulExpr()::double @[ 
        result:=Atom
        (op:=(mul|div) rhs:=Atom { result = Do(result, op, rhs); })*
        { return result; }
    ];
    rule AddExpr()::double @[
        result:=MulExpr
        (op:=(add|sub) rhs:=MulExpr { result = Do(result, op, rhs); })*
        { return result; }
    ];
    rule Expr()::double @[
        { result::double; }
        ( t:=id set result=Expr { Vars[t.Value.ToString()] = result; }
        | result=AddExpr )
        { return result; }
    ];
};

def Do(left::double, op::Token, right::double)::double
{
    switch op.Type {
        case add; return left + right;
        case sub; return left - right;
        case mul; return left * right;
        case div; return left / right;
    };
    return double.NaN; // unreachable
};

但如果表达式解析是您唯一需要的，您就不需要解析器生成器了；有更简单的解析方法，例如使用类似这样的 Pratt 解析器。如果您只需要解析简单的文本字段（如电话号码），您可以使用正则表达式。即使您需要完整的编程语言，也不一定需要自己创建；例如，您可以重用 Loyc.Syntax.dll 中附带的 LLLPG 的 LES 解析器（它还不是 100% 完整，但对于 LLLPG 来说已经足够可用了），如果您不重用解析器，您仍然可能想重用词法分析器。

因此，在您开始编写解析器之前，尤其是在编写重要的内容而不是“为了好玩”时，请认真考虑现有解析器是否足够。如果您对 LES、Loyc 树或使用 Loyc 库（Loyc.Essentials.dll、Loyc.Collections.dll 等）有任何疑问，请告诉我。

解析术语

我将从简短的解析术语词汇表开始。

首先，语法由终结符和非终结符组成。

终结符是输入中的一个项；当您定义词法分析器时，终结符是单个字符，当您定义解析器时，终结符是来自词法分析器的标记。更具体地说，语法仅关注标记的类型，而不关注其值。例如，您的标记类型之一可能是 Number，解析器不能特殊处理某个数字；因此，如果您需要区分数字“0”和其他数字，那么您的词法分析器就必须为此数字创建一个特殊的标记类型（例如 Zero），因为语法不能基于标记的值来做决策。注意：在 LLLPG 中，如果需要，您可以规避此规则，但这并不美观。

非终结符是语法中的一个规则。因此，在本例语法中

token Spaces @[ (' '|'\t')+ ];
  token Id @[
    ('a'..'z'|'A'..'Z'|'_')
    ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*
  ];
  token Int @[ '0'..'9'+ ];
  token Token @[ Spaces | Id | Int ];

非终结符是 Spaces、Id、Int 和 Token，而终结符是诸如 's'、'\t'、'9' 等输入。

关于解析的传统文献假定存在一个单一的“起始规则”，代表整个语言。例如，如果您想解析 C#，起始规则会说“零个或多个 using 语句，后跟零个或多个命名空间和/或类”。

rule Start @[ UsingStmt* TopLevelDecl* ];
rule TopLevelDecl @[ NamespaceStmt | TypeDecl ];
...

但是，LLLPG 比这更灵活。它不限制您只有一个起始规则；相反，LLLPG 假定您可能从任何未标记为 private 的规则开始。毕竟，您可能只想解析语言的一个子集，例如方法声明、单个语句或单个表达式。

LLLPG 规则以一种不太标准的方式表达语法。首先，LLLPG 表示法基于 ANTLR 表示法，而 ANTLR 表示法本身与 EBNF（扩展巴科斯-瑙尔范式）略有不同，在某些圈子里，EBNF 被认为更标准。此外，由于 LLLPG 嵌入在另一种编程语言（LES 或 EC#）中，它使用 @[...] 表示法，意为“标记文字”。标记文字是标记的序列，不被宿主语言解释；宿主语言仅确定“标记文字”的边界并保存标记，以便 LLLPG 以后可以使用它们。因此，EBNF 中的规则可能如下所示

Atom = ['-'], (num | id);

LLLPG 中的相同规则如下所示

rule Atom @[ ('-')? (num | id) ];

在 EBNF 中，[Foo] 表示 Foo 是可选的，而 LLLPG 使用 Foo? 来表示相同的概念。某些版本的 EBNF 使用 {Foo} 来表示零个或多个 Foo 的列表，而 LLLPG 使用 Foo* 来表示相同的内容。

在 LLLPG 中，与 ANTLR 一样，{...} 表示一个正常的代码块（C#），因此大括号也不能表示列表。在 LLLPG 1.0 中，我决定支持 ANTLR 和 EBNF 风格之间的折衷：允许您编写 [...]? 或 [...]* 而不是 (...)? 或 (...)*；? 或 * 后缀仍然是必需的。因此，方括号表示可空性——方括号内的区域可能不消耗任何输入。

替代和分组在 LLLPG 和 EBNF 中的工作方式相同（例如 (a | b)），尽管 LLLPG 还提供 (a / b) 表示法，我将在后面解释。

此外，一些语法表示法不允许循环，甚至不允许可选项。例如，形式的“四元组”语法就是这样定义的。我在我的博客文章《语法：理论与实践》中进一步讨论了这一点。

“语言”与“语法”是不同的概念。语法代表某种语言，但通常有多种可能的语法可以代表同一种语言。“语言”一词指的是被认为是有效的句子集合；两种不同的语法代表同一种语言，如果它们接受或拒绝相同的输入（或者反过来看，如果可以从两种语法生成相同的“句子”集合）。例如，以下四条规则都代表数字列表。

rule Digits1 @[ '0'..'9'+ ];
rule Digits2 @[ '0'..'9'* '0'..'9' ];
rule Digits3 @[ '0'..'9' | Digits3 '0'..'9' ];
rule Digits4 @[ ('0'..'9'+)* ];

如果我们把每条规则都看作一个独立的语法，那么这四种语法都代表同一种语言（数字列表）。但这些语法是不同类型的：Digits1 是 LL(1) 语法，Digits2 是 LL(2)，Digits3 是 LALR(1)，而我不知道 Digits4 算什么（它非常模糊且奇怪）。由于 LLLPG 是 LL(k) 解析器生成器，它支持前两种语法，但无法处理后两种；它会打印关于 Digits3 和 Digits4 的“歧义”警告，然后生成无法正常工作的代码。实际上，虽然 Digits4 确实是歧义的，但 Digits3 实际上是无歧义的。但是，Digits3 “在 LL(k)”方面**确实**是歧义的，这意味着它从 LL(k) 的角度（也就是 LLLPG 的角度）来看是歧义的。

可空（nullable）这个词的意思是“可以匹配空”。例如，@[ '0'..'9'* ] 是可空的，因为它通过不执行任何操作成功“匹配”诸如“hello, world”之类的输入；但是 @[ '0'..'9'+ ] 是不可空的，并且只会匹配至少包含一个数字的输入。

LL(k) 与竞争对手对比

LLLPG 属于 LL(k) 系列的解析器生成器。它适用于编写词法分析器（也称为标记器或扫描器）和解析器，但不适用于编写将词法分析和解析合并为一步的单阶段解析器。它比 Coco/R 等 LL(1) 解析器生成器更强大。

LL(k) 解析器，无论是生成的还是手工编写的，都非常受欢迎。我个人喜欢 LL(k) 类别的解析器，因为我觉得它们直观，而且它们之所以直观，是因为在手工编写解析器时，自然会主要得到一个 LL(k) 解析器。但是，还有另外两个流行的计算机语言解析器生成器家族，基于 LALR(1) 和 PEG。

  • LALR(1) 解析器是简化的 LR(1) 解析器，它——嗯，解释 LALR(1) 是什么需要很多篇幅。总之，LALR(1) 解析器支持左递归，并使用基于表的查找，手工编写非常不切实际，即总是需要解析器生成器或类似的基础设施，而 LL(k) 语法则易于手工编写，因此易于理解。LALR(1) 既不是 LL(k) 语法的超集也不是子集；虽然我熟悉 LALR(1)，但我承认我对它更通用的近亲 LR(k) 一无所知，而且我不知道有任何 LR(k) 的解析器生成器或使用 LR(k) 的项目。无论优劣，LR(k)（k>1）都不太受欢迎。我相信 LR 系列解析器的主要优点是 LR 解析器支持左递归，而 LL 解析器不支持（稍后会详细介绍）。
  • PEG 是带有语法谓词的递归下降解析器，因此 PEG 语法可能与您使用 LLLPG 的语法非常相似。但是，PEG 解析器传统上不使用预测（尽管预测可能被添加为一种优化），这意味着它们不会提前尝试弄清楚输入的含义；例如，如果输入是“42”，PEG 解析器不会查看“4”并决定“哦，这看起来像一个数字，所以我要调用数字子解析器”。相反，PEG 解析器只是“尝试”每个选项，从第一个开始（它是空格吗？它是标识符吗？），直到其中一个成功解析输入。没有预测步骤，PEG 解析器显然需要记忆化以提高效率（也就是说，在每个输入字符处记忆失败和成功的匹配，以避免在不同上下文中重复相同的操作）。PEG 通常将词法分析（标记化）和解析合并到单个语法中（尽管这不是必需的），而其他类型的解析器则将词法分析和解析分成独立的阶段。

当然，我也应该提到正则表达式，这可能是所有解析工具中最受欢迎的。但是，虽然您可以使用正则表达式来完成简单的解析任务，但它们对于“全面”解析（例如解析整个源文件）毫无用处。原因是正则表达式不支持递归；例如，以下规则不可能用正则表达式表示。

rule PairsOfParens @[ '(' PairsOfParens? ')' ];

由于这个限制，我不认为正则表达式是“严肃”的解析工具。

还存在其他类型的解析器生成器，但不太受欢迎。请注意，我只讨论计算机语言的解析器；自然语言处理（例如解析英语）通常依赖于可以更灵活地处理歧义的不同类型的解析器。LLLPG 实际上不适合 NLP。

正如我所说，LL(k) 与其最接近的近亲 PEG 之间的主要区别在于，LL(k) 解析器使用预测，而 LL(k) 语法通常存在歧义，而 PEG 不使用预测，并且 PEG 的定义假装不存在歧义，因为它有一个明确定义的优先级系统。

“预测”意味着在采取某个分支之前弄清楚要采取哪个分支。在“普通”LL(k) 解析器（没有与谓词）中，解析器做出决定并且“永不回头”。例如，在解析以下 LL(1) 语法时

public rule Tokens @[ Token* ];
public rule Token  @[ Float | Id | ' ' ];
token Float        @[ '0'..'9'* '.' '0'..'9'+ ];
token Id           @[ IdStart IdCont* ];
rule  IdStart      @[ 'a'..'z' | 'A'..'Z' | '_' ];
rule  IdCont       @[ IdStart | '0'..'9' ];

Token 方法将获取下一个输入字符（称为 LA0 或向前查看零），检查它是否是数字或'.'，如果是则调用 Float，否则调用 Id（或跳过空格）。如果输入是“42”之类的，不符合 Float 的定义，问题将在 Float 方法中被检测到，而不是在 Token 中，并且解析器无法后退并尝试其他方法。如果您添加一个新的 Int 规则

...
public rule Token @[ Float | Int | Id ];
token Float       @[ '0'..'9'* '.' '0'..'9'+ ];
token Int         @[ '0'..'9'+ ];
token Id          @[ IdStart IdCont* ];
...

现在您遇到了问题，因为解析器可能需要无限的向前查看才能区分 Float 和 Int。默认情况下，LLLPG 使用 LL(2)，这意味着它最多允许两个字符的向前查看。通过两个字符的向前查看，可以判断输入如“1.5”是 Float，但无法仅通过查看第三个字符来判断“42”是 Float 还是 Int。因此，此语法在 LL(2) 中是歧义的，即使向前查看无限时它是无歧义的。解析器可以正常处理个位数整数，但给定一个两位数整数，它将调用 Float，然后由于缺少预期的 '.' 而产生错误。

PEG 解析器没有这个问题；它将首先“尝试” Float，如果失败，解析器将后退并尝试 Int。但是，存在性能权衡，因为输入将被扫描两次以处理两个规则。

尽管 LLLPG 被设计用于解析 LL(k) 语法，但它处理歧义的方式类似于 PEG：如果 A|B 是歧义的，解析器将默认选择 A，因为它排在前面，但它也会警告您关于歧义。

由于前导数字的数量是无限的，LLLPG 将认为此语法无论您的最大向前查看 k（如 LL(k)）是多少，都是歧义的。您可以通过将 Float 和 Int 合并到单个规则中来解决此冲突。

public rule Tokens @[ Token* ];
public rule Token  @[ Number | Id ];
token Number       @[ '.' '0'..'9'+
                    | '0'..'9'+ ('.' '0'..'9'+)? ];
token Id           @[ IdStart IdCont* ];
...

不幸的是，有时要正确合并规则有点棘手。在这种情况下，问题是 Int 总是以数字开头，但 Float 则不是。我在这里的解决方案是将“没有前导数字”的情况与“有前导数字”的情况分开，成为单独的“替代项”。您可以采用其他几种解决方案，我将在本文后面讨论。

我提到 PEG 可以将词法分析和解析合并到单个语法中，因为它们有效地支持无限向前查看。为了说明 LL(k) 解析器通常为什么不能将词法分析和解析合并，假设您想解析一个支持变量赋值（如 x = 0）和函数调用（如 x(0)）的程序，类似这样。

// "Id" means identifier, LParen means left parenthesis '(', etc.
rule Expr    @[ Assign | Call | ... ];
rule Assign  @[ Id Equals Expr ];
rule Call    @[ Id LParen ArgList ];
rule ArgList ...
...

如果输入是以标记的形式接收的，那么这个语法只需要 LL(2)：Expr 解析器只需查看第二个标记，以确定它是 Equals ('=') 还是 LParen ('(')，从而决定调用 Assign 还是 Call。但是，如果输入是以字符的形式接收的，那么多少向前查看都不够！输入可能是这样的。

this_name_is_31_characters_long = 42;

要直接从字符解析此内容，需要 33 个字符的向前查看（LL(33)），当然，原则上，向前查看的数量没有限制。此外，LLLPG 设计用于少量向前查看，如 LL(2) 或 LL(4)；双位数几乎总是错误的。LL(33) 可能会产生一个庞大且效率低下的解析器（我甚至不敢尝试）。

总之，LL(k) 解析器不如 PEG 解析器灵活，因为它们通常限于 k 个字符或标记的向前查看，而 k 通常很小。相比之下，PEG 在解析失败时总是可以“后退”并尝试其他替代项。LLLPG 通过“语法谓词”弥补了这个问题，语法谓词允许无限向前查看，但您必须自己插入它们，因此涉及的工作量略有增加，您必须注意向前查看问题。作为交换，您的解析器可能具有更好的性能，因为您明确知道何时在执行昂贵的操作（大的向前查看）。我说“可能”是因为我找不到比较 LL(k) 解析器和 PEG 解析器的基准测试，但我听说 PEG 速度较慢，直观地我认为 PEG 所需的记忆化和重试肯定有成本，不可能免费。预测也不是免费的，但由于向前查看有严格的限制，成本通常不会很高。但请注意，过度使用语法谓词可能会导致 LLLPG 解析器比 PEG 解析器慢，尤其是考虑到 LLLPG 不使用记忆化。

让我们简要讨论一下 LL(k) 与 LALR(1)。可惜，我对 LALR(1) 的记忆自从大学以来已经模糊了，而且在搜索时，我没有找到任何让我觉得真正满意的 LALR(1) 解释。基本上，LALR(1) 既不“优于”也不“劣于”LL(k)，它只是不同。正如维基百科 所说。

LALR(k) 解析器与 LL(k) 解析器是不可比较的——对于任何大于 0 的 j 和 k，都存在 LALR(j) 语法不是 LL(k) 语法，反之亦然。事实上，对于任何 k >= 0，判断给定的 LL(1) 语法是否为 LALR(k) 是不可判定的。

但我感觉大多数广泛使用的 LALR 解析器生成器仅支持 LALR(1)，而不是 LALR(k)；因此，粗略地说，LLLPG 比 LALR(1) 解析器生成器更强大，因为它可以使用多个向前查看标记。但是，由于 LALR(k) 和 LL(k) 是不兼容的，您需要更改 LALR(1) 语法才能在 LL(k) 解析器生成器中工作，反之亦然。

以下是关于这三类解析器生成器的关键点。

LL(k):

  • 易于学习：只需查看生成的代码，您就可以直接了解其工作原理。
  • 通过操作代码（{...}）轻松添加自定义行为。
  • 简单的默认错误处理。当出现意外输入时，LL(k) 解析器始终可以在失败点报告它期望的输入。
  • 可预测的良好性能。性能取决于**实际**需要的向前查看字符数，而不是语法定义中指定的最大 k。LL(k) 解析器的性能可能会因嵌套规则过深而受到影响，因为每个规则都需要方法调用（通常还需要预测步骤）；特别是表达式语法经常有这个问题。但在 LLLPG 中，您可以使用一个技巧来处理大型表达式语法而无需深度嵌套（我想我将在未来的文章中讨论这一点；我的技术在我的LES 语法中得到了证明。）
  • LL(k) 解析器生成器，包括 LLLPG，可以在 LL(k) 语法范围之外支持有价值的额外功能，例如零宽度断言（又名与谓词），以及处理歧义的多种技术。
  • 不允许左递归（直接或间接）
  • 严格限制向前查看。很容易编写需要无限向前查看的语法，因此此类语法必须修改才能在 LL(k) 中工作。顺便说一句，ANTLR 通过 LL(*) 等技术克服了这个问题。
  • 低内存需求。
  • 通常需要单独的解析器和词法分析器。

LALR(1):

  • 如果您找不到好的教程，学习起来很困难；生成的代码可能无法理解。
  • 支持左递归（直接和间接）
  • 有些人认为 LALR(1) 语法更优雅。例如，考虑一个代表数字逗号分隔列表的“List”规则。此规则的 LALR(1) 形式为 num | List ',' num，而该规则的 LL(1) 形式为 num (',' num)*。哪个更好？您决定。
  • 低内存需求。
  • 通常需要单独的解析器和词法分析器。
  • LALR 解析器生成器通常有指定运算符优先级的显式机制。

PEG:

  • 新！ (2004 年正式化)
  • 无限向前查看
  • “无歧义”（眨眼，眨眼）——或者更确切地说，任何歧义都被忽略，“第一个规则获胜”
  • 作为标准功能支持零宽度断言。
  • 语法是**可组合**的。合并不同的 PEG 解析器比合并 LL/LR 解析器更容易。
  • 性能特征没有得到很好的记录（在我看来），但我的直觉告诉我，一个简单的基于记忆化的 PEG 解析器生成器通常会产生缓慢的解析器。也就是说，我认为这三种解析器类型对于解析大小为 N 的文件都提供大约 O(N) 的性能。
  • 高内存需求（由于记忆化）。
  • 支持“自定义操作”并不明显。尽管一个规则可能解析成功，但它的调用者可能会失败（而且经常会失败），所以我猜一个规则执行的任何工作都必须是事务性的，即必须能够撤销该操作。
  • 支持统一语法：单个语法中的解析器和词法分析器。

正则表达式:

  • 语法非常简短，但通常非常晦涩。
  • 直接匹配字符；不能用于基于标记的解析。
  • 无法解析任何规模较大的语言，因为它们不支持递归或多个“规则”。
  • 大多数正则表达式库都有特殊的简写指令，如 \b，在使用解析器生成器时需要更多的代码来表达。
  • 正则表达式传统上是解释执行的，但也可以编译。尽管正则表达式执行一种解析，但正则表达式引擎即使生成代码也不会被称为“解析器生成器”。
  • 正则表达式与 DFA 和 NFA 密切相关。

如果您遗漏了什么，请告诉我。

学习 LLLPG，带数字示例

既然您了解了竞争对手，仍然想使用 LLLPG？哦，谢天谢地！好的，让我们来解析一些数字。还记得之前的代码吗？

public rule Tokens @[ Token* ];
public rule Token  @[ Float | Id | ' ' ];
token Float        @[ '0'..'9'* '.' '0'..'9'+ ];
token Int          @[ '0'..'9'+ ];
token Id           @[ IdStart IdCont* ];
rule  IdStart      @[ 'a'..'z' | 'A'..'Z' | '_' ];
rule  IdCont       @[ IdStart | '0'..'9' ];

如果您希望我此时指出 token 和 rule 之间的区别……不，我留到下一篇文章讲。现在还不重要；只需使用 token 来定义 token 规则（如 Float、Int 和 Id），您就没事了。

现在，由于 Float 和 Int 在 LL(k) 中是歧义的，所以我建议将它们合并为单个规则。

token Number       @[ '.' '0'..'9'+
                    | '0'..'9'+ ('.' '0'..'9'+)? ];

这可能是最干净的解决方案，但还有其他方法，而这些替代方案对于学习 LLLPG 非常有用！首先，一种看起来更简单的解决方案是这个：

token Number      @[ '0'..'9'* ('.' '0'..'9'+)? ];

但现在您会遇到问题，因为它匹配空输入，或者它匹配“hello”而不消耗任何输入。因此，LLLPG 会抱怨 Token 是“可空的”，因此不能用于循环（参见 Tokens）。毕竟，如果您在循环中调用 Number 并且它什么都不匹配，您就会陷入无限循环，这非常糟糕。

零宽度断言：语法谓词

您实际上可以通过以下方式阻止它匹配空输入：

token Number @[ &('0'..'9'|'.')
                '0'..'9'* ('.' '0'..'9'+)? ];

这里我引入了*零宽度断言*（ZWA），也称为*与谓词*，因为它使用“与”符号（&）。有两种与谓词，称为“语法谓词”和“语义谓词”。这是*语法谓词*，意味着它测试语法，意味着它测试从当前位置开始的语法片段。并且因为它是一个零宽度断言，它不消耗任何输入（更准确地说，它消耗输入，然后在 Dispose() 被调用时恢复到起始位置，无论成功或失败）。与谓词有两种形式，正形式 & 检查条件是否为真，负形式 &! 检查条件是否为假。

所以，&('0'..'9'|'.') 表示数字必须以 '0'..'9' 或 '.' 开头。现在 Number() 不可能匹配空输入。不幸的是，LLLPG 不够智能，无法*知道*它不能匹配空输入；它目前根本不分析与谓词（它只是运行它们），因此它不理解 &('0'..'9'|'.') 引起的效果。因此，它仍然会抱怨 Token 是可空的，尽管它不是。希望在未来版本中，当我和其他聪明人有时间弄清楚如何进行分析时，这个问题能得到修复。

语法谓词生成两个方法来处理它。

private bool Try_Number_Test0(int lookaheadAmt)
{
  using (new SavePosition(this, lookaheadAmt))
    return Number_Test0();
}
private bool Number_Test0()
{
  if (!TryMatchRange('.', '.', '0', '9'))
    return false;
  return true;
}

第一个方法假定存在一个名为 SavePosition 的数据类型（通常，您可以自己定义它，或从我编写的基类继承）。SavePosition 的作用是：

  1. 保存当前的 InputPosition，并在调用 Dispose() 时恢复该位置。
  2. 将 InputPosition 增加 lookaheadAmt（通常为零，但并非总是如此），其中 0 <= lookaheadAmt < k。

Try_ 方法用于启动语法谓词，然后进行回溯，无论结果是真还是假。第二个方法决定当前输入位置是否存在期望的输入。语法谓词还假定存在 TryMatch 和（对于词法分析器）TryMatchRange 方法，如果存在一个期望的字符（或标记），则必须返回 true（并前进到下一个输入位置），否则返回 false。

这是 Number() 本身的 C# 代码。

void Number()
{
    int la0, la1;
    Check(Try_Number_Test0(0), "[.0-9]");
    for (;;) {
        la0 = LA0;
        if (la0 >= '0' && la0 <= '9')
            Skip();
        else
            break;
    }
    la0 = LA0;
    if (la0 == '.') {
        la1 = LA(1);
        if (la1 >= '0' && la1 <= '9') {
            Skip();
            Skip();
            for (;;) {
                la0 = LA0;
                if (la0 >= '0' && la0 <= '9')
                    Skip();
                else
                    break;
            }
        }
    }
}

Check() 的作用是在 ZWA 未匹配时打印错误。如果 Number 规则被标记为 private，并且调用 Number() 的规则已验证 Try_Number_Test0 为 true，那么为了效率，Check() 的调用将被预匹配分析（在第 1 部分中提到）消除。

零宽度断言：语义谓词

现在继续，另一种方法是：

token Number  @[ {bool dot=false;}
                 ('.' {dot=true;})?
                 '0'..'9'+ (&{!dot} '.' '0'..'9'+)?
               ];

这里我使用了另一种 ZWA，即*语义谓词*，来测试点是否为 false（&{!dot}，可以等效地写成 &!{dot}）。&{expr} 仅指定一个必须为真才能继续的条件；它通常用于解决语法中两个可能路径之间的歧义。语义谓词比语法谓词是一个明显更简单的功能，并且是 LLLPG 中首先实现的。它们仅在预测期间测试用户定义的表达式。

因此，我在这里创建了一个“dot”标志，如果第一个字符是点，则将其设置为“true”。仅当“dot”标志未设置时，才允许序列 '.' '0'..'9'+。此方法有效；但是，您必须小心使用 &{...}，因为 &{...} 块的执行时间可能比您预期的要早；下面对此进行了解释。

这是为此版本的 Number 生成的代码。

void Number()
{
    int la0, la1;
    bool dot = false;
    la0 = LA0;
    if (la0 == '.') {
        Skip();
        dot = true;
    }
    MatchRange('0', '9');
    for (;;) {
        la0 = LA0;
        if (la0 >= '0' && la0 <= '9')
            Skip();
        else
            break;
    }
    la0 = LA0;
    if (la0 == '.') {
        if (!dot) {
            la1 = LA(1);
            if (la1 >= '0' && la1 <= '9') {
                Skip();
                Skip();
                for (;;) {
                    la0 = LA0;
                    if (la0 >= '0' && la0 <= '9')
                        Skip();
                    else
                        break;
                }
            }
        }
    }
}

&{...} 中的表达式可以包含“替换变量”$LI 和 $LA，它们分别引用当前向前查看索引和当前向前查看值；如果您想对输入字符运行测试，这些很有用。例如，当您想检测*字母*时，您可以这样写：

rule Letter @[ 'a'..'z' | 'A'..'Z' ];
token Word @[ Letter+ ];

但这并不能检测*所有*可能的字母；还有 áĉçèntéd 字母、grΣεk 字母、Russiaи 字母等等。我一直通过语义与谓词来支持这些其他字母。

rule Letter @[ 'a'..'z' | 'A'..'Z'| &{char.IsLetter((char) $LA)} 0x80..0xFFFC ];
[FullLLk] token Word @[ Letter+ ];

0x80..0xFFFC 表示 .NET char 支持的所有非 ASCII 字符，而箭头运算符 -> 是 LeMP/LES 中用于强制转换的表示法；C# 等效写法是 char.IsLetter((char) $LA)。$LA 将被替换为相应的向前查看标记，通常是 LA0，但并非总是如此。现在，当您查看生成的代码时，您会注意到与谓词已复制到 Word 规则中。

void Word()
{
  int la0;
  Letter();
  for (;;) {
    la0 = LA0;
    if (la0 >= 'A' && la0 <= 'Z' || la0 >= 'a' && la0 <= 'z')
      Letter();
    else if (la0 >= 128 && la0 <= 65532) {
      la0 = LA0;
      if (char.IsLetter((char) la0))
        Letter();
      else
        break;
    } else
      break;
  }
}

在规则之间复制与谓词是正常行为，当一个规则需要使用与谓词来决定是否调用另一个规则时就会发生。ANTLR 将此称为“提升”（hoisting），所以我也这样称呼它：谓词已从 Letter 提升到 Word。（在此特定情况下，我必须添加 FullLLk 才能这样工作；更多关于此的信息将在以后的文章中讨论。）

在编写 EC# 解析器时，我注意到当涉及局部变量时，提升是不好的，因为一个函数显然不能引用另一个方法的局部变量。例如，前面 Number 示例中的谓词不应被提升。为确保它不会在规则之间复制，您可以在大括号内添加 [Local] 属性。

token Number  @[ {bool dot=false;}
                 ('.' {dot=true;})?
                 '0'..'9'+ (&{[Local] !dot} '.' '0'..'9'+)?
               ];

注意：目前 [Local] 标志仅为 &{semantic} 谓词实现，而不为 &(syntactic) 谓词实现。

门（Gates）

这里有一个最终技巧。

token Number  @[ '.'? '0'..'9' =>
                 '0'..'9'* ('.' '0'..'9'+)? ];

此示例引入了我称为“门”的功能。X 之前的语法片段 ('.'? '0'..'9'+) 实际上并没有被 Number 本身使用，但它可以被调用者用来决定是否调用该规则。

门是一种高级但简单的机制，用于改变预测的工作方式。回想一下，解析是一系列预测和匹配步骤。首先，解析器决定下一步要采取什么路径，这称为“预测”，然后根据该决定进行匹配。通常，预测和匹配基于**相同的信息**。但是，门 => 会将**不同的信息**提供给预测和匹配。门的左侧用于预测分析；右侧用于匹配。

决定 Token 是否*调用* Number 规则是一个预测决策，因此它使用门的左侧。这确保了*调用者*不会认为 Number 可以匹配空输入。当为 Number 本身生成代码时，门的左侧将被忽略。相反，Number 只运行匹配代码，即右侧 '0'..'9'* ('.' '0'..'9'+)?。（门的左侧 => 不会影响Number的代码，因为门表达式不在循环中或在由 | 分隔的替代项列表中，所以不需要*预测决策*。）

门是一种欺骗预测系统的方式。您告诉它期望某种模式，然后说“不，不，匹配这个其他模式。”门很少需要，但它们可以为某些棘手的问题提供简单的解决方案。

这是为 Number 生成的代码，但请注意，（没有门的情况下）'0'..'9'* ('.' '0'..'9'+)? 会生成完全相同的代码。

void Number()
{
    int la0, la1;
    for (;;) {
        la0 = LA0;
        if (la0 >= '0' && la0 <= '9')
            Skip();
        else
            break;
    }
    la0 = LA0;
    if (la0 == '.') {
        la1 = LA(1);
        if (la1 >= '0' && la1 <= '9') {
            Skip();
            Skip();
            for (;;) {
                la0 = LA0;
                if (la0 >= '0' && la0 <= '9')
                    Skip();
                else
                    break;
            }
        }
    }
}

门也可以用来产生无意义的代码，例如：

   // ('A' => 'Q')?
   la0 = LA0;
   if (la0 == 'A')
     Match('Q');

但请不要这样做。

请注意，门（与语法谓词不同）不提供无限向前查看。例如，如果 k=2，则 ('a' 'b' 'c' 'd' => ...) 中的字符 'c' 'd' 将无效。

门运算符 => 的优先级高于 |，因此 a | b => c | d 解析为 a | (b => c) | d。

还有一件事，几乎不值得一提。实际上有两个门运算符：普通运算符 => 和“*等价门*” <=>。它们之间的区别在于分配给门左侧的跟随集。普通门 => 的“假”跟随集为 _*（任意），并且涉及此跟随集的歧义警告将被抑制。“等价门” <=> 告诉 LLLPG 不要替换左侧的跟随集，以便两侧具有相同的跟随集。（在所有情况下，右侧的跟随集都正常计算，例如在 (('a' => A) 'b') 中， A 的跟随集是 'b'）。只有当以下情况时，使用等价门才有意义：

  1. 左侧和右侧总是具有相同的长度。
  2. 两侧都较短，因此门表达式 P => M 的跟随集可以影响预测决策。

到目前为止，我从未需要使用 <=>。

更多关于与谓词

我们来看看，我之前提到过与谓词的执行时间可能比您预期的要早。考虑这个例子：

flag::bool = false;
public rule Paradox @[ {flag = true;} &{flag} 'x' / 'x' ];

这里我引入了“/”运算符。它的行为与“|”运算符完全相同，但它会抑制两个分支之间的歧义警告（如果 flag == true，则两个分支都匹配 'x'，因此它们肯定存在歧义）。

调用 Paradox() 后 flag 的值是多少？由于两个分支相同（'x'），LLLPG 做出决策的唯一方法是通过测试与谓词 &{flag}。但操作 {flag=false;} 和 {flag=true;} 在预测之后执行，所以 &{flag} 实际上首先运行，即使它出现在 {flag=true;} 之后。当您查看实际生成的代码时，可以清楚地看到这一点。

bool flag = false;
public void Paradox()
{
  if (flag) {
    flag = true;
    Match('x');
  } else
    Match('x');
}

这里发生了什么？嗯，LLLPG 根本不读取 LA0，因为它无助于做出决策。因此，常规的预测步骤被 &{flag} 的测试所取代，然后执行匹配代码（左分支为 {flag = true;} 'x'，右分支为 'x'）。

这个例子将给出以下警告：“在与谓词 &{} 之前放置代码块 {} 是不好的风格，因为与谓词通常首先运行。”

但在另一种意义上，与谓词的执行时间可能比您预期的要晚。让我们再次看看之前 Number 规则的代码。

token Number  @[ {dot::bool=false;}
                 ('.' {dot=true;})?
                 '0'..'9'+ (&{!dot} '.' '0'..'9'+)?
               ];

此规则生成的代码是：

void Number()
{
/* ignore this part
  int la0, la1;
  bool dot = false;
  la0 = LA0;
  if (la0 == '.') {
    Skip();
    dot = true;
  }
  MatchRange('0', '9');
  for (;;) {
    la0 = LA0;
    if (la0 >= '0' && la0 <= '9')
      Skip();
    else
      break;
  }*/
  la0 = LA0;
  if (la0 == '.') {
    if (!dot) {
      la1 = LA(1);
      if (la1 >= '0' && la1 <= '9') {
        Skip();
        Skip();
        for (;;) {
          la0 = LA0;
          if (la0 >= '0' && la0 <= '9')
            Skip();
          else
            break;
        }
      }
    }
  }
}

这里我将提请您注意 (&{!dot} '.' '0'..'9'+)? 的处理方式：LLLPG 首先检查 if (la0 == '.')，然后是 if (!dot)，即使 &{!dot} 写在语法的前面。另一个例子更具体地展示了 LLLPG 的行为。

token Foo @[ (&{a()} 'A' &{b()} 'B')? ];

void Foo()
{
  int la0, la1;
  la0 = LA0;
  if (la0 == 'A') {
    if (a()) {
      la1 = LA(1);
      if (la1 == 'B') {
        if (b()) {
          Skip();
          Skip();
        }
      }
    }
  }
}

首先 LLLPG 测试 'A'，然后检查 &{a()}，然后测试 'B'，最后检查 &{b()}；就好像与谓词被“推”到右边一个位置一样。实际上，我决定所有零宽度断言都应该以这种方式工作，以提高性能。为了理解这一点，请考虑之前的 Letter 和 Word 规则。

rule Letter @[ 'a'..'z' | 'A'..'Z'| &{char.IsLetter($LA -> char)} 0x80..0xFFFC ];
[FullLLk] token Word @[ Letter+ ];

在 Word 的代码中，您可以看到 char.IsLetter 在测试 LA0 之后被调用。

if (la0 >= 'A' && la0 <= 'Z' || la0 >= 'a' && la0 <= 'z')
  Letter();
else if (la0 >= 128 && la0 <= 65532) {
  la0 = LA0;
  if (char.IsLetter((char) la0))
    Letter();
  else
    break;
} else
  break;

这很有道理；如果首先调用 char.IsLetter，那么测试 'a'..'z' | 'A'..'Z' 就没有意义了。在更大的上下文，比如像这样的“Token”规则中，这更有意义。

[FullLLk] rule Token @[ Spaces / Word / Number / Punctuation / Comma / _ ];

Token 方法看起来会是这样（为简洁起见，删除了一些换行符）。

void Token()
{
  int la0, la1;
  la0 = LA0;
  switch (la0) {
  case '\t':  case ' ':
    Spaces();
    break;
  case '.':
    {
      la1 = LA(1);
      if (la1 >= '0' && la1 <= '9')
        Number();
      else
        Punctuation();
    }
    break;
  case '0':  case '1':  case '2':  case '3':  case '4':
  case '5':  case '6':  case '7':  case '8':  case '9':
    Number();
    break;
  case '!':  case '#':  case '$':  case '%':  case '&':
  case '*':  case '+':  case ',':  case '-':  case '/':
  case '<':  case '=':  case '>':  case '?':  case '@':
  case '\\': case '^':  case '|':
    Punctuation();
    break;
  default:
    if (la0 >= 'A' && la0 <= 'Z' || la0 >= 'a' && la0 <= 'z')
      Word();
    else if (la0 >= 128 && la0 <= 65532) {
      la0 = LA0;
      if (char.IsLetter((char) la0))
        Word();
      else
        MatchExcept();
    } else
      MatchExcept();
    break;
  }
}

在这个例子中，显然在检查 &{char.IsLetter(...)} 之前检查 LA0 更有意义。如果 LLLPG 先调用与谓词，代码将是这种形式：

void Token()
{
  int la0, la1;
  la0 = LA0;
  if (char.IsLetter((char) la0)) {
    switch (la0) {
      // All the same switch cases as before
    }
  } else {
    switch (la0) {
      // All the same switch cases again!
    }
  }
}

Token 的代码会更长，而且更慢，因为我们会对每个输入字符调用 char.IsLetter，而不仅仅是 Unicode 范围 0x80..0xFFFC 中的字符。因此，显然，作为一般规则，LLLPG 在 ZWA 之前测试字符值是很好的。

事实上，我现在正在质疑是否应该交错测试。如您所见，它目前将测试位置 0 的字符/标记，然后是位置 0 的 ZWA，然后是位置 1 的字符/标记，然后是位置 1 的 ZWA。这似乎是我开始时最好的方法，但在 EC# 解析器中，这种顺序会产生一个 3122 行的 Stmt（语句）方法（原始的 rule 只有 58 行），这几乎占了整个解析器 LOC 的一半；看起来在任何 ZWA 之前测试 LA(0) 和 LA(1) 可能会更好，至少对于该特定规则来说是这样。

下划线和波浪线

下划线 _ 表示“匹配任何终结符”，而 ~(X|Y) 表示“匹配任何终结符，但 X 或 Y 除外”。下一节有一个同时使用两者的示例。

在 ~(X|Y) 中，X 和 Y 必须是终结符（如果 X 和/或 Y 是非终结符，请考虑使用类似 &!(X|Y) _ 的方法）。

关于 ~(...) 和 _ 的一个微妙之处是，它们都排除了 EOF（在词法分析器中为 -1）。因此 ~X 实际上意味着“X 或 EOF 以外的任何东西”；而 ~(~EOF) 不代表 EOF，它代表空集（据我所知，这是完全无用的）。顺便说一句，~ 会导致 LLLPG 使用 MatchExcept() API，LLLPG *假定*该 API 不会匹配 EOF。因此，对于 ~(X|Y)，LLLPG 生成 MatchExcept(X, Y)，这必须等同于 MatchExcept(X, Y, EOF)。

设置向前查看

纯 LL(k) 解析器向前查看最多 k 个终结符以做出分支决策，一旦做出决定就会坚持下去，它们不会“回溯”或尝试其他方法。因此，如果 k 太低，LLLPG 将生成做出错误决策的代码。

LLLPG 的默认 k 值为 2，在大多数情况下足够了，只要您的语法设计为 LL(k)。要将 k 增加到 X，只需将 [DefaultK(X)] 属性添加到语法（即 LLLPG 语句），或将 [k(X)] 属性添加到单个规则（[LL(X)] 是同义词）。这是一个代表 “双引号” 和 ““三引号”” 字符串的示例，其中 k=2 不够。

private token DQString @[
    '"' ('\\' _  | ~('"'|'\\'|'\r'|'\n'))* '"'? ];
];
[k(4)]
private token TQString @[
    '"' '"' '"' nongreedy(Newline / _)* '"' '"' '"' 
    "'''"       nongreedy(Newline / _)* "'''"
];
[k(4)]
private token Token @[
    ( {_type = TT.Spaces;}    Spaces
    ...
    | {_type = TT.String;}    TQString
    | {_type = TT.String;}    DQString
    ...
    )
];

这里我在两种字符串中都使用了“_”，表示“匹配任何字符”，但这暗示字符串可以无限延长。为了解决这个问题，我添加了非贪婪含义“在有意义时退出循环”（贪婪和非贪婪在我的博客中解释得更详细）。

只有两个字符的向前查看，LLLPG 无法判断 """this""" 是空的 DQString（""）还是三引号的 TQString。由于 TQString 列在前面，LLLPG 将始终选择 TQString 当 Token 以 "" 开头时，但这可能是错误的决定。您还会收到类似以下的警告。

warning : Loyc.LLParserGenerator.Macros.run_LLLPG: 
Alternatives (4, 5) are ambiguous for input such as «""» (["], ["])

在这种情况下，[k(3)] 就足够了，但使用比必需值稍高的数字也没关系，所以我在这里使用了 [k(4)]。

LLLPG 不是解析器生成器的法拉利。

在我编写 EC# 的经历中，我发现 LLLPG 在处理某些语法（尤其是高度歧义的语法，例如开发过程中不小心编写的语法）时，几乎会消耗无限的时间和内存，并且处理时间会随着 k 指数级增长。事实上，即使是默认的 LL(2)，某些复杂的语法也会让 LLLPG 运行很长时间并占用大量内存。在 LL(3) 时，同样的“坏语法”会让它在 LL(3) 时几乎永远运行并耗尽您所有的内存。在我使用 LLLPG 0.92 编写 EC# 解析器时，我做了一个看似无害的更改，导致它即使在 LL(2) 下处理我的语法也几乎永远运行。

问题很难追踪，因为它似乎只在大而复杂的语法中发生，但最终我找到了编写一个简短的语法，让 LLLPG 感到棘手。

[DefaultK(2)] [FullLLk(false)]
LLLPG lexer {
    rule PositiveDigit @[ '1'..'9' {""Think positive!""} ];
    rule WeirdDigit @[ '0' | &{a} '1' | &{b} '2' | &{c} '3' 
             | &{d} '4' | &{e} '5' | &{f} '6' | &{g} '7'
             | &{h} '8' | &{i} '9' ];
    rule Start @[ (WeirdDigit / PositiveDigit)* ];
}

最初 LLLPG 需要大约 15 秒来处理这个，但我设法修复了它；现在 LLLPG 可以毫无察觉地处理这个语法。但是，我意识到有一个类似的语法，这个修复根本无效。

[DefaultK(2)] [FullLLk(false)]
LLLPG lexer {
    rule PositiveDigit @[ '1'..'9' {""Think positive!""} ];
    rule WeirdDigit @[ '0' | &{a} '1' | &{b} '2' | &{c} '3' 
             | &{d} '4' | &{e} '5' | &{f} '6' | &{g} '7'
             | &{h} '8' | &{i} '9' ];
    rule Start @[ WeirdDigit+ / PositiveDigit+ ];
}

同样，这需要大约 15 秒（LL(2)）和几乎无限的时间（LL(3)），并且看起来需要重大的设计更改才能克服这个问题。

幸运的是，大多数语法不会让 LLLPG 变得非常慢，但它也不是一个速度极快的工具。在我的笔记本电脑上，LLLPG 大约需要 3 秒钟分别处理 EC# 的词法分析器和解析器。

因此，在我找到时间修复速度问题之前，我建议使用 LL(2)（这是默认设置），除非在您需要更多的特定规则中（LLLPG 允许您在每个规则上设置自定义 LL(k) 设置）。

总结

到现在为止，我们已经涵盖了所有基本功能。准备好阅读第 3 部分了吗？然后点击链接！

在未来的文章中，我将讨论更多关于以下主题的内容。

  • token 与 rule.
  • LLLPG 使用的 API
  • 保存输入
  • 管理歧义
  • 错误处理
  • [FullLLk] 与“近似”LL(k)
  • 我最喜欢的 LLLPG *没有*的功能：基于长度的消歧。
  • 真实示例：解析 LES 或其他内容。当然，本文附带的示例代码本身几乎就是一个真实示例。欢迎其他解析建议。
  • 如何进行“树形解析”：如何在三阶段解析中使用 LLLPG，其中您在主解析阶段之前按括号对标记进行分组。
  • 如何进行关键字解析：LLLPG 可以直接处理关键字，尽管生成的代码相当大。
  • LLLPG 的工作原理：简要浏览源代码？不过，我想没人那么关心。
  • 关于 Loyc 及其库的所有信息。.
  • 使用 LeMP 可以做什么：除了 LLLPG 之外的其他源代码操作器。
  • 您希望 LLLPG 支持 C# 以外的语言吗？ 告诉我哪种语言。更好的是，问我如何编写新的输出模块，我将专门写一篇关于它的文章。

我也很想听听您计划如何在自己的项目中 YoLLPG。别忘了与您的编译器编写朋友和大学教授分享这篇文章！（哥们，你的朋友写编译器？我**真的**希望有你这样的朋友。）

历史

有关历史，请参见第 1 部分。

© . All rights reserved.