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

О деревьях, используемых в лингвистике, см. дерево разбора .

Абстрактное синтаксическое дерево для следующего кода алгоритма Евклида :

while b ≠ 0:
    if a > b:
        a := a - b
    else:
        b := b - a
return a

Абстрактное синтаксическое дерево ( AST ) — это структура данных, используемая в информатике для представления структуры программы или фрагмента кода. Это древовидное представление абстрактной синтаксической структуры текста (часто исходного кода ), написанного на формальном языке . Каждый узел дерева обозначает конструкцию, встречающуюся в тексте. Иногда его называют просто синтаксическим деревом .

Синтаксис является «абстрактным» в том смысле, что он не представляет все детали реального синтаксиса, а лишь структурные или связанные с содержанием детали. Например, группирующие круглые скобки неявно присутствуют в древовидной структуре, поэтому их не обязательно представлять как отдельные узлы. Аналогично, синтаксическая конструкция, такая как оператор if-condition-then, может быть обозначена посредством одного узла с тремя ветвями.

Это отличает абстрактные синтаксические деревья от конкретных синтаксических деревьев, традиционно называемых деревьями синтаксического анализа . Деревья синтаксического анализа обычно создаются синтаксическим анализатором в процессе трансляции и компиляции исходного кода . После построения в AST добавляется дополнительная информация посредством последующей обработки, например контекстного анализа .

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

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

Абстрактные синтаксические деревья — это структуры данных , широко используемые в компиляторах для представления структуры программного кода. AST обычно является результатом фазы синтаксического анализа компилятора. Он часто служит промежуточным представлением программы на нескольких этапах, необходимых компилятору, и оказывает сильное влияние на конечный результат компилятора.

Мотивация

AST имеет несколько свойств, которые помогают на дальнейших этапах процесса компиляции:

• AST можно редактировать и расширять, добавляя такую ​​информацию, как свойства и аннотации для каждого содержащегося в нем элемента. Такое редактирование и аннотирование невозможно с исходным кодом программы, поскольку это влечет за собой его изменение.
• По сравнению с исходным кодом AST не содержит несущественных знаков препинания и разделителей (фигурные скобки, точки с запятой, круглые скобки и т. д.).
• AST обычно содержит дополнительную информацию о программе из-за последовательных этапов анализа компилятора. Например, он может хранить позицию каждого элемента в исходном коде, позволяя компилятору печатать полезные сообщения об ошибках.

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

Дизайн

Проектирование AST часто тесно связано с проектированием компилятора и его ожидаемыми функциями.

Основные требования включают следующее:

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

Эти требования можно использовать для разработки структуры данных для AST.

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

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

После проверки правильности AST служит основой для генерации кода. AST часто используется для создания промежуточного представления (IR), иногда называемого промежуточным языком , для генерации кода.

Другое использование

Разница AST

Разность AST или разность коротких деревьев состоит из вычисления списка различий между двумя AST. Этот список различий обычно называется сценарием редактирования. Сценарий редактирования напрямую ссылается на AST кода. Например, действие редактирования может привести к добавлению нового узла AST, представляющего функцию.

Обнаружение клонов

AST — это мощная абстракция для обнаружения клонов кода .

См. также

• Абстрактный семантический граф (ASG), также называемый графом терминов.
• Составной узор
• Граф потока управления
• Ориентированный ациклический граф (DAG)
• Объектная модель документа (DOM)
• Дерево выражений
• Расширенная форма Бэкуса – Наура
• Lisp — семейство языков, написанных в виде деревьев, с макросами для управления деревьями кода.
• Дерево разбора , также известное как конкретное синтаксическое дерево.
• Дерево семантического разрешения (SRT)
• Алгоритм сортировочной станции
• Таблица символов
• ДеревоDL
• Интерпретаторы абстрактного синтаксического дерева

Дальнейшее чтение

• Джонс, Джоэл. «Идиомы реализации абстрактного синтаксического дерева» (PDF) . (обзор реализации AST в различных языковых семьях)
• Нямтиу, Юлиан; Фостер, Джеффри С.; Хикс, Майкл (17 мая 2005 г.). Понимание эволюции исходного кода с использованием сопоставления абстрактного синтаксического дерева . МСР'05. Сент-Луис, Миссури: ACM. CiteSeerX   10.1.1.88.5815 .
• Вюрш, Михаэль. Улучшение обнаружения изменений исходного кода на основе абстрактного синтаксического дерева (дипломная работа).
• Лукас, Джейсон (16 августа 2006 г.). «Мысли об абстрактном синтаксическом дереве Visual C++ (AST)» .

Внешние ссылки

• AST View : плагин Eclipse для визуализации дерева Java. абстрактного синтаксиса
• «Абстрактное синтаксическое дерево и манипулирование Java-кодом в Eclipse IDE» . eclipse.org .
• «Представление CAST» . cs.utah.edu .
• eli project : Разбор абстрактного синтаксического дерева
• «Стандарт метамодели абстрактного синтаксического дерева» (PDF) .
• «Модернизация на основе архитектуры — ADM: метамоделирование абстрактного синтаксического дерева — ASTM» . ( стандарт OMG ).
• JavaParser : библиотека JavaParser предоставляет вам абстрактное синтаксическое дерево вашего Java-кода. Структура AST позволяет вам легко и программно работать с кодом Java.
• Spoon : библиотека для анализа, преобразования, переписывания и передачи исходного кода Java. Он анализирует исходные файлы для создания хорошо продуманного AST с мощным API анализа и преобразования.
• AST Explorer : веб-сайт, помогающий визуализировать AST на нескольких популярных языках, таких как Go, Python, Java и JavaScript.