19/2/26, 13:59 Abstract syntax tree - Wikipedia
Abstract syntax tree
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. An abstract syntax tree for the following code for the Euclidean
algorithm:
This distinguishes abstract syntax trees
from concrete syntax trees, traditionally while b != 0:
if a > b:
designated parse trees. Parse trees are a := a - b
typically built by a parser during the else:
b := b - a
source code translation and compiling return a
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.
[Link] 1/5
19/2/26, 13:59 Abstract syntax tree - Wikipedia
Application in compilers
Abstract syntax trees are data structures widely used in compilers to represent the structure of
program code. An AST is usually the result of the syntax analysis phase of a compiler. It often serves
as an intermediate representation of the program through several stages that the compiler requires,
and has a strong affect on the final output of the compiler.
Motivation
An AST has several properties that aid in the additional steps of the compilation process:
An AST can be edited and enhanced with information such as properties and annotations for
every element it contains. Such editing and annotation is impossible with the source code of a
program, since it would imply changing it.
Compared to the source code, an AST does not include nonessential punctuation and delimiters
(braces, semicolons, parentheses, etc.).
An AST usually contains extra information about the program, due to the consecutive stages of
analysis by the compiler. For example, it may store the position of each element in the source
code, allowing the compiler to print useful error messages.
Languages are often ambiguous by nature. In order to avoid this ambiguity, programming languages
are often specified as a context-free grammar (CFG). However, there are often aspects of
programming languages that a CFG can't express, but are part of the language and are documented in
its specification. These are details that require a context to determine their validity and behavior. For
example, if a language allows new types to be declared, a CFG cannot predict the names of such types
nor the way in which they should be used. Even if a language has a predefined set of types, enforcing
proper usage usually requires some context. Another example is duck typing, where the type of an
element can change depending on context. Operator overloading is yet another case where correct
usage and final function are context-dependent.
Design
The design of an AST is often closely linked with the design of a compiler and its expected features.
Core requirements include the following:
Variable types must be preserved, as well as the location of each declaration in source code.
The order of executable statements must be explicitly represented and well defined.
Left and right components of binary operations must be stored and correctly identified.
Identifiers and their assigned values must be stored for assignment statements.
These requirements can be used to design the data structure for the AST.
Some operations will always require two elements, such as the two terms for addition. However, some
language constructs require an arbitrarily large number of children, such as argument lists passed to
programs from the command shell. As a result, an AST used to represent code written in such a
language has to also be flexible enough to allow for the quick addition of an unknown quantity of
children.
[Link] 2/5
19/2/26, 13:59 Abstract syntax tree - Wikipedia
To support compiler verification it should be possible to unparse an AST into source code form. The
source code produced should be sufficiently similar to the original in appearance and identical in
execution, upon recompilation. The AST is used intensively during semantic analysis, where the
compiler checks for correct usage of the elements of the program and the language. The compiler also
generates symbol tables based on the AST during semantic analysis. A complete traversal of the tree
allows verification of the correctness of the program.
After verifying correctness, the AST serves as the base for code generation. The AST is often used to
generate an intermediate representation (IR), sometimes called an intermediate language, for the
code generation.
Other usages
AST differencing
AST differencing, or for short tree differencing, consists of computing the list of differences between
two ASTs.[1] This list of differences is typically called an edit script. The edit script directly refers to
the AST of the code. For instance, an edit action may result in the addition of a new AST node
representing a function.
Clone detection
An AST is a powerful abstraction to perform code clone detection.[2]
Definition
Arities
Let be a set of sorts, an arity is a tuple , for , also written as
. More precisely, .
Let be an -indexed family of disjoint sets of operators. If is an
operator arity we say that has sort and has arguments of sorts .
ASTs
Fix be a finite set of sorts, and an -indexed family of disjoint sets of operators. Let
be an -indexed family of disjoint sets of variables. The family of
abstract syntax trees, or ASTs, is the smallest -indexed family of disjoint sets closed under the
following conditions:
1. Variables are ASTs: if , then .
[Link] 3/5
19/2/26, 13:59 Abstract syntax tree - Wikipedia
2. Operators combine ASTs: If is an operator of arity , and for all
, then .
See also
Abstract semantic graph (ASG), also called term graph
Composite pattern
Control-flow graph
Directed acyclic graph (DAG)
Document Object Model (DOM)
Expression tree
Extended Backus–Naur form
Lisp, a family of languages written in trees, with macros to manipulate code trees
Parse tree, also known as concrete syntax tree
Semantic resolution tree (SRT)
Shunting-yard algorithm
Syntax (programming languages)
Symbol table
TreeDL
Abstract Syntax Tree Interpreters
References
1. Fluri, Beat; Wursch, Michael; PInzger, Martin; Gall, Harald (2007). "Change Distilling:Tree
Differencing for Fine-Grained Source Code Change Extraction" ([Link]
7.70731). IEEE Transactions on Software Engineering. 33 (11): 725–743.
doi:10.1109/tse.2007.70731 ([Link] ISSN 0098-5589 (http
s://[Link]/issn/0098-5589). S2CID 13659557 ([Link]
ID:13659557).
2. Koschke, Rainer; Falke, Raimar; Frenzel, Pierre (2006). "Clone Detection Using Abstract Syntax
Suffix Trees" ([Link] 2006 13th Working Conference on
Reverse Engineering. IEEE. pp. 253–262. doi:10.1109/wcre.2006.18 ([Link]
wcre.2006.18). ISBN 0-7695-2719-1. S2CID 6985484 ([Link]
985484).
Further reading
Jones, Joel. "Abstract Syntax Tree Implementation Idioms" ([Link]
094334/[Link] (PDF). Archived
from the original ([Link]
(PDF) on 21 July 2024. Retrieved 9 November 2011. (overview of AST implementation in various
language families)
Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (May 17, 2005). Understanding Source Code
Evolution Using Abstract Syntax Tree Matching. MSR'05. Saint Louis, Missouri: ACM.
CiteSeerX [Link].5815 ([Link]
[Link] 4/5
19/2/26, 13:59 Abstract syntax tree - Wikipedia
Würsch, Michael. Improving Abstract Syntax Tree based Source Code Change Detection ([Link]
[Link]/seal/research/tools/archive/[Link]) (Diploma thesis).
Lucas, Jason (16 August 2006). "Thoughts on the Visual C++ Abstract Syntax Tree (AST)" (https://
[Link]/cppblog/thoughts-on-the-visual-c-abstract-syntax-tree-ast/).
Robert Harper (2016). Practical Foundations for Programming Languages ([Link]
u/~rwh/pfpl/) (Second Edition). Cambridge University Press.
External links
AST View ([Link] an Eclipse plugin to visualize a Java
abstract syntax tree
"Abstract Syntax Tree and Java Code Manipulation in the Eclipse IDE" ([Link]
cles/Article-JavaCodeManipulation_AST/[Link]). [Link].
"CAST representation" ([Link]
[Link].
eli project ([Link] Abstract Syntax Tree
Unparsing
"Architecture‑Driven Modernization — ADM: Abstract Syntax Tree Metamodeling — ASTM" (http://
[Link]/spec/ASTM/). (OMG standard).
JavaParser ([Link] The JavaParser library provides you with an Abstract Syntax
Tree of your Java code. The AST structure then allows you to work with your Java code in an easy
programmatic way.
Spoon ([Link] A library to analyze, transform, rewrite, and transpile
Java source code. It parses source files to build a well-designed AST with powerful analysis and
transformation API.
AST Explorer ([Link] A website to help visualize ASTs in several popular
languages such as Go, Python, Java, and JavaScript.
Retrieved from "[Link]
[Link] 5/5