Pck：解析器构造工具包
4.92/5 (8投票s)
一个用于不同解析工具的解析器生成器和统一系统
请访问 Pck 的 GitHub 仓库 获取最新代码。我正在每天开发它。
引言
PCK 是一个巨大的工程，至少对于一个人来说是这样，但它是多年渴望的结晶。我一直希望能使用任何我需要的语法和任何我需要的解析器。PCK 是实现这一目标的一步。它目前支持 Yacc/Bison 和 Flex/lex。即将支持 GOLD、ANTLR 以及可能的 Coco/R。
此外，Pck 的独特之处在于它将生成过程（包括语法转换）的许多环节暴露给控制台，以便您可以在将其输入到转换的下一阶段之前，使用中间工具处理输出。例如，您可能可以将语法的较高层级表示转换为引擎使用的较低层级表示，然后对其进行左分解以进行 LL(1) 解析，然后再将其传递给生成器，这有点像您的编译器和链接器协同工作。
它目前支持 LL(1)，LALR(1) 已完成约 60% - 它已经可以解析并生成表，但我认为在进行更多研究之前，解析器不会准备好。我正在尝试使用自底向上的解析器进行树形处理，这并不容易。
LL(1) 解析器目前运行良好，GitHub 也在定期更新。
背景
解析器生成器的优点在于，它们有很多。
解析器生成器的缺点在于，它们有很多。
每个解析器生成器都有其优点和缺点，然后还要考虑可用语法的情况，尤其是对于 C 或 SQL92 等非平凡的语言标准。通常，您可以找到一个解析器生成器，它拥有您需要的语法，但缺少您需要的一些技术规范，或者它不支持您需要的平台。
然而，大多数解析器生成器都使用相同的基本上下文无关语法 (CFG) 范式和有限状态范式来处理词法分析器，因此它们具有非常相似的基本格式。
Pck 的目标是最终能够翻译各种语法格式，以便用户可以选择最适合其语法的解析器，或者以他们最舒适的格式组合语法，而无需考虑工具。
免责声明：Pck 无法翻译代码，因此我们不处理语法文件中的代码。此类代码必须手动移植，尽管随着项目的成熟，lex 和 yacc 的生成将在解释这些语法中的代码方面变得更加智能，因为这些语法几乎全部基于代码。幸运的是，像 ANTLR 这样的更现代的解析器不鼓励使用代码来解决语法中的语义和词法结构。毋庸置疑，Pck 最适合使用 Gold 等无代码生成器生成的语法。
除了作为语法翻译引擎，Pck 本身也是一个解析器生成器，目前生成 LL(1) 解析器，并将添加更多类型。
它还提供另一种语法格式，“XBNF”，该格式深受 EBNF/ABNF 和程序员语法格式的启发。它是无代码的，具有属性，易于理解，易于与其他格式相互转换，并且足够表达，能够以其所表示的语言结构的完全保真度来表示其他语法。当然，它也可以自我表达。
然而，Pck 的主要格式称为 PCK 规范。它是一种简单的基于规则的格式，可以包含属性、语法规则和词法规则，尽管它不一定包含所有这三项（如果您需要，有些可以纯粹是 lex 文档或纯粹是语法文档）。
属性是针对非终结符和终结符的。
A:hidden,collapsed=true,color="green"
将指定非终结符 A 具有两个 boolean 属性，值为 true（由于未明确指示值，hidden=true 是隐式的），以及一个值为绿色的 string 属性 (color)。 String 转义类似于 C# - 不支持 \U。
语法规则格式与此处使用的格式相同： http://hackingoff.com/compilers/ll-1-parser-generator
A -> B c
B -> b a
B ->
词法规则格式如下：
literal='literal' // example - all are posix+stdx regex in single quotes \' escaped
identifier='[A-Z_a-z][A-Z_a-z0-9]*'
CFG 规则、属性和词法规则可以混合出现在文档中，但最好将属性放在前面，然后是 CFG 语法规则，最后是词法规则。
支持 C 风格的行注释，但由于该格式是基于行的，因此不支持 C 风格的块注释。
这种格式很重要，因为通常所有语法在转换为目标格式之前都会先转换为这种格式，这使得翻译代码编写起来更容易，也更灵活。
这种格式几乎总是由机器生成的，所以你不必在意它是否丑陋。
Pck 提供了一种非常干净的 XBNF 格式，您可以使用它来编写语法。
/****************************************************************\
* xbnf.xbnf: 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 { "|" expression };
expression= { symbol };
symbol= literal | regex | identifier |
"(" expressions ")" | // parentheses
"[" expressions "]" | // optional
"{" expressions ("}"|"}+"); // loop {} or {}+
//
// attributes
//
// recognized attributes are hidden, collapsed, terminal, start,
// and blockEnd (string)
attributes<collapsed>= attribute { "," attribute};
attribute<color="red">= identifier [ "=" attrvalue ];
attrvalue<color="orange">= literal | integer | identifier;
//
// terminals
//
// XBNF "knows" what is a terminal and what isn't simply because
// a terminal is anything that doesn't reference other symbols
// If you want to reference other symbols in a terminal, mark
// it with the "terminal" attribute. You shouldn't need to.
literal= '"([^"\\]|\\.)*"';
regex= '\'([^\'\\]|\\.)*\'';
identifier= '[A-Z_a-z][\-0-9A-Z_a-z]*';
integer= '\-?[0-9]+';
// hide comments and whitespace
whitespace<hidden>= {" "|"\v"|"\f"|"\t"|"\r"|"\n"}+;
// 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 is not supported
or="|";
lt="<";
gt=">";
eq="=";
semi=";";
comma=",";
lparen="(";
rparen=")";
lbracket="[";
rbracket="]";
lbrace="{";
rbrace="}";
rbracePlus="}+";
在使用此语法进行解析之前，您需要将其转换为 Pck 格式（或另一种语法格式）。
所有这一切的核心是 pckw 控制台实用程序。pckp 实用程序是同一应用程序的便携式 .NET Core 版本，功能完全相同。我们在这里将使用 pckw。
这是相当庞大的用法屏幕。如您所见，这是多个实用程序的集合。
Usage: pckw <command> [<arguments>]
Commands:
pckw fagen [<specfile> [<outputfile>]] [/class <classname>]
[/namespace <namespace>] [/language <language>]
<specfile> The pck specification file to use (or stdin)
<outputfile> The file to write (or stdout)
<classname> The name of the class to generate
(or taken from the filename or from the start symbol of the grammar)
<namespace> The namespace to generate the code under (or none)
<language> The .NET language to generate the code for (or draw from filename or C#)
Generates an FA tokenizer/lexer in the specified .NET language.
pckw ll1gen [<specfile> [<outputfile>]] [/class <classname>] [/namespace <namespace>]
[/language <language>]
<specfile> The pck specification file to use (or stdin)
<outputfile> The file to write (or stdout)
<classname> The name of the class to generate
(or taken from the filename or from the start symbol of the grammar)
<namespace> The namespace to generate the code under (or none)
<language> The .NET language to generate the code for (or draw from filename or C#)
Generates an LL(1) parser in the specified .NET language.
pckw ll1factor [<specfile> [<outputfile>]]
<specfile> The pck specification file to use (or stdin)
<outputfile> The file to write (or stdout)
Factors a pck grammar spec so that it can be used with an LL(1) parser.
pckw ll1tree <specfile> [<inputfile>]
<specfile> The pck specification file to use
<inputfile> The file to parse (or stdin)
Prints a tree from the specified input file using the specified pck specification file.
pckw xlt [<inputfile> [<outputfile>]] [/transform <transform>] [/assembly <assembly>]
<inputfile> The input file to use (or stdin)
<outputfile> The file to write (or stdout)
<transform> The name of the transform to use
(or taken from the input and/or output filenames)
<assembly> The assembly to reference
Translates an input format to an output format.
Available transforms include:
pckToLex Translates a pck spec to a lex/flex spec
pckToYacc Translates a pck spec to a yacc spec
xbnfToPck Translates an xbnf grammar to a pck spec.
哇！需要了解的内容很多。让我们开始吧。
首先，我们看到 fagen。此实用程序将生成一个 .NET 代码文件，其中包含指定输入 PCK 规范的标记生成器。我们可以使用它来生成解析器用于消耗输入的代码。它需要一个 PCK 文件，所以给它一个。根据您指定的输出文件扩展名，或您指定的 /language 选项，将生成相应语言的代码文件。类名是从文件名、语法或 /class 参数派生的。请注意，目前由于 Microsoft 的 CodeDOM 提供程序存在错误，生成的 VB 代码将无法在未进行重大修改的情况下工作。这可能会在将来的版本中得到解决，但目前不行。
pckw fagen xbnf.ll1.pck XbnfTokenizer.cs
上面的命令将为 xbnf.ll1.pck 输入文件生成一个标记生成器。
接下来，我们看到 ll1gen。此实用程序生成一个 .NET 代码文件，其中包含指定输入的 LL(1) 类解析器。请注意，LL(1) 解析器在使用前必须对大多数语法进行分解。这是算法的一个特性，也适用于 Coco/R 等其他 LL(1) 解析器。命令行选项与 fagen 相同。
pckw ll1gen xbnf.ll1.pck XbnfParser.cs
上面的命令将为 xbnf.ll1.pck 文件生成一个解析器。
除非您确定自己知道在做什么，否则请确保始终从完全相同的输入规范生成解析器和标记生成器，否则符号将不匹配，解析也将失败。
好的，我们看到可以从 PCK 文件生成解析器和标记生成器。如何获取 PCK 文件？
目前，您的选择是手动创建，或者从 XBNF 转换。我将很快在此处添加其他格式的导入器，首先是 ANTLR。
我们将使用上面发布的 xbnf.xbnf 语法文件。如何将其转换为 PCK？
pckw xlt xbnf.xbnf xbnf.pck
上面的命令将使用 xlt 实用程序的“xbnfToPck”转换来实现此目的，它根据文件扩展名知道要使用哪个转换。您也可以使用 /transform 选项明确指定它。您还可以使用自己创建的转换，并通过 /assembly 选项引用它们，该选项接受文件名或程序集名称。
我们稍后会详细讨论这一点。现在，请记住我说过在使用 LL(1) 解析器之前必须对语法进行分解？方法如下：
pckw ll1factor xbnf.pck xbnf.ll1.pck
ll1factor 实用程序会修改语法，尝试通过更改语法的构成来消除左递归和 LL(1) 语法冲突，同时保留其匹配的语言。通过使用属性来折叠输出树中添加的节点，可以尽可能地使此过程透明。并非所有语法都可以由 LL(1) 解析器解析，事实上，许多语法即使在分解后也无法解析。然而，LL(1) 具有其优点，例如效率高且易于使用。在 LL(1) 可行的情况下，它通常是最佳选择。
现在我们有了一个适合 LL(1) 的 PCK 规范文件，我们可以使用它来生成解析器和标记生成器（如前所示），或者我们可以使用以下命令测试我们的语法：
pckw ll1tree xbnf.pck xbnf.xbnf
这将把解析 xbnf.xbnf 文件的结果以树形结构打印到控制台。我们实际上刚刚使用 xbnf.xbnf 语法解析了它本身！
我们不必将所有这些分开进行。
pckw xlt xbnf.xbnf /transform xbnfToPck | pckw ll1factor > xbnf.ll1.pck
pckw ll1parse xbnf.ll1.pck xbnf.xbnf
然后，如果我们想生成代码：
pckw ll1gen xbnf.ll1.pck XbnfParser.cs /namespace Pck
pckw fagen xbnf.ll1.pck XbnfTokenizer.cs /namespace Pck
最后，如果我们想将其导出为 lex 和 yacc（我们不需要为 YACC 分解语法）：
pckw xlt xbnf.xbnf /transform xbnfToPck | pckw xlt /transform pckToLex > xbnf.l
pckw xlt xbnf.xbnf /transform xbnfToPck | pckw xlt /transform pckToYacc > xbnf.y
让我们进入有趣的部分。制作我们自己的转换并使用 API！
Using the Code
使用代码本身的主要原因，除了生成的解析器和标记生成器之外，是为了实现转换。
要做到这一点，您需要引用程序集 pck，并且几乎肯定需要 pck.cfg 和 pck.fa。
using System.IO;
using Pck;
[Transform("foobar",".foo",".bar","Transforms a foo into a bar.")]
public class MyTransform
{
public static void Transform(TextReader reader,TextWriter writer)
{
// your transform code goes here - here's an identity transform
string line = null;
while(null!=(line=reader.ReadLine())
writer.WriteLine(line);
}
}
在这里，我们声明了一个名为“foobar”的转换，它接受输入文件类型“.foo”并生成类型为“.bar”的文件，我们提供了一个描述，并在一个单独的 static 方法中实现了一个简单的身份转换，签名如下：
static void Transform(TextReader reader, TextWriter writer) {}
我们已用 Transform 属性修饰了其包含的类，并指定了有关转换的基本信息。
现在我们可以将其编译为 foobar.dll 并像这样使用它：
pckw xlt input.foo output.bar /assembly foobar.dll
或
pckw xlt input.foo /transform foobar /assembly foobar.dll > output.bar
仅此而言，它对我们作为转换开发者或用户来说都没有太大用处，所以让我们深入研究如何使其有价值。
通常，您的输入类型或输出类型将是 PCK 规范文件。事实上，我强烈建议您避免直接从一种语法转换为另一种语法，因为这样更困难，灵活性也更低。取而代之的是，将一种语法转换为 PCK 规范，然后再将 PCK 规范文件转换为另一种语法。这样做将允许您利用提供的 API 来帮助进行转换。它还将允许您的用户通过您的语法作为起点或终点，来与其他语法格式相互转换。因此，通过实现 PCK 到 Gold 的转换，您也间接添加了 XBNF 到 Gold 的转换，通过添加 Gold 到 PCK 的转换，您也间接添加了 Gold 到 YACC 的转换（通过 Gold -> PCK -> YACC）。
在这里，我们将描述基本过程，但您可以随时查看提供的三个转换以获得更深入的真实世界示例，其中 XbnfToPck 是最复杂的。
大多数时候，您将同时处理规范的语法部分和词法部分，但 Pck 为每个部分提供了不同的 DOM。我在读取 PCK 文件时，由于每个 DOM 都会解析它并从中获取自己的信息，我会将文档预加载到字符串中，然后将其单独传递给每个 Parse 方法。所以如果您的输入类型是“.pck”，那么前三行很可能看起来像这样：
public static void Transform(TextReader input,TextWriter output)
{
var buf= input.ReadToEnd();
var cfg = CfgDocument.Parse(buf);
var lex = LexDocument.Parse(buf);
...
}
解析完成后，lex 和 cfg 都会为您提供其相关部分的 DOM。使用 cfg 中的符号和规则，以及 lex 变量中的词法规则来构建您的输出。
您可以使用 cfg.Rules 集合枚举语法规则，使用 EnumSymbols() 或 FillSymbols() 函数枚举符号。
您可以使用 lex.Rules 枚举词法规则。更重要的是，您可以获得每个规则的正则表达式作为正则表达式 DOM 树，这意味着您可以更容易地将其重新格式化为目标格式的正则表达式。
从 DOM 输出很容易，因为 ToString() 表示都生成 PCK 格式的数据。
现在我们来谈谈使用生成的标记生成器和解析器。
标记生成器只是一个遵循两个基本契约的类。第一个是，它实现了 IEnumerable<Token>。第二个是，它始终返回一个正确的“#EOS”符号作为最后读取的最后一个标记。
使用 fagen 生成的类符合该契约，但您可以自由创建自己的类。
生成的 LL(1) 解析器的工作方式很像 Microsoft 的 XmlReader。它们有一个 Read() 函数，一个 NodeType 属性，一个 Symbol 属性（类似于 XmlReader 中的 Name）和一个 Value 属性。它们还报告行号、列号和位置，以及任何错误。只要 Read() 返回 true，就在循环中调用它，然后在每次迭代中根据其他属性执行操作。它非常简单。
它们还公开了一个 ParseSubtree() 函数，该函数以解析树的形式返回当前位置的子树。
除了 Pck/FA：正则表达式和有限状态引擎，我还会发布更多关于 Pck 的文章，包括更深入地介绍如何编写转换的文章，因为我会亲自开发它们，所以请务必回头查看，并关注我的 GitHub 以获取最新信息。它只会越来越好。
历史
- 2019 年 8 月 6 日 - 初次提交