Перейти к содержанию

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

Материал из Википедии — свободной энциклопедии
Дерево с оператором цикла в корне; в левом поддереве условие «b ≠ 0», в правом — условный оператор с двумя присваиваниями и оператор возврата
Абстрактное синтаксическое дерево для приведённой ниже записи алгоритма Евклида:
while b ≠ 0:
   if a > b:
      a := a − b
   else:
      b := b − a
return a

Абстрактное синтаксическое дерево (АСД; англ. abstract syntax tree, AST) — представление программы в виде дерева. Им пользуются компиляторы, переводящие программу в машинный код, и другие средства обработки исходного кода. Каждый узел дерева обозначает конструкцию языка, а потомки узла — части этой конструкции[1]➤. Так, выражение a + b становится узлом «сложение», а его потомки — a и b[2][комм. 1].

Дерево называют абстрактным потому, что оно передаёт не саму запись программы, а её смысл. В нём нет узлов для скобок, точек с запятой и запятых, а также для тех правил грамматики, которые ничего не добавляют к содержанию[1]. Этим АСД отличается от дерева разбора[англ.] — дерева, которое воспроизводит разбор текста по правилам грамматики полностью[4]➤. Понятие абстрактного синтаксиса ввёл Джон Маккарти в 1962 году, предложив описывать конструкции языка независимо от того, какими знаками они записаны[5]➤.

Работать с деревом удобнее, чем со строкой текста: структура программы в нём задана явно, а к узлам можно добавлять сведения, полученные при анализе. Дерево строит синтаксический анализатор➤; затем по нему проверяют программу на ошибки, переводят её в другие промежуточные представления или сразу выполняют[4][6]➤. Вне компиляторов АСД используют статические анализаторы, средства поиска уязвимостей и рефакторинга, программы поиска повторяющегося кода и сравнения версий, а также применяют в машинном обучении на исходном коде➤.

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

[править | править код]
Дерево разбора: в корне список операторов, ниже узлы присваивания, выражения и отдельные листья для знаков «=» и «;»
Дерево разбора для фрагмента A = B + C*2; D = 1. Здесь свой узел получает каждое применённое правило грамматики, а каждая часть записи, включая точки с запятой, становится отдельным листом

Дерево разбора, или дерево конкретного синтаксиса, показывает, как текст программы выводится по правилам грамматики. В нём есть узел для каждого применённого правила и лист для каждого токена исходного текста, включая разделители[комм. 2]. Свои узлы получают даже те правила, которые лишь переименовывают одну конструкцию в другую. Абстрактное дерево всего этого не содержит: пунктуация и вспомогательные правила выражены самой формой дерева[4].

Проще всего разница видна на примере скобок. В выражении (a + b) * c скобки нужны только для того, чтобы задать порядок действий. В абстрактном дереве порядок задан положением узлов: узел сложения оказывается потомком узла умножения[2]. Отдельные узлы для скобок становятся не нужны[1].

Где именно провести границу между двумя видами деревьев, каждый разработчик решает сам, исходя из задач своего инструмента. Дерево Clang, компилятора языков Си и C++, близко и к тексту программы, и к формулировкам стандарта языка: в нём, в частности, сохранены скобки. Выражения, значение которых компилятор мог бы подсчитать заранее — например, 2 + 3, — тоже оставлены как есть. Этим в документации Clang объясняют, почему такое дерево удобно средствам рефакторинга[7].

Ещё дальше идёт платформа Roslyn: в неё входят компиляторы языков C# и Visual Basic от Microsoft, а построенное ими синтаксическое дерево она открывает другим программам. Это дерево «полной точности» (англ. full fidelity) хранит каждый элемент исходного текста, включая пробелы, комментарии и директивы препроцессора. Незначимые элементы объединены в так называемую тривию и привязаны к соседним токенам[комм. 3], поэтому по любому узлу можно точно восстановить соответствующий ему фрагмент текста[8]➤. Библиотека tree-sitter[англ.], применяемая в текстовых редакторах, строит именно дерево конкретного синтаксиса и обновляет его по мере правки файла, не разбирая файл заново целиком[9].

Понятие абстрактного синтаксиса

[править | править код]

Маккарти изложил это понятие в докладе на конгрессе ИФИП 1962 года. Он сравнил его с нормальной формой Бэкуса, которой пользовались в отчёте об Алголе[комм. 4]. Такая форма описывает язык синтетически: она объясняет, как программа собирается из частей. Для перевода программы нужно обратное — уметь разобрать её на части. Поэтому Маккарти предложил описание аналитическое и притом абстрактное, то есть не зависящее от того, какими знаками записана конструкция[5].

Для арифметических выражений Алгола Маккарти ввёл четыре предиката — проверки, отвечающие «да» или «нет». Предикаты isconst, isvar, issum и isprod сообщают, чем является выражение: константой, переменной, суммой или произведением. К ним Маккарти добавил функции addend, augend, mplier и mpcand, извлекающие из выражения его части. При таком описании безразлично, записана ли сумма как a+b, как +ab или как (PLUS A B): важно лишь, что сумму можно опознать и разобрать[5]. Впоследствии Маккарти считал эту работу первым употреблением понятия абстрактного синтаксиса[10].

Абстрактный синтаксис языка можно записать формально, а по этой записи — получить готовый код структур данных. Для этого в рамках проекта Zephyr, который совместно вели Принстонский университет и Виргинский университет, разработали язык ASDL (англ. Abstract Syntax Description Language). Описание на ASDL перечисляет виды узлов дерева и части каждого из них, а инструменты превращают такое описание в определения типов на C, C++, Java или ML. Для абстрактного синтаксиса ASDL играет ту же роль, что регулярные выражения — для лексической структуры языка, а контекстно-свободная грамматика — для синтаксической[11]. На ASDL, в частности, записана абстрактная грамматика Python; она доступна через стандартный модуль ast[12].

Устройство дерева

[править | править код]

Что хранится в узле

[править | править код]

Узел хранит вид конструкции и ссылки на потомков. Листья дополнительно содержат сведения о значении. Это либо сам литерал — записанное прямо в тексте число или строка, — либо ссылка на запись в таблице символов, перечне имён из программы[4]. Кроме того, узлы обычно помнят, какому месту исходного текста они соответствуют. Это нужно, чтобы выдавать понятные сообщения об ошибках и связывать результаты анализа с конкретной строкой файла. Так, режим -ast-dump в Clang показывает для каждого узла диапазон строк и столбцов[7], а анализатор Babel по запросу добавляет к узлам смещения в тексте[13].

Дробность узлов

[править | править код]

При проектировании дерева выбирают степень дробности узлов. Можно обойтись одним общим видом узла, различая конструкции значением поля, а можно завести отдельный вид для каждой конструкции языка. Например, для арифметических операций с двумя операндами первый путь даёт единственный узел «двухместная операция» с полем, где записан знак операции. Второй путь даёт отдельные классы AddBinary, SubtractBinary и так далее с общим предком Binary. Второй вариант предпочтителен, если с узлами связано поведение, а не только данные[4].

Как узлы описывают в разных языках

[править | править код]

Способ записи узлов зависит от языка, на котором написан сам инструмент. В функциональных языках дерево описывают алгебраическим типом данных: у такого типа столько разновидностей, сколько есть видов узлов, а функции над деревом определяют сопоставлением с образцом. Компилятор при этом сам указывает на необработанные виды узлов. В объектно-ориентированных языках узлы делают классами, производными от общего абстрактного предка, а выбор нужной обработки поручают полиморфизму: длинного ветвления по видам узлов не требуется[4].

Обход дерева

[править | править код]

Проверку типов, генерацию кода, подсчёт метрик и прочую работу над деревом обычно оформляют по схеме «Посетитель». Узлы при этом остаются простыми хранилищами данных, а каждый вид обработки выносится в отдельный объект-посетитель. Такое разделение применяют, когда одно дерево обрабатывают по-разному в нескольких местах. Если обработка всего одна, посетитель не нужен: её методы размещают прямо в узлах[4].

Построение дерева

[править | править код]

Строит дерево синтаксический анализатор — как написанный вручную, так и порождённый генератором вроде Yacc или ANTLR. Узлы, как правило, создаются снизу вверх, по мере того как анализатор распознаёт всё более крупные конструкции. При работе с генератором вызовы, создающие узлы, вставляют в секции семантических действий — фрагменты кода, которые срабатывают при распознавании соответствующего правила грамматики[4].

Формально это описывает синтаксически управляемая трансляция. Каждому нетерминалу грамматики — вспомогательному понятию вроде «выражения» или «оператора» — сопоставляют атрибут, значением которого служит узел дерева. Семантическое правило строит этот узел из узлов, полученных для символов правой части. Правила, ничего не добавляющие к содержанию, просто передают наверх узел одного из своих символов[1]. Общую теорию приписывания значений узлам дерева разработал Дональд Кнут в 1968 году. В его атрибутных грамматиках[англ.] одни атрибуты вычисляются по потомкам узла, другие — по его предкам; первые называют синтезируемыми, вторые — наследуемыми[14].

Возможен и другой порядок: сначала построить полное дерево разбора, а затем обойти его и удалить всё, что не входит в абстрактный синтаксис[комм. 5]. Существуют также генераторы, которые по краткому описанию структуры дерева сами порождают код для его представления и построения[4].

Применение в компиляторах и интерпретаторах

[править | править код]

Проверка программы

[править | править код]

В крупных системах трансляции смысловые проверки выполняют именно над деревом[4]. Семантический анализатор берёт дерево вместе с таблицей символов и выясняет, согласуется ли программа с определением языка. В частности, он сверяет типы операндов каждой операции с допустимыми и при необходимости вставляет в дерево узлы преобразования типов[комм. 6][15].

Переход к другим представлениям

[править | править код]

Промежуточные представления бывают двух видов. Древовидные — это дерево разбора и абстрактное синтаксическое дерево. Линейные лишены иерархии; самое известное из них — трёхадресный код, цепочка простейших шагов вроде сложения двух значений[3]. После проверок дерево служит основой для получения кода. Простейшие трансляторы обходят дерево и сразу выдают текст на целевом языке. В более сложных случаях дерево переводят в другое промежуточное представление. Это может быть язык передачи регистров (англ. register transfer language) — набор команд вида «взять из регистра, положить в регистр» — либо SSA-форма (англ. static single assignment), в которой каждой переменной значение присваивается лишь один раз. Встречаются и преобразования дерева в дерево: так описывают, например, перестройку циклов[4].

Близкое к АСД представление — ориентированный ациклический граф выражений. Он строится теми же средствами, но одинаковые подвыражения представлены в нём одним общим узлом, к которому ведёт несколько рёбер. Это позволяет выявить повторяющиеся вычисления и выполнить их однократно[16].

Выполнение программы по дереву

[править | править код]

Программу можно выполнять и напрямую, рекурсивно обходя её дерево. Такой интерпретатор — простой и естественный способ реализовать язык. Но его традиционно считают и самым медленным: на каждом узле происходит вызов виртуального метода, а такие вызовы обходятся дорого. Чтобы ускорить выполнение, разработчики переходят к байт-коду — заранее подготовленной последовательности простых команд. За скорость платят негибким и трудным в сопровождении форматом[6].

Обойти это ограничение помогают самооптимизирующиеся интерпретаторы, которые меняют дерево прямо во время работы программы. Узел переписывается под те типы данных, которые на нём действительно встречаются, — и это даёт общий способ ускорять конструкции языков с динамической типизацией. Этот подход лёг в основу платформы Truffle для GraalVM[6][17]. Сравнение 2023 года показало, что преимущество байт-кода не столь очевидно, как принято думать. Испытание проводили на системах метакомпиляции[комм. 7]. В таких условиях интерпретаторы по дереву оказались сопоставимы с байт-кодовыми по скорости, а иногда и чуть быстрее их. Байт-код остаётся компактнее в памяти[17].

Другие применения

[править | править код]

Средства разработки

[править | править код]

На дерево опираются инструменты, которым нужно понимать устройство кода, а не только его текст: линтеры, сообщающие об ошибках и нарушениях оформления, средства подсветки синтаксиса и навигации, средства автоматического форматирования. Для JavaScript сложился общепринятый формат такого дерева — спецификация ESTree[18]; ей с рядом оговорённых отступлений следует анализатор Babel[13].

Требования к дереву в редакторе кода иные, чем в компиляторе. Разработчики tree-sitter формулируют их так: разбор должен быть достаточно быстрым, чтобы выполняться при каждом нажатии клавиши, и достаточно устойчивым, чтобы давать полезный результат даже при синтаксических ошибках[9]. Той же устойчивости служит принятый в Roslyn приём: незавершённый или ошибочный код представляют особыми токенами — пропущенными (англ. skipped) и отсутствующими (англ. missing)[комм. 8], — и дерево строится в любом случае[8].

Рефакторингом называют перестройку кода, не меняющую его поведения. Автоматические средства рефакторинга выполняют её как преобразование дерева в дерево, после чего изменённое дерево выводят обратно в текст программы[4]. Чтобы при этом не потерялись комментарии и расстановка отступов, дерево должно хранить и те элементы текста, которые для компилятора незначимы. Именно этим объясняется устройство деревьев полной точности в Roslyn[8].

Поиск повторов и сравнение версий

[править | править код]

Повторяющийся код составляет 5—10 % исходного кода крупных программных систем, и его выявление снижает стоимость сопровождения. Метод, предложенный Айрой Бакстером и соавторами в 1998 году, ищет по поддеревьям как точные повторы, так и приблизительные. Поскольку метод опирается на устройство программы, а не на её текст, найденные повторы можно устранять механически, вынося общий фрагмент в отдельную процедуру[19]. Позже для той же задачи стали применять суффиксные деревья, построенные по вытянутому в строку представлению АСД[20].

Частичное сопоставление деревьев двух версий программы показывает, как исходный код меняется со временем[21]. Оно же позволяет выделять мелкие изменения там, где обычное построчное сравнение слишком грубо[22]. Алгоритм GumTree вычисляет редакционное предписание (англ. edit script) — последовательность действий над узлами дерева, переводящую одну версию в другую. Текстовое сравнение видит лишь добавления и удаления, а GumTree распознаёт ещё и перемещения кода, поэтому описание правки выходит ближе к замыслу разработчика[23].

Анализ защищённости

[править | править код]

При поиске уязвимостей дерево служит одним из источников сведений об устройстве программы. Метод обобщённой экстраполяции уязвимостей выявляет в кодовой базе места, синтаксически похожие на уже известный уязвимый участок[24]. Более общее представление — граф свойств кода (англ. code property graph) — сводит в единую структуру данных абстрактное синтаксическое дерево, граф потока управления и граф зависимостей программы[англ.]. Обходами такого графа записывают образцы типовых уязвимостей, в том числе переполнений буфера и целочисленных переполнений, и ищут такие места в больших массивах исходного кода[25].

Машинное обучение на коде

[править | править код]

Модели, обучаемые на исходном коде, берут из дерева сведения об устройстве программы — то, что теряется, если считать код просто последовательностью слов. В модели code2vec фрагмент кода раскладывают на пути в его дереве: путь — это пара листьев и цепочка узлов, которая их соединяет. Затем пути сворачивают в один вектор постоянной длины, причём вес каждого пути модель подбирает сама при обучении. По этому вектору предсказывают свойства фрагмента, например имя метода[26].

См. также

[править | править код]

Примечания

[править | править код]

Комментарии

  1. ↑ В литературе по компиляторам то же дерево часто называют просто синтаксическим деревом. В русском переводе книги Ахо и соавторов оба названия прямо объявлены синонимами[3].
  2. ↑ Токен — отдельная единица текста программы, выделенная при первичном разборе: имя, число, знак операции, скобка или точка с запятой.
  3. ↑ Тривия не входит в число потомков узла. Токену достаётся вся тривия, идущая за ним до конца строки; тривию в самом начале файла забирает первый токен[8].
  4. ↑ Так эту нотацию называет сам Маккарти вслед за отчётом об Алголе[5]; ныне за ней закрепилось название форма Бэкуса — Наура.
  5. ↑ Дерево не всегда собирают целиком. Обычно компилятор порождает трёхадресный код➤ в тот момент, когда анализатор лишь «делает вид», что строит дерево: узлы и их атрибуты хранятся, пока нужны, а затем уничтожаются[3].
  6. ↑ Такие проверки называют статическими: «статический» здесь означает «выполняемый компилятором», а не во время работы программы[3].
  7. ↑ В таких системах — например, RPython и GraalVM — JIT-компилятор и сборщик мусора предоставляются независимо от конкретного языка, поэтому реализация языка сводится к написанию одного интерпретатора[17].
  8. ↑ Пропущенный токен — лишний фрагмент текста, который анализатор не сумел никуда пристроить и отложил в сторону, чтобы продолжить разбор. Отсутствующий — противоположный случай: такого фрагмента в тексте нет, но грамматика его требует, и анализатор ставит на его место пустой токен[8].

Источники

  1. 1 2 3 4 Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Разд. 5.3.1. Построение синтаксических деревьев // Компиляторы: принципы, технологии и инструментарий. — 2-е изд. — М. : Вильямс, 2008. — ISBN 978-5-8459-1349-4.
  2. 1 2 Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Разд. 1.2.2. Синтаксический анализ // Компиляторы: принципы, технологии и инструментарий. — 2-е изд. — М. : Вильямс, 2008. — ISBN 978-5-8459-1349-4.
  3. 1 2 3 4 Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Разд. 2.8.1. Два вида промежуточных представлений // Компиляторы: принципы, технологии и инструментарий. — 2-е изд. — М. : Вильямс, 2008. — С. 136—137. — ISBN 978-5-8459-1349-4.
  4. 1 2 3 4 5 6 7 8 9 10 11 12 Jones J. (2003). Abstract Syntax Tree Implementation Idioms (PDF). Proceedings of the 10th Conference on Pattern Languages of Programs (PLoP 2003) (англ.).
  5. 1 2 3 4 McCarthy J. (1963). Towards a Mathematical Science of Computation (PDF). In Popplewell C. M. (ed.). Information Processing 1962: Proceedings of IFIP Congress 62 (англ.). Amsterdam: North-Holland. pp. 21—28.
  6. 1 2 3 Würthinger T.; Wöß A.; Stadler L.; Duboscq G.; Simon D.; Wimmer C. (2012). Self-Optimizing AST Interpreters. Proceedings of the 8th Symposium on Dynamic Languages (DLS ’12) (англ.). pp. 73—82. doi:10.1145/2384577.2384587.
  7. 1 2 Introduction to the Clang AST (англ.). Clang documentation. LLVM Project. Дата обращения: 11 августа 2026. Архивировано 6 августа 2026 года.
  8. 1 2 3 4 5 Use the .NET Compiler Platform SDK syntax model (англ.). Microsoft. Дата обращения: 11 августа 2026. Архивировано 11 августа 2026 года.
  9. 1 2 tree-sitter — An incremental parsing system for programming tools (англ.). GitHub. Дата обращения: 11 августа 2026.
  10. ↑ John McCarthy — Papers (англ.). Formal Reasoning Group, Stanford University. Дата обращения: 11 августа 2026. Архивировано 30 июля 2026 года.
  11. ↑ Wang D. C.; Appel A. W.; Korn J. L.; Serra C. S. (1997). The Zephyr Abstract Syntax Description Language (PDF). Proceedings of the Conference on Domain-Specific Languages (DSL ’97) (англ.). USENIX Association. pp. 213—227.
  12. ↑ ast — Abstract Syntax Trees (англ.). Python 3 documentation. Python Software Foundation. Дата обращения: 11 августа 2026.
  13. 1 2 @babel/parser (англ.). Babel documentation. Дата обращения: 11 августа 2026.
  14. ↑ Knuth D. E. (1968). Semantics of context-free languages. Mathematical Systems Theory (англ.). 2 (2): 127—145. doi:10.1007/BF01692511.
  15. ↑ Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Разд. 1.2.3. Семантический анализ // Компиляторы: принципы, технологии и инструментарий. — 2-е изд. — М. : Вильямс, 2008. — ISBN 978-5-8459-1349-4.
  16. ↑ Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Разд. 6.1.1. Ориентированные ациклические графы для выражений // Компиляторы: принципы, технологии и инструментарий. — 2-е изд. — М. : Вильямс, 2008. — ISBN 978-5-8459-1349-4.
  17. 1 2 3 Larose O.; Kaleba S.; Burchell H.; Marr S. (2023). AST vs. Bytecode: Interpreters in the Age of Meta-Compilation (PDF). Proceedings of the ACM on Programming Languages (англ.). 7 (OOPSLA2): 318—346. doi:10.1145/3622808.
  18. ↑ ESTree Specification (англ.). GitHub. Дата обращения: 11 августа 2026. Архивировано 30 июля 2026 года.
  19. ↑ Baxter I. D.; Yahin A.; Moura L.; Sant’Anna M.; Bier L. (1998). Clone Detection Using Abstract Syntax Trees (PDF). Proceedings of the International Conference on Software Maintenance (ICSM ’98) (англ.). IEEE. pp. 368—377.
  20. ↑ Koschke R.; Falke R.; Frenzel P. (2006). Clone Detection Using Abstract Syntax Suffix Trees. 13th Working Conference on Reverse Engineering (WCRE ’06) (англ.). IEEE. pp. 253—262. doi:10.1109/WCRE.2006.18.
  21. ↑ Neamtiu I.; Foster J. S.; Hicks M. (2005). Understanding Source Code Evolution Using Abstract Syntax Tree Matching. Proceedings of the 2005 International Workshop on Mining Software Repositories (MSR ’05) (англ.). pp. 1—5. doi:10.1145/1083142.1083143.
  22. ↑ Fluri B.; Würsch M.; Pinzger M.; Gall H. C. (2007). Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction. IEEE Transactions on Software Engineering (англ.). 33 (11): 725—743. doi:10.1109/TSE.2007.70731.
  23. ↑ Falleri J.-R.; Morandat F.; Blanc X.; Martinez M.; Monperrus M. (2014). Fine-grained and Accurate Source Code Differencing. Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering (ASE ’14) (англ.). pp. 313—324. doi:10.1145/2642937.2642982.
  24. ↑ Yamaguchi F.; Lottmann M.; Rieck K. (2012). Generalized Vulnerability Extrapolation Using Abstract Syntax Trees. Proceedings of the 28th Annual Computer Security Applications Conference (ACSAC ’12) (англ.). pp. 359—368. doi:10.1145/2420950.2421003.
  25. ↑ Yamaguchi F.; Golde N.; Arp D.; Rieck K. (2014). Modeling and Discovering Vulnerabilities with Code Property Graphs. 2014 IEEE Symposium on Security and Privacy (англ.). pp. 590—604. doi:10.1109/SP.2014.44.
  26. ↑ Alon U.; Zilberstein M.; Levy O.; Yahav E. (2019). code2vec: Learning Distributed Representations of Code. Proceedings of the ACM on Programming Languages (англ.). 3 (POPL): 1—29. doi:10.1145/3290353.

Литература

[править | править код]
  • Ахо А. В., Лам М. С., Сети Р., Ульман Дж. Д. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools / пер. с англ. под ред. И. В. Красикова. — 2-е изд.. — М.: Вильямс, 2008. — 1184 с. — ISBN 978-5-8459-1349-4.
  • Appel A. W., Palsberg J. Modern Compiler Implementation in Java (англ.). — 2nd ed.. — Cambridge: Cambridge University Press, 2002. — 512 p. — ISBN 0-521-82060-X.
  • Grune D., van Reeuwijk K., Bal H. E., Jacobs C. J. H., Langendoen K. Modern Compiler Design (англ.). — 2nd ed.. — New York: Springer, 2012. — 843 p. — ISBN 978-1-4614-4698-9.
Источник — https://ru.wikipedia.org/w/index.php?title=Абстрактное_синтаксическое_дерево&oldid=154921810