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

Qwertie

4.96/5 (15投票s)

2015 年 6 月 20 日

LGPL3

23分钟阅读

23585

1147

担心正则表达式难以理解、重复、难以正确使用且不支持递归？阅读第 5 部分，这可能是迄今为止最有用的部分！

下载 LLLPG-1.3.2.zip - 1.7 MB，包含 VS 集成 + 示例
在 GitHub 上查看示例或源代码

欢迎来到第 5 部分

LLLPG 的新用户？您可以从第 1 部分开始，但如果您以前解析过内容，请随意从这里开始。

我终于决定完成本系列文章，并为 LLLPG 添加一些新功能，使其更灵活和更具吸引力，尤其可以作为正则表达式的替代品。本文的一半专门介绍新功能，另一半专门介绍高级解析技巧。

回顾一下，LLLPG 是一个集成到“增强型”C# 语言中的解析器生成器。该工具接受散布有 LLLPG 语法或语法片段的普通 C# 代码，并输出纯 C#。LLLPG 相对于其他工具的优势

LLLPG 生成简单、相对简洁、快速的代码。
作为 Visual Studio 自定义工具，它非常适合那些对于正则表达式来说稍微有点大的中等规模解析任务。LLLPG 也足够复杂，可以解析像“增强型 C#”这样复杂的语言，这是 LLLPG 通常的输入语言。
您可以将解析器添加到现有类中——非常适合编写 static Parse 方法。
您可以在解析过程中避免内存分配（非常适合解析短字符串！）
不需要运行时库（尽管我建议使用 Loyc.Syntax.dll 作为您的运行时库以获得最大的灵活性，以及其依赖项 Loyc.Collections.dll 和 Loyc.Essentials.dll。）
学习曲线短：LLLPG 直观易用，因为它增强了现有的编程语言，并且*不*尝试代表您做所有事情。此外，生成的代码遵循输入代码的结构，因此您可以轻松了解该工具的行为方式。
只需学习一个解析模型：其他一些系统对词法分析器使用一个模型（正则表达式），对解析器使用另一个模型。通常，词法分析器与解析器具有完全不同的语法，并且词法分析器无法处理嵌套注释等（lex 和 yacc 甚至是独立的程序！）。LLLPG 只使用一个模型，LL(k)；其词法分析器和解析器具有几乎相同的语法和行为。
对于棘手的情况，LLLPG 提供零宽度断言（又称语义和句法谓词）和“门”。
与正则表达式相比，LLLPG 允许递归语法，通常会减少语法片段的重复，并且由于 LLLPG 只支持 LL(k)，它减轻了正则表达式拒绝服务攻击的风险。另一方面，LLLPG 不那么方便，因为语法往往比正则表达式长，*更改*语法需要安装 LLLPG 工具，并且正确编写 LL(k) 语法可能比编写正则表达式需要更多的思考。
与 ANTLR 相比，LLLPG 是为 C# 而不是 Java 设计的，所以自然有 Visual Studio 插件，而且我没有将一半文档作为书出售。语法与 ANTLR 相当，但表面上不同，因为与 ANTLR 规则不同，LLLPG 规则类似于函数声明。此外，我最近尝试了 ANTLR 4，我对输出代码的低效感到震惊。
来自 LeMP 的额外功能（稍后详述）

LLLPG 1.3.2 的新功能

“外部 API”：在 LLLPG 1.1 中，您必须编写一个派生自 BaseLexer 或 BaseParser 的类，其中包含 LLLPG API，例如 Match、LA0、Error 等。现在您可以将该 API 封装在字段或局部变量中。这意味着您可以拥有不同的基类，或者您可以将词法分析器/解析器放入值类型 (struct) 或 static class 中。
“自动值保存器：在 LLLPG 1.1 中，如果您想保存规则或令牌的返回值，您（有时）必须手动创建关联变量。在新版本中，您可以将“标签”附加到任何终结符或非终结符，这将使 LLLPG 在方法开始时自动创建变量。更好的是，您通常可以不附加标签。
自动返回值：当您在规则中使用 $result 或 result: 标签时，LLLPG 会自动创建一个名为 result 的变量来保存当前规则的返回值，并在方法结束时添加 return result 语句。
隐式 LLLPG 块：不再编写 LLLPG(lexer) { /* rules */ }，规则周围带大括号，现在允许您编写 LLLPG(lexer); /* rules */，这样您就不会被迫对规则进行过多缩进。
any 命令和 inline 规则：详情如下。
新的基类 BaseParserForList<Token,int> 比旧基类 BaseParser<Token> 更易于使用。
LLLPG 现在将在语法操作的代码中插入 #line 指令。虽然对编译器错误很有用，但此功能在调试时会让人感到迷惑；要将 #line 指令转换为注释，请在 LLLPG 命令之前附加以下属性：[AddCsLineDirectives(false)]。

将 LLLPG 与“外部”API 结合使用

您可以使用 inputSource 和 inputClass 选项来指定 LLLPG 应该向其发送所有 API 调用的对象。inputClass 应该是 inputSource 引用的对象的数据类型。例如，如果您指定 inputSource(src)，LLLPG 会将 '+'|'-' 这样的语法片段转换为 src.Match('+','-') 这样的代码。如果没有 inputSource 选项，这将只是 Match('+','-')。

Loyc.Syntax.dll（LLLPG 1.3 附带）具有 LexerSource 和 LexerSource<C> 类型，它们派生自 BaseLexer 并提供 LLLPG 词法分析器 API。使用这些选项时，词法分析器看起来像这样

using Loyc;
using Loyc.Syntax.Lexing;

public class MyLexer {
  public MyLexer(string input, string fileName = "") { 
    src = new LexerSource((UString)input, fileName);
  }
  LexerSource src;

  LLLPG (lexer(inputSource(src), inputClass(LexerSource))) {
    public rule Token()         @[ Id  | Spaces | Newline ];
    private rule Id             @[ IdStartChar (IdStartChar|'0'..'9'|'\'')* ];
    private rule IdStartChar    @[ 'a'..'z'|'A'..'Z'|'_' ];
    private rule Spaces         @[ (' '|'\t')+ ];
    private rule Newline        @[ ('\n' | '\r' '\n'?)
      {src.AfterNewline();} // increments LineNumber
    ];
  }
}

LexerSource 接受任何 ICharSource 的实现；ICharSource 表示具有 Slice(...) 方法的字符源，该方法用于加速对单个字符的访问。如果您的输入只是一个字符串 S，请使用 new LexerSource((UString)S) 将字符串转换为 LexerSource；还提供了快捷方式 (LexerSource)S。UString 是 string 的包装器，实现了 ICharSource 接口（UString 中的 U 表示“unicode”；详情请参阅 UString 的文档）。

自动值保存器

您通常需要将内容存储在变量中，而在 LLLPG 1.1 中这很不方便，因为您必须手动创建变量来存储内容。现在 LLLPG 可以为您创建变量。考虑这个整数解析器

/// Usage: int num = new Parser("1234").ParseInt();
public class Parser : BaseLexer {
  /// Note: a string converts implicitly to UString
  public Parser(UString s) : base(s) {}

  LLLPG (lexer(terminalType: int));

  public token int ParseInt() @[
    ' '*
    (neg:'-')?
    ( digit:='0'..'9' {$result = 10*$result + (digit - '0');} )+ 
    EOF
    {if (neg != 0) $result = -$result;}
  ];
}

标签 neg:'-' 导致 LLLPG 在方法开始时创建一个变量 (int neg = 0)，并将匹配结果赋值给它 (digit = MatchAny())。变量的类型由 terminalType(...) 选项控制，但词法分析器的默认类型是 int，因此在此示例中不需要它。

这与现有语法 digit:='0'..'9' 不同，因为 : 在方法*开始*时创建变量，而 := 在当前作用域中创建变量 (var digit = MatchRange('0', '9');)。无论哪种情况，在动作块内部，LLLPG 都将识别命名标签 $neg 或 $digit 并将其替换为实际变量名，即 neg 或 digit。

这个例子还使用了 $result，这使得 LLLPG 创建一个名为 result 的变量，其返回类型与方法相同（在本例中为 int），并在最后返回它。因此，生成的代码看起来像这样

public int ParseInt()
{
    int la0;
    int neg = 0;
    int result = 0;

    ... parsing code ...

    if (neg)
        result = -result;
    return result;
}

你甚至不必明确地应用标签。上述规则也可以这样写

public token int ParseInt() @[
    ' '*
    ('-')?
    ( '0'..'9' {$result = 10*$result + ($('0'..'9') - '0');} )+ 
    EOF
    {if ($'-' != 0) $result = -$result;}
];

在此版本中，我删除了标签 neg 和 digit，而是将 $'-' 和 $('0'..'9') 引用到我的语法操作中。这使得 LLLPG 创建两个变量来表示 '-' 和 '0'..'9' 的值

int ch_dash = 0;
int ch_0_ch_9 = 0;
...
if (la0 == '-')
    ch_dash = MatchAny();
ch_0_ch_9 = MatchRange('0', '9');
...

就好像我在语法中使用了 ch_dash:'-' 和 ch_0_ch_9:'0'..'9' 一样。

最后但同样重要的是，您可以使用（ admittedly 怪异的）+: 运算符向列表中添加内容。例如

/// Usage: int num = new IntParser("1234").Parse();
public class Parser : BaseLexer {
  public Parser(UString s) : base(s) {}

  LLLPG (lexer(terminalType: int));

  public rule int ParseInt() @[
    ' '* (digits+:'0'..'9')+
    // Use LINQ to convert the list of digits to an integer
    {return digits.Aggregate(0, (n, d) => n * 10 + (d - '0'));}
  ];
}

/// Generated output for ParseInt()
public int ParseInt()
{
    int la0;
    List<int> digits = new List<int>();
    for (;;) {
        la0 = LA0;
        if (la0 == ' ')
            Skip();
        else
            break;
    }
    digits.Add(MatchRange('0', '9'));
    for (;;) {
        la0 = LA0;
        if (la0 >= '0' && la0 <= '9')
            digits.Add(MatchAny());
        else
            break;
    }
    return digits.Aggregate(0, (n, d) => n * 10 + (d - '0'));
}

在 ANTLR 中，您使用 += 来完成相同的操作。显然，+: 更丑陋；不幸的是，我已将 += 定义为“将某些内容添加到*用户定义*的列表”，而 +: 表示“在方法开始时自动*创建*一个列表，并将某些内容添加到其中”。

总而言之，如果 Foo 代表一个规则、令牌类型或一个字符，则以下五个运算符可用

x=Foo：将现有变量 x 设置为 Foo 的值
x+=Foo：将 Foo 的值添加到现有列表变量 x（即 x.Add(Foo())，如果 Foo 是规则）
x:=Foo：在当前作用域中创建一个变量 x，以 Foo 作为其值（即 var x = Foo();，如果 Foo 是规则）。
x:Foo：在方法开始时创建一个名为 x 的适当类型的变量，并在此处将 x 设置为该变量。如果 Foo 是令牌或字符，请使用 terminalType 代码生成选项来控制 x 的声明类型（例如 LLLPG(parser(terminalType: Token))）如果您在多个位置使用标签 x，LLLPG 将只创建一个名为 x 的（非列表）变量。
x+:Foo：在方法开始时创建一个名为 x 的适当类型的*列表*变量，并将 Foo 的值添加到列表中（即 x.Add(Foo())，如果 Foo 是规则）。默认情况下，列表将具有 List<T> 类型（其中 T 是适当的类型），您可以使用 listInitializer 选项全局更改列表类型（例如 LLLPG(parser(listInitializer: IList<T> _ = new DList<T>()))，如果您喜欢 DList）

您只能将这些运算符用于“原始”语法元素：终结符集和规则引用。例如，digits:(('0'..'9')*) 和 digits+:(('0'..'9')*) 是非法的；但 (digits+:('0'..'9'))* 是合法的。

“内联”规则

LLLPG 1.3 支持“内联”规则，这些规则在使用位置逐字插入。这是一个例子

LLLPG(lexer);

inline extern rule IdStartChar @[ 'a'..'z'|'A'..'Z'|'_' ];
inline extern rule IdContChar @[ IdStartChar|'0'..'9' ];
rule Identifier @[ IdStartChar IdContChar* ];

这只会生成一个方法作为输出（Identifier），IdStartChar 和 IdContChar 的内容已内联。我还使用了 extern 修饰符来抑制 IdStartChar 和 IdContChar 的代码生成；否则，这些方法将存在但不会被调用。

目前，内联仅允许用于没有参数且没有返回值的规则。内联也是“不卫生的”；例如，内联规则可能包含引用仅存在于内联发生位置的局部变量的代码。不建议这样做

/// Input
rule Foo @[ digit:'0'..'9' Unsanitary ];
inline rule Unsanitary @[ {Console.WriteLine(digit);} ];

/// Output
void Foo()
{
    var digit = MatchRange('0', '9');
    Console.WriteLine(digit);
}
void Unsanitary()
{
    Console.WriteLine(digit);
}

“any”指令

在一个罕见的特性蔓延胜利中，LLLPG 1.3 允许您用一个额外的“单词”属性标记一个规则，这个属性可以是任何单词，然后用“any”指令引用该单词。例如

rule Words @[ (any fruit ' ')* ];
fruit rule Apple @[ "apple" ];
fruit rule Grape @[ "grape" ];
fruit rule Lemon @[ "lemon" ];

在这里，Words 规则使用 any fruit，它等效于

rule Words @[ ((Apple / Grape / Lemon) ' ')* ];

单词 fruit 从输出中去除。您也可以将 [fruit] 写入一个带有方括号的普通属性，但在这种情况下，该属性*保留*在输出中。

any 指令还有一个“any..in”版本，其中您提供一个语法片段，该片段对每个匹配的规则重复。这最好通过示例解释

rule SumWords::int @[ (any word in (x+:word) ' ')* {return x.Sum();} ];
word rule One::int @[ ""one"" {return 1;}  ];
word rule Two::int @[ ""two"" {return 2;}  ];
word rule Ten::int @[ ""ten"" {return 10;} ];

SumWords 规则可以等效地写成

rule int SumWords @[ ((x+:One / x+:Two / x+:Ten) ' ')* {return x.Sum();} ];

高级解析主题！

在介绍完所有这些新功能之后，我们来谈谈

如何在不进行内存分配的情况下进行解析
如何解析关键字
将优先级级别折叠成一个规则
使用令牌树进行解析
如何解析像 Python 这样对缩进敏感的语言
使用 LeMP 缩短代码

如何在词法分析器中避免内存分配

我提到 LLLPG 允许您避免内存分配，现在我将演示。在成熟的解析器中避免内存分配几乎是不可能的，因为您需要分配内存来存储您的语法树。但在更简单的情况下，您可以优化您的扫描器以避免创建垃圾对象。

以下示例解析电子邮件地址，除了单个 LexerSource（每个线程只分配一次）之外，不分配*任何*内存

struct EmailAddress
{
  public EmailAddress(string userName, string domain) 
    { UserName = userName; Domain = domain; }
  public UString UserName;
  public UString Domain;
  public override string ToString() { return UserName + ""@"" + Domain; }

  LLLPG (lexer(inputSource(src), inputClass(LexerSource))) {
    // LexerSource provides the APIs expected by LLLPG. This is
    // static to avoid reallocating the helper object for each email.
    [ThreadStatic] static LexerSource<UString> src;

    /// <summary>Parses email addresses according to RFC 5322, not including 
    /// quoted usernames or non-ASCII addresses (TODO: support Unicode).</summary>
    /// <exception cref="FormatException">The input is not a legal email address.</exception>
    public static rule EmailAddress Parse(UString email)
    {
      if (src == null)
        src = new LexerSource<UString>(email, "", 0, false);
      else
        src.Reset(email, "", 0, false); // re-use old object

      @[ UsernameChars(src) ('.' UsernameChars(src))* ];
      int at = src.InputPosition;
      UString userName = email.Substring(0, at);

      @[ '@' DomainCharSeq(src) ('.' DomainCharSeq(src))* EOF ];
      UString domain = email.Substring(at + 1);
      return new EmailAddress(userName, domain);
    }
    static rule UsernameChars(LexerSource<UString> src) @[
      ('a'..'z'|'A'..'Z'|'0'..'9'|'!'|'#'|'$'|'%'|'&'|'\''|
      '*'|'+'|'/'|'='|'?'|'^'|'_'|'`'|'{'|'|'|'}'|'~'|'-')+
    ];
    static rule DomainCharSeq(LexerSource<UString> src) @[
             ('a'..'z'|'A'..'Z'|'0'..'9')
      ( '-'? ('a'..'z'|'A'..'Z'|'0'..'9') )*
    ];
  }
}

此示例演示您可以将 LexerSource 作为参数在规则之间传递，尽管在此处它实际上是多余的，并且 src 参数可以安全删除。

此示例如何避免内存分配

LexerSource 在线程局部变量中只分配一次，然后在后续调用中通过调用 Reset(...) 重复使用。Reset(...) 接受与构造函数相同的参数。
它使用 UString 而不是 string。UString 是 Loyc.Essentials.dll 中定义的一个 struct，它表示字符串的一个片段。当此示例调用 email.Substring() 时，它没有创建新字符串，它只是创建了一个引用 email 字符串一部分的 UString。
它使用 LexerSource<UString> 而不是 LexerSource。请记住，LexerSource 接受对 ICharSource 的引用，因此如果您编写 new LexerSource((UString)"string")，您正在将 UString 装箱到堆中。相反，new LexerSource<UString>((UString)"string") 不会将 UString 装箱。
它使用四参数构造函数 new LexerSource<UString>(email, "", 0, false)。最后一个参数很重要；默认情况下，LexerSource 会分配一个 LexerSourceFile 对象（LexerSource.SourceFile 属性），该对象跟踪文件中换行符的位置，以便您可以在整数索引和（行，列）对之间进行转换。通过将此参数设置为 false，您可以关闭此功能以避免内存分配。

关键字解析

假设我们有一种语言，其中包含 for、foreach、while、if、do 和 function 等关键字。我们可以编写如下代码（假设您已定义一个填充了令牌类型的 enum TT）

[k(9)]
private token TT IdOrKeyword @[
      "do"        {return TT.Do;      }
    / "if"        {return TT.If;      }
    / "for"       {return TT.For;     }
    / "foreach"   {return TT.Foreach; }
    / "while"     {return TT.While;   }
    / "function"  {return TT.Function;}
    / Identifier  {return TT.Id;      } 
];

public token ScanNextToken() @[
      Spaces        { return TT.Spaces; } 
    / t:IdOrKeyword
    / t:Operator
    / t:Literal
    / ...
    { return t; }
];

此示例使用 [k(9)] 将预读增加到 9（比任何关键字都长），仅在此规则内。不幸的是，这并不能完全按您期望的方式工作。此示例存在两个问题

foreach 分支是不可达的，因为它将被检测为关键字 for 后跟 each。
“form”、“ifone”和“functionality”等单词将被解析为关键字后跟一个 Identifier。

您可以通过将 foreach 分支移动到 for 分支上方来解决第一个问题，以赋予其更高的优先级。

您可以使用门（=>）或零宽度谓词（&(...)）来解决第二个问题，以确保关键字*不*后跟某些其他字符，例如字母或数字，这会暗示它不是关键字。如果您使用门而不是谓词，生成的代码会更有效率，因此我的标准解决方案如下

[k(/*k must be longer than the longest keyword*/)]
private token IdOrKeyword @
    [ "first_keyword"  (EndId => {/* custom action for this keyword */})
    / "second_keyword" (EndId => {/* custom action for this keyword */})
    / "third_keyword"  (EndId => {/* custom action for this keyword */})
    / Identifier // normal identifier
    ];

// If a keyword is followed by a letter or number then it is NOT a keyword.
// So this rule is used to cause LLLPG to verify that there is no letter or
// number after the keyword. 'extern' suppresses code generation because
// this rule is not actually called, it merely alters prediction in a gate.
extern token EndId @[
    ~('a'..'z'|'A'..'Z'|'0'..'9'|'_') | EOF
];

实际上还有第三个问题。由于 LLLPG 的限制，如果您有大量关键字，LLLPG 可能需要很长时间才能分析您的语法。问题的一部分是 IdOrKeyword 被分析了不止一次：它被单独分析，然后它在生成 ScanNextToken 的代码时被“比较分析”，因为 LLLPG 必须弄清楚何时调用 IdOrKeyword 以及何时调用其他规则。因此，您可以通过使用一个门在 ScanNextToken 分析期间“隐藏” IdOrKeyword 来提高速度，如下所示

public token ScanNextToken() @[
      Spaces        { return TT.Spaces; } 
    / (Id => t:IdOrKeyword)
    / t:Operator
    / t:Literal
    / ...
    { return t; }
];

门 Id => t:IdOrKeyword 通过说“如果它看起来像一个标识符，则调用 IdOrKeyword() - 忽略 IdOrKeyword() 内部各种分支之间的所有差异”来简化分析。

将优先级级别折叠成一个规则

LL(k) 解析的传统缺点之一是解析表达式时每个优先级级别都需要一个单独的规则。考虑这个**完全可操作的**示例，它将表达式解析为 Loyc 树

class ExprParser : BaseParserForList<StringToken, string>
{
    public ExprParser(string input) 
        : this(input.Split(' ').Select(word => 
               new StringToken { Type=word }).ToList()) {}
    public ExprParser(IList<StringToken> tokens, ISourceFile file = null) 
        : base(tokens, default(StringToken), file ?? EmptySourceFile.Unknown) 
        { F = new LNodeFactory(SourceFile); }

    protected override string ToString(string tokType) { return tokType; }

    LNodeFactory F;
    LNode Op(LNode lhs, StringToken op, LNode rhs) { 
        return F.Call((Symbol)op.Type, lhs, rhs, lhs.Range.StartIndex, rhs.Range.EndIndex);
    }

    LLLPG(parser(laType: string, terminalType: StringToken));

    public rule LNode Expr() @[
        result:Expr1 [ "=" r:=Expr
                       { $result = Op($result, $"=", r); } ]?
    ];
    rule LNode Expr1() @[
        result:Expr2 ( op:=("&&"|"||") r:=Expr2
                       { $result = Op($result, op, r); } )*
    ];
    rule LNode Expr2() @[
        result:Expr3 ( op:=(">"|"<"|">="|"<="|"=="|"!=") r:=Expr3
                       { $result = Op($result, op, r); } )*
    ];
    rule LNode Expr3() @[
        result:Expr4 ( op:=("+"|"-") r:=Expr4 
                       { $result = Op($result, op, r); } )*
    ];
    rule LNode Expr4() @[
        result:PrefixExpr ( op:=("*"|"/"|">>"|"<<") r:=PrefixExpr
                       { $result = Op($result, op, r); } )*
    ];
    rule LNode PrefixExpr() @[
        ( "-" r:=PrefixExpr { $result = F.Call((Symbol)"-", r, 
                                        $"-".StartIndex, r.Range.EndIndex); }
        / result:PrimaryExpr )
    ];
    rule LNode PrimaryExpr() @[
        result:Atom
        (   "(" Expr ")" { $result = F.Call($result, $Expr, $result.Range.StartIndex); }
        |   "." rhs:Atom { $result = F.Dot ($result, $rhs,  $result.Range.StartIndex); }
        )*
    ];
    rule LNode Atom() @[
        "(" result:Expr ")" { $result = F.InParens($result); }
    /   _ { 
            double n; 
            $result = double.TryParse($_.Type, out n) 
                    ? F.Literal(n) : F.Id($_.Type);
        }
    ];
}

我设计这个例子是为了在没有词法分析器的情况下工作（我真的不推荐这种方法，但这使例子简短）。它会接受用空格分隔的标记，因此您可以使用这样的代码进行测试

Console.WriteLine(new ExprParser("x . Foo ( 0 ) * ( 7.5 + 2.5 ) > 100").Expr());

为了让它编译，它只需要一些 using 和 StringToken 的定义（见下文）。

请注意，在解析器中间有一系列 Expr 规则：Expr1、Expr2、Expr3 和 Expr4。在用于“真实”语言的解析器中，可能还有更多。并且请注意，即使解析像“42”这样的简单表达式，总是会出现相同的调用堆栈：Expr、Expr1、Expr2、Expr3、Expr4、PrefixExpr、PrimaryExpr、Atom。这效率低下。然而，将所有“中缀”运算符（ExprN）折叠成一个规则是直接的。这涉及一个表示当前“优先级下限”的整数，以及一个语义谓词 &{...}

public rule LNode Expr(int prec = 0) @[
    result:PrefixExpr
    greedy // to suppress ambiguity warning
    (   // Remember to add [Local] when your predicate uses a local variable
        // (Someday I'll make [Local] the default; use [Hoist] for non-local)
        &{[Local] prec <= 10}
        "=" r:=Expr(10)
        { $result = Op($result, $"=", r); }
    |   &{[Local] prec < 20}
        op:=("&&"|"||") r:=Expr(20)
        { $result = Op($result, op, r); }
    |   &{[Local] prec < 30}
        op:=(">"|"<"|">="|"<="|"=="|"!=") r:=Expr(30)
        { $result = Op($result, op, r); }
    |   &{[Local] prec < 40}
        op:=("+"|"-") r:=Expr(40)
        { $result = Op($result, op, r); }
    |   &{[Local] prec < 50}
        op:=("*"|"/"|">>"|"<<") r:=Expr(50)
        { $result = Op($result, op, r); }
    )*
];

这里我将我的优先级级别乘以 10，以便将来可以轻松添加更多优先级级别（在现有级别之间）。

它是如何工作的？较低的 prec 值表示较低的优先级级别，其中 0 表示最外层表达式。匹配具有某个优先级级别的运算符后，Expr 调用自身，并提高“优先级下限”，此时低优先级运算符将不再匹配，但高优先级运算符仍然匹配。

让我们分析表达式“- 6 * 5 > 4 - 3 - 2”。首先调用 Expr(0)，PrefixExpr 匹配 -6。此时，可以匹配任何中缀运算符。匹配 * 后，调用 Expr(50)，它匹配 5 然后返回（因为它无法匹配 >），Expr(0) 调用 Op 创建一个 LNode，表示子表达式 -6 * 5。接下来，匹配 >，因此调用 Expr(30)。

Expr(30) 匹配 4，然后它看到 -，所以它检查 prec < 40。这是真的，所以它调用 Expr(40)。Expr(40) 匹配 3，然后它看到第二个 -。这次 prec < 40 是*假的*，所以它返回。Expr(30) 调用 Op 创建子表达式 4.0 - 3.0。

接下来，Expr(30) 看到第二个 - 并检查 prec < 40，这是*真的*，所以它匹配第二个 - 并调用 Expr(40)，它匹配 2 并返回。然后 Expr(30) 调用 Op 创建子表达式 (4.0 - 3.0) - 2.0。最后，Expr(30) 返回，并且 Expr(0) 创建表达式树 (-6 * 5) > ((4.0 - 3.0) - 2.0)。

注意左结合和右结合运算符的区别

对于左结合（例如 4 - 3 - 2 被解析为 (4 - 3) - 2），您应该调用 Expr(N)，并且您的谓词应该检查 prec < N。
对于右结合（例如 a = b = c 被解析为 a = (b = c)），您应该调用 Expr(N)，并且您的谓词应该检查 prec <= N。

付出一些额外的努力，为了最大限度地提高效率，您还可以将 PrefixExpr 和 PrimaryExpr 规则合并到 Expr 中

public rule LNode Expr(int prec = 0) @[
    ( "-" r:=Expr(50) { $result = F.Call((Symbol)"-", r, 
                                  $"-".StartIndex, r.Range.EndIndex); }
    / result:Atom )
    greedy // to suppress ambiguity warning
    (   // Remember to add [Local] when your predicate uses a local variable
        &{[Local] prec <= 10}
        "=" r:=Expr(10)
        { $result = Op($result, $"=", r); }
    |   &{[Local] prec < 20}
        op:=("&&"|"||") r:=Expr(20)
        { $result = Op($result, op, r); }
    |   &{[Local] prec < 30}
        op:=(">"|"<"|">="|"<="|"=="|"!=") r:=Expr(30)
        { $result = Op($result, op, r); }
    |   &{[Local] prec < 40}
        op:=("+"|"-") r:=Expr(40)
        { $result = Op($result, op, r); }
    |   &{[Local] prec < 50}
        op:=("*"|"/"|">>"|"<<") r:=Expr(50)
        { $result = Op($result, op, r); }
    |   "(" Expr ")" // PrimaryExpr
        { $result = F.Call($result, $Expr, $result.Range.StartIndex); }
    |   "." rhs:Atom // PrimaryExpr
        { $result = F.Dot ($result, $rhs,  $result.Range.StartIndex); }
    )*
];

在这里，您可以将 PrimaryExpr 视为具有 60 的优先级级别，但由于 prec 从未达到那么高，因此在最后两个分支上无需包含像 &{[Local] prec < 60} 这样的谓词。

甚至可以将最后一个规则 Atom 合并到这个规则中，但我们不要太激动。

为了使此示例编译，请在 ExprParser 上方添加以下代码，并确保您的项目引用了 Loyc.Syntax.dll、Loyc.Collections.dll 和 Loyc.Essentials.dll

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using Loyc;
using Loyc.Syntax;
using Loyc.Syntax.Lexing;

struct StringToken : ISimpleToken<string>
{
    public string Type { get; set; }
    public object Value { get { return Type; } }
    public int StartIndex { get; set; }
}

树解析

在几乎所有编程语言中，都可以在词法分析器和解析器之间插入一个中间阶段，将括号、方括号和花括号组合在一起，以生成“令牌树”。我一直以来的做法是编写一个普通的词法分析器，将像 { w = (x + y) * z >> (-1); } 这样的代码转换为一系列令牌对象

{  w  =  (  x  +  y  )  *  z  >>  (  -  1  )  ;  }

然后我使用一个名为 TokensToTree 的“词法分析器包装器”，它将其转换为一个在开括号下具有子项的树，像这样

{  }
|
|
+--- w  =  (  )  *  z  >>  (  )  ;
           |               |
           |               |
           +--- x  +  y    +---  -  1

令牌的子节点存储在 Value 属性中，类型为 TokenTree，它派生自 DList<Token>，并由 Children 属性返回。

你为什么要这样做？有几个原因

它允许解析器“立即”跳过括号中的表达式内容，以查看之后的内容。考虑 C# 表达式 (List<T> L) => L.Count：这与 (List < T > L) + L.Count 的解析方式完全不同！为了避免无限预读的需要，我觉得在我的 EC# 解析器中，预处理成表达式树是值得的。
有些人发现它对于实现允许语法扩展的宏系统很有用。

预处理步骤本身很简单；您可以使用现有的 TokensToTree 类（如果您的词法分析器实现了 ILexer 并生成 Token 结构），或复制并修改现有代码。（事后看来，我认为将闭括号作为开括号的子项会更好，因为目前 LLLPG 倾向于在并非真正 EOF 的情况下给出关于“EOF”的错误消息，它只是子令牌流的末尾。）

那么如何将 LLLPG 与令牌树一起使用呢？LLLPG 不直接支持令牌树，因此它只会看到树当前“级别”的令牌序列，例如 w = ( ) * z >> ( ) ;。例如，考虑 LES 解析器。通常您使用 LesLanguageService.Value.Parse("code") 这样的代码来调用它，但您可以手动构建完整的解析管道，如下所示

var input = (UString)"{ w = (x + y) * z >> (-1); };";
var errOut = new ConsoleMessageSink();
var lexer = new LesLexer(input, "", errOut);
var tree = new TokensToTree(lexer, true); // <= Convert tokens to tree!
var parser = new LesParser(tree.Buffered(), lexer.SourceFile, errOut);
var results = parser.ParseStmtsLazy().Buffered();

最初，LesParser 从令牌树的“顶层”开始，在此示例中，它只看到两个令牌，两个大括号。在我的解析器中，我使用两个辅助函数来导航进（Down）和出（Up）子树

Stack<Pair<IList<Token>, int>> _parents;

protected bool Down(IList<Token> children)
{
    if (children != null) {
        if (_parents == null)
            _parents = new Stack<Pair<IList<Token>, int>>();
        _parents.Push(Pair.Create(TokenList, InputPosition));
        _tokenList = children;
        InputPosition = 0;
        return true;
    }
    return false;
}
protected void Up()
{
    Debug.Assert(_parents.Count > 0);
    var pair = _parents.Pop();
    _tokenList = pair.A;
    InputPosition = pair.B;
}

（写完这个之后，我决定将这些方法添加到 BaseParserForList 中，这样您就可以根据需要从自己的解析器中调用它们。）

在语法中，括号和大括号的处理方式如下

|   // (parens)
    t:=TT.LParen rp:=TT.RParen {e = ParseParens(t, rp.EndIndex);}
|   // {braces}
    t:=TT.LBrace rb:=TT.RBrace {e = ParseBraces(t, rb.EndIndex);}

例如，ParseBraces 看起来像这样——它调用 Down，调用 StmtList，这是语法规则之一，最后调用 Up 返回到令牌树的上一层。

protected LNode ParseBraces(Token t, int endIndex)
{
    RWList<LNode> list = new RWList<LNode>();
    if (Down(t.Children)) {
        StmtList(ref list);
        Up();
    }
    return F.Braces(list.ToRVList(), t.StartIndex, endIndex);
}

LES 解析器当然生成 Loyc 树，而 Loyc 树又使用 RVLists，这些在它们自己的单独文章中描述；此函数使用 RWList，它是 RVList 的可变版本。

如何解析对缩进敏感的语言

Python 使用缩进和换行符来表示程序结构

if foo:
  while bar < 100:
    bar *= 2;
else:
  print("unfoo! UNFOO!")

换行符通常表示语句的结束，而冒号表示“子”块的开始。在括号、方括号或大括号内，换行符被忽略

s = ("this is a pretty long string that I'd like "
  + " to continue writing on the next line")

如果你不使用括号，Python 3 不会试图弄清楚你是否“真的”想在下一行继续一个语句

# SyntaxError after '+': invalid syntax
s = "this is a pretty long string that I'd like " + 
    " to continue writing on the next line"

在括号内，缩进被忽略，所以这是允许的

if foo:
    s = ("this is a pretty long string that I'd like "
+ " to continue writing on the next line")
    print(s)

处理这种语言最简单的方法是插入一个预处理器（后处理器？）步骤，在词法分析器之后和解析器之前。Loyc.Syntax.dll 包含一个用于此目的的预处理器，名为 IndentTokenGenerator。以下是它的使用方法

使用 BaseILexer<CharSrc, Token> 作为词法分析器的基类，而不是 BaseLexer<CharSrc> 或 BaseLexer。这将为您实现 ILexer<Token> 接口，这是 IndentTokenGenerator 所必需的。与 BaseLexer 一样，您需要在使用 AfterNewline() 从文件中读取每个换行符后调用它（有关详细信息，请参阅 BaseILexer 的文档）。

如果您使用标准 Token 类型（Loyc.Syntax.Lexing.Token），您可以将词法分析器封装在 IndentTokenGenerator 中，如下所示

/// given class YourLexerClass : BaseILexer<ICharSource,Token> { ... }
var lexer = new YourLexerClass(input);
/// IndentTokenGenerator needs a list of tokens that trigger indent tokens 
/// to be generated, e.g. Colon in Python-like languages.
var triggers = new[] { (int)YourTokenType.Colon };
var wrapr = new IndentTokenGenerator(lexer, triggers, 
    new Token((int)YourTokenType.Semicolon, 0, 0, null))
{
    /// This property specifies triggers that only have an effect when
    /// they appear at the end of a line (they are ignored elsewhere)
    EolIndentTriggers = triggers, 
    /// Tokens that represent indentation and unindent
    IndentToken = new Token((int)YourTokenType.Indent, 0, 0, null),
    DedentToken = new Token((int)YourTokenType.Dedent, 0, 0, null),
};
/// LCExt.Buffered() is an extension method that lazily converts an 
/// IEnumerator<T> or IEnumerator<T> to a list (I've used it because
/// BaseILexer is an enumerator, so ToList() can't be used directly)
List<Token> tokens = wrapr.Buffered().ToList();
var parser = new YourParserClass(tokens);

有关更多信息，请参阅 IndentTokenGenerator 的文档；它具体记录了我将如何处理 Python 等示例。

如果您不使用标准 Token 类型，则可以改用 IndentTokenGenerator，您只需实现其抽象方法。如果您需要自定义生成器的行为，则可以从这些类中的任何一个派生并重写其虚方法。

使用 LeMP 缩短代码

在 LLLPG 1.3 中，我终于完成了一些基本的宏功能，这样您就可以做很多与解析无关的事情。请参阅我的新文章“使用 LeMP 避免繁琐的编码”以了解更多信息。

新的 unroll 和 replace 宏，特别是对于消除 LLLPG 解析器中的一些样板代码很有用。您将在 LLLPG 1.3 的示例中看到这些宏的实际应用

结束

我希望您喜欢这篇文章，并且您会使用 LLLPG 来满足您的解析需求。我没有因此赚到一分钱；我只想要您的反馈，以及一份在 Roslyn 或 WebAssembly 工作的工作。一如既往，我将收到并回复发布在此文章上的任何评论。

历史

2015-08-24：首次发布时，这篇文章没有出现在任何过滤器中包含“C#”的人的每周新闻通讯中。CP 中的一个错误最近已修复，因此“更新”文章有望使其这次出现。

LLLPG v1.3.2 (2015 年 6 月 19 日)

发布了 LLLPG 第 5 部分文章
独立版本：将 BaseParser/BaseLexer 替换为双用途 LexerSource/ParserSource，它们既可以用作基类，也可以用作具有 LLLPG 的 inputSource 和 inputClass 选项的对象。
LoycSyntaxForVs.vsix 现在安装（并且碰巧可以工作）在 VS 2015 RC 中
LES“Python 模式”(ISM) 已安装并测试
实现并测试 IndentTokenGenerator
将 IIndexToLine 添加为 ILexer<Token> 的一部分，因为某些词法分析器没有 SourceFile，并且 BaseLexer 无论如何都实现了 IndexToLine
为 Visual Studio 2010 到 2015 中的增强 C# 实现了 VS 语法高亮器
LLLPG：添加了 listInitializer: var _ = new List<T>() 选项
在 LeMP 中添加了演示窗口。将 LllpgForVisualStudio.exe 重命名为 LoycFileGeneratorForVS.exe
ILexer<Token> 现在有一个类型参数；NextToken() 现在返回 Maybe<Token> 而不是 Token?，这样 Token 就不需要是结构体。
添加了 BaseILexer<CharSrc,Token>，并将其安装为 LesLexer 的新基类
添加了 BaseLexer.ErrorSink 属性；默认行为仍然是抛出 FormatException
LLLPG 错误修复：SavePosition 现在以 inputClass 选项的值为前缀。
LLLPG Bug 修复：result:Terminal 没有自动 return result。
LLLPG：添加了 parser(CastLA(bool)) 选项；它默认为 true，这在使用 ParserSource<Token> 时通常需要。
添加了 ParserSource<...>；为 BaseParser 和 BaseParserForList 添加了可选的 MatchType 参数。
将 TT 类型参数添加到 ISimpleToken 和 IToken。通常 TT=int。
LLLPG：现在生成 C# #line 指令（仅限语法操作）。调整了输出头消息。
LLLPG：LLLPG(...) 语句后不再需要大括号
LLLPG：添加了对 $result 变量的支持。
LLLPG：添加了对内联规则（inline 关键字）的基本支持
LLLPG：添加了对 any foo in (foo ...) 表达式的支持，其中 foo 指的是一个或多个其他规则上的属性或单词属性。
LLLPG StageOneParser：开始添加“!”后缀运算符以类似于 ANTLR 的旧功能；未完成。
LLLPG：添加了 AutoValueSaverVisitor 以识别标签和替换，例如 a:Foo b+:Bar Baz {$Baz}，以及集成测试和新的 terminalType 选项。
Loyc.Syntax：添加了 BaseParserForList 和 BaseParserNoBacktracking（未经测试）。添加了 ISimpleToken 接口。
Loyc.Syntax：为 BaseLexer<CharSrc> 添加了 CharSrc 类型参数，以避免在词法分析期间装箱。添加了 LexerSource 和 LexerSource<CharSrc>，用于 LLLPG 的新 inputClass 和 inputSource 选项。
LLLPG：添加了 inputSource 和 inputClass 选项以增加灵活性，因此词法分析器和解析器不再需要使用 BaseLexer / BaseParser 作为它们的基类。
LLLPG：在某些情况下，goto 标签得到了改进，例如在 (Foo | Bar) 中，标签将是 matchFoo 和 matchBar，而不是 match1 和 match2
LLLPG：部分修复了 PredictionAnalysisVisitor 中导致 EC# 解析器将 alias(...) 调用解析为类型别名构造的非确定性错误。
LeMP：大量增强功能，请参阅我的 LeMP 文章

LLLPG v1.1.0 (2014 年 2 月 23 日)

实现了 / 运算符的复杂歧义抑制行为（在第 4 部分中描述）
Loyc：移除了对 nunit.framework.dll 的依赖，替换为 Loyc.MiniTest
Loyc：添加了枚举 Severity。将 IMessageSink.Write(Symbol,...) 更改为 IMessageSink.Write(Severity,...)。重建了 LesSyntaxForVs2010 以匹配 LLLPG 1.1.0 使用的 DLL（出于某种原因，如果 LES 语法高亮器使用不同的 DLL 版本，即使 LLLPG 有自己的所有 DLL 副本，LLLPG SFG 也会中断）。

LLLPG v1.0.1

Bug 修复（词法分析器）：现在当反转集包含 EOF 时调用 MatchExcept(set)
错误修复（解析器）：从 MatchExcept(..., EOF) 中删除了 EOF
Bug 修复：默认值不再能改变解析器行为，除非输入错误
将 Match(...) 的最大参数从 3 增加到 4
错误/警告包含替代项的字符串版本（如果很短）
为每个 Alts 在输出中添加了“Line N: (...|...|...)”注释，并添加了 [AddComments(bool)] 选项
在 [Verbosity(2)] 和 [Verbosity(3)] 处添加了更多有用的跟随集信息
Error(InputPosition + li, "...") 更改为 Error(li, "...")

LLLPG v1.0 (2014 年 2 月 8 日)

EC# 支持
演示和文章已更新
演示现在默认使用 EC#（仍包含 LES 版本）并支持“数学”表达式，例如 2(2 + 5) => 14。

LLLPG v0.9.1 (2013 年 11 月 19 日)

更新了演示，使其更简洁，并消除了对 Loyc 库的依赖。
一些错误修复，一个新的 alias(X = Y) 命令，并消除了对 IntSet 的依赖。

LLLPG v0.9 (2013 年 10 月 7 日)

首次发布，附带第 1 部分文章