鹦鹉虚拟机/Squaak 教程/运算符和优先级
第一集： 简介
第二集： 窥探编译器内部
第三集： Squaak 细节和第一步
第四集： PAST 节点和更多语句
第五集： 变量声明和作用域
第六集： 作用域和子程序
第七集： 运算符和优先级
第八集： 哈希表和数组
第九集： 总结和结论
到目前为止，我们已经实现了 Squaak 语言的很大一部分。我们已经看到了赋值、控制流语句、变量声明和作用域、子程序和调用。到目前为止，我们的表达式仅限于单个值，例如字符串文字和整数常量。在本集中，我们将增强 Squaak 以便它可以处理运算符，这样你就可以构建更复杂的表达式。
我们首先简要介绍一下使用递归下降解析器（PCT 生成的解析器）解析表达式时遇到的问题。考虑以下迷你语法，它是一个非常基本的计算器。
rule TOP {
<expression>*
}
rule expression {
<term>
}
rule term {
<factor> [ <addop> <factor> ]*
}
token addop { '+' | '-' }
rule factor {
<value> [ <mulop> <value> ]*
}
token mulop { '*' | '/' | '%' }
rule value{
| <number>
| '(' <expression> ')'
}
这种基本的表达式语法通过利用递归下降解析器的性质来实现运算符优先级（如果你还没有见过这个词，就在谷歌上搜索一下）。然而，用这种方式解析表达式的最大缺点是，解析树可能会变得相当大。也许更重要的是，解析过程效率不高。让我们来看一些示例输入。我们不会像在 第二集 中那样显示解析树，而只是显示一个概要。
输入：42 导致以下解析树
TOP
expression
term
factor
value
number
42
如你所见，这个单个数字的输入将在解析实际数字之前调用 6 个语法规则。你可能会觉得这还不错。
输入："1 + 2" 导致以下解析树（我们现在忽略运算符）
TOP
expression
term
factor
| value
| number
| 1
factor
value
number
2
只调用了几个语法规则，这也不是什么大问题。
输入："（1 + 2）* 3" 导致以下解析树
TOP
expression
term
factor
value
| expression
| term
| | factor
| | value
| | number
| | 1
| term
| factor
| value
| number
| 2
value
number
3
正确；仅仅为了解析这个简单的输入就调用了 16 个语法规则。我认为这有点效率低下。重点是，使用递归下降解析器实现运算符优先级有一些问题，而且考虑到有更好的方法来解析像这样的表达式，所以这不是最好的方法。查看 这个很好的解释 或在谷歌上搜索。
我想向你解释一下，自底向上解析是如何针对表达式（或者一般意义上的自底向上解析器；Yacc/Bison 是解析器生成器，它们会根据你的语法规范生成自底向上解析器）工作的，同时考虑运算符优先级。然而，我已经大约 6 年没有在 CS 课程中学过这个了，我不记得具体的细节。如果你真的想知道，请查看上一节末尾的链接。实际上值得一看。现在，我假设你知道问题所在，这样我就可以立即介绍针对基于 PCT 的编译器的解决方案。在你解析输入的某个时刻，你可能会遇到一个表达式。在这一点上，我们希望解析器从自顶向下切换到自底向上解析。鹦鹉语法引擎支持这一点，并且可以使用以下方式进行使用
rule expression is optable { ... }
请注意，我们在这里使用了“表达式”这个词，但你可以用任何名字来命名它。这声明了，每当你需要一个表达式时，就会激活自底向上解析器。当然，这个“optable”必须填充一些我们需要才能解析的运算符。这可以通过以下方式声明运算符来实现
proto 'infix:*' is tighter('infix:+') { ... }
这定义了运算符“*”（“infix:”是一个前缀，告诉运算符解析器这个运算符是一个中缀运算符；还有其他类型，例如前缀、后缀和其他）。“is tighter”子句表示“*”运算符的优先级高于“+”运算符。正如你可能已经猜到的那样，还有其他子句来声明等效优先级（“is equiv”）和较低优先级（“is looser”）。
正确拼写所有子句（例如，“is equiv”）非常重要（例如，不要写成“is equil”），否则你可能会在尝试运行编译器时收到一些神秘的错误消息。请查看参考文献部分中的运算符表指南，其中包含更多关于此方面的详细信息。
当然，表达式解析器不仅仅解析运算符，它还必须解析操作数。那么，我们如何声明代表操作数的最基本实体呢？它可以是任何东西，从一个基本的整数常量、一个函数调用，甚至是一个函数定义（但是将两个函数定义加起来并没有多大意义，对吧？）。操作数以递归下降方式解析，因此解析器必须在某个地方从自底向上（表达式解析）切换回自顶向下。为了声明这个“切换”点，请编写以下内容
proto 'term:' is tighter('prefix:-')
is parsed(&term) { ... }
名称“term:”是运算符自底向上解析器的内置名称；每当需要一个新的操作数时，它都会被调用。“is parsed”子句告诉解析器“term”（它意外地看起来像“term:” ，但你也可以给它起任何其他名字）解析操作数。
注意：在“term:”规则的声明中添加“is tighter”子句非常重要。否则你的表达式解析器将无法工作！我在这方面的知识有限，但我通常将它定义为相对于已定义的最紧运算符的“is tighter”。
我们已经定义了表达式（自底向上）解析器的入口点和出口点，现在是时候添加运算符了。让我们看一下 Squaak 的运算符及其优先级。运算符按优先级递减的顺序列出（以便高优先级运算符列在顶部）。（我不确定这个优先级表与其他语言相比是否通用；某些运算符可能与你习惯的运算符相比具有不同的优先级。至少数学运算符是按照标准数学规则组织的）。
unary "-" unary "not" * / % + - .. < <= >= > != == and or
（“..”是字符串连接运算符）。除了为表达式解析器定义入口点和出口点之外，你还需要定义一个运算符作为参考点，以便可以相对于该参考点定义其他运算符的优先级。我个人更喜欢将优先级最低的运算符声明为参考点。这可以通过以下方式实现
proto 'infix:or' is precedence('1') { ... }
现在，可以定义其他运算符
proto 'infix:and' is tighter('infix:or') { ... }
proto 'infix:<' is tighter('infix:and') { ... }
proto 'infix:+' is tighter('infix:<') { ... }
proto 'infix:*' is tighter('infix:+') { ... }
proto 'prefix:not' is tighter('infix:*') { ... }
proto 'prefix:-' is tighter('prefix:not') { ... }
请注意，有些运算符缺失。请查看练习部分。有关运算符表使用的更多详细信息，请查看鹦鹉存储库中的 docs/pct/pct_optable_guide.pod。
Squaak 有两个逻辑运算符：and 和 or；and 只有当两个操作数都计算为真时才返回真，而 or 只要至少有一个操作数计算为真就返回真。两个操作数都是短路计算的，这意味着如果不需要计算两个操作数，它们就不会计算。例如，如果 and 运算符的第一个操作数计算为假，那么就没有必要计算第二个操作数，因为 and 表达式的最终结果不可能再变为真（记住：两个操作数都必须计算为真）。
让我们考虑如何实现这一点。在计算 and 表达式时，我们首先计算第一个操作数，如果它是真，只有这时才有意义计算第二个操作数。这种行为看起来很像 if 语句，不是吗？在 if 语句中，第一个子语句总是被计算的，如果为真，第二个子语句（“then”块）就会被计算（记住，第三个子语句 -- “else” 子句 -- 是可选的）。如果能使用 PAST::Op( :pasttype('if') ) 节点来实现 and 运算符，那将是件好事。你可以使用 “is pasttype” 子句来做到这一点！以下是方法：
proto 'infix:and' is tighter('infix:or')
is pasttype('if') { ... }
那么 or 运算符呢？在计算 or 表达式时，会计算第一个操作数。如果它计算为真，则无需计算第二个操作数，因为 or 表达式的结果已经是真！只有当第一个操作数计算为假时，才需要计算第二个子语句。嗯...... 我们的意思是，除非第一个操作数计算为真，否则计算第二个子语句。猜猜你需要什么 pasttype 来做到这一点！
运算符 PAST 类型和 PIR 指令
[edit | edit source]在上一节中，我们介绍了可以指定的“pasttype”子句。这意味着对于该运算符（例如，我们讨论的“and”运算符），将创建一个 PAST::Op( :pasttype('if') ) 节点。如果未指定 pasttype 会发生什么？
在这种情况下，将创建一个默认的 PAST::Op 节点，默认的 pasttype 为 'call'。换句话说，将创建一个调用声明的运算符的 PAST::Op 节点。例如，“infix:+” 运算符会导致对子例程“infix:+” 的调用。这意味着你需要为每个运算符实现子例程。现在，这有点可惜。显然，一些语言对“+”运算符有非常奇特的语义，但许多语言只想使用 Parrot 的内置加法指令。我们如何实现这一点？不要添加“pasttype”子句，而是指定“pirop”子句。“pirop” 或“PIR 运算符”子句告诉代码生成器应该生成哪个运算符。它不会生成具有操作数作为参数的子例程调用，而是会生成具有运算符操作数作为参数的指定指令。很酷吧？让我们看一个例子：
proto 'infix:+' is tighter('infix:<')
is pirop('n_add') { ... }
这指定使用“n_add”指令，它告诉 Parrot 创建一个新的结果对象，而不是更改其中一个操作数。你可能会想，为什么不直接使用“add”指令（它接受两个操作数，更新第一个）呢？好吧，如果你省略这个“is pirop”部分，就会生成以下内容：
$P12 = "infix:+"($P10, $P11)
你会看到，涉及到三个寄存器。正如我们之前提到的，PCT 不会进行任何优化。因此，它不会生成上面的指令，而是直接发出以下内容：
n_add $P12, $P10, $P11
这意味着寄存器 $P10 和 $P11 中的 PMC 会被相加，并赋值给一个新创建的 PMC，该 PMC 被存储在寄存器 $P12 中。
是否使用环绕运算符
[edit | edit source]Squaak 支持带括号的表达式。括号可以用来改变表达式中的计算顺序，就像你在其他语言中看到的那样。除了中缀、前缀和后缀运算符之外，你还可以定义环绕运算符，它使用左右分隔符来指定。这是实现带括号的表达式的理想方式
proto 'circumfix:( )' is looser('infix:+')
is pirop('set') { ... }
默认情况下，将为每个运算符生成一个子例程调用，在本例中为对“circumfix:( )”的调用。但是，我们只对被括起来的表达式感兴趣。子例程只会返回表达式。相反，我们可以使用 pirop 属性来指定应该生成哪个 PIR 操作；在本例中为“set”操作，它将一个寄存器设置为另一个寄存器的内容。
这个解决方案可以正常工作，但“set”指令有点浪费。发生的事情是，某个寄存器的内容被简单地复制到另一个寄存器中，然后在后面的代码生成中使用。这个“set”指令最好被优化掉。目前，PCT 中没有实现任何优化。
添加带括号的表达式语法规则有一个替代方案，方法是将其作为 term 的替代方案添加。然后，term 语法规则最终将变为：
rule term {
| <float_constant> {*} #= float_constant
| <integer_constant> {*} #= integer_constant
| <string_constant> {*} #= string_constant
| <primary> {*} #= primary
| '(' <expression> ')' {*} #= expression
}
当然，尽管我们节省了一条生成的指令，但解析器效率会略低，原因我们在本节开头讨论过。当然，你可以自由地决定如何实现这一点；本节只是解释了这两种方法。在某个时候，PCT 中会实现优化。我怀疑“无用”指令（比如我们刚刚看到的“set”指令）会被删除。
表达式解析器的动作方法
[edit | edit source]对于我们介绍的所有语法规则，我们还介绍了一个动作方法，该方法在语法规则完成匹配后被调用。optable 的动作方法是什么？自然，必须执行一些操作。
嗯，它确实有，但坦白地说，我无法向你解释。每次需要 optable 的动作方法时，我都会从现有的动作文件中复制它。当然，动作方法的名称应该与 optable 的名称匹配（包含“is optable”子句的规则）。所以，这里就是：
method expression($/, $key) {
if ($key eq 'end') {
make $($<expr>);
}
else {
my $past := PAST::Op.new(
:name($<type>),
:pasttype($<top><pasttype>),
:pirop($<top><pirop>),
:lvalue($<top><lvalue>),
:node($/) );
for @($/) {
$past.push( $($_) );
}
make $past;
}
}
下一步是什么？
[edit | edit source]本节介绍了运算符的实现，它允许我们编写复杂的表达式。到目前为止，我们语言的大部分内容都已实现，只有一件事除外：聚合数据结构。这将是 第 8 节 的主题。我们将介绍两种聚合数据类型：数组和哈希表，并了解如何实现它们。我们还将讨论在将这些聚合作为子例程参数传递时会发生什么，以及它与基本数据类型的区别。
练习
[edit | edit source]- 问题 1
目前，Squaak 只有整数和字符串常量的语法规则，没有浮点数常量的语法规则。实现这个语法规则。浮点数由零个或多个数字组成，后面跟着一个小数点和至少一位数字，或者至少一位数字后面跟着一个小数点和任意多个数字。例如：42.0、1.、.0001。各个数字和小数点之间不能有空格。确保你理解“规则”和“标记”之间的区别。
- 提示
- 目前，Parrot 语法引擎 (PGE)，即“执行”正则表达式（你的语法规则）的组件，按顺序匹配替代子规则。这意味着这将不起作用：
rule term {
| <integer_constant>
| <float_constant>
...
}
因为当给出输入“42.0”时，“42”将被 <integer_constant> 匹配，而小数点和“0”将保留下来。因此，将 <float_constant> 替代方案放在 <integer_constant> 之前的 term 规则中。在某个时候，PGE 将支持最长标记匹配，因此这个问题将消失。
- 解决方案
token float_constant {
[
| \d+ '.' \d*
| \d* '.' \d+
]
{*}
}
- 问题 2
实现缺失的运算符：（二元）“-”、“<=”、“>=”、“==”、“!=”、“/”、“%”、“or”。
- 解决方案
为了完整起见（方便你复制粘贴），以下是为 Squaak 编写的运算符声明列表：
rule expression is optable { ... }
proto 'infix:or' is precedence('1')
is pasttype('unless') { ... }
proto 'infix:and' is tighter('infix:or')
is pasttype('if') { ... }
proto 'infix:<' is tighter('infix:and') { ... }
proto 'infix:<=' is equiv('infix:<') { ... }
proto 'infix:>' is equiv('infix:<') { ... }
proto 'infix:>=' is equiv('infix:<') { ... }
proto 'infix:==' is equiv('infix:<') { ... }
proto 'infix:!=' is equiv('infix:<') { ... }
proto 'infix:+' is tighter('infix:<')
is pirop('n_add') { ... }
proto 'infix:-' is equiv('infix:+')
is pirop('n_sub') { ... }
proto 'infix:..' is equiv('infix:+')
is pirop('n_concat') { ... }
proto 'infix:*' is tighter('infix:+')
is pirop('n_mul') { ... }
proto 'infix:%' is equiv('infix:*')
is pirop('n_mod') { ... }
proto 'infix:/' is equiv('infix:*')
is pirop('n_div') { ... }
proto 'prefix:not' is tighter('infix:*')
is pirop('n_not') { ... }
proto 'prefix:-' is tighter('prefix:not')
is pirop('n_neg') { ... }
proto 'term:' is tighter('prefix:-')
is parsed(&term) { ... }
参考资料
[edit | edit source]- docs/pct/pct_optable_guide.pod