пока b ≠ 0 : если a > b : a := a - b иначе : b := b - a вернуть aАбстрактное синтаксическое дерево ( AST ) — это структура данных, используемая в информатике для представления структуры программы или фрагмента кода. Это древовидное представление абстрактной синтаксической структуры текста (часто исходного кода ), написанного на формальном языке . Каждый узел дерева обозначает конструкцию, встречающуюся в тексте. Иногда его называют просто синтаксическим деревом .
Синтаксис является «абстрактным» в том смысле, что он не представляет каждую деталь, появляющуюся в реальном синтаксисе, а скорее только структурные или связанные с содержанием детали. Например, группирующие скобки подразумеваются в структуре дерева, поэтому их не обязательно представлять как отдельные узлы. Аналогично, синтаксическая конструкция, такая как оператор if-condition-then, может быть обозначена с помощью одного узла с тремя ветвями.
Это отличает абстрактные синтаксические деревья от конкретных синтаксических деревьев, традиционно называемых синтаксическими деревьями . Синтаксические деревья обычно строятся синтаксическим анализатором в процессе трансляции и компиляции исходного кода . После построения дополнительная информация добавляется в AST посредством последующей обработки, например, контекстного анализа .
Абстрактные синтаксические деревья также используются в системах анализа и преобразования программ .
Абстрактные синтаксические деревья — это структуры данных, широко используемые в компиляторах для представления структуры программного кода. AST обычно является результатом фазы синтаксического анализа компилятора. Он часто служит промежуточным представлением программы через несколько этапов, требуемых компилятором, и оказывает сильное влияние на конечный вывод компилятора.
AST имеет несколько свойств, которые помогают на дальнейших этапах процесса компиляции:
Языки часто неоднозначны по своей природе. Чтобы избежать этой неоднозначности, языки программирования часто определяются как контекстно-свободная грамматика (CFG). Однако часто существуют аспекты языков программирования, которые CFG не может выразить, но являются частью языка и документируются в его спецификации. Это детали, которые требуют контекста для определения их допустимости и поведения. Например, если язык позволяет объявлять новые типы, CFG не может предсказать имена таких типов или способ, которым они должны использоваться. Даже если язык имеет предопределенный набор типов, обеспечение надлежащего использования обычно требует некоторого контекста. Другим примером является утиная типизация , когда тип элемента может меняться в зависимости от контекста. Перегрузка операторов — еще один случай, когда правильное использование и конечная функция зависят от контекста.
Проектирование AST часто тесно связано с проектированием компилятора и его ожидаемыми функциями.
Основные требования включают в себя следующее:
Эти требования можно использовать при проектировании структуры данных для AST.
Некоторые операции всегда требуют двух элементов, например, два термина для сложения. Однако некоторые языковые конструкции требуют произвольно большого количества потомков, например, списки аргументов, передаваемые программам из командной оболочки . В результате AST, используемый для представления кода, написанного на таком языке, также должен быть достаточно гибким, чтобы обеспечить быстрое добавление неизвестного количества потомков.
Для поддержки проверки компилятором должна быть возможность депарсить AST в исходный код. Полученный исходный код должен быть достаточно похож на оригинал по внешнему виду и идентичен по исполнению после повторной компиляции. AST интенсивно используется во время семантического анализа , где компилятор проверяет правильность использования элементов программы и языка. Компилятор также генерирует таблицы символов на основе AST во время семантического анализа. Полный обход дерева позволяет проверить правильность программы.
После проверки корректности AST служит основой для генерации кода. AST часто используется для генерации промежуточного представления (IR), иногда называемого промежуточным языком , для генерации кода.
Дифференцирование AST, или для краткости древовидное дифференцирование, состоит из вычисления списка различий между двумя AST. [1] Этот список различий обычно называется скриптом редактирования. Скрипт редактирования напрямую ссылается на AST кода. Например, действие редактирования может привести к добавлению нового узла AST, представляющего функцию.
AST — это мощная абстракция для обнаружения клонов кода . [2]
