Как работает backpatching с маркерами?

Question

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

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

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

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

я нашел this code, в которых они принимают входной файл и создание файла с языком 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 есть.

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

A (возможно) проще всего просто запомнить адрес операторов перехода и патч в целевом адресе, когда он известен. Это называется «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»), на самом деле не связаны с backpatching. Они могут использоваться для многих целей. В однопроходном генерации кода часто бывает необходимо выполнить какое-то действие в середине правила, а backpatching - всего лишь один пример.

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

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