LL：一个解析器生成器游乐场

由于 Visual Studio 集成项目，源代码太大了，无法在此处发布，但这里有一个指向 GitHub 存储库 的链接。

引言

这个项目是一个意外。或者说，是一个实验。有时，它们之间的区别很小。

它开始于 这里，使用了我用来教读者如何编写 LL 语法分析器的代码库。

我的珠穆朗玛峰是 LL(k) 语法分析，而这朝着那个方向迈出了一步。我发现用于演示解析的源代码也是一个非常好的实验来源。

它在 DebugLL1Parser 和 DebugTokenizer 中使用 string，因此在调试会话中很容易检查。

我一直在使用它作为平台来试验 LL(k) 算法。

这个项目作为它自己的语法分析器生成器也很有用，因为它为 LL(1) 文法生成高效的表解析器。它优于 Newt，并且更可靠。语法略有改进，并且属性系统已扩展。总的来说，它使用相同的语法系统。更多关于 Newt 的信息请参考 这里，但不要使用 Newt。使用这个。

请注意，这个语法分析器仍然是 LL(1) 的。

背景

为了使用此代码库做更多事情而不仅仅是生成您可以使用 的语法分析器，您需要熟悉我 这里 使用的代码库，因为这只是它的一个演变。

正如我所说，语法格式与 Newt 类似。这是结构。

/****************************************************************\
*  ebnf.ebnf: a self describing grammar for describing grammars  *
*   by codewitch honey crisis, july 2019                         *
\****************************************************************/

grammar<start>= productions;

//
// productions
//
// marking a non-terminal with collapse removes it from 
// the tree and propagates its children to its parent
// marking a terminal with it similarly hides it from
// the result but not from the grammar, unlike hidden
//
productions<collapsed> = production productions | production;
production= identifier [ "<" attributes ">" ] "=" expressions ";";

//
// expressions
//
expressions<collapsed>= expression "|" expressions | expression;
expression= { symbol }+ |;
symbol= literal | regex | identifier | 
    "(" expressions ")" | 
    "[" expressions "]" |
    "{" expressions ("}"|"}+");

//
// attributes
//
// recognized attributes are hidden, collapsed, terminal, start, 
// followsConflict (which can be "error", "first" or "last")
// and blockEnd (string)
attributes<collapsed>= attribute "," attributes | attribute;
attribute<color="red">= identifier [ "=" attrvalue ];
attrvalue<color="orange">= literal | integer | identifier;

//
// terminals
//
literal= '"([^"\\]|\\.)*"';
regex= '\'([^\'\\]|\\.)*\'';
identifier= '[A-Z_a-z][\-0-9A-Z_a-z]*';
integer= '\-?[0-9]+';

// hide comments and whitespace
//
// if you mark a production with the terminal attribute, you
// can use ebnf to define it. Anything that's text or regex 
// is automatically a terminal
whitespace<hidden,terminal>= {" "|"\v"|"\f"|"\t"|"\r"|"\n"}+; 
// equiv regex would be the much shorter '[ \v\f\t\r\n]+';
// otherwise they are exactly the same

// single quotes denote regex. make sure to escape single
// quotes in the regex with \'
// attributes get passed through to the parser, and you can define your own
lineComment<hidden,color="green">= '//[^\n]*[\n]';
blockComment<hidden,blockEnd="*/",color="green">= "/*";

// defining these isn't required, but gives
// us better constant names
// double quotes denote a literal. the escapes are nearly the
// same as C#. \U and \x are not supported
or="|";
lt="<";
gt=">";
eq="=";
semi=";";
comma=",";
lparen="(";
rparen=")";
lbracket="[";
rbracket="]";
lbrace="{";
rbrace="}";
rbracePlus="}+"; 

就像我说的那样，与 Newt 类似。“color”属性不是由 LL 定义的。它们只是传递给解析器。在这种情况下，我将它们用于语法高亮。您可以创建任何您想要的属性，然后在解析期间检索它们。这很好。

Using the Code

此存储库包含几个项目

• ll - 主运行时库，包括用于创建和渲染解析器和表格的整个 API 和 DOM
• llrt - 使用生成的解析器所需的最小运行时。不要同时包含这个和 ll
• llgen - 用于生成解析器的工具（由于 Microsoft 的 VBCodeProvider 中的一个错误，VB 生成已损坏，C# 运行良好）
• lltree - 用于为给定文法和输入文件渲染 ASCII 解析树的工具
• llvstudio - 在 Visual Studio 2017（和 2019？）中使用的自定义工具“LL”，可以像 llgen 一样渲染
• llgui - 用于编辑 EBNF 的正在进行中的 GUI。尚未完全工作
• lltest - 我编写的作为命令行实用程序的一个测试。

DebugLL1Parser 和 DebugTokenizer 类仅使用 string 用于内部信息，因此在调试器中查看它们的操作很容易。我在将这些更改烘焙到 LL1TableParser 和 TableTokenizer 类之前，使用它们来原型化对解析器和词法分析器算法的更改。

Cfg 和 Ebnf 都非常庞大，包含用于操作 CFG 和 EBNF 文档的 API。后者公开了一个完整的 DOM 对象模型。

lltree 的 Main() 函数向我们展示了如何在不生成解析器的情况下，从任意文法执行基本解析。一切都在运行时完成。

/// <summary>
/// Usage: lltree $grammarfile $inputfile
/// </summary>
/// <param name="args">The grammar file and the input file to parse</param>
/// <returns></returns>
static int Main(string[] args)
{
    if (2!=args.Length)
    {
        _PrintUsage();
        return 1;
    }
    // read the ebnf document from the file.
    var ebnf = EbnfDocument.ReadFrom(args[0]);
    var hasErrors = false;
    // here we validate the document and print any
    // validation errors to the console.
    foreach (var msg in ebnf.Validate(false))
    {
        if (EbnfErrorLevel.Error == msg.ErrorLevel)
        {
            hasErrors = true;
            Console.Error.WriteLine(msg);
        }
    }
    // even if we have errors, we keep going.

    // create a CFG from the EBNF document
    var cfg = ebnf.ToCfg();

    // we have to prepare a CFG to be parsable by an LL(1)
    // parser. This means removing left recursion, and 
    // factoring out first-first and first-follows conflicts
    // where possible.
    // here we do that, and print any errors we encounter.
    foreach(var msg in cfg.PrepareLL1(false))
    {
        if(CfgErrorLevel.Error==msg.ErrorLevel)
        {
            hasErrors = true;
            Console.Error.WriteLine(msg);
        }
    }
    // if we don't have errors let's set up our parse.
    if(!hasErrors)
    {
        // the tokenizer is created from the EBNF document because
        // it has the terminal definitions, unlike the CFG,
        // see https://codeproject.org.cn/Articles/5162249/How-to-Make-an-LL-1-Parser-Lesson-1

        // The FileReaderEnumerable takes a filename and exposes IEnumerable<char> from
        // them. Tokenizers expect IEnumerable<char> (typically a string or char array)
        var tokenizer = ebnf.ToTokenizer(cfg, new FileReaderEnumerable(args[1]));

        // now create our parser. and since the parser *might* return multiple parse trees
        // in some cases, we keep reading until the end of document, calling ParseSubtree()
        // each time to get the result back as a ParseNode tree. We then take those nodes and
        // write them to the console via an implicit call to their ToString method
        using (var parser = cfg.ToLL1Parser(tokenizer))
            while (ParserNodeType.EndDocument != parser.NodeType)
                Console.WriteLine(parser.ParseSubtree());
                
        return 0;
                
    }
    return 1;
}

生成解析器涉及更多，但是使用生成的解析器比使用运行时解析器更容易。要初始化一个，您只需执行以下操作

var parser = new MyParser(new MyTokenizer(inputSource));

虽然使用它们的方式完全相同，除了明显的性能差异。然而，运行时解析器运行速度与生成的解析器大致相同，但是调试解析器显然要慢得多。

关注点

这里有一个巨大的 API 值得探索，老实说，我还没有时间将它全部记录下来，但是如果您关注此页面和此 GitHub，它会随着时间的推移而扩展。这个项目仍在研究中。

历史

• 2019 年 7 月 25 日 - 初始提交