Введение
Деревообразное представление абстрактной синтаксической структуры исходного кода, деревья, используемые в лингвистике. Абстрактное синтаксическое дерево (AST) — это структура данных, используемая в информатике для представления структуры программы или фрагмента кода. Это древовидное представление абстрактной синтаксической структуры текста (часто исходного кода), написанного на формальном языке. Каждый узел дерева обозначает конструкцию, встречающуюся в тексте. Иногда его называют просто синтаксическим деревом. Синтаксис является "абстрактным" в том смысле, что он не отражает все детали реального синтаксиса, а лишь структурные или содержательные детали. Например, группирующие скобки подразумеваются структурой дерева и поэтому не должны представляться отдельными узлами. Аналогично, синтаксическая конструкция, такая как "if condition then statement", может быть представлена одним узлом с тремя ветвями. Это отличает абстрактные синтаксические деревья от конкретных синтаксических деревьев, традиционно называемых деревьями разбора. Деревья разбора обычно строятся парсером в процессе перевода и компиляции исходного кода. После построения в AST добавляется дополнительная информация посредством последующей обработки, например, контекстного анализа. Абстрактные синтаксические деревья также используются в анализе программ и системах преобразования программ.
the trees used in linguistics
An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring in the text. It is sometimes called just a syntax tree. The syntax is "abstract" in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content related details. For instance, grouping parentheses are implicit in the tree structure, so these do not have to be represented as separate nodes. Likewise, a syntactic construct like an if condition then statement may be denoted by means of a single node with three branches. This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees. Parse trees are typically built by a parser during the source code translation and compiling process. Once built, additional information is added to the AST by means of subsequent processing, e. g., contextual analysis. Abstract syntax trees are also used in program analysis and program transformation systems.
Применение в компиляторах
Абстрактные синтаксические деревья — это структуры данных, широко используемые в компиляторах для представления структуры исходного кода программы. AST обычно является результатом этапа синтаксического анализа компилятора. Оно часто служит промежуточным представлением программы на протяжении нескольких этапов, необходимых компилятору, и оказывает значительное влияние на конечный результат компиляции.
Различение AST
AST дифференцирование, или, сокращенно, дифференцирование деревьев, заключается в вычислении списка различий между двумя AST. Этот список различий обычно называется сценарием изменений. Сценарий изменений напрямую относится к AST кода. Например, операция изменения может привести к добавлению нового узла AST, представляющего функцию.
Обнаружение клона
AST — мощная абстракция для обнаружения клонов кода.