Pck/Cfg：PCK 中的上下文无关文法
5.00/5 (3投票s)
使用PCK的文法系统，并理解其背后的概念
引言
这是关于解析器构造工具包 (PCK) 系列文章之一。我称之为“Puck”。
免责声明：一如既往，请使用GitHub 来获取代码片段，因为我每天都在此基础上进行构建。我总是在每篇文章中提供当时最新的PCK构建版本，但我在文章之间会进行大量改进。所以，请再次使用GitHub。我只在此处发布代码片段，以监测兴趣和遵循传统。我不会回到Code Project更新这些代码片段中的修复和改进。
本文涵盖了pck.cfg 程序集，但它也涵盖了其背后的概念，这些概念更为重要。
背景
最好已经使用过解析器生成器，尤其是PCK。您对解析的任何背景知识都有帮助，但我会尽量保持简单。
首先，让我们回顾一下我一篇早期文章中的内容，因为它在这里至关重要
无论底层解析算法如何，任何解析器要想工作，都必须具备某种文法。几乎我们为解析生成的所有内容都将从该文法生成。文法描述了我们想要解析的“语言”。到目前为止，我们只打算解析上下文无关语言，所以我们需要一个上下文无关文法，或CFG。
PCK 处理CFG中的基本操作，但要理解它们，我们需要探索这一切是如何在概念上工作的。
让我们从解析过程的概述开始。我们将探讨这个小的C语言片段。
int main() {
printf("Hello World");
return 0;
}
CFG文法是这里的重点，但文法本身通常不理解输入流中的单个字符。它们处理的是标记，标记是小的文本片段——本质上是词素，并附带一个关联的符号/标签。
上面可以分解为这些标记
keyword: int
(whitespace)
identifier: main
lparen: (
rparen: )
(whitespace)
lbrace: {
(whitespace)
identifier: printf
lparen: (
string: "Hello World"
rparen: )
semi: ;
(whitespace)
keyword: return
(whitespace)
int: 0
semi: ;
(whitespace)
rbrace: }
注意，冒号左侧是“附加”到冒号右侧的文本片段的符号。请注意，空格基本上被忽略了。
总之，文法不在乎值是什么。它只关心左侧部分——符号。这就是文法看到的内容
keyword,identifier,lparen,rparen,lbrace,identifier,
lparen,string,rparen,semi,keyword,int,semi,rbrace
这些称为终结符，或终结符。它们是我们解析树的叶子。我们从输入文本创建这些，但这是一个单独的过程，由Pck/FA 覆盖。CFG 不关心那部分。非终结符是树中的节点，它们是CFG的中心。我们使用它们来对从输入中获得的这些终结符列表施加层次结构。
最简单地说，CFG 是一个规则集。规则本身由称为符号的元素组成，这些符号可以是“终结符”或“非终结符”。我们将使用小写字母表示终结符，大写字母表示非终结符，但实际上这并不重要。这只是为了清晰。
规则的形式是
A -> B c
这里，A 是左侧，B c 是右侧出现的两个符号（分别为非终结符和终结符）。出现在任何规则左侧的符号自动是非终结符。因为我们所有的都是大写字母，所以任何规则的左侧只会出现大写字母。
我们可以有多个具有相同左侧的规则。
A -> b
A -> c
这有时被写成简写形式
A -> b | c
虽然左侧称为非终结符，但右侧称为规则的推导。
当我们拥有多个具有相同左侧非终结符的推导时，这意味着规则可以通过多种方式解析。这有点像一个选择。上面可以读作“A 被推导为终结符 b 或 c。”
当有多个符号出现在右侧/推导中，如第一个示例所示，这代表符号序列，例如“A 被推导为非终结符 B 后跟终结符 c”。
规则可以是空的，或 nil，这意味着它没有右侧，例如
A ->
这通常有助于将其与其他 A 规则结合起来，以使它们成为可选的，例如
A -> c
A ->
这表明 A 可以被推导为终结符 c 或什么都没有。
规则可以是递归的，使得左侧在右侧的推导中被引用。这会在文法中创建一种“循环”，这对于描述重复的构造很有用，例如函数调用中的参数列表。
A -> c A
唯一的问题是，一类解析算法——即LL，包括LL(1)——是有限制的，规则不能是左递归的，否则会产生无限循环，所以下面的不允许
A -> A c
对此有解决方法，您必须执行这些解决方法才能使文法对某些解析器（如LL解析器）有效。将文法进行修改以适应解析器称为因子化。甚至有一些程序化方法，这超出了本文的范围。但是，即使经过因子化和消除左递归，并非所有文法都可以用所有算法解析。
一系列规则共同构成文法，并定义了我们语言的总体大纲/层次结构。
非终结符的结构和形式由规则定义。终结符尚未定义——仅在规则中引用。终结符的定义由 Pck/FA 覆盖，但概念概述在我以前的一篇文章中进行了介绍。
文法只需要按句柄引用符号。它不需要关于它们的其他直接信息，除了规则提供的。在我们的代码中，我们将简单地使用字符串来表示符号，但它们可以是整数、GUID 或您想要的任何内容，只要值充当唯一的句柄。
这就导致了一个非常简单的CFG总体数据结构。
一个规则有一个字符串字段用于左侧，以及一个零个或多个字符串的列表用于右侧/推导。
而一个文法只是这些规则的列表。
巧妙之处在于我们如何处理它们。大致来说，大多数解析算法需要执行五个主要步骤。
第一件事是知道如何确定哪些符号是非终结符，哪些是终结符，即使它们都只是字符串。这很容易。出现在任何规则左侧的都是非终结符。规则引用的所有其他符号都是终结符。请记住，虽然非终结符由这些规则定义，但终结符在别处定义。现在，它们是“抽象的”。
第二件需要做的事情是概念上“扩充”文法，添加两个保留的终结符，“#EOS”（在其他教程中常表示为“$”）是输入流结束标记，以及“#ERROR”，它表示流中未识别的输入部分。这些没有用户提供的定义。它们在读取输入时根据需要生成并由解析器消耗。
第三件需要做的事情是能够计算 PREDICT/FIRSTS 集。FIRSTS 是可以出现在每个非终结符开头的终结符。如果您查看任何文法，可以看到右侧的第一个符号（或空/nil）——符号。这就是我们需要的。但是，如果它是非终结符，我们需要获取它的 FIRSTS，依此类推。最终，每个非终结符都应该有一个详尽的列表，列出出现在右侧第一个的终结符，以及 nil（如果存在如前所示的空/nil 规则）。
PREDICT 集与 FIRSTS 集相同，除了它们还包含每个终结符的规则，因此您知道它的来源。实际上，由于 PREDICT 集包含 FIRSTS 集包含的所有信息，因此最好避免直接计算 FIRSTS 集，而只计算 PREDICT 集。
第四件需要做的事情是计算 FOLLOWS 集。FOLLOWS 集是可以直接出现在给定非终结符之后的终结符。这比计算 FIRSTS 和 PREDICT 集要棘手。您必须扫描文法，查找引用您的非终结符的其他规则，以找出什么可以跟在它们后面。我们将在下面的示例中对此进行探讨。
最后，第五件需要做的事情是创建解析表。我所遇到的所有基于CFG的解析算法都使用这些信息来做到这一点。它们可能以截然不同的方式使用信息，但它们都需要这些操作。
在本课中，我们将声明CFG的类并执行这五个步骤中的四个。
演练
根据我们上面概述的内容，让我们通过一个具体的例子在概念上进行探讨。我们将使用与Andrew Begel 出色的工作相同的示例，因此也可以参考。
考虑以下文法
E -> E + T | T
T -> T * F | F
F -> ( E ) | int
或其长格式等效形式
E -> E + T
E -> T
T -> T * F
T -> F
F -> ( E )
F -> int
这代表了一个简单的算术语言的文法，该语言支持 *、+ 和 () 运算符。
非终结符是 E、T 和 F。
终结符是 +、*、(、) 和 int。
文法也是左递归的，正如前面提到的，这是不可行的。我们将手动重构它并消除左递归。
看看前两条规则（简写形式）
E -> E + T | T
在这里，对于左侧非终结符（E）与右侧箭头第一个部分（E + T）相同的每个规则，我们取箭头右侧不包含 E 的部分（+T），并将其放入我们称之为 E' 的新规则中。
E' -> + T
现在，在每个新规则之后，添加 E'。
E' -> + T E'
现在添加一个额外的规则，它是空/nil。
E' -> + T E'
E' ->
现在我们必须修复原始的 E 规则。为此，我们取所有不以 E 开头的右侧，并在它们后面添加 E'。
E -> T E'
如果我们对 T 也这样做，我们将得到以下文法
E -> T E'
E' -> + T E' |
T -> F T'
T' -> * F T' |
F -> ( E ) | int
或长格式
E -> T E'
E' -> + T E'
E' ->
T -> F T'
T' -> * F T'
T' ->
F -> ( E )
F -> int
请注意，我们没有对 F 做任何事情，因为它不是左递归的。
以上是我们将会使用和引用的修改后的文法，请牢记这一点。
现在我们可以继续计算 FIRSTS 集（或更一般地说，PREDICT 集，但我们将特别关注 FIRSTS）。
和以前一样，FIRSTS 是任何非终结符可能出现的第一个终结符，而 PREDICT 是相同的，但带有每个 FIRSTS 的来源规则。
让我们从一个简单的开始，FIRSTS(F) 和 PREDICT(F) - F 的 firsts 和 predict 表。
我们看到 F-> ( E )，所以我们可以说 ( 是 F 的 FIRSTS 之一，并且一个 PREDICT 条目是 ( F-> ( E ),( )
我们还看到 F-> int，所以我们可以说 int 是 F 的 FIRSTS 之一，并且一个 PREDICT 条目是 ( F-> int,int )
我们完成了 F，它有两个条目。从现在开始，我们将只列出 FIRSTS 集以提高可读性。PREDICT 集可以从上述的来源规则推断出来。
FIRSTS(E) = { (, int }
FIRSTS(E') = { +, nil }
FIRSTS(T) = { (, int }
FIRSTS(T') = { *, nil }
最后，我们已经完成的
FIRSTS(F) = { (, int }
好了。现在开始 FOLLOWS 集。
FOLLOWS() 告诉我们可能出现在非终结符之后的终结符。这不是非终结符的最终终结符。而是可能跟在其后面的终结符。计算它很棘手，因为您必须查看非终结符出现的所有规则——也就是说，检查包含非终结符的所有推导，以找出什么可以跟在它后面，即使那样，也不完全那么简单。有一个关于 nil 规则的非显而易见的情况。
因此，我们现在找到非终结符出现在任何箭头右侧的每个位置，如上所述，寻找任何跟在其后面的东西。当我们找到一个非终结符跟在其后面时，我们取 FIRSTS 并使用它们。当我们找到一个终结符跟在其后面时，我们使用它。我们还必须特别处理 nil/空规则，以及出现在推导最右侧的非终结符。
在我们开始之前，我们必须虚拟地用一个特殊的起始规则来扩充文法，该规则在我们的起始符号后包含 #EOS（输入流结束）终结符。在这里，这个规则是
S -> E #EOS
这很重要，这样我们才能知道何时到达解析的末尾。
现在我们已经为计算 FOLLOWS 的目的扩充了文法，我们可以继续了。
让我们来计算 FOLLOWS(E)
显然，#EOS 是基于上面扩充的规则之一。查看文法中的所有规则，看看 E 是否出现在其他地方。它确实出现了。它出现在一个 F 规则下。跟在其后面的是终结符 )，所以我们添加它。我们完成了 E。
现在让我们来计算 FOLLOWS(E')
这个比较棘手。文法中没有直接跟在其后面的东西。它出现在几个规则的末尾，请记住我们需要处理它。为此，我们需要检查引用它的规则。
E -> T E'
我们可以看到它来自 E，所以如果你仔细想想，跟在 E 后面的也跟在 E' 后面。
E' -> + T E'
对于这个，情况相同，但正如 Andrew Begel 指出的那样，这是一个同义反复：跟在 E' 后面的就是跟在 E' 后面的，所以我们忽略它。
继续 FOLLOWS(T)
足够简单。T 后面跟着 E'。因此，开始 E' 的任何终结符都必须是跟在 T 后面的终结符。
换句话说，FOLLOWS(T) = FIRSTS(E')
但是等等，里面有一个 nil。还记得我说 nil 规则需要特殊处理吗？现在到了。
我们不能让来自 FIRSTS 集的那个 nil 存在。因为它来自 FIRSTS(E')，那么，由于我们的可选规则，FOLLOWS(E') 的任何内容也跟在其后面。相信我，如果你进行计算，它是这样工作的。请记住，它来自哪个 FIRSTS，它就会有哪个 FOLLOWS。
应用这些原则，让我们全部完成
FOLLOWS(E) = { #EOS, ) }
FOLLOWS(E') = { #EOS, ) }
FOLLOWS(T) = { +, #EOS, ) }
FOLLOWS(T') = { +, #EOS, ) }
FOLLOWS(F) = { *, +, #EOS, ) }
我们完成了。
如前所述，对于大多数解析算法，我们需要这些 FIRSTS/PREDICT 和 FOLLOWS 结果来生成解析表。
Pck/Cfg 为我们处理了所有这些。
PCK 的 CFG 规则以概述的格式指定。不同的解析器系统可能以不同的格式指定其规则，但它们都代表相同的东西。PCK 使用的格式相当普遍。
PCK 具有“PCK 规范”文件格式，其中可以包含词法分析器规则、CFG 规则，或两者的组合，以及标记其中声明的符号的属性，并带有额外信息。
这是一个简单的基于行的格式，使用上面上下文中概述的结构。词法分析器规则和属性超出了本文的范围。
这是我们上面创建的简单表达式语法格式的完整 PCK 规范文件。
E:start
E -> E add T
E -> T
T -> T mul F
T -> F
F -> lparen E rparen
F -> int
add='\+'
mul='\*'
lparen='\('
rparen='\)'
int='[0-9]+'
斜体部分是属性。它应用于非终结符 E，名为“start”。由于没有指定“=<value>”，它隐式为 start=true。
这一切只是告诉文法哪个符号是起始符号。如果未指定，则使用文法中的第一个非终结符。斜体和粗体部分是本文档中与 CFG 相关的内容。其他所有内容都将被忽略。Pck/FA 使用其他部分来生成标记器。
通常，这些文件是机器生成的。但是，它们是 PCK 功能的核心，因此应该加以介绍。
Using the Code
首先，除非您正在实现自己的上下文无关解析算法，否则您不需要直接使用大部分代码。我们将首先介绍您在进行运行时创建解析器等操作时会使用的常见内容。
通常，我们希望首先获得一个 PCK 规范。我们可以从文件读取它，或者使用以下方法从字符串解析一个：
var cfg = CfgDocument.ReadFrom(filename);
或
var cfg = CfgDocument.Parse(text);
respectively.
或者，我们可以通过编程方式创建（或修改）它们。
var cfg = new CfgDocument();
// add the first rule entry from our example above
cfg.Rules.Add(new CfgRule("E","T","E'"));
无论我们如何获取它，问题是我们如何处理它？
通过将相应的算法“联机”，我们可以用它创建解析器，这非常普遍。例如，引用 pck.ll1 程序集允许：
var parser = cfg.ToLL1Parser(tokenizer); // we got our tokenizer from elsewhere
我们可以将其写入字符串。
Console.WriteLine(cfg); // calls cfg.ToString() implicitly
我们可以克隆它或将其与另一个 CFG 进行相等比较。
var cfg2 = cfg.Clone();
Console.WriteLine(cfg==cfg2); // prints True
我们可以添加、修改或删除规则。
cfg.Rules[0].Right[0]="F"; // modifies E -> T E' to be E -> F E'
我们可以枚举或填充包含非终结符和终结符的集合。
foreach(var nt in cfg.EnumNonTerminals()) Console.WriteLine(nt);
foreach(var t in cfg.EnumTerminals()) Console.WriteLine(t);
foreach(var s in cfg.EnumSymbols()) Console.WriteLine(s);
var ntl = cfg.FillNonTerminals();
var tl = cfg.FillTerminals();
var sl = cfg.FillSymbols();
我们可以计算 firsts、follows 和 predict 集。
var firsts = cfg.FillFirsts();
var follows=cfg.FillFollows();
var predict=cfg.FillPredict();
这些用于各种解析器算法来计算它们的解析表，尽管每个算法使用它们的方式不同，或者可能不直接使用所有这些。
还有很多内容，坦率地说，您可能永远不会用到其中大部分，所以我们将跳过。但请记住这些信息，因为它将使使用 PCK 更加清晰，并为未来的文章提供背景。
历史
- 2019 年 8 月 17 日 - 初始提交