一次性代码生成在生成条件代码时存在一个小问题。一个典型的if
陈述:
if CONDITION then ALTERNATIVE_1 else ALTERNATIVE_2
需要编译成这样的东西:
compute CONDITION
JUMP_IF_TRUE label1
JUMP_IF_FALSE label2
label1:
code for ALTERNATIVE_1
JUMP label3
label2:
code for ALTERNATIVE_2
JUMP label3
label3:
next statement
但是当代码为CONDITION
正在生成,不知道在哪里生成label1
and label2
是,并且当代码为ALTERNATIVE_1
and ALTERNATIVE_2
正在生成,不知道在哪里生成label3
is.
实现此目的的一种方法是使用标签的符号名称(如上面的伪代码所示),并在已知时填写实际值。这需要在跳转语句中存储符号名称,这使数据结构变得复杂(特别是,您不能只使用二进制汇编代码)。它还需要第二遍,只是为了填充跳跃目标。
一种(可能)更简单的方法是只记住跳转语句的地址,并在已知目标地址时修补它。这称为“回补”,因为您要返回并修补生成的代码。
事实证明,在许多情况下,您最终会得到同一个标签的多个分支。一个典型的例子是像 C 系列那样的“短路”布尔值&&
and ||
运营商。例如,扩展原始示例:
if (CONDITION_1 and CONDITION_2) or CONDITION_3 then ALTERNATIVE_1 else ALTERNATIVE_2
compute CONDITION_1
JUMP_IF_TRUE label1
JUMP_IF_FALSE label2
label1:
compute CONDITION_2
JUMP_IF_TRUE label3
JUMP_IF_FALSE label2
label2:
compute CONDITION_3
JUMP_IF_TRUE label3
JUMP_IF_FALSE label4
label3:
code for ALTERNATIVE_1
JUMP label5
label4:
code for ALTERNATIVE_2
JUMP label5
label5:
next statement
事实证明,对于简单语言来说,只需要记住两个不完整的跳转语句(通常称为“真”和“假”)。因为可能会有多次跳转到同一个目标,所以每一次跳转实际上都是一个不完整跳转语句的链表,其中目标地址用于指向链表中的下一个跳转。因此,回溯会遍历列表,修补正确的目标,并使用原始目标来查找需要修补的前一条语句。
你所说的标记(这是 yacc/bison 所说的“中规则生产”的一个实例)与回补并没有真正的关系。它们可用于多种目的。在一次性代码生成中,通常需要在规则中间执行某些操作,回补只是一个例子。
例如,在假设的if
语句,有必要在执行之前初始化 backpatch 列表CONDITION
被解析,然后在开头进行回补THEN
and ELSE
条款。 (在整个解析结束时将触发另一个backpatchif
声明,但该声明将出现在规则的最终操作中。)
在规则中间执行操作的最简单方法是插入中间规则操作,这相当于插入带有操作的空“标记”产生式,如您指向的示例 bison 文件中所示。