Abstract syntax tree
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (February 2013) |
while b ≠ 0:
if a > b:
a := a - b
else:
b := b - a
return a
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.
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 impact on the final output of the compiler.
Motivation
An AST has several properties that aid the further 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 inessential 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.
ASTs are needed because of the inherent nature of programming languages and their documentation. 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 behaviour. 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 quick addition of an unknown quantity of children.
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.
type "Program"
start 0
end 831
body
0
type "ExpressionStatement"
start 0
end 140
expression
type "CallExpression"
start 0
end 139
callee
type "ArrowFunctionExpression"
start 2
end 135
id null
expression false
generator false
async false
params []
body
type "BlockStatement"
start 8
end 135
body
0
type "VariableDeclaration"
start 14
end 64
declarations […]
kind "let"
1
type "ExpressionStatement"
start 69
end 114
expression {…}
2
type "ExpressionStatement"
start 119
end 133
expression {…}
arguments []
optional false
1
type "FunctionDeclaration"
start 143
end 203
id
type "Identifier"
start 152
end 156
name "l33t"
expression false
generator false
async false
params []
body
type "BlockStatement"
start 159
end 203
body
0
type "ExpressionStatement"
start 165
end 201
expression
type "CallExpression"
start 165
end 201
callee
type "MemberExpression"
start 165
end 176
object {…}
property {…}
computed false
optional false
arguments
0 {…}
optional false
2
type "FunctionDeclaration"
start 208
end 783
id
type "Identifier"
start 217
end 227
name "gen_sensor"
expression false
generator false
async false
params []
body
type "BlockStatement"
start 230
end 783
body
0
type "VariableDeclaration"
start 236
end 271
declarations
0
type "VariableDeclarator"
start 240
end 271
id {…}
init {…}
kind "let"
1
type "IfStatement"
start 276
end 325
test
type "BinaryExpression"
start 280
end 298
left
type "AssignmentExpression"
start 281
end 291
operator ">>="
left {…}
right {…}
operator "=="
right
type "Literal"
start 296
end 298
value 20
raw "20"
consequent
type "BlockStatement"
start 300
end 325
body
0 {…}
alternate null
2
type "VariableDeclaration"
start 331
end 761
declarations
0
type "VariableDeclarator"
start 335
end 761
id {…}
init {…}
kind "let"
3
type "ReturnStatement"
start 767
end 780
argument
type "Identifier"
start 774
end 780
name "sensor"
3
type "VariableDeclaration"
start 784
end 809
declarations
0
type "VariableDeclarator"
start 788
end 809
id
type "Identifier"
start 788
end 794
name "sensor"
init
type "CallExpression"
start 797
end 809
callee
type "Identifier"
start 797
end 807
name "gen_sensor"
arguments []
optional false
kind "let"
4
type "ExpressionStatement"
start 811
end 830
expression
type "CallExpression"
start 811
end 830
callee
type "MemberExpression"
start 811
end 822
object
type "Identifier"
start 811
end 818
name "console"
property
type "Identifier"
start 819
end 822
name "log"
computed false
optional false
arguments
0
type "Identifier"
start 823
end 829
name "sensor"
optional false
5
type "jaajajajajajajajajajajajaj"
sourceType "module"
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
- Symbol table
- TreeDL
- Abstract Syntax Tree Interpreters
References
- ^ Fluri, Beat; Wursch, Michael; PInzger, Martin; Gall, Harald (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. ISSN 0098-5589. S2CID 13659557.
Further reading
- Jones, Joel. "Abstract Syntax Tree Implementation Idioms" (PDF). (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 10.1.1.88.5815.
- Würsch, Michael. Improving Abstract Syntax Tree based Source Code Change Detection (Diploma thesis).
- Lucas, Jason (16 August 2006). "Thoughts on the Visual C++ Abstract Syntax Tree (AST)".
External links
- AST View: an Eclipse plugin to visualize a Java abstract syntax tree
- "Abstract Syntax Tree and Java Code Manipulation in the Eclipse IDE". eclipse.org.
- "CAST representation". cs.utah.edu.
- eli project: Abstract Syntax Tree Unparsing
- "Abstract Syntax Tree Metamodel Standard" (PDF).
- "Architecture‑Driven Modernization — ADM: Abstract Syntax Tree Metamodeling — ASTM". (OMG standard).
- JavaParser: 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: 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: A website to help visualize ASTs in several popular languages such as Go, Python, Java, and JavaScript.
| Authority control databases: National |
|---|
