Как работает обратный патч с маркерами?

Question

Я искал по всему Интернету и не мог найти правильное объяснение того, как работает обратная рассылка?

Не могли бы вы объяснить, как работает резервирование? Как это работает с маркерами?

Я знаю, что у него есть 2 основных типа маркеров:

1. со следующим квадом в нем
2. со следующим списком в нем

Я нашел этот код, в котором они берут входной файл и создают файл на языке RISKI.

В своем первом броске они имеют:

PROGRAM : N FUNCTION M MAIN_FUNCTION

и вы можете видеть, что N и M являются маркерами (они являются пустыми рулонами).

Answer 1

Генерация однопроходного кода имеет небольшую проблему с генерацией кода для условных выражений. Типичный 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 а также label2 и когда код для ALTERNATIVE_1 а также ALTERNATIVE_2 генерируется, неизвестно где label3 является.

Одним из способов сделать это является использование символьных имен для меток, как в приведенном выше псевдокоде, и заполнение фактических значений, когда они известны. Это требует хранения символического имени в операторе jump, что усложняет структуру данных (в частности, вы не можете просто использовать двоичный код на ассемблере). Это также требует второго прохода, просто чтобы заполнить цели прыжка.

(Возможно) более простой способ состоит в том, чтобы просто запомнить адрес операторов прыжка и вставить адрес назначения, когда он известен. Это называется "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

Оказывается, что для простых языков необходимо запомнить только два неполных оператора перехода (часто называемые "истина" и "ложь"). Поскольку может быть несколько переходов к одной и той же цели, каждый из них на самом деле является связанным списком неполных операторов перехода, где целевой адрес используется для указания на следующий переход в списке. Таким образом, обратная установка исправлений проходит по списку, исправляя правильную цель и используя исходную цель, чтобы найти предыдущее утверждение, которое необходимо исправить.

То, что вы называете маркерами (которые являются примером того, что yacc/bison называет "Mid-Rule Productions"), на самом деле не связано с бэкаптингом. Они могут быть использованы для многих целей. При генерации однопроходного кода часто необходимо выполнить какое-то действие в середине правила, и создание резервных копий является лишь одним примером.

Например, в гипотетическом if оператора, необходимо будет инициализировать списки бэкапов до того, как CONDITION анализируется, а затем возвращается в начале THEN а также ELSE статьи. (Еще один патч будет запущен в конце разбора всего if утверждение, но это будет в последнем действии правила.)

Самый простой способ выполнить действия в середине правила - это вставить действие в середине правила, что эквивалентно вставке пустой "маркерной" продукции с действием, как в указанном вами примере файла зубров.