Что определяет, как AST должен быть преобразован в целевой язык

Question

Структура AST определяется синтаксической грамматикой. Мне интересно, что определяет, как AST должен быть преобразован в целевой язык. Это синтаксическая грамматика целевого языка?

Answer 1

Реальный ответ заключается в том, что языковая семантика управляет переводом.

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

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

Некоторые инструменты (я создаю один, см. Мою биографию) фактически позволяют вам писать правила перевода, которые выражают именно эти «патчи». Мы можем их "переписать" по правилам; то, что они позволяют вам выразить, это фрагмент синтаксиса на исходном языке и фрагмент синтаксиса на целевом языке, и утверждают, что последний является семантически верным переводом первого. Таким образом, вы можете буквально построить переводчик, написав большой набор таких правил. [Вы получаете большой набор, потому что реальные языки имеют много синтаксических комбинаций и семантических интерпретаций].

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

Если вы спросите, я могу предоставить некоторые ссылки на примеры, но они относятся к нашим инструментам.

Answer 2

Структура AST определяется синтаксической грамматикой.

Вроде. Дерево разбора (или конкретное синтаксическое дерево) напрямую соответствует структуре грамматики. Синтаксическое дерево abstract является абстракцией дерева синтаксического анализа, которое не учитывает ненужные части. То, что является и не имеет значения, также зависит от семантики языка.

Например, выражения (x) и x производят один и тот же AST в большинстве реализаций большинства языков, но вы можете сделать это только в том случае, если эти два значения эквивалентны в соответствии с семантикой языка. Например, в Лиспе (x) будет вызовом функции x, тогда как x будет доступом к переменной x. Так что это пример, когда разные семантики приводят к разным AST.

Мне интересно, что определяет, как AST должен быть преобразован в целевой язык. Это синтаксическая грамматика целевого языка?

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

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

Таким образом, логика для создания правильной целевой программы из AST зависит от семантики исходного языка, а также от синтаксиса и семантики целевого языка.