Абстрактное синтаксическое дерево

В формальных языках и компьютерной лингвистике АБСТРАКТНОЕ СИНТАКСИЧЕСКОЕ ДЕРЕВО (AST), или просто синтаксическое дерево является представление в древовидной структуре абстрактной синтаксической структуры исходного кода, написанного на языке программирования. Его внутренние узлы — операторы, а листья — операнды. Каждый узел в дереве обозначает конструкцию, которая встречается в исходном коде. Абстрактное синтаксическое дерево в основном используется для перевода и оптимизации кода. Синтаксис является «абстрактным» в том смысле, что он представляет не все детали, присутствующие в реальном синтаксисе, а скорее только структурные или связанные с контентом детали. В качестве примера мы можем представить дерево, которое представляет логическое выражение. В этом дереве компилятор может очень удобно оптимизировать — например, если одна ветвь дизъюнкции всегда верна, нет необходимости оценивать другую ветвь. Синтаксис является абстрактным в том смысле, что он не отражает каждую деталь, встречающуюся в реальном синтаксисе. Например, группирующие скобки являются неявными и синтаксическими конструкциями в древовидной структуре как if-условие-затем, и их можно обозначить одним узлом с двумя ветвями.
В PHP абстрактное синтаксическое дерево было введено, начиная с седьмой версии между исходным и машинным кодами.
Это отличает абстрактные синтаксические деревья от конкретных синтаксических деревьев, традиционно обозначаемых деревьев синтаксического анализа, которые обычно создаются синтаксическим анализатором в процессе преобразования и компиляции исходного кода. После создания дополнительная информация добавляется в AST посредством последующей обработки, например, контекстного анализа.
Абстрактные синтаксис дерева также используются в анализе программ и трансформация программ систем.
Абстрактные синтаксические деревья — это структуры данных, широко используемые в компиляторах для представления структуры программного кода. AST обычно является результатом фазы синтаксического анализа компилятора. Он часто служит промежуточным представлением программы через несколько этапов, которые требуются компилятору, и оказывает сильное влияние на конечный результат компилятора.
Абстрактное синтаксическое дерево имеет несколько свойств, которые помогают дальнейшие этапы процесса компиляции:

• Абстрактное синтаксическое дерево может быть отредактировано и дополнено информацией, такой как свойства и аннотации для каждого элемента, который он содержит. Такое редактирование и аннотирование невозможно с исходным кодом программы, поскольку это подразумевает его изменение.
• По сравнению с исходным кодом абстрактное синтаксическое дерево не содержит необязательных знаков препинания и разделителей (скобки, точки с запятой, скобки и т. д.).
• Абстрактное синтаксическое дерево обычно содержит дополнительную информацию о программе из-за последовательных этапов анализа компилятором. Например, оно может хранить положение каждого элемента в исходном коде, что позволяет компилятору печатать полезные сообщения об ошибках.
• Абстрактные синтаксические деревья необходимы из-за внутренней природы языков программирования и их документации. Языки часто неоднозначны по своей природе. Чтобы избежать этой неоднозначности, языки программирования часто указываются в качестве контекстно-свободной грамматики (CFG). Однако часто существуют аспекты языков программирования, которые CFG не может выразить, но они являются частью языка и задокументированы в его спецификации. Это детали, которые требуют контекста для определения их достоверности и поведения. Например, если язык позволяет объявлять новые типы, CFG не может предсказать имена таких типов или способ их использования. Даже если язык имеет предопределенный набор типов, для обеспечения правильного использования обычно требуется некоторый контекст. Другой пример — утиная типизация (англ. Duck typing), где тип элемента может меняться в зависимости от контекста. Перегрузка оператора — это еще один случай, когда правильное использование и конечная функция определяются на основе контекста. Java предоставляет отличный пример, где оператор «+» является как числовым сложением, так и конкатенацией строк.

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

• Типы переменных должны быть сохранены как и расположение каждого объявления в исходном коде.
• Порядок исполняемых операторов должен быть явно представлен и четко определен.
• Левый и правый компоненты бинарных операций должны храниться и правильно идентифицироваться.
• Идентификаторы и их назначенные значения должны быть сохранены для операторов присваивания.
• Эти требования могут быть использованы для разработки структуры данных для AST.

Некоторые операции всегда требуют двух элементов, таких как два условия для сложения. Однако для некоторых языковых конструкций требуется произвольно большое количество дочерних элементов, например списки аргументов, передаваемые в программы из командной оболочки. В результате AST, используемый для представления кода, написанного на таком языке, также должен быть достаточно гибким, чтобы можно было быстро добавлять неизвестное количество детей.
Для поддержки проверки компилятором должна быть возможность разбирать AST в форме исходного кода. Созданный исходный код должен быть достаточно похожим на оригинал по внешнему виду и идентичным по исполнению после перекомпиляции.
Из-за сложности требований к абстрактному синтаксическому дереву и общей сложности компилятора, выгодно применять принципы разработки программного обеспечения. Одним из них является использование проверенных шаблонов проектирования для повышения модульности и простоты разработки.
Разные операции не обязательно имеют разные типы, поэтому важно иметь иерархию классов звукового узла. Это имеет решающее значение при создании и модификации AST по мере развития компилятора.
Поскольку компилятор обходит дерево несколько раз, чтобы определить синтаксическую корректность, важно сделать обход дерева простой операцией. При достижении этого компилятор выполняет определенный набор операций в зависимости от типа каждого узла, поэтому часто имеет смысл использовать поведенческий шаблон посетителя.
Абстрактное синтаксическое дерево активно используется во время семантического анализа, где компилятор проверяет правильность использования элементов программы и языка. Компилятор также генерирует таблицы символов на основе AST во время семантического анализа. Полный обход дерева позволяет проверить правильность программы.
После проверки правильности абстрактное синтаксическое дерево служит основой для генерации кода. AST часто используется для генерации промежуточного представления (IR), иногда называемого промежуточным языком, для генерации кода.

Лит.: Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (May 17, 2005). Understanding Source Code Evolution Using Abstract Syntax Tree Matching. MSR’05. Saint Louis, Missouri: ACM. CiteSeerX 10.1.1.88.5815. Baxter, Ira D.; Yahin, Andrew; Moura, Leonardo; Sant’ Anna, Marcelo; Bier, Lorraine (November 16–19, 1998). Clone Detection Using Abstract Syntax Trees (PDF). Proceedings of ICSM’98. Bethesda, Maryland: IEEE. Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C. «Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction» (PDF). (direct link to PDF)

© При копировании активная ссылка на сайт обязательна

См. Алфавитный указатель статей Большой энциклопедии знаний