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

Loyc LL(k) 解析器生成器:第三部分

starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.84/5 (6投票s)

2014 年 2 月 24 日

LGPL3

22分钟阅读

viewsIcon

26155

downloadIcon

1254

这次有很多新内容,包括一个(几乎)完整的 C# 解析器演示

欢迎来到第 3 部分

LLLPG 新手?请从第 1 部分开始。 

还有很多内容要讲,所以我们开始吧。LLLPG 1.1.0 与本文同时发布,并有一些小改进(参见底部的历史记录)。此外,zip 文件现在有四个演示,而不仅仅是一个:

  • CalcExample-Standalone:无依赖项的表达式计算器
  • CalcExample-UsingLoycLibs:使用 Loyc.Syntax.dll 中的 BaseLexerBaseParser 的表达式计算器
  • CalcExample-UsingLoycTrees:其解析器生成 Loyc 树而不是直接计算结果的表达式计算器。
  • EnhancedC#Parser:我将 LLLPG 使用的 C# 解析器从 Ecs.exe 中剥离出来,并放入这个演示程序中。

另一个下载链接是用于 VS2010 的 LES 语法高亮显示器的新版本(尚无 EC# 高亮显示器可用。)一个(不完善但很好用)用于 Notepad++ 的 LES 语法高亮显示器也可以在用户定义语言列表中找到。

今日目录:

  1. Loyc 库概述
  2. 配置 LLLPG
  3. 样板
  4. 带参数和返回值的规则
  5. 识别器的参数
  6. 保存输入
  7. LLLPG 中的错误处理机制
  8. 一个随机事实

Loyc 库概述

在编写解析器时,您必须决定是否使用 Loyc 运行时库;不使用它们的主要优点是您不必随应用程序分发 3 个 Loyc DLL。但它们包含许多有用的东西,所以请查看一下是否喜欢它们。

对于基于 LLLPG 的解析器来说,重要的库是 Loyc.Syntax.dll,它依赖于 Loyc.Essentials.dllLoyc.Collections.dll。这些 DLL 包含其大多数类的文档,通过 Loyc.Syntax.xmlLoyc.Essentials.xmlLoyc.Collections.xml 自动可用于 VS IntelliSense,尽管最好的文档是源代码

我现在才开始编写关于这些库的概述文章。所以简单来说,让我非常简要地说明这些库的用途和内容。

Loyc.Essentials.dll 是一个通用代码库,用于补充 .NET BCL(标准库)。它包含以下几类内容

  • 集合相关内容:接口、适配器、帮助类、基类、扩展方法以及简单“核心”集合的实现。
  • 几何:简单的通用几何接口和类,例如 Point<T>Vector<T> 
  • 数学:允许在通用代码中执行算术运算的通用数学接口。还包括定点类型、128 位整数数学和 MathEx 中方便的额外数学函数。
  • 其他实用程序:消息接收器 (IMessageSink)、对象标签 (ITags, HashTags)、ICloneable<T>接口适配器生成Symbol、线程相关内容、NUnit 的微型克隆 (MiniTest, RunTests)、EzStopwatchWeakReference<T>、派生自 InvalidOperationException 的额外通用异常类型(例如 InvalidStateException, ReadOnlyException)以及各种低级功能和扩展方法。Compatibility:非常少量的 .NET 4.5 内容,向后移植到 .NET 4.0。

注意:Loyc.Essentials API 尚未 100% 稳定(欢迎反馈)。此外,由于 Loyc.Essentials 已经包含许多 LINQ 样式的内容,我打算最终整合 Linq to Collections 的核心功能,但目前只编写了部分。

IMessageSink 作为一个简单、通用的日志接口。建议您的解析器将警告和错误报告给 IMessageSink 对象。您可以使用 MessageSink.Console 将(彩色)错误打印到控制台,使用 MessageSink.Null 抑制输出,并使用 MessageSink.FromDelegate((type, context, message, args) => {...}) 自定义错误处理。

G 类具有通用的数字解析器,对于词法分析器非常有用,例如 TryParseDouble,它可以解析任何合理的基数的数字,因此对于十六进制浮点字面量(如 0xF.Fp+1,表示 31.875)很有用。

Loyc.Collections.dll 是一个数据结构库,目前大部分由我编写,其中大部分都相当复杂

  • VLists:这个数据结构值得注意,因为 Loyc 节点 (LNode) 使用 RVList<LNode> 作为它们的参数和属性。这是一个实现细节,理想情况下您无需了解;但是 C# 没有我可以用它来隐藏类型的 typedef,并且由于 VLists 是 struct,如果您将它们视为 IList<T>,它们将被装箱,而您实际上不希望那样。
  • ALists,包括类似于 B+ 树的数据结构 BList<T>BDictionary<K,V> 和我最喜欢的 BMultiMap<K,V>,以及我打算在语法高亮器中使用的新的 SparseAList<T>
  • CPTrie,一种用于大型整数集以及具有长公共前缀的字符串大型集或字典的内存高效数据结构。
  • 基于 InternalSet<T> 的可变/不可变快速克隆哈希树:Set<T>MSet<T>Map<T>MMap<T>。这可能是我最喜欢的数据结构,尽管我还没有写过关于它的文章。
  • InvertibleSet<T> 是一个可以被反转的集合,因此它在概念上具有无限大小,包含不在给定有限列表中的所有内容。
  • Bijection<K1,K2>:双射是一个一对一函数及其逆函数。它通过一对 IDictionaries 实现,一个将 K1 映射到 K2,另一个将 K2 映射到 K1。您可以选择底层字典类型。

Loyc.Syntax.dll 为 LLLPG 提供了基础,并包含了 LES(语法树交换格式)的参考实现

  • BaseLexer 是使用 LLLPG 创建的词法分析器的推荐基类。
  • BaseParser<Token> 专为使用 LLLPG 创建的解析器设计。
  • ICharSource(在 Loyc.Essentials.dll 中定义)是词法分析器的标准字符源。
  • ISourceFile 封装了一个 ICharSource、一个文件名字符串以及一个用于将字符索引转换为(行、列)对并返回的映射。它派生自 IIndexPositionMapper
  • SourceRange 是一个三元组 (ISourceFile Source, int StartIndex, int Length),表示源文件中的字符范围。
  • SourcePos 是一个 (filename, line, column) 三元组。虽然 SourceRange 是一个结构体,因此可以紧凑存储,但 SourcePos 假定使用频率低得多,它是一个类,因此可以派生自 LineAndPos,后者是一个 (line, column) 对。
  • IndexPositionMapper 提供从 SourceRangeSourcePos 的映射以及反向映射,但您通常不需要使用此类别,因为此转换是 BaseLexer 的内置功能。在您的词法分析器中,您必须在每个换行符处调用 AfterNewline(),以便索引-位置映射正常工作。
  • LNode 是一个 Loyc 节点(或同义词:Loyc 树)。LNodeFactory 通常用于帮助构造 LNode
  • LesLanguageService.Value 提供了一个 LES 解析器和打印机,两者都尚未完全完成。它实现了 IParsingService
  • SourceFileWithLineRemaps 是一个用于具有 #line 指令的语言的辅助类。
  • Precedence:一种简单但灵活的运算符优先级和“可混淆性”概念的标准表示。
  • CodeSymbols 是一个 static class,其中充满了 Loyc 树中用于运算符(Add 表示 +,Sub 表示 -,Mul 表示 *,Set 表示 =,Eq 表示 == 等)、语句(Class 表示 #classEnum 表示 #enum,ForEach 表示 #foreach 等)、修饰符(Private 表示 #private,Static 表示 #static,Virtual 表示 #virtual 等)、类型(Void 表示 #voidInt32 表示 #int32,Double 表示 #double 等)、琐事(TriviaInParens 表示 #trivia_inParens 等)的标准 Symbol

Loyc 库只包含“安全”的可验证代码。

注意:有些链接指向 SourceForge 代码浏览器,它会截断代码的右侧。要在代码中向右滚动,请单击任何一行代码,然后按住向右箭头键。

配置 LLLPG

LLLPG 可以通过 Visual Studio 的自定义工具调用,也可以通过命令行(或在预构建步骤中)运行 LLLPG.exe filename 来调用。

LLLPG --help 报告以下命令行选项

--forcelang: Specifies that --inlang overrides the input file extension.
  Without this option, known file extensions override --inlang.
--help: show this screen
--inlang=name: Set input language: --inlang=ecs for Enhanced C#, --inlang=les for LES
--macros=filename.dll: load macros from given assembly
  (by default, just LEL 'prelude' macros are available)
--max-expand=N: stop expanding macros after N expansions.
--noparallel: Process all files in sequence
--outext=name: Set output extension and optional suffix:
    .ecs (Enhanced C#), .cs (C#), .les (LES)
  This can include a suffix before the extension, e.g. --outext=.output.cs
  If --outlang is not used, output language is chosen by file extension.
--outlang=name: Set output language independently of file extension
--parallel: Process all files in parallel (this is the default)
--timeout: Aborts the processing thread(s) after this number of seconds
  (0=never, default=30)
--verbose: Print extra status messages (e.g. discovered Types, list output files).

有问题吗?

其中一些选项,例如 --verbose--timeout=N,在 LLLPG 自定义工具中受支持;您可以在 Visual Studio 的“自定义工具命名空间”字段中放置命令行选项。不支持 --outext 选项,因为 Visual Studio 要求 LLLPG 在提供“自定义工具命名空间”值之前选择输出文件扩展名;如果您想要 LES 输出,可以使用 LLLPG_Les 作为自定义工具名称而不是 LLLPG

注意:没有 --verbose 选项,[Verbosity(N)] 语法属性不起作用。

在您的 *.ecs 或 *.les 输入文件中,调用 LLLPG 的语法是使用以下语句之一

LLLPG(lexer)                 { /* rules */ };
LLLPG(lexer(...options...))  { /* rules */ };
LLLPG(parser)                { /* rules */ };
LLLPG(parser(...options...)) { /* rules */ };
LLLPG   { /* parser mode is the default */ };

LES 需要分号,而 EC# 不需要。此外,LES 文件允许不带括号的 LLLPG lexer {...}LLLPG parser {...},这(由于 LES 的语法规则)与 LLLPG(lexer) {...}LLLPG(parser) {...} 完全等价。

目前,lexer 只有一种选项可用

  • setType(type):大型集合的数据类型。当您编写包含四个以上元素的集合时,例如 'a'|'e'|'i'|'o'|'u'|'y',LLLPG 会生成一个集合对象,并使用 set.Contains(la0) 进行预测,使用 Match(set) 进行匹配,例如,它不是生成 Match('a', 'e', 'i', 'o', 'u', 'y'),而是生成一个包含类似于 static HashSet<int> RuleName_set0 = NewSet('a', 'e', 'i', 'o', 'u', 'y'); 的语句的集合,然后调用 Match(RuleName_set0)。默认值是 HashSet<int>

以下选项可用于 parser

  • setType(type):大型集合的数据类型(与 lexer 的工作方式相同)
  • laType(type)la0la1 等的数据类型。这通常是您用来表示标记类型的 enum 的名称(默认值:int)。
  • matchType(type)matchCast(type):导致将类型转换添加到传递给 Match 的所有令牌类型。例如,如果您使用 matchCast(int) 选项,它会将 Match('+', '-') 更改为 Match((int) '+', (int) '-')matchCastmatchType 的同义词。
  • allowSwitch(bool):是否允许 switch 语句(默认值:true)。在 C# 中,switch case 必须是常量,因此某些 laType 数据类型(如 Symbol)与 switch 不兼容。因此,此选项可用于阻止生成 switch 语句。需要布尔文字 truefalse(在 LES 中为 @true@false)。

上述选项适用于 lexerparser 辅助对象,它们控制代码生成并定义如何解释终端

  • lexer 模式需要数字终端,并允许像 1..31'a'..'z' 这样的数字范围
  • parser 模式允许任何字面量或复杂标识符,但不支持数字范围。

除了 lexerparser 选项之外,您还可以在 LLLPG 语句之前添加一个或多个以下属性

  • [FullLLk(true)]:启用更深层的预测分析(稍后解释)
  • [Verbosity(int)]:打印额外消息以帮助调试语法。需要一个整数文字并指定要打印多少细节:1 表示基本信息,2 表示额外信息,3 表示过多信息。打印的详细信息包括首集、后继集和预测树。注意:此属性在没有 --verbose 选项的情况下不起作用。
  • [NoDefaultArm(true)]:在所有您未提供 defaulterror 分支的岔路口添加对 Error(...) 的调用(参见下面的“错误处理机制”部分)。
  • [LL(int)](同义词:[k(int)][DefaultK(int)]):指定此语法中默认的最大前瞻字符或标记数。
  • [AddComments(false)]:默认情况下,输出文件中会在每个 Alts(分支点:| / * ?)生成的代码前面打印一行注释。[AddComments(false)] 会删除这些注释。

样板

EC# 语法文件的典型结构如下。您将首先定义令牌类型和词法分析器...

using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using Loyc;               // optional (for IMessageSink, Symbol, etc.)
using Loyc.Collections;   // optional (many handy interfaces & classes)
using Loyc.Syntax.Lexing; // optional (for BaseLexer)
using Loyc.Syntax;        // optional (for BaseParser<Token>, LNode)

namespace MyLanguage
{
    using TT = TokenType; // Abbreviate TokenType as TT

    public enum TokenType
    {
        EOF = -1,
        Unknown = 0,
        Spaces = 1, 
        Newline = 2,
        Number = 3,
        /* add more token names here */
    }

    // Optional: define a class/struct for Tokens, or use Loyc.Syntax.Lexing.Token.
    // In the latter case, define a "public static TokenType Type(this Token t)" 
    // extension method and define your TokenTypes based on TokenKind. Example:
    // http://sourceforge.net/p/loyc/code/HEAD/tree/Src/Loyc.Syntax/LES/TokenType.cs
    public struct Token {
        public TokenType Type;
        public int StartIndex;
        /* add additional members here */
    }

    class MyLexer : BaseLexer
    {
        // If using the Loyc libraries: BaseLexer reads character data from an
        // ICharSource. The string wrapper StringSlice implements ICharSource.
        public MyLexer(string text, string fileName = "") 
            : this((StringSlice)text, fileName) { }
        public MyLexer(ICharSource text, string fileName = "") 
            : base(text, fileName) { }

        // Error handler that may be called by LLLPG or BaseLexer. LLLPG requires 
        // many other methods and properties provided by the base class.
        protected override void Error(int lookahead, string message)
        {
            Console.WriteLine("At index {0}: {1}", InputPosition + lookahead, message);
        }

        // Loyc.Syntax: ISourceFile.IndexToLine(i) converts index to line/column
        public new ISourceFile SourceFile { get { return base.SourceFile; } }

        LLLPG (lexer)
        {
            private TokenType _type;
            private int _startIndex;

            public token Token NextToken()
            {
                _startIndex = InputPosition;
                @[ { _type = TT.Spaces; }  (' '|'\t')+
                 | { _type = TT.Newline; } Newline
                 | { _type = TT.Number; }  Number
                 | ...
                 | error _?
                   { _type = TT.Unknown; Error(0, "Unrecognized token"); }
                 ];
                return new Token() { 
                    Type = _type, StartIndex = _startIndex, ...
                };
            }

            // 'extern' suppresses code generation, so the code of Newline is
            // inherited from BaseLexer but LLLPG still knows what's in it.
            extern token Newline @[ '\r' '\n'? | '\n' ];

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

BaseLexer 只要求您定义一个 Error() 方法。BaseParser<Token> 需要更多工作,因为

  • 它不了解您的 TokenType:需要转换为“int”,因为 C# 不允许泛型类有效地比较未知枚举值或将其转换为 int。因此,您必须使用 matchType(int) 选项,并且 BaseParser 要求您定义 EOFInt,而 LLLPG 本身需要您定义 EOF
  • 它不知道如何从 Token 中获取您的 TokenType,因此您必须重写 LA0Int
  • 与基于 ICharSource (Loyc 版本) 或 IList<char> (zip 文件中的独立版本) 的 BaseLexer 不同,BaseParser 不负责存储输入令牌,因为我无法确定管理输入令牌的单一合理方式。因此,您的派生类负责存储令牌列表并重写 LT(i) 以向基类提供 Token(由 Match(...) 方法返回)。

所以,这是一个解析器的典型大纲

namespace MyLanguage
{
    public partial class MyParser : BaseParser<Token>
    {
        ISourceFile _sourceFile;
        List<Token> _tokens;

        public MyParser(ICharSource text, string fileName)
        {
            // Grab all tokens from the lexer and ignore spaces
            var lexer = new MyLexer(text, fileName);
            _sourceFile = _lexer.SourceFile;
            _tokens = new List<Token>();
            Token t;
            while ((t = lexer.NextToken()).Type != TT.EOF) {
                if ((t.Type != TT.Spaces && t.Type != TT.Newline))
                    _tokens.Add(t);
            }
        }

        #region Methods & properties required by BaseParser and LLLPG
        // Here are a couple of things required by LLLPG itself (EOF, LA0, 
        // LA(i)) followed by the helper methods required by BaseParser. 
        // The difference between "LA" and "LT" is that "LA" refers to the 
        // lookahead token type (e.g. TT.Num, TT.Add, etc.), while "LT" 
        // refers to the entire token (that's the Token structure, in this 
        // example.) LLLPG itself only requires LA, but BaseParser assumes 
        // that there is also a "Token" struct or class, which is the type 
        // returned by its Match() methods.

        const TokenType EOF = TT.EOF;
        TokenType LA0 { get { return LT0.Type; } }
        TokenType LA(int offset) { return LT(offset).Type; }

        protected override int EofInt() { return (int) EOF; }
        protected override int LA0Int { get { return (int) LT0.Type; } }
        protected override Token LT(int i)
        {
            i += InputPosition;
            if (i < _tokens.Count) {
                return _tokens[i];
            } else {
                return new Token { Type = EOF };
            }
        }
        protected override void Error(int lookahead, string message)
        {
            int tokenIndex = InputPosition + lookahead, charIndex;
            if (tokenIndex < _tokens.Count)
                charIndex = _tokens[tokenIndex].StartIndex;
            else
                charIndex = _sourceFile.Text.Count;
            SourcePos location = _sourceFile.IndexToLine(charIndex);
            Console.WriteLine("{0}: {1}", location.ToString(), message);
        }
        // BaseParser.Match() uses this for constructing error messages.
        protected override string ToString(int tokenType)
        {
            switch ((TT) tokenType) {
            case TT.Id:     return "identifier";
            case TT.Num:    return "number";
            case TT.Set:    return "':='";
            case TT.LParen: return "'('";
            case TT.RParen: return "')'";
            default:        return ((TokenType) tokenType).ToString();
            }
        }

        #endregion

        LLLPG(parser(laType(TokenType), matchType(int)))
        {
            public rule LNode Start() @[...];
        }
    }
} 

(我很乐意接受减少样板代码量的建议。如果您正在解析整个编程语言,这些样板代码没什么大不了的,但对于“快速而粗糙”的小型解析器来说,这有点多。)

通常更方便将语法与其他代码分开存储在单独的文件中,因为您无法在 LLLPG 文件中获得代码完成/IntelliSense。因此,我总是将我的解析器标记为 partial,这样我就可以在 IDE 理解的文件中编写部分代码。

通常,您将在语法中使用 {actions} 来生成语法树对象。您可以自行设计语法树,也可以使用 Loyc 树 (LNode)。LNode 具有用于构造它们的 static 方法,但使用 LNodeFactory 更方便,因为它会跟踪当前源文件 (ISourceFile) 并提供更多种类的方法来构造树。这是一个构造 LNode 的小型表达式解析器(假设词法分析器生成 Loyc Tokens)

public partial class MyParser : BaseParser<Token>
 {
    LNodeFactory F;

    public MyParser(...)
    {
        ISourceFile file = ...;
        F = new LNodeFactory(file);
    }

    LLLPG (parser(laType(TokenType), matchType(int)))
    {
        alias("(" = TT.LParen);
        alias(")" = TT.RParen);
        alias("*" = TT.Mul);
        alias("/" = TT.Div);
        alias("+" = TT.Add);
        alias("-" = TT.Sub);

        LNode BinOp(Symbol type, LNode lhs, LNode rhs)
        {
            return F.Call(type, lhs, rhs, lhs.Range.StartIndex, rhs.Range.EndIndex);
        }

        public rule LNode Start() @[ e:=AddExpr EOF {return e;} ];

        private rule LNode AddExpr() @[
            e:=MulExpr
            [ op:=("+"|"-") rhs:=MulExpr {e = BinOp((Symbol) op.Value, e, rhs);} ]*
            { return e; }
        ];

        private rule LNode MulExpr() @[ 
            e:=PrefixExpr
            [ op:=("*"|"/") rhs:=PrefixExpr 
              {e = BinOp((Symbol) op.Value, e, rhs);}
            ]*
            {return e;}
        ];

        private rule LNode PrefixExpr() @
            [ minus:="-" e:=Atom {return F.Call(S.Sub, e, minus.StartIndex, e.Range.EndIndex);}
            | e:=Atom            {return e;}
            ];

        private rule LNode Atom() @[
            {LNode r;}
            ( t:=TT.Id          {r = F.Id(t);}
            | t:=TT.Num         {r = F.Literal(t);}
            | "(" r=Expr() ")"
            | error             {r = F._Missing;}
              {Error(0, "Expected identifer, number, or (parens)");}
            )
            {return r;}
        ];
    }
}

LLLPG 1.1.0 的 zip 文件中包含一个完整示例(请注意,演示打印的“#”符号计划移除)。顺便说一句,如果您对如何更改 LLLPG 以更紧凑或优雅的方式构造语法树有任何想法,我虚心接受建议。

带参数和返回值的规则

您可以为任何规则添加参数和返回值,并在调用任何规则时使用参数

// Define a rule that takes an argument and returns a value.
// Matches a pattern like TT.Num TT.Comma TT.Num TT.Comma TT.Num...
// with a length that depends on the 'times' argument.
token double Mul(int times) @[
    x:=TT.Num 
    nongreedy(
       &{times>0} {times--;}
        TT.Comma y:=Num
        {x *= y;})*
    {return x;}
];
// To call a rule with a parameter, add a parameter list after 
// the rule name.
rule double Mul3 @[ x:=Mul(3) {return x;} ];

这是为此解析器生成的代码

double Mul(int times)
{
  int la0, la1;
  var x = Match(TT.Num);
  for (;;) {
     la0 = LA0;
     if (la0 == TT.Comma) {
        if (times > 0) {
          la1 = LA(1);
          if (la1 == Num) {
             times--;
             Skip();
             var y = MatchAny();
             x *= y;
          } else
             break;
        } else
          break;
     } else
        break;
  }
  return x;
}
double Mul3()
{
  var x = Mul(3);
  return x;
}

Foo(123) 和带有空格的 Foo (123) 之间存在差异。Foo(123) 使用参数 123 调用 Foo 规则;Foo (123) 等同于 Foo 123,因此匹配规则(或终结符)Foo,然后是数字 123(在 ASCII 中为“{”)。

识别器的参数

正如您在上一篇文章中学到的,每个规则都可以有一个由语法谓词 &(...) 调用的“识别器形式”。识别器始终具有 bool 返回类型,无论主规则的返回类型如何,并且任何动作块 {...} 都从识别器中移除(目前无法保留动作块,抱歉)。

您可以使用规则上的 recognizer 属性来保留或丢弃识别器中的参数。观察以下规则如何生成代码

LLLPG(parser) { 
    [recognizer { void FooRecognizer(int x); }]
    token double Foo(int x, int y) @[ match something ];

    token double FooCaller(int x, int y) @[
        Foo(1) Foo(1, 2) &Foo(1) &Foo(1, 2)
    ];
}

Foo 的识别器版本将只接受一个参数,因为 recognizer 属性只指定了一个参数。尽管 recognizer 属性使用 void 作为 FooRecognizer 的返回类型,但 LLLPG 忽略了这一点,并将返回类型更改为 bool

double Foo(int x, int y)
{
  Match(match);
  Match(something);
}
bool Try_FooRecognizer(int lookaheadAmt, int x)
{
  using (new SavePosition(this, lookaheadAmt))
     return FooRecognizer(x);
}
bool FooRecognizer(int x)
{
  if (!TryMatch(match))
     return false;
  if (!TryMatch(something))
     return false;
  return true;
}
double FooCaller(int x, int y)
{
  Foo(1);
  Foo(1, 2);
  Check(Try_FooRecognizer(0, 1), "Foo");
  Check(Try_FooRecognizer(0, 1, 2), "Foo");
}

请注意,LLLPG 不会验证 FooCaller 是否将正确数量的参数传递给 FooFooRecognizer,至少在此情况下不会。因此,LLLPG 不会抱怨或更改不正确的调用 Foo(1)Try_FooRecognizer(0, 1, 2)。通常,LLLPG 只会重复您提供的参数列表,无论它是否有意义。但是,当一个普通规则“转换”为识别器时,LLLPG 可以自动减少该规则调用的其他规则的参数数量,如下所示

[recognizer {void BarRecognizer(int x);}]
token double Bar(int x, int y) @[ match something ];

rule void BarCaller @[
    Bar(1, 2)
];

rule double Start(int x, int y) @[ &BarCaller BarCaller ];

生成的代码

double Bar(int x, int y)
{
  Match(match);
  Match(something);
}
bool Try_BarRecognizer(int lookaheadAmt, int x)
{
  using (new SavePosition(this, lookaheadAmt))
     return BarRecognizer(x);
}
bool BarRecognizer(int x)
{
  if (!TryMatch(match))
     return false;
  if (!TryMatch(something))
     return false;
  return true;
}
void BarCaller()
{
  Bar(1, 2);
}
bool Try_Scan_BarCaller(int lookaheadAmt)
{
  using (new SavePosition(this, lookaheadAmt))
     return Scan_BarCaller();
}
bool Scan_BarCaller()
{
  if (!BarRecognizer(1))
     return false;
  return true;
}
double Start(int x, int y)
{
  Check(Try_Scan_BarCaller(0), "BarCaller");
  BarCaller();
}

请注意,BarCaller() 调用 Bar(1, 2),带两个参数。但是,Scan_BarCaller(它是 BarCaller 的自动生成的识别器名称)调用 BarRecognizer(1),只带一个参数。有时主规则 (Bar) 需要的参数在规则的识别器形式 (BarRecognizer) 中不需要,因此 LLLPG 允许您在 recognizer 属性中删除参数;LLLPG 将在生成规则的识别器版本时自动删除调用站点的参数。您只能从参数列表的末尾删除参数;例如,如果您编写

[recognizer { void XRecognizer(string second); }]
rule double X(int first, string second) @[ match something ];

LLLPG **不会注意到**您删除了*第一个*参数而不是*第二个*参数,它只会注意到识别器具有*更短的*参数列表,因此它只会删除*第二个*参数。此外,LLLPG 只会从对识别器的调用中删除参数,而不是对主规则的调用中删除参数,因此识别器不能接受比主规则更多的参数。

保存输入

LLLPG 识别三个运算符,用于将读取终端或非终端的结果“赋值”给变量:=、:= 和 +=。此表显示了如何为这些运算符生成代码

运算符 示例 终端生成的代码 非终结符生成的代码
= x=Foo x = Match(Foo); x = Foo();
:= x:=Foo var x = Match(Foo); var x = Foo();
+= x+=Foo x.Add(Match(Foo)); x.Add(Foo());

您可以匹配一组终端中的一个,例如 x:=('+'|'-'|'.') 生成的代码类似于 var x = Match('+', '-', '.')(或者对于大型集合,为 var x = Match(set))。然而,目前 LLLPG 不支持匹配非终端列表,例如 x:=(A()|B()) 不受支持。

我正在考虑添加一个功能,您可以简单地编写 Foo 而不是 foo:=Foo,然后稍后在代码中编写 $Foo,这样就可以追溯地保存值。例如,与其像这样编写代码

private rule LNode IfStmt() @[
    {LNode @else = null;}
    t:=TT.If "(" cond:=Expr ")" then:=Stmt 
    greedy(TT.Else @else=Stmt)?
    {return IfNode(t, cond, then, @else);}
];

它将被这样编写

private rule LNode IfStmt() @[
    {LNode @else = null;}
    TT.If "(" Expr ")" Stmt 
    greedy(TT.Else @else=Stmt)?
    {return IfNode($TT.If, $Expr, $Stmt, @else);}
];

这将减少语法内部的混乱。这个想法(尚未实现)来自 ANTLR,它也有类似的功能(实际上更强大)。有什么建议吗?

LLLPG 中的错误处理机制

好吧,坦率地说,我还没有 100% 弄清楚如何在解析器中正确处理错误,但我认为 LLLPG 确实为您提供了足够的灵活性。

首先,在匹配单个终端时,LLLPG 让您自己的代码负责错误处理。例如,如果规则是这样写的

rule PlusMinus @[ '+'|'-' ];

生成的代码是

void PlusMinus()
{
  Match('-', '+');
}

所以 LLLPG 依赖 Match() 方法来决定如何处理错误。如果下一个输入既不是 '-' 也不是 '+'Match() 应该怎么做

  • 抛出异常?
  • 打印错误,消耗一个字符并继续?
  • 打印错误,保持 InputPosition 不变并继续?

我不确定最佳方法是什么,但您可以根据自己的选择处理这种情况。如果您对这种默认的错误处理有任何建议,请留下评论。

对于需要 if/else 链或 switch 语句的情况,LLLPG 的默认行为是乐观的:简单地说,它假定没有错误的输入。当您编写

rule Either @[ 'A' | B ];

输出为

void Either()
{
  int la0;
  la0 = LA0;
  if (la0 == 'A')
    Skip();
  else
    B();
}

在没有错误输入的情况下,如果输入不是 'A',那么它一定是 B。因此,当您编写替代项列表时,如果其中一个作为包罗万象或默认项有意义,您应该将其放在替代项列表的最后,这将使其成为默认项。您还可以通过在某个替代项的开头编写单词 default 来指定哪个分支是默认项

rule B @[ 'B' ];
rule Either @[ default 'A' | B ];

void B()
{
  Match('B');
}
void Either()
{
  int la0;
  la0 = LA0;
  if (la0 == 'A')
    Match('A');
  else if (la0 == 'B')
    B();
  else
    Match('A');
}

请记住,如果替代项之间存在歧义,则替代项的顺序控制着它们的优先级。因此,您至少有两个理由更改不同替代项的顺序

  1. 当替代项重叠时,给予一个比另一个更高的优先级
  2. 在输入无效的情况下,选择一个作为默认值

有时这些目标是冲突的:您可能希望某个分支具有更高的优先级并且*也*是默认值。这就是 default 关键字的用武之地。在此示例中,“辅音”分支是默认分支

LLLPG(lexer)
{
    rule ConsonantOrNot @[ 
        ('A'|'E'|'I'|'O'|'U') {Vowel();} / 'A'..'Z' {Consonant();}
    ];
}

void ConsonantOrNot()
{
  switch (LA0) {
  // (Newlines between cases removed for brevity)
  case 'A': case 'E': case 'I': case 'O': case 'U':
    {
      Skip();
      Vowel();
    }
    break;
  default:
    {
      MatchRange('A', 'Z');
      Consonant();
    }
    break;
  }
}

您可以使用 default 关键字将“元音”分支标记为默认值,在这种情况下,也许我们应该将其称为“非辅音”而不是“元音”

LLLPG(lexer) {
    rule ConsonantOrNot @[ 
        default ('A'|'E'|'I'|'O'|'U') {Other();} 
               / 'A'..'Z' {Consonant();}
    ];
}

生成的代码将有所不同

static readonly HashSet<int> ConsonantOrNot_set0 = NewSet('A', 'E', 'I', 'O', 'U');
void ConsonantOrNot()
{
    do {
        switch (LA0) {
        case 'A': case 'E': case 'I': case 'O': case 'U':
            goto match1;
        case 'B': case 'C': case 'D': case 'F': case 'G':
        case 'H': case 'J': case 'K': case 'L': case 'M':
        case 'N': case 'P': case 'Q': case 'R': case 'S':
        case 'T': case 'V': case 'W': case 'X': case 'Y':
        case 'Z':
            {
                Skip();
                Consonant();
            }
            break;
        default:
            goto match1;
        }
        break;
    match1:
        {
            Match(ConsonantOrNot_set0);
            Other();
        }
    } while (false);
}");

此代码确保第一个分支匹配所有不在 'B'..'D'、'F'..'H'、'J'..'N'、'P'..'T' 或 'V'..'Z' 范围内的字符,即非辅音(*注意*:此行为是在 LLLPG 1.0.1 中添加的;LLLPG 1.0.0 将 default 仅视为重新排序替代项。)

命名默认分支永远不应改变生成的解析器在*输入有效时*的行为。默认分支在输入出乎意料时被调用,这意味着它专门是一种错误处理机制。

注意(A | B | default C) 通常(但并非总是)与 (A | B | C) 相同。粗略地说,在后一种情况下,如果代码会更简单,LLLPG 有时会允许 A 或 B 处理无效输入。

另一个错误处理功能是 LLLPG 可以自动插入错误处理程序,在所有比调用 Match 更复杂的情况下。这通过 [NoDefaultArm(true)] 语法选项实现,该选项导致在输入不在预期集合中时调用 Error(int, string) 方法。这是一个示例

//[NoDefaultArm]
LLLPG(parser)
{
    rule B @[ 'B' ];
    rule Either @[ ('A' | B)* ];
}


void B()
{
  Match('B');
}
void Either()
{
  int la0;
  for (;;) {
     la0 = LA0;
     if (la0 == 'A')
        Skip();
     else if (la0 == 'B')
        B();
     else
        break;
  }
}

添加 [NoDefaultArm] 后,输出更改为

void Either()
{
  int la0;
  for (;;) {
     la0 = LA0;
     if (la0 == 'A')
        Skip();
     else if (la0 == 'B')
        B();
     else if (la0 == EOF)
        break;
     else
        Error(InputPosition + 0, "In rule 'Either', expected one of: (EOF|'A'|'B')");
  }
}

错误消息是预定义的,并且 [NoDefaultArm] 目前不支持单独的规则。

此模式可能不足以用于专业语法,因此我正在征求改进建议。使用此功能的另一种方法是使用 default_error 在单个循环中选择性地启用它。例如,此语法生成与上一个语法相同的输出

LLLPG(parser)
{
    rule B @[ 'B' ];
    rule Either @[ ('A' | B | default_error)* ];
}

default_error 必须单独使用;它不支持,例如,附加自定义操作。

您可以使用 error 分支自定义特定循环的错误处理

void Error(string s) { ... }

LLLPG
{
    rule B @[ 'B' ];
    rule Either @[ ('A' | B | error _ {Error(""Anticipita 'A' aŭ B ĉi tie"");})* ];
}

在这个例子中,我用世界语写了一个自定义错误信息;这是输出

void B()
{
  Match('B');
}
void Either()
{
  int la0;
  for (;;) {
    la0 = LA0;
    if (la0 == 'A')
      Skip();
    else if (la0 == 'B')
      B();
    else if (la0 == EOF)
      break;
    else {
      MatchExcept();
      Error("Anticipita 'A' aŭ B ĉi tie");
    }
  }
}

请注意,我在 error 分支内使用了 _ 来跳过无效的终端。error 分支的行为与 default 分支非常相似,不同之处在于它不参与预测决策。一种正式的解释方式是,(A | B | ... | error E) 等价于 (A | B | ... | default ((~_) => E)),尽管我实际上并不是那样实现的,所以它可能不是完全等价的。

我认为我应该提及的关于错误处理的另一件事是 Check() 函数,它用于检查 &and 谓词是否匹配。之前您已经看到一个进行预测决策的 and-谓词,例如

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

在这种情况下,'.' '0'..'9'+ 只有在 !dot 的情况下才会匹配

...
la0 = LA0;
if (la0 == '.') {
    if (!dot) {
        la1 = LA(1);
        if (la1 >= '0' && la1 <= '9') {
            Skip();
            Skip();
            for (;;) {
                ...

代码之所以这样,是因为 Number 的后续集是 _*,这将在下一篇文章中解释,我将在其中讨论 tokenrule 之间的区别。由于后续集,LLLPG 假定 Number 后面可能会跟着 '.',因此 !dot 必须包含在预测决策中。但如果 Number 是一个正常的 rule(并且 Number 的后续集不包括 '.'

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

那么生成的代码是不同的

...
la0 = LA0;
if (la0 == '.') {
  Check(!dot, "!dot");
  Skip();
  MatchRange('0', '9');
  for (;;) {
    ...

在这种情况下,当 LLLPG 看到 '.' 时,它决定进入可选项 (&{!dot} '.' '0'..'9'+)?,而不首先检查 &{!dot},因为 '.' 不被视为*跳过*可选项的有效输入。基本上 LLLPG 认为“如果这里有一个点,匹配可选项是唯一合理的事情”。所以,它假设有一个 Check(bool, string) 方法,它会在预测*之后*调用该方法来检查 &{!dot}

目前您不能(通常)强制将 and-谓词作为预测的一部分进行检查;预测分析*仅*在需要解决歧义时检查 and-谓词。您也不能抑制 Check 语句或覆盖 Check 的第二个参数。如果此限制给您带来问题,请告诉我。

LLLPG 的错误处理就到这里了!

一个随机事实

你知道吗?与 ANTLR 不同,LLLPG 在解释由 |/ 分隔的循环和替代项时并不太关心括号。例如,所有以下规则都被解释为相同的方式并生成相同的代码

rule Foo1 @[ ["AB" | "A" | "CD" | "C"]*     ];
rule Foo2 @[ [("AB" | "A" | "CD" | "C")]*   ];
rule Foo3 @[ [("AB" | "A") | ("CD" | "C")]* ];
rule Foo4 @[ ["AB" | ("A" | "CD") | "C"]*   ];
rule Foo5 @[ ["AB" | ("A" | ("CD" | "C"))]* ];

循环 (*) 和所有分支都被集成到一个单一的预测树中,无论您如何使用括号进行调整。了解这一点可能会帮助您更好地理解错误消息和生成的代码。

另一个值得知道的事情是,当 | 的左侧和右侧都是终结符时,它的行为是不同的。('1'|'3'|'5'|'9' '9') 不被视为*四个*替代项,而只被视为*两个*:('1'|'3'|'5') | '9' '9',正如您从生成的代码中可以看到的

  la0 = LA0;
  if (la0 == '1' || la0 == '3' || la0 == '5')
    Skip();
  else {
    Match('9');
    Match('9');
  }

发生这种情况是因为在 LLLPG 中,“终结符集”始终是一个单一单元,即当 | 的左侧和右侧都是终结符集时,多个终结符(例如 ('A'|'B'))会被组合并视为与单个终结符 'X' 相同。如果您在第一个替代项中插入一个空代码块,它就不再被视为简单终结符,LLLPG 无法再将终结符合并到单个集合中。在这种情况下,LLLPG 会看到四个替代项,从而导致不同的输出

rule Foo@[ '1' {/*empty*/} | '3' | '5' | '9' '9' ];

void Foo()
{
  int la0;
  la0 = LA0;
  if (la0 == '1')
    Skip();
  else if (la0 == '3')
    Skip();
  else if (la0 == '5')
    Skip();
  else {
    Match('9');
    Match('9');
  }
}

第 3 部分结束

更新:第 4 部分现已发布!

以下主题仍将在未来的文章中讨论:

  • FullLLk 与“近似”LL(k)
  • tokenrule
  • 管理歧义。
  • LLLPG 使用的 API。当然,您已经见过它,我只需要编写一个完整的参考。
  • 高级技术:树解析、关键字解析、将多个优先级级别折叠为一个规则以及 EC# 解析器使用的其他技巧。
  • 关于 Loyc 及其库的一切。您可以使用 LeMP 完成的事情:除了 LLLPG 之外的其他源代码操作器。

您是否正在使用 LLLPG 解析一种有趣的语言?请留言!

历史  

LLLPG v1.0.1:

  • bug 修复(词法分析器):现在当倒置集包含 EOF 时,我们调用 MatchExcept(set)
  • bug 修复(解析器):从 MatchExcept(..., EOF) 中移除了 EOF
  • bug 修复:除了不良输入,default 不再能改变解析器行为
  • Match(...) 的最大参数数量从 3 增加到 4
  • 错误/警告包含 alt 的字符串版本(如果它很短)
  • 为每个 Alts 添加了“Line N: (...|...|...)”注释到输出,以及 [AddComments(bool)] 选项
  • [Verbosity(2)][Verbosity(3)] 中添加了更多有用的后续集信息
  • Error(InputPosition + li, "...") 更改为 Error(li, "...")

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 SFG 会中断,即使 LLLPG 有自己的所有 DLL 副本。)
更早的历史记录:请参阅第 1 部分
© . All rights reserved.