Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Abstract syntax tree
Tree representation of the abstract syntactic structure of source code

An abstract syntax tree (AST) is a tree data structure used in computer science to represent the abstract syntactic structure of source code written in a formal language. Unlike concrete syntax trees or parse trees, which are generated by a parser during compiling, ASTs omit certain syntactic details such as grouping parentheses, focusing instead on the program’s structural or content-related constructs. ASTs are enriched through processes like contextual analysis and play a crucial role in program analysis and program transformation, helping to simplify code manipulation and compilation tasks.

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Abstract syntax tree yet.
We don't have any PDF documents related to Abstract syntax tree yet.
We don't have any Books related to Abstract syntax tree yet.
We don't have any archived web articles related to Abstract syntax tree yet.

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.

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.

Clone detection

An AST is a powerful abstraction to perform code clone detection.2

See also

Further reading

Wikimedia Commons has media related to Abstract syntax trees.

References

  1. 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. https://dx.doi.org/10.1109/tse.2007.70731 ↩

  2. Koschke, Rainer; Falke, Raimar; Frenzel, Pierre (2006). "Clone Detection Using Abstract Syntax Suffix Trees". 2006 13th Working Conference on Reverse Engineering. IEEE. pp. 253–262. doi:10.1109/wcre.2006.18. ISBN 0-7695-2719-1. S2CID 6985484. 0-7695-2719-1 ↩