Алгоритм переписывания модифицированной семантики goto

Question

У меня есть большой набор унаследованного кода на старом самопонятном языке сценариев, который мы компилируем / переводим в javascript.

На этом языке есть условный переход, переход на метку. Отличие от общего утверждения goto состоит в том, что обратные прыжки невозможны. В этом языке нет вложенных операторов if и циклов.

Поскольку goto не существует в javascript, я ищу алгоритм, который преобразует goto mylabel и mylabel: в семантически эквивалентную структуру.

Я думал об использовании ifs, но нашел это не тривиальным из-за произвольного вложения меток goto.

Пример:

if cond1 goto a
do something1
if cond2 goto b
do something2
a:
do something3
if cond3 goto c
do something4
c:
do something5
b:

Может быть переписано как:

lbl_b=false;
lbl_c=false;

lbl_a = cond1;
if (!cond1) {
  do something1;
  lbl_b = cond2;
  if (!lbl_b) {
    do something2;
  }
}
if (!lbl_b) {
  do something3;
  lbl_c = cond3;
  if (!lbl_c) {
    do something4;
  }
  do something5;
}

Однако я не смог вывести общий алгоритм из этого.

Answer 1

Обычно это называется Удаление Goto , у нас была однажды студенческая работа, где была задача реализовать ее для C. В общем, вы должны работать с циклами (к сожалению, мы не выложили эту работу онлайн ). Но поскольку у вас есть ограничение, что вы можете прыгать только вперед, это относительно просто:

Разобрать все строки и собрать все метки. Создайте для каждой метки флаг "skip_to_label". Инициализировать в начале все флаги на ложь Когда вы соответствуете условному переходу для метки X, вы теперь добавляете каждую строку до строки метки с помощью «если не skip_to_label» и устанавливаете для флага значение true.

Этого должно хватить и на работу, но конечно не очень оптимально.

Как вы можете оптимизировать это: вместо того, чтобы предварительно добавлять if, просто сохраняйте набор флагов для каждой строки, и вместо того, чтобы устанавливать что-то в false, просто добавьте для строк соответствующий флаг в наборе.

Теперь вы можете сделать if для группы, которая содержит все строки, где набор не изменяется, а условием являются логические флаги набора.

Пример с вашим заданным кодом:

set                    your code
empty                  if cond1 goto a 
skip_to_a,             do something1
skip_to_a,             if cond2 goto b
skip_to_a, skip_to_b   do something2
skip_to_a, skip_to_b   a:
skip_to_b              do something3
skip_to_b, skip_to_c   if cond3 goto c
skip_to_b, skip_to_c   do something4
skip_to_b, skip_to_c   c:
skip_to_b              do something5
skip_to_b              b:

Теперь вы пишете перед каждой строкой либо if (s), либо начинаете сверху и делаете блок if, пока набор остается неизменным.

Итак, когда вы начинаете, вы получаете свой первый на пустом месте, это условный переход, поэтому вместо этого вы устанавливаете свой флаг

if cond1 goto skip_to_a=true;

теперь набор меняется, и вы вводите свой блок с if из набора:

if (!skip_to_a) BEGIN
   do something1
   if cond2 skip_to_b=true;
   END

следующее изменение в наборе, поэтому новый блок if:

if (!skip_to_a and !skip_to_b) BEGIN
   do something2
   END

и так далее (я думаю, вы поняли идею).

РЕДАКТИРОВАТЬ : Как можно хорошо видеть на множествах в примере, в целом невозможно моделировать его с помощью вложенных if, например строки с skip_to_a и строки с skip_to_b перекрываются, но ни одна из них не содержит другой завершенной.

Answer 2

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

Преимущество этого в том, что goto можно заменить простым вызовом метода. Недостатком является то, что для длинных сценариев или циклов вы можете получить довольно большие стеки вызовов.

Используя этот метод, простой алгоритм будет:

goto_label_count := 0 // Find out how many methods we need to generate
For each line:
    if line is goto
        goto_label_count := goto_label_count + 1

Write function head
Write "goto0();"

goto_count := 0 // Generate code
For each line:
    if line is goto
        if goto_count > 0
             write "goto"+goto_count+"();" // produce call to last goto found
        write function header for corresponding goto //("goto"+goto_count+"()")
        goto_count := goto_count + 1
    else
        translate normally
Generate end of code

Это может привести к дополнительным проблемам. Например, что из области видимости для переменных? Но, по крайней мере, это альтернативный подход, который, я надеюсь, должен привести вас в порядок в дальнейшем. ;)

Answer 3

Компиляция на другой язык обычно сложнее, чем необходимо.Более простой способ - не компилировать на другой язык, а интерпретировать код в javascript.Таким образом, было бы легко создать ваш оператор goto с любой семантикой, какой бы вы хотели.

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

Answer 4

Вы могли бы сделать что-то вроде отслеживания состояния перехода в цикле while, но это не выглядело бы слишком красиво:

var goto = null ;

do {
  if(goto == null && cond1) goto = 'a' ;
  if(goto == null) do_something(1) ;
  if(goto == null && cond2) goto = 'b' ;
  if(goto == null) do_something(2) ;
  if(goto == null || goto == 'a') goto = null;
  if(goto == null) do_something(3) ;
  if(goto == null && cond3) goto = 'c' ;
  if(goto == null) do_something(4) ;
  if(goto == null || goto == 'c') goto = null ;
  if(goto == null) do_something(5) ;
  if(goto == null || goto == 'b') goto = null ;
} while(goto != null)