鹦鹉虚拟机/鹦鹉语法引擎
鹦鹉语法引擎 (PGE) 是在鹦鹉上实现 Perl 6 正则表达式语法的引擎。Perl 6 正则表达式语法比 Perl 5 中的正则表达式语法强大得多，也更具表现力。由于许多其他语言中的正则表达式实现都基于 Perl 5 实现，因此 Perl 6 比它们也更强大。Perl 6 的正则表达式和语法与 Perl 5 模块“Parse::RecDescent”或解析器生成器程序 Yacc 和 Bison 等解析器生成器非常相似。然而，与 Yacc/Bison 不同的是，Perl 6 语法引擎使用递归下降算法而不是 LALR 算法。对于普通读者来说，这些差异并不重要，但我们将在后面更详细地讨论它们。
Perl 6 语法是词法分析器（将源代码分解为标记）和解析器（将标记组合成模式）的组合。语法的词法分析部分是正则表达式引擎。语法的解析部分是我们将在这里描述的规则系统。
 | 本章的前半部分将介绍一些关于解析器和解析算法的背景知识。如果您已经熟悉解析器，您可以跳到关于规则和操作的部分。 |
在我们进一步讨论 PGE 之前，我们需要讨论一些更多术语，我们还需要快速了解解析器使用的算法。通过理解算法和这些算法的局限性，您作为编译器设计者应该能够更有效地使用这些工具。
编译器的输入是一个源代码文件，用特定的高级语言编写，它包含各种组件。考虑 C 编程语言中的以下语句
int x = add_both(5, 4);
这条语句需要被分解成更小的块，这些块代表各个组件。正如我们已经看到的那样，一个块被称为“标记”。正则表达式引擎，即词法分析器，用于通过将输入迭代地与已知正则表达式匹配来将输入分解为标记。使用这种方法，上面的语句可以分解成以下标记
KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"int" "x" "=" "add_both" "(" "5" "," "4" ")"
请注意，空格已从列表中删除，因此只有“重要”的内容被转换为标记。每个标记包含两条重要的信息：类型（“关键字”、“标识符”等）和值（“int”、“x”等）。解析器可以将标记类型排列成一个模式，而操作可以使用标记值来构造 PAST 解析树。
如果一个标记的有序组与解析器的给定输入模式匹配，则称为字符串。对于编译器来说，所有有效的字符串集合称为语言。指定这种语言的规则称为语法。
编译器的第三部分是后端。后端，也称为目标代码生成器，将输入源的中间数据表示（解析树）转换为目标语言。在我们的例子中，目标语言是 PIR 或 PBC。所有编译器都是由这三个关键组件组成的：词法分析器、解析器和后端。鹦鹉为词法分析器提供了正则表达式，并处理所有目标语言生成。作为编译器设计者，您唯一需要设计的是解析器。但是，关于解析器，我们还需要了解很多信息。
解析输入标记字符串有两种方法。首先，我们可以进行自顶向下解析，从最高级别的标记开始尝试匹配。其次，我们可以进行自底向上解析，从小的标记开始尝试将它们组合成越来越大的标记，直到我们得到最高级别。两种解析方法的最终目标都是将输入标记字符串缩减为单个匹配标记。
yacc 或 Bison 等解析器生成器会生成自底向上的解析器。
作为一个简单的自底向上解析示例，我们将从标记字符串的左侧开始，尝试将小的标记组合成更大的标记。最终，我们想要的是一个代表整个输入的标记。我们通过利用两个基本操作来实现这一点：移进和归约。移进操作意味着我们将一个新的输入标记读入解析器。归约操作意味着我们将匹配的从小标记组成的模式转换为单个更大的标记。让我们将此方法应用到下面的实践中。
KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"int" "x" "=" "add_both" "(" "5" "," "4" ")"
如果我们意识到标记“int”和“x”是一个变量声明，那么上面的字符串将变成下面的字符串。我们将前两个标记归约为一个变量声明标记
DECLARATION OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"=" "add_both" "(" "5" "," "4" ")"
现在，我们从左到右移动，将标记移进解析器。在我们到达括号之前，我们无法看到可以归约的任何内容。我们可以将开括号和闭括号，以及它们中间的所有标记归约为一个参数列表，如下所示
DECLARATION OPERATOR IDENTIFIER ARGUMENT_LIST
"=" "add_both"
现在，我们知道，当我们有一个标识符后面跟着一个参数列表时，它是一个函数调用。我们将这两个标记归约为一个函数调用标记
DECLARATION OPERATOR FUNCTION_CALL
"="
最后，通过跳过一些步骤，我们可以将其转换为赋值语句
ASSIGNMENT_STATEMENT
每次我们将一组小的标记归约为一个更大的标记时，我们都会将它们添加到树中。我们将小的标记添加为更大标记的子节点。我们在这里讨论的这种类型的解析器称为“移进-归约”解析器，因为这些是解析器执行的操作。移进-归约解析器的一个子集，对于算术表达式很有用，称为运算符优先级解析器，我们将在下面进一步讨论。
- 注意
- 移进-归约解析器容易出现一种称为移进-归约冲突的特定类型的错误。移进-归约冲突是由新的输入标记导致解析器移进或归约造成的。换句话说，解析器对于输入标记有多个选项。包含可能出现移进-归约冲突的语法称为二义语法。虽然有一些方法可以纠正这种冲突，但通常最好重新设计语言语法以完全避免它们。有关这方面的更多信息，请参见页面底部的资源部分。
自顶向下解析器与自底向上解析器略有不同。我们从最高级别的标记开始，尝试通过测试更小的模式来进行匹配。这个过程可能效率低下，因为我们经常必须测试许多不同的模式才能找到一个匹配的模式。但是，我们获得了一种避免移进-归约冲突的能力，也获得了一定的鲁棒性，因为我们的解析器在放弃之前会尝试多个选项。假设我们有一个标记字符串和一个用于 STATEMENT 标记的顶层定义。以下是用上下文无关语法表示的定义
STATEMENT := ASSIGNMENT | FUNCTION_CALL | DECLARATION
当然，这是一个简单的示例，不足以满足像 C 这样的语言。“:=” 符号类似于“由…组成”这句话。竖线“|”等同于“或”。因此，上面的语句表示“语句由赋值或函数调用或声明组成”。
我们有这条语法规则，它告诉我们语句是什么，我们也有我们的输入标记字符串
KEYWORD IDENTIFIER OPERATOR IDENTIFIER PAREN INTEGER OPERATOR INTEGER PAREN
"int" "x" "=" "add_both" "(" "5" "," "4" ")"
自顶向下解析器将尝试 STATEMENT 定义中的每个备选方案，以查看它是否匹配。如果一个不匹配，它将移动到下一个备选方案，然后再次尝试。因此，我们先尝试 ASSIGNMENT 规则，而 ASSIGNMENT 定义如下
ASSIGNMENT := (VARIABLE_NAME | DECLARATION) '=' (EXPRESSION | FUNCTION_CALL)
圆括号用于将事物组合在一起。用英语来说，这条语句表示“赋值是一个变量名或一个声明，后面跟着一个‘=’，后面跟着一个表达式或一个函数调用”。因此，为了满足 ASSIGNMENT，我们先尝试 VARIABLE_NAME，然后尝试 DECLARATION。字符串“int x”是一个声明而不是一个简单的变量名，因此 VARIABLE_NAME 失败，而 DECLARATION 成功。接下来，‘=’ 匹配。为了满足最后一段，我们先尝试 EXPRESSION，它失败了，然后我们尝试 FUNCTION_CALL，它成功了。我们以此类推，尝试备选方案，逐渐从更大和更小的标记移动到更小的标记，直到我们匹配了整个输入字符串。一旦我们匹配了最后一个输入标记，如果我们也满足了顶层匹配，那么解析器就会成功。
这种类型的解析器称为“递归下降”解析器，因为我们递归到每个子规则中，然后从解析树的顶部逐渐下降到底部。一旦最后一个子规则成功，整个匹配就成功，解析器返回。
在这个过程中，当一个规则匹配时，我们在 PAST 树中创建一个节点。因为我们在一个规则成功之前先测试所有子规则，所以所有子节点在更高层节点创建之前就已经创建好了。这使得解析树从底部向上创建，即使我们是从树的顶部开始向下移动的。
自顶向下解析器可能效率低下，因为解析器会尝试匹配显然无法成功的模式。但是，我们有一些技巧可以用来“修剪”可能性树，通过将解析器引导到特定路径或阻止它沿着不会匹配的分支进行移动。我们还可以阻止解析器从子规则回溯到更大的规则，这有助于减少不必要的重复。
像 PGE 中使用的递归下降解析器一样，是一种自顶向下的解析器。这意味着它试图从最高级别的定义开始，并逐步向下匹配给定的输入。顶级规则始终称为 TOP。之后，我们可以根据需要创建更多其他规则来指定我们的整个语法。让我们从创建一个非常简单的递归下降解析器开始，尝试解析我们之前给出的输入
int x = add_both(5, 4);
以下是我们基本解析器的一部分
rule TOP {
<assignment> | <function_call> | <declaration>
}
rule assignment {
<lvalue> '=' <rvalue>
}
rule lvalue {
<variable_name> | <variable_declaration>
}
rule rvalue {
<expression> | <function_call>
}
rule function_call {
<identifier> '(' <arguments> ')'
}
rule variable_declaration {
'int' <identifier>
}
这只是解析器的一部分，但思路应该很清楚。我们用常量或其他规则来定义每个规则。尖括号“<”和“>”表示我们需要匹配子规则。单引号用于表示字面字符串常量。
规则有一些我们可以使用的基本操作符，其中一些已经讨论过。熟悉正则表达式的人会认识大多数操作符。
| 操作符 | 含义 | 示例 | 解释 |
|---|---|---|---|
* |
"零个或多个" | <number>* '.' <number> |
接受一个字符串，其中包含零个或多个数字，后面跟着一个点，最后跟着一个数字。例如：1234.5 |
+ |
"一个或多个" | <letter>+ <number> |
一个或多个字母，后面跟着一个数字。例如：abcde5，或 ghij6 |
? |
"一个或零" | <number>? '.' <number>+ |
一个可选的数字，后面跟着一个点和一个一个或多个数字的字符串。例如：1.234 或 .234 |
[] |
分组 | <letter> [<letter> | <number>]* |
一个字母，后面跟着任意数量的字母或数字。例如：a123、ident、wiki2txt |
我们已经讨论过或操作符“|”。以下是一些示例。
- 十进制数
rule decimal_numbers {
<digit>* '.' <digit>+
|<digit>+ '.' <digit>*
}
- 函数参数
rule function_parameters {
'(' [ <identifier> [ ',' <identifier> ]* ]? ')'
}
当 PGE 成功匹配规则时，它会创建一个特殊的“匹配对象”，其中包含有关匹配的信息。此匹配对象可以发送到用 PIR 或 NQP 编写的函数进行处理。接收匹配对象的处理函数称为 **操作**。语法中的每个规则都具有一个名称相同的关联操作函数。
当我们完成成功匹配后，我们需要将匹配对象发送到操作方法。我们使用特殊符号 `{*}` 来执行此操作。`{*}` 发送当前匹配对象，不一定是完整的对象。如果需要，您可以在规则中多次调用 `{*}` 以多次调用操作方法。以下是一个示例
rule k_r {
{*} #Calls the action method with an empty match object
'hello'
{*} #calls the action method after matching 'hello'
'world'
{*} #Calls the action method after matching 'hello' 'world'
}
关于操作方法有两点需要记住
- 解析器从左到右，从上到下移动。在上面的 k_r 示例中，如果输入是“hello johnny”，则操作方法将被调用前两次，但该规则将无法匹配单词“world”，并且操作方法将不会被调用第三次。
- 即使还有更多尝试的可能性，解析器也会在成功匹配后返回。考虑以下示例，其中只有一个操作方法可以根据备选方案的结果被调用。在这个例子中，如果输入是“hello franky”，则操作方法只会被调用 `{*}` 后的 'franky'。在匹配后，解析器返回，不再尝试匹配 'johnny'。
rule say_hello {
'hello'
[
| 'tommy' {*}
| 'franky' {*}
| 'johnny' {*}
]
}
有时指定哪个操作方法被调用非常有用，当有一系列可能性时。这是因为我们希望以不同的方式对待某些匹配。为了以不同的方式对待操作方法，我们使用一个特殊的注释语法
rule say_hello {
'hello'
[
| 'tommy' {*} #= tommy
| 'franky' {*} #= franky
| 'johnny' {*} #= johnny
]
}
特殊的 “#=” 符号不是常规注释。相反，它是操作方法的第二个参数，称为“键”。如果您使用 “#=” ，则操作方法将接收两个参数：匹配对象和键。然后，您可以测试键的值来确定如何处理匹配对象。我们将在下一章关于 NQP 的内容中详细讨论。