如何使用标记工作？ [英] How does backpatching work with markers?

问题描述

我已经在互联网上搜索过，但找不到正确的解释，了解如何使用backpatching。

您能解释一下我的backpatching是如何工作的？

我知道它有两种主要的标记类型：

1. 下一个四元组


2. 下一个列表

我找到此代码，其中正在接受输入文件并使用RISKI语言创建文件。

在他们的第一个卷中，他们有：

 程序：N FUNCTION M MAIN_FUNCTION 
  

< / div>< p>单向代码生成对于生成用于条件的代码有一个小问题。一个典型的 if 语句：

  if CONDITION then ALTERNATIVE_1 else ALTERNATIVE_2 
  

需要编译成这样：

  compute CONDITION 
 JUMP_IF_TRUE label1 
 JUMP_IF_FALSE label2 
 
 label1：
 ALTERNATIVE_1的代码
 JUMP label3 
 
 label2：
 ALTERNATIVE_2的代码
 JUMP label3 
 
 label3：
下一个语句
  

但是当生成 CONDITION 的代码时，不知道 label1 ALTERNATIVE_1 和的代码时，和 label2 正在生成ALTERNATIVE_2 ，不知道 label3 在哪里。

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

一个（可能）更简单的方法是只记住跳转语句的地址，目标地址。这被称为backpatching，因为你回去并修补生成的代码。

结果是，在许多情况下，你结束了多个分支标签。典型的情况是短路布尔类似于C系列的&& 和 || 运算符。例如，扩展原始示例：

  if（CONDITION_1和CONDITION_2）或CONDITION_3，然后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：
 ALTERNATIVE_1的代码
 JUMP label5 
 
 label4：
 ALTERNATIVE_2的代码
 JUMP label5 
 
 label5：
下一条语句
  

事实证明，对于简单的语言，只需要记住两个不完整的跳转语句（通常称为true和false）。因为可能有多个跳转到同一个目标，其中每个实际上是一个不完全跳转语句的链表，其中目标地址用于指向列表中的下一个跳转。所以，backpatching回到列表，修补正确的目标，并使用原来的目标找到上一个需要修补的语句。

调用标记（这是yacc / bison所指的Mid-Rule Productions的一个实例）并不与backpatching真正相关。它们可用于许多目的。在一代码代码生成中，通常需要在规则中间执行一些操作，而反向处理只是一个例子。

例如，在假设如果语句，则必须在解析 CONDITION 之前初始化backpatch列表，然后在开始时进行backpatch THEN 和 ELSE 子句。 （另一个backpatch将在整个语句的解析结束时被触发，但是一个将在规则的finnal动作中。）

在规则中间执行操作的最简单的方法是插入中间规则操作，这相当于插入一个带有操作的空标记生产，如示例bison文件你指向。

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).

解决方案

One-pass code generation has a small problem with generating code for conditionals. A typical if statement:

if CONDITION then ALTERNATIVE_1 else ALTERNATIVE_2

needs to be compiled into something like this:

  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

But when the code for CONDITION is being generated, it is not known where label1 and label2 are, and when the code for ALTERNATIVE_1 and ALTERNATIVE_2 is being generated, it is not known where label3 is.

One way to do this is to use symbolic names for the the labels, as in the above pseudocode, and fill in the actual values when they are known. That requires storing a symbolic name in the jump statement, which complicates the datastructures (in particular, you can't just use a binary assembler code). It also requires a second pass, just to fill in jump targets.

A (possibly) simpler way is to just remember the address of the jump statements, and patch in the target address when it is known. This is known as "backpatching", because you go back and patch the generated code.

It turns out that in many cases, you end up with multiple branches to the same label. A typical case is "short-circuit" booleans like the C-family's && and || operators. For example, extending the original example:

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

It turns out that for simple languages, it is only necessary to remember two incomplete jump statements (often called "true" and "false"). Because there might be multiple jumps to the same target, each of these is actually a linked list of incomplete jump statements, where the target address is used to point to the next jump in the list. So the backpatching walks back through the list, patching in the correct target and using the original target to find the previous statement which needs to be patched.

What you call markers (which are an instance of what yacc/bison refers to as "Mid-Rule Productions") are not really related to backpatching. They can be used for many purposes. In one-pass code-generation, it is often necessary to perform some action in the middle of a rule, and backpatching is just one example.

For example, in the hypothetical if statement, it would be necessary to initialize the backpatch lists before the CONDITION is parsed and then backpatch at the beginning of the THEN and ELSE clauses. (Another backpatch will be triggered at the end of the parse of the entire if statement, but that one will be in the rule's finnal action.)

The easiest way to perform actions in the middle of a rule is to insert a mid-rule action, which is equivalent to inserting an empty "marker" production with an action, as in the example bison file you point to.

这篇关于如何使用标记工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！