3

I've searched all over the Internet and could not find a proper explanation of how backpatching works?

Can you please explain me how does backpatching works? How does it work with the markers?

I know it has 2 main types of markers:

  1. with next-quad in it
  2. with next-list in it

I found this code, in which they are taking an input file and creating a file with RISKI language.

In their first roll they have:

PROGRAM : N FUNCTION M MAIN_FUNCTION

and you can see that N and M are markers (they are empty rolls).

4

1 回答 1

9

一次性代码生成在为条件生成代码方面存在一个小问题。一个典型的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生成for的代码时，不知道在哪里label1和在哪里，在生成for和label2的代码时，也不知道在哪里。ALTERNATIVE_1ALTERNATIVE_2label3

一种方法是使用标签的符号名称，如上面的伪代码，并在已知值时填写实际值。这需要在跳转语句中存储一个符号名称，这会使数据结构复杂化（特别是，您不能只使用二进制汇编代码）。它还需要第二遍，只是为了填写跳跃目标。

一种（可能）更简单的方法是只记住跳转语句的地址，并在目标地址已知时修补它。这称为“backpatching”，因为您返回并修补生成的代码。

事实证明，在许多情况下，您最终会得到同一个标签的多个分支。&&一个典型的例子是像 C 系列和运算符这样的“短路”布尔值||。例如，扩展原始示例：

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

事实证明，对于简单的语言，只需要记住两个不完整的跳转语句（通常称为“真”和“假”）。因为可能有多个跳转到同一个目标，每一个实际上都是一个不完整跳转语句的链表，其中目标地址用于指向链表中的下一个跳转。因此，backpatching 遍历列表，修补正确的目标并使用原始目标找到需要修补的先前语句。

您所说的标记（这是 yacc/bison 称为“Mid-Rule Productions”的一个实例）与回补并没有真正的关系。它们可用于多种用途。在一次性代码生成中，通常需要在规则中间执行一些操作，回补只是一个例子。

例如，在假设的if陈述中，有必要在解析之前初始化 backpatch 列表，然后在and子句CONDITION的开头进行 backpatch 。（另一个 backpatch 将在整个语句的解析结束时触发，但该补丁将在规则的最终操作中。）THENELSEif

在规则中间执行操作的最简单方法是插入中间规则操作，这相当于插入带有操作的空“标记”产生式，如您指向的示例野牛文件中所示。

于 2014-01-23T01:22:46.590 回答