如何创建 LL(1) 解析器：第 1 课
5.00/5 (19投票s)
分 3 课轻松创建简单的解析器
引言
解析器通常是其他软件的组成部分，而不是其本身完整的软件。它们用于将结构化文本分解为有意义的信息树，以便其他软件进行处理。解析器可能最常用于编译器。它们可以获取 C# 程序或 C++ 程序之类的文本数据，并根据语言的语法将其转换为数据树。
解析器还用于处理基于 Internet 的文本数据，如 JSON、XML 和 HTML。您的网页浏览器使用解析器，以便可以将 HTML 文档转换为相应的布局和显示元素，并将 JavaScript 转换为可运行的代码。您的电子商务网站使用解析器将 XML AJAX 数据转换为数据库信息。解析器对您在 Internet 上进行的几乎所有操作都至关重要，但它们存在于其他软件的后面。
在本文中，我们将探讨用于创建简单生成解析器的 LL(1) 解析算法。
在仔细搜索互联网以寻找“龙书”的替代方案（一本令人生畏的书）之后，我发现网上确实没有关于构建解析器的完整教程。所有信息都在那里，但分散、混乱，有时甚至相互矛盾。我希望未来想要开发解析器生成器的编码人员可以使用这篇教程来入门，理解关键概念以及如何将它们结合起来。
目标不是生成解析器生成器，而是展示该算法的工作原理。为此，我们将制作一个运行时解析器。我们不会制作一个快速的解析器，也不会制作一个功能齐全的解析器，但我们将为实现这些目标奠定基础，并使用易于理解的代码。
背景
LL(1) 解析可以说是最简单的无上下文解析形式。它自顶向下解析文档，并从生成的输入创建左推导树。它的工作方式几乎与递归下降解析相同。
它相对于递归下降解析的主要优点是，机器生成 LL(1) 表比生成递归函数稍微容易一些。在实践中，使用表通常比使用大量递归方法更快。递归下降解析非常适合手工编写的解析器。每种方法的性能由于优缺点不同而有所不同（它们在某些方面比其他方面更有效），但在实践中它们非常接近，因此相对性能差异只是学术上的。
无论底层算法如何，任何解析器要工作，都必须具有某种形式的语法。我们用于解析的几乎所有内容都将从该语法生成。语法描述了我们要解析的“语言”。到目前为止，我们只打算解析无上下文语言，所以我们需要一个无上下文语法，即 CFG。
(根据评论中与 David O'Neil 的讨论扩展了引言。)
让我们从概述解析过程开始。我们将探讨这个 C 语言片段。
int main() {
printf("Hello World");
return 0;
}
上面提到了 CFG（无上下文语法），但语法本身通常不理解输入流中的单个字符。它们与令牌（token）一起工作，令牌是小的文本片段——本质上是词素（lexeme），并附带一个符号/标签。
上述内容可以分解为以下令牌：
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
这些被称为终结符（terminal symbols）或终结符。它们是我们解析树的叶子。我们将在第二课中从输入文本创建它们。非终结符（non-terminals）是树中的节点。我们使用它们来为从输入中获得的这些终结符列表施加层次结构。
目前，我们将专注于 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(1) 解析器有效。将语法进行调整以与 LL(1) 解析器配合使用称为因子分解 。甚至还有一些可以以编程方式进行的方法，超出了本教程的范围。然而，即使经过左因子分解和消除左递归，并非所有语法都可以使用 LL(1) 解析。它最适合简单的语言。
一系列规则共同构成语法，并定义我们语言的整体大纲/层次结构。
非终结符的结构和形式由规则定义。终结符尚未定义——只在规则中引用。终结符的定义将在下一课中介绍，因为定义终结符的方法不同。
语法只需要通过其句柄引用符号。除了规则提供的其他信息外，它不需要关于它们的任何其他直接信息。在我们的代码中，我们将简单地使用字符串来表示符号，但它们可以是整数、GUID 或你想要的任何东西，只要值充当唯一的句柄。
这导致了对整个 CFG 的一个非常简单的数据结构。
规则有一个用于左侧的字符串字段，以及一个用于右侧/推导的零个或多个字符串的列表。
与此同时，语法只是这些规则的列表。
诀窍在于我们如何处理它们。粗略地说，我们需要执行五个主要步骤。
我们需要做的第一件事是知道如何确定哪些符号是非终结符，哪些是终结符，即使它们都只是字符串。这很容易。出现在任何规则左侧的任何内容都是非终结符。所有其他被规则引用的符号都是终结符。请记住，虽然非终结符由这些规则定义，但终结符在别处定义。现在，它们是“抽象”的。
我们需要做的第二件事是概念上“扩充”语法，添加两个保留的终结符，“#EOS”（在其他教程中通常表示为“$”），它是输入流的结束标记，以及“#ERROR”，它表示流中未识别的输入位。这些没有用户提供的定义。它们是在必要时读取输入时生成的，并由解析器消耗。
我们需要做的第三件事是能够计算 FIRST/PREDICT 集合。FIRST 是可以出现在每个非终结符开头的终结符。如果你看任何语法，你都可以看到第一个右侧符号（或空/nil）——符号。这就是我们需要的。但是，如果它是非终结符，我们就需要获取它的 FIRSTS，依此类推。最终，每个非终结符都应该有一个出现作为第一个右侧的终结符的详尽列表，如果存在空/nil 规则，则为 nil，如前所示。
PREDICT 集合与 FIRSTS 集合相同，只是它们还包含与每个终结符关联的规则，这样你就知道它们来自哪里。在实践中，由于 PREDICT 集合包含 FIRSTS 集合包含的所有信息，因此最好避免直接计算 FIRSTS 集合，而只计算 PREDICT 集合。
我们需要做的第四件事是计算 FOLLOWS 集合。FOLLOWS 集合是可以直接出现在给定非终结符之后的终结符。这比计算 FIRSTS 和 PREDICT 集合更棘手。你必须扫描语法，寻找引用你的非终结符的其他规则，以找出什么可以跟随它们。我们将在下面的示例中介绍这一点。
最后，我们需要做的第五件事是创建解析表。幸运的是，一旦我们有了 PREDICT 和 FOLLOWS 集合，这一步就很简单了。
在本课中，我们将为 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')，那么 whatever FOLLOWS(E') 也跟随它，这是因为我们的可选规则。相信我，如果你计算一下，它就是这样工作的。记住，无论它来自哪个 FIRSTS，它都将拥有它。
应用这些原则，让我们全部处理完：
FOLLOWS(E) = { #EOS, ) }
FOLLOWS(E') = { #EOS, ) }
FOLLOWS(T) = { +, #EOS, ) }
FOLLOWS(T') = { +, #EOS, ) }
FOLLOWS(F) = { *, +, #EOS, ) }
我们完成了这一步。
现在终于到了简单的事情了。让我们构建我们的解析表。
我们为每个终结符有一列，为每个非终结符有一行。在每个单元格中，我们都有一个规则，或者为空。
| + | * | ( | ) | int | #EOS | |
| E | ||||||
| E' | ||||||
| T | ||||||
| T' | ||||||
| F |
我们的解析表将大致如下所示：
现在，我们需要填写规则。这就是我们之前生成的 PREDICT 集合的作用。
对于每一行，我们得到该行的 PREDICT，它是一组终结符和与该行非终结符关联的规则。让我们处理 E。
记住 FIRSTS(E) = { (, int }
而相应的预测都是规则 E-> T E'
现在我们的表看起来像：
| + | * | ( | ) | int | #EOS | |
| E | E-> T E' | E-> T E' | ||||
| E' | ||||||
| T | ||||||
| T' | ||||||
| F |
现在让我们来处理 E'。
FIRSTS(E') = { +, nil }
哎呀，表中没有 nil。我们该怎么办？
这就是我们的 FOLLOWS 集合派上用场的地方。每当我们看到一个 nil 时，我们就取该非终结符行的 FOLLOWS，并使用它的终结符来告诉我们使用哪个列。我们使用的规则来自带有 nil 的 PREDICT，所以它将是一个空/nil 规则。下面，我们采用 follows，这样我们就可以看到在哪里放置我们的规则。
FOLLOWS(E') = { #EOS, ) }
填写表的下一行后，我们得到：
| + | * | ( | ) | int | #EOS | |
| E | E-> T E' | E-> T E' | ||||
| E' | E' -> + T E' | E' -> | E' -> | |||
| T | ||||||
| T' | ||||||
| F |
现在让我们填写其余的行：
| + | * | ( | ) | int | #EOS | |
| E | E-> T E' | E-> T E' | ||||
| E' | E' -> + T E' | E' -> | E' -> | |||
| T | T-> F T' | T-> F T' | ||||
| T' | T'-> | T'-> * F T' | T'-> | T'-> | ||
| F | F-> ( E ) | F-> int |
呼。我们完成了！
编写这个混乱的程序
现在我们已经概念性地探讨了过程，让我们来编写代码。包含的项目包含所有 3 课，但我们将专注于 Lesson 1 文件夹中的内容。请随身携带源代码，因为我们有时只简要地引用它。我们将再次回顾这 5 个步骤，这次会将它们与代码的各个部分联系起来。
CfgRule 是一个定义单个语法规则的类，例如 A -> B c。
在实践中，最好使你的规则类实现值语义以进行相等性比较，以便规则可以用作字典中的键并找到重复的规则等。其中包含的类实现了值语义。
Cfg 是一个定义规则集合的类。Rules 集合是主要的驱动程序。
让我们声明上面提到的语法。您可以看到下面我们必须手动输入。
var cfg = new Cfg();
// E -> T E'
cfg.Rules.Add(new CfgRule("E", "T", "E'"));
// E' -> + T E'
cfg.Rules.Add(new CfgRule("E'", "+", "T", "E'"));
// E' ->
cfg.Rules.Add(new CfgRule("E'"));
// T -> F T'
cfg.Rules.Add(new CfgRule("T", "F", "T'"));
// T' -> * F T'
cfg.Rules.Add(new CfgRule("T'", "*", "F", "T'"));
// T' ->
cfg.Rules.Add(new CfgRule("T'"));
// F -> ( E )
cfg.Rules.Add(new CfgRule("F", "(", "E", ")"));
// F -> int
cfg.Rules.Add(new CfgRule("F", "int"));
接下来，让我们探讨一下我们的步骤是如何映射的，但在那之前，我想对代码中大量使用的集合做一个小说明。
我通常使用 FillXXXX 模式来返回集合，而许多人可能会使用 GetXXXX 方法或属性。
这样做稍微灵活一些，因为你可以操作现有的集合。所有 FillXXXX 方法都接受一个可选的 result 参数。如果未传递，或者如果它是 null，则将创建一个新集合来填充。在这两种情况下，结果都是方法的返回值。因此，要像调用 GetXXXX 方法一样调用它，只需省略结果参数，例如 foo = FillXXXX();
简而言之，让我们回顾一下我们的五个步骤：
- 区分终结符和非终结符符号
- 使用
#EOS和#ERROR终结符扩充语法 - 计算 FIRSTS/PREDICT 集合
- 计算 FOLLOWS 集合
- 生成解析表
让我们探索代表我们无上下文语法的 Cfg 类。
步骤 1 由 FillNonTerminals()、FillTerminals() 和 FillSymbols() 处理，每个都有一个相应的私有 _EnumXXXX() 方法，允许惰性枚举。
步骤 2 由 FillTerminals() 和 _EnumTerminals() 自动处理。
FillSymbols()返回语法中的所有符号，包括非终结符和终结符，非终结符在前，终结符在后。FillNonTerminals()返回语法中的所有非终结符。FillTerminals()返回语法中的所有终结符，保留的#EOS和#ERROR终结符是集合中的最后一个终结符。
只要 Rules 集合不变，这些符号将始终按相同顺序返回——非终结符在前，然后是终结符，然后是保留的终结符，但否则按它们在语法中出现的顺序。
步骤 3 由 FillPredicts() 处理，它填充一个以非终结符为键的字典，其中包含元组的集合，每个元组是一个规则和一个终结符符号或 nil。
步骤 4 由 FillFollows() 处理，它填充一个以非终结符为键的字典，其中包含终结符集合。
步骤 5 由 ToParseTable() 处理，因为我们无法填写现有的解析表，所以它打破了模式。它返回一个嵌套字典，外层以非终结符符号为键，内层以终结符符号为键，内层的值是规则。这代表了我们上面的解析表。
到目前为止，这就是全部内容。随意运行和查看代码，但在本课中，没有多少输出可以演示——这只是为了让解析器的其余部分正常工作的准备。
当它在第三课中开始成形，并且我们回顾 CFG 时，其余的将到位，但首先我们将在第二课中探索词法分析/标记化，在那里我们将构建一个微型、辅助的正规表达式引擎。
历史
- 2019年7月14日：首次提交