Альфа переименование на многих языках

Question

У меня есть, как мне кажется, довольно сложная техническая задача: я хочу иметь возможность надежно переименовывать идентификаторы на нескольких языках (как можно больше). Это потребует особого внимания к каждому языку, и я прошу совета о том, как минимизировать объем работы, которую я должен выполнять, используя общий код. Было бы замечательно что-то вроде единой синтаксической структуры синтаксического разбора или абстрактного синтаксиса, которая уже поддерживает многие языки.

Например, вот код Python:

def foo(x):
    def bar(y):
        return x+y
    return bar

Альфа-переименование от x до y изменяет x на y и сохраняет семантику . Так бы и стало:

def foo(y):
    def bar(y1):
        return y+y1
    return bar

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

Я также хотел бы сохранить как можно больше форматирования: комментарии, интервалы, отступы. Но это не обязательно на 100%, это было бы просто замечательно.

Любые советы?

Answer 1

Чтобы сделать это безопасно, вам необходимо определить

• всех идентификаторов (и тех вещей, которые не являются, например, серединой комментария) в вашем коде
• области действия для каждого идентификатора
• возможность замены нового идентификатора на старый в тексте
• возможность определения, вызывает ли переименование идентификатора затенение другого имени

Чтобы точно определить идентификаторы, вам нужен как минимум лексер с точностью до языка.Идентификаторы в PHP выглядят иначе, чем do в COBOL.

Чтобы определить области действия, вы должны определить структуру программы на практике, так как большинство "областей" определяются такой структурой.Это означает, что вам нужен анализатор с точным языком;Области в PHP отличаются от областей в COBOL.

Чтобы определить, какие имена допустимы в каких областях, вам необходимо знать правила определения языка.Ваш язык может настаивать на том, что идентификатор X будет ссылаться на разные X в зависимости от контекста, в котором находится X (рассмотрим конструкторы объектов с именем X с разными аргументами).Теперь вы должны иметь возможность обходить структуры контекста в соответствии с правилами именования.Одиночное наследование, множественное наследование, перегрузка, типы по умолчанию - все это в значительной степени потребует от вас построения модели областей действия для программ, вставки идентификаторов и соответствующих типов в каждую область, а затем восхождения с точки встречи идентификатораЗапрограммируйте текст в различных областях в соответствии с семантикой языка.Вам понадобятся таблицы символов, связи наследования, AST и возможность навигации по всем этим.Эти структуры отличаются от PHP и COBOL, но у них много общих идей, поэтому вам, вероятно, понадобится библиотека с поддержкой общей концепции.

Чтобы переименовать идентификатор, вам нужно изменитьтекст.В миллионе строк кода вам нужно осторожно указать .Модификация узла AST - один из способов осторожного указания.На самом деле вам нужно изменить все идентификаторы, которые соответствуют переименованному;вам нужно перелезть через дерево, чтобы найти их все, или записать в AST, где есть все ссылки, чтобы их можно было легко найти.После изменения дерева вы должны восстановить исходный текст после изменения AST.Это много машин;см. мой ТАК ответ о том, как довольно распечатать AST , предварительно сохранив все то, что вы разумно предлагаете, должно быть сохранено.(Другой вариант - отслеживать в AST, где находится текст строки, и читать / исправлять / записывать файл.)

Перед обновлением файла необходимо проверить, что у вас нетчто-то не в тени.Рассмотрим этот код:

 {  local x;
     x=1;
    {local y;
     y=2;
      {local z;
         z=y
         print(x);
      }
    }
 }

Мы согласны, что этот код выводит «1».Теперь мы решили переименовать y в x.Мы разбили область видимости, и теперь оператор print, который концептуально ссылается на внешний x, относится к x, захваченному переименованным y.Код теперь печатает «2», поэтому наше переименование сломало его.Это означает, что нужно проверить все другие идентификаторы в областях, в которых может быть найдена переименованная переменная, чтобы увидеть, «захватывает» ли новое имя какое-то имя, которое мы не ожидали.(Это будет законно, если в распечатке выписывается z).

Это много машин.

Да, есть фреймворк, который имеет почти все это, а также ряд надежных языковых интерфейсов.См. Наш инструментарий реинжиниринга программного обеспечения DMS .Он имеет парсеры, производящие AST, довольно принтеры для вывода текста из AST, общий механизм управления таблицей символов (включая поддержку множественного наследования), механизм посещения / модификации AST.Это довольно печатный механизм для превращения АСТ обратно в текст.Он имеет внешние интерфейсы для C, C ++, COBOL и Java , которые реализуют разрешение имен и типов (например, области видимости таблицы мгновенных символов и идентификатор для сопоставлений записей таблицы символов);у него есть интерфейсы для многих других языков, которые еще не реализовали область видимости.

Мы только что завершили упражнение по реализации "переименования" для Java.(Все вышеперечисленные вопросы конечно появились).Мы собираемся запустить один для C ++.

Answer 2

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

Answer 3

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

cp file file.orig
sed -i 's/\b(newTokenName)\b/TEMPTOKEN/g' file
sed -i 's/\b(oldTokenName)\b/newTokenName/g' file

С GNU sed это сломается на PHP.Перезапись \ b на общее совпадение токена, например ([^ a-zA-Z ~ $ -_] [^ a-zA-Z0-9 ~ $ -_]) будет работать на большинстве C, Java, PHP и Python, но не Perl (необходимо добавить @ и% к символам токена. Кроме того, потребуется архитектура плагина, которая работает для любого языка, который вы хотите добавить. В какой-то момент появятся два языка, правила именования переменных и функцийбудет несовместимым, и в этот момент вам нужно будет делать все больше и больше в плагине.