Когда использовать абстрактное или конкретное дерево синтаксиса?

Question

Я занимаюсь исследованиями в компиляторах. Лексер, кажется, очень прямолинейный: возьмите «предложение» и разделите его на слова (или жетоны). Для обеспечения правильной грамматики необходим парсер. Парсер обычно берет маркеры и строит дерево, которое приводит к корневому узлу (слова в предложениях, параграфах, страницах и т. Д.).

От this question Казалось бы, парсер будет строить АСТ. AST содержит только то, что необходимо для выполнения кода, поэтому такие вещи, как скобки, не нужны, поскольку приоритет оператора встроен в AST. АСТ, вероятно, все потребности компилятора.

Но как насчет преобразования кода с одного языка на другой? Взятие готового языка (грамматика) или существующей грамматики и преобразование его в другое, где правила приоритета операторов могут или не могут быть разными? Является ли приоритет оператора «встроенным» в КНТ?

В качестве примера можно сказать, что я составил язык и хотел перевести его в PHP-код. Тернарный оператор на большинстве языков имеет ассоциативность справа налево. PHP неправильно использует ассоциативность слева направо (see more about this here). Я хочу, чтобы «мой язык» использовался справа налево, но в результате PHP-код должен применять скобки для получения правильного результата в PHP (с link to Wikipedia, результат должен быть «поезд» вместо «лошади»).

Значит, для перевода на язык КНТ будет лучше? Является ли приоритет оператора обычно встроенным в КНТ? Есть что-то промежуточное? Существуют ли примеры сравнения обоих деревьев с простым алгебраическим уравнением? Любые примеры, иллюстрирующие тернарный оператор?

(Is «перекодировать» правильный термин для «языка программирования перевода» Поиск Google вызывает преобразование медиа?).

То, что я пытаюсь выяснить: когда это более уместно использовать один над другим?

Answer 1

АСТ, который моделирует все семантические детали исходного языка, это все, что вам нужно. По определению, если он правильно моделирует семантику, а ваш langauge включает в себя тернарный оператор, то он будет моделировать конкретный порядок, в котором операторы применяются (например, результаты по умолчанию по умолчанию, например, круглые скобки) правильно.

Итак, ваша проблема не в AST. Он генерирует другой язык с использованием аналогичных (тройных) операторов, приоритет которых отличается.

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

В целом, генерация последовательностей кода, которые достигают желаемого результата, может быть довольно сложной, и есть много способов сделать это. Вот почему книги компилятора толстые, а не тонкие. Вы, кажется, неявно остановились на «получите АСТ, идите по АСТ, код слюны»; это почти генератор кода «на лету». И это работает адекватно, если вам все равно, если сгенерированный код особенно хорош, а целевой язык довольно близок к исходному языку.

Если проблема генерации кода более сложна, то, что обычно происходит, используется AST, чтобы генерировать то, что соответствует модели потока данных вычисления, состоящей из операторов, которые производят результаты, и потребляют результаты предыдущих операторов, заземляя в «операторах», которые извлекают значения переменных и константы.Затем представление потока данных перемещается для генерации кода; это имеет то преимущество, что вы можете выбрать оператора в представлении потока данных, найти соответствующую последовательность кода на целевом языке, сгенерировать это, а затем беспокоиться о том, как собираются операнды. Более эффективные схемы соответствуют подграфам потока данных (представляющим эквивалентные составные конструкции целевого языка) на графике потока данных; это может привести к значительному улучшению кода. Зачастую для генерации еще лучшего кода можно применять оптимизацию на целевом языке после генерации необработанного кода. В обоих случаях вам нужно беспокоиться об управлении результатами оператора; могут ли они быть переданы непосредственно следующему оператору целевого языка или должны идти в какое-то временное хранилище (для машинного кода это может быть другой регистр или ячейка памяти). Делать все это непросто; опять же, поэтому книги компилятора не тонкие.

Вариант этой идеи - преобразования программ источника в источник. Это сопоставляет конструкции в исходном коде «непосредственно» с конструкциями в целевом коде, хотя это обычно делается за кулисами, работая на АСТ, потому что непрочитанный текст на языке программирования трудно сопоставить. Наш DMS Software Reengineering Toolkit является примером такого рода систем. С помощью такого инструмента вы пишете шаблоны на исходном языке (которые неявно соответствуют дереву синтаксического анализа) и соответствующие шаблоны в целевом langauge (неявно создающие АСТ ASTT). Вы можете написать сложные исходные или целевые конструкции, которые в значительной степени влияют на приведенный выше график потока данных. Оптимизация после генерации состоит из большего количества правил перезаписи, которые преобразуют целевой код в целевой код.

Итог: наличие АСТ на самом деле недостаточно, если ваш перевод действительно тривиален. . Вы можете узнать больше о том, что вам нужно в этом ответе SO: https://stackoverflow.com/a/3460977/120163

ВНИМАНИЕ: Ниже следует громкое мнение.

Re «Transcoder»: Я предпочитаю использовать термин «компиляция», «перевод» или «источник-источник». Я занимаюсь разработкой инструментов анализа программ и манипуляций уже почти 40 лет. Я никогда не слышал термин «транскодер», пока не столкнулся с этим вопросом SO: Experience migrating legacy Cobol/PL1 to Java и ответ, описывающий ИМХО, действительно ужасную схему перевода кода, называемую NACA. Я слышал, что этот термин набирает силу; Я не понимаю, почему мы должны были придумать другой термин, когда у нас есть вполне адекватные. Обычно это признак того, что кто-то изобретает высшее священство; «давайте придумаем блестящий новый термин, чтобы люди не понимали, что мы делаем». Я рад оставить этот термин таким действительно ужасным переводам.