Абстрактное синтаксическое дерево (АСД; ) — представление программы в виде дерева. Им пользуются компиляторы, переводящие программу в машинный код, и другие средства обработки исходного кода. Каждый узел дерева обозначает конструкцию языка, а потомки узла — части этой конструкции. Так, выражение a + b становится узлом «сложение», а его потомки — a и b.
Дерево называют абстрактным потому, что оно передаёт не саму запись программы, а её смысл. В нём нет узлов для скобок, точек с запятой и запятых, а также для тех правил грамматики, которые ничего не добавляют к содержанию. Этим АСД отличается от — дерева, которое воспроизводит разбор текста по правилам грамматики полностью. Понятие абстрактного синтаксиса ввёл Джон Маккарти в 1962 году, предложив описывать конструкции языка независимо от того, какими знаками они записаны.
Работать с деревом удобнее, чем со строкой текста: структура программы в нём задана явно, а к узлам можно добавлять сведения, полученные при анализе. Дерево строит синтаксический анализатор; затем по нему проверяют программу на ошибки, переводят её в другие промежуточные представления или сразу выполняют. Вне компиляторов АСД используют статические анализаторы, средства поиска уязвимостей и рефакторинга, программы поиска повторяющегося кода и сравнения версий, а также применяют в машинном обучении на исходном коде.
Абстрактное дерево и дерево разбора
Дерево разбора, или дерево конкретного синтаксиса, показывает, как текст программы выводится по правилам грамматики. В нём есть узел для каждого применённого правила и лист для каждого токена исходного текста, включая разделители. Свои узлы получают даже те правила, которые лишь переименовывают одну конструкцию в другую. Абстрактное дерево всего этого не содержит: пунктуация и вспомогательные правила выражены самой формой дерева.
Проще всего разница видна на примере скобок. В выражении (a + b) * c скобки нужны только для того, чтобы задать порядок действий. В абстрактном дереве порядок задан положением узлов: узел сложения оказывается потомком узла умножения. Отдельные узлы для скобок становятся не нужны.
Где именно провести границу между двумя видами деревьев, каждый разработчик решает сам, исходя из задач своего инструмента. Дерево Clang, компилятора языков Си и C++, близко и к тексту программы, и к формулировкам стандарта языка: в нём, в частности, сохранены скобки. Выражения, значение которых компилятор мог бы подсчитать заранее — например, 2 + 3, — тоже оставлены как есть. Этим в документации Clang объясняют, почему такое дерево удобно средствам рефакторинга.
Ещё дальше идёт платформа Roslyn: в неё входят компиляторы языков C# и Visual Basic от Microsoft, а построенное ими синтаксическое дерево она открывает другим программам. Это дерево «полной точности» () хранит каждый элемент исходного текста, включая пробелы, комментарии и директивы препроцессора. Незначимые элементы объединены в так называемую тривию и привязаны к соседним токенам, поэтому по любому узлу можно точно восстановить соответствующий ему фрагмент текста. Библиотека , применяемая в текстовых редакторах, строит именно дерево конкретного синтаксиса и обновляет его по мере правки файла, не разбирая файл заново целиком.
Понятие абстрактного синтаксиса Маккарти изложил это понятие в докладе на конгрессе ИФИП 1962 года. Он сравнил его с нормальной формой Бэкуса, которой пользовались в отчёте об Алголе. Такая форма описывает язык синтетически: она объясняет, как программа собирается из частей. Для перевода программы нужно обратное — уметь разобрать её на части. Поэтому Маккарти предложил описание аналитическое и притом абстрактное, то есть не зависящее от того, какими знаками записана конструкция.
Для арифметических выражений Алгола Маккарти ввёл четыре предиката — проверки, отвечающие «да» или «нет». Предикаты isconst, isvar, issum и isprod сообщают, чем является выражение: константой, переменной, суммой или произведением. К ним Маккарти добавил функции addend, augend, mplier и mpcand, извлекающие из выражения его части. При таком описании безразлично, записана ли сумма как a+b, как +ab или как (PLUS A B): важно лишь, что сумму можно опознать и разобрать. Впоследствии Маккарти считал эту работу первым употреблением понятия абстрактного синтаксиса.
Абстрактный синтаксис языка можно записать формально, а по этой записи — получить готовый код структур данных. Для этого в рамках проекта Zephyr, который совместно вели Принстонский университет и Виргинский университет, разработали язык ASDL (). Описание на ASDL перечисляет виды узлов дерева и части каждого из них, а инструменты превращают такое описание в определения типов на C, C++, Java или ML. Для абстрактного синтаксиса ASDL играет ту же роль, что регулярные выражения — для лексической структуры языка, а контекстно-свободная грамматика — для синтаксической. На ASDL, в частности, записана абстрактная грамматика Python; она доступна через стандартный модуль ast.
Устройство дерева
Что хранится в узле Узел хранит вид конструкции и ссылки на потомков. Листья дополнительно содержат сведения о значении. Это либо сам литерал — записанное прямо в тексте число или строка, — либо ссылка на запись в таблице символов, перечне имён из программы. Кроме того, узлы обычно помнят, какому месту исходного текста они соответствуют. Это нужно, чтобы выдавать понятные сообщения об ошибках и связывать результаты анализа с конкретной строкой файла. Так, режим -ast-dump в Clang показывает для каждого узла диапазон строк и столбцов, а анализатор Babel по запросу добавляет к узлам смещения в тексте.
Дробность узлов При проектировании дерева выбирают степень дробности узлов. Можно обойтись одним общим видом узла, различая конструкции значением поля, а можно завести отдельный вид для каждой конструкции языка. Например, для арифметических операций с двумя операндами первый путь даёт единственный узел «двухместная операция» с полем, где записан знак операции. Второй путь даёт отдельные классы AddBinary, SubtractBinary и так далее с общим предком Binary. Второй вариант предпочтителен, если с узлами связано поведение, а не только данные.
Как узлы описывают в разных языках Способ записи узлов зависит от языка, на котором написан сам инструмент. В функциональных языках дерево описывают алгебраическим типом данных: у такого типа столько разновидностей, сколько есть видов узлов, а функции над деревом определяют сопоставлением с образцом. Компилятор при этом сам указывает на необработанные виды узлов. В объектно-ориентированных языках узлы делают классами, производными от общего абстрактного предка, а выбор нужной обработки поручают полиморфизму: длинного ветвления по видам узлов не требуется.
Обход дерева Проверку типов, генерацию кода, подсчёт метрик и прочую работу над деревом обычно оформляют по схеме «Посетитель». Узлы при этом остаются простыми хранилищами данных, а каждый вид обработки выносится в отдельный объект-посетитель. Такое разделение применяют, когда одно дерево обрабатывают по-разному в нескольких местах. Если обработка всего одна, посетитель не нужен: её методы размещают прямо в узлах.
Построение дерева Строит дерево синтаксический анализатор — как написанный вручную, так и порождённый генератором вроде Yacc или ANTLR. Узлы, как правило, создаются снизу вверх, по мере того как анализатор распознаёт всё более крупные конструкции. При работе с генератором вызовы, создающие узлы, вставляют в секции семантических действий — фрагменты кода, которые срабатывают при распознавании соответствующего правила грамматики.
Формально это описывает синтаксически управляемая трансляция. Каждому нетерминалу грамматики — вспомогательному понятию вроде «выражения» или «оператора» — сопоставляют атрибут, значением которого служит узел дерева. Семантическое правило строит этот узел из узлов, полученных для символов правой части. Правила, ничего не добавляющие к содержанию, просто передают наверх узел одного из своих символов. Общую теорию приписывания значений узлам дерева разработал Дональд Кнут в 1968 году. В его одни атрибуты вычисляются по потомкам узла, другие — по его предкам; первые называют синтезируемыми, вторые — наследуемыми.
Возможен и другой порядок: сначала построить полное дерево разбора, а затем обойти его и удалить всё, что не входит в абстрактный синтаксис. Существуют также генераторы, которые по краткому описанию структуры дерева сами порождают код для его представления и построения.
Применение в компиляторах и интерпретаторах
Проверка программы В крупных системах трансляции смысловые проверки выполняют именно над деревом. Семантический анализатор берёт дерево вместе с таблицей символов и выясняет, согласуется ли программа с определением языка. В частности, он сверяет типы операндов каждой операции с допустимыми и при необходимости вставляет в дерево узлы преобразования типов.
Переход к другим представлениям Промежуточные представления бывают двух видов. Древовидные — это дерево разбора и абстрактное синтаксическое дерево. Линейные лишены иерархии; самое известное из них — трёхадресный код, цепочка простейших шагов вроде сложения двух значений. После проверок дерево служит основой для получения кода. Простейшие трансляторы обходят дерево и сразу выдают текст на целевом языке. В более сложных случаях дерево переводят в другое промежуточное представление. Это может быть язык передачи регистров () — набор команд вида «взять из регистра, положить в регистр» — либо SSA-форма (), в которой каждой переменной значение присваивается лишь один раз. Встречаются и преобразования дерева в дерево: так описывают, например, перестройку циклов.
Близкое к АСД представление — ориентированный ациклический граф выражений. Он строится теми же средствами, но одинаковые подвыражения представлены в нём одним общим узлом, к которому ведёт несколько рёбер. Это позволяет выявить повторяющиеся вычисления и выполнить их однократно.
Выполнение программы по дереву Программу можно выполнять и напрямую, рекурсивно обходя её дерево. Такой интерпретатор — простой и естественный способ реализовать язык. Но его традиционно считают и самым медленным: на каждом узле происходит вызов виртуального метода, а такие вызовы обходятся дорого. Чтобы ускорить выполнение, разработчики переходят к байт-коду — заранее подготовленной последовательности простых команд. За скорость платят негибким и трудным в сопровождении форматом.
Обойти это ограничение помогают самооптимизирующиеся интерпретаторы, которые меняют дерево прямо во время работы программы. Узел переписывается под те типы данных, которые на нём действительно встречаются, — и это даёт общий способ ускорять конструкции языков с динамической типизацией. Этот подход лёг в основу платформы Truffle для GraalVM. Сравнение 2023 года показало, что преимущество байт-кода не столь очевидно, как принято думать. Испытание проводили на системах метакомпиляции. В таких условиях интерпретаторы по дереву оказались сопоставимы с байт-кодовыми по скорости, а иногда и чуть быстрее их. Байт-код остаётся компактнее в памяти.
Другие применения
Средства разработки На дерево опираются инструменты, которым нужно понимать устройство кода, а не только его текст: линтеры, сообщающие об ошибках и нарушениях оформления, средства подсветки синтаксиса и навигации, средства автоматического форматирования. Для JavaScript сложился общепринятый формат такого дерева — спецификация ESTree; ей с рядом оговорённых отступлений следует анализатор Babel.
Требования к дереву в редакторе кода иные, чем в компиляторе. Разработчики tree-sitter формулируют их так: разбор должен быть достаточно быстрым, чтобы выполняться при каждом нажатии клавиши, и достаточно устойчивым, чтобы давать полезный результат даже при синтаксических ошибках. Той же устойчивости служит принятый в Roslyn приём: незавершённый или ошибочный код представляют особыми токенами — пропущенными () и отсутствующими (), — и дерево строится в любом случае.