Автоматизированный алгоритм удаления GOTO

Я слышал, что теоретически возможно выразить любой поток управления на языке Turing-complete, используя только конструктивные программирующие конструкции (условные обозначения, циклы и перерывы цикла и вызовы подпрограмм) без каких-либо произвольных GOTO заявления. Есть ли способ использовать эту теорию для автоматизации рефакторинга кода, который содержит GOTO, в код, который не работает?

Скажем, у меня есть произвольная одна подпрограмма на простом императивном языке, например C или Pascal. У меня также есть синтаксический анализатор, который может проверить, что эта подпрограмма действительна, и создать из нее абстрактное дерево синтаксиса. Но код содержит GOTO и ярлыки, которые могут прыгать вперед или назад в любую произвольную точку, в том числе в или из условных или циклов, но не вне самой подпрограммы.

Есть ли алгоритм, который мог бы взять этот AST и переработать его в новый код, который семантически идентичен, но не содержит выражений Labels или GOTO?

Ответ 1

Я думаю, что вы хотите читать Taming Control Flow от Erosa и Hendren, 1994. (Более ранняя ссылка на Google ученого).

Кстати, петлевые перерывы также легко устранить. Существует простая механическая процедура, связанная с созданием логической переменной состояния и реструктуризацией вложенных условных выражений для создания линейного потока управления. Он не создает красивый код:)

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

for (Type Index = Start;        function loop(Index: Type):    
     Condition(Index);              if (Condition)
     Index = Advance(Index)){           return                      // break
   Body                             Body
}                                   return loop(Advance(Index))     // continue
                                loop(Start)

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

{
    Type Index = Start;
    while (true) {
        if (!Condition(Index))
            break;
        Body;
        continue;
    }
}

Ответ 2

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

Один из способов всегда исключить gotos - преобразовать программу следующим образом. Начните с нумерации всех инструкций в исходной программе. Например, с учетом этой программы:

start:
    while (true) {
        if (x < 5) goto start;
        x++
    }

Вы можете пронумеровать следующие утверждения:

0 start:
1     while (x < 3) {
2         if (x < 5) goto start;
3         x++
      }

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

int PC = 0;
while (PC <= 3) {
    if (PC == 0) {
         PC = 1;             // Label has no effect
    } else if (PC == 1) {
         if (x < 3) PC = 4;  // Skip loop, which ends this function.
         else PC = 2;        // Enter loop.
    } else if (PC == 2) {
         if (x < 5) PC = 0;  // Simulate goto
         else PC = 3;        // Simulate if-statement fall-through
    } else if (PC == 3) {
         x++;
         PC = 1;             // Simulate jump back up to the top of the loop.
    }
}

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

Надеюсь, это поможет!

Ответ 3

Я использую либо/и многогранный спаг, и огромный 77to90, чтобы начать процесс рефакторинга fortran, а затем преобразовать его в источник Matlab. Тем не менее, эти инструменты всегда оставляют 1/4 до 1/2 из goto в программе.

Я написал утилиту для удаления goto, которая выполняет что-то похожее на то, что вы описываете: он принимает fortran-код и рефакторирует все оставшиеся goto из программы и заменяет их условными выражениями и do/cycle/exit, которые затем могут быть преобразованы в другие языки, такие как matlab. Вы можете больше узнать о процессе, который я здесь использую:

http://engineering.dartmouth.edu/~d30574x/consulting/consulting_gotorefactor.html

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