鹦鹉虚拟机/操作符和表达式
自上而下的解析有一些问题。首先，它很慢，因为它可能需要尝试许多替代方案才能找到匹配项。每次在匹配上失败时，它都需要返回到前面的规则并再次尝试。另一个问题是，对于具有许多小令牌、操作符优先级和许多子规则的语句，解析树可能会变得非常大。考虑一个简单的数学表达式“1 * 2 + 5”和以下语法
EXPRESSION := TERM ADD_OP TERM TERM := (NUMBER MUL_OP NUMBER) | NUMBER ADD_OP := '+' | '-' MUL_OP := '*' | '/'
我们上面的等式创建了一个非常复杂的解析树
EXPRESSION
TERM
NUMBER 2
MUL_OP "*"
NUMBER 5
ADD_OP "+"
TERM
NUMBER 5
对于像数学表达式这样的东西，我们希望使用自下而上的解析器而不是自上而下的解析器。一种特殊的自下而上的解析器类型，称为 **操作符优先级表解析器**，在这些任务中特别有效且适合。为了创建操作符优先级表，PGE 有一个名为 optable 的特殊工具。
通过创建一个 is optable 的规则来创建一个操作符。这是一个例子
rule expression is optable { ... }
... 不是省略，而是规则的一部分。如果没有 ... 三个点，你的规则将无法工作。这被称为 _yada yada yada_ 操作符，用于定义函数原型。PGE 将使用您指定的选项为您实例化该函数。关键字 is optable 告诉解析器转换为自下而上的模式以解析表达式
在操作符中，使用 proto 关键字而不是 rule 或 token 关键字来指定令牌。proto 定义必须定义几件事：操作符的名称和类型、操作符的优先级以及用于执行特定操作的 PIR 代码。以下是一些示例
proto 'infix:+' is precidence('1') is pirop('add') { ... }
proto 'prefix:-' is tighter('infix:+') is pirop('neg') { ... }
proto 'postfix:++' is equal('prefix:-') { ... }
这些示例展示了如何解析三个常见操作符：两个值之间的“+”，负数的负值（例如“-123”）和后缀自增运算符（“x++”）。这里有很多重要的关键字，这甚至不是你制作完整表达式解析器所需的所有关键字。
操作符有四种类型：**前缀**、**后缀**、**中缀**和 **环绕**。以下是一些示例
| 类型 | 示例 | 用途 |
|---|---|---|
| 前缀 | prefix:-
|
-123 |
| 后缀 | postfix:*
|
x* |
| 中缀 | infix:+
|
x+y |
| 环绕 | circumfix:()
|
(x) |
| 后缀环绕 | postcircumfix:[]
|
x[y] |
| 三元 | ternary:?
|
x?y:z |
如前所述，自下而上的解析器会遇到一个称为移进-归约冲突的特定问题。移进-归约冲突发生在解析器无法确定是移进新的输入令牌还是归约它已有的令牌时。以下是从 C 编程语言中的一个示例
-x + 2 * y
我们知道，因为我们从小就被教导了操作符优先级，所以表达式是这样分组的
(-x) + (2 * y)
但是，计算机除非我们告诉它操作符遵循的优先级，否则不知道这一点。例如，在不知道操作符作用的顺序的情况下，解析器可能会按照先到先得的方式对表达式进行分组，如下所示
((-x) + 2) * y
或者它可能会移进所有令牌并从右侧开始归约
-(x + (2 * y)
关键是，我们需要创建规则来告诉操作符优先级解析器如何解析这些冲突。以下是可以指定的优先级规则
| 代码 | 效果 |
|---|---|
is precidence('1')
|
设置基本优先级。引号中的数字是任意的。重要的是这是一个常量，其他操作符可以相对于此定义。 |
is equiv('OPERATOR')
|
这里，单词 OPERATOR 将被替换为现有的操作符，例如 is operator('infix:+') 这表明一个操作符与另一个操作符具有相同的优先级。所有具有相同优先级的操作符都是从左到右计算的。 |
is tighter('OPERATOR')
|
该操作符比 OPERATOR 绑定更紧密。在表达式 -x + y 中，我们期望 prefix:- 比 infix:+ 绑定更紧密。 |
is looser('OPERATOR')
|
与 is tighter() 类似，但相反。表明该操作符比 OPERATOR 绑定得更松散 |
我们在示例中没有显示，但也可以确定操作符是从左到右还是从右到左起作用。我们使用 is assoc 关键字定义这一点。下表总结了这些规则
| 结合性 | 解释 |
|---|---|
is assoc('right')
|
|
is assoc('left')
|
|
is assoc('list')
|
|
is assoc('chain')
|
|
is assoc('none')
|
有三种方法可以指定操作符的行为。第一种是将操作符与 PIR 操作码关联。第二种是将操作符与 PAST 节点类型关联。最后，指定操作符动作的第三种方法是创建一个函数。前两种方法分别可以使用 is pirop() 和 is pasttype() 说明符执行。
对于简单的操作，创建和调用函数没有意义。对于可以使用 Parrot 已经定义的 PASM 操作码非常快地执行的简单算术运算，尤其如此。使用代码 is pirop('opname') 将操作符实现为单个操作码。
一些操作符，例如逻辑操作符，可以使用 PAST 已经提供的节点类型来最好地实现。使用 is pasttype('TYPE') 形式来指定要使用的 PAST 节点类型。
默认情况下，除非您将操作符指定为 is pirop 或 is pasttype，否则操作符将默认为函数。因此，大多数操作符默认为函数，这对于打算允许操作符重载的语言来说非常有用。
在这本书中，我们将偶尔使用术语“Proto”、“Proto Regex”或“Protoregex”，它在 Perl 6 文档中也经常使用。Proto类似于规则，但它们提供了类似于多重分派的功能：你可以拥有多个相同名称的规则，这些规则取决于传递给它的操作数。通过将运算符声明为 proto，你为它命名，并且还允许将来对语言进行添加。对于使用运算符重载的语言来说，这是一个重要的功能。
Protos 使用 proto 关键字定义。它们可以在自上而下或自下而上的解析器中使用，但由于它们最常作为运算符重载的支持机制，因此它们最常在自下而上的运算符优先级解析器中使用。要定义一个新的 proto，请使用以下形式
proto NAME OPTIONS { ... }
在这个声明中，{ ... } 是一段代码：你实际上必须在花括号之间键入三个点（省略号）。这样做是为了提醒解析器这不是规则本身的实现，而实际上只是一个签名或其他函数的前向声明。例如，我们可以定义一个 proto MyProto
proto MyProto { ... }
在另一个文件中，我们可以定义函数来实现它
.sub MyProto # Insert the parameter list and function logic here .sub
.sub MyProto # Another MyProto! # Insert a different parameter list and different function logic here .end
术语是运算符之间的值。在以下表达式中
1 + 2 * 3
数字 1、2 和 3 都是术语。术语使用普通规则解析，并使用以下语法加载到运算符优先级表中
proto 'term:' is precedence('1') is parsed(&term) { ... }
当然，你可以根据需要设置优先级，但通常最好使术语尽可能紧凑地解析。is parsed() 属性指定术语应该使用名为“term”的规则进行解析。你可以使用普通的规则语法来定义这个术语。& 符号是 NQP 用于引用子例程的符号。在本例中，所讨论的子例程是用于解析术语的语法方法（但它可以想象成任何其他东西）。在下一章中，我们将更多地了解 NQP 和符号。
术语是解析器从自下而上解析切换回自上而下解析的方式。
创建解析器后，我们需要创建与它们关联的方法来构建解析树所需的 PAST 节点。幸运的是，这些方法很容易创建，通常最好的选择是使用其他语言实现中的基本模板。
术语的定义与任何其他规则一样，不需要任何特殊语法。但是，表达式需要一些特殊的注意。