Abstract syntax tree

For the trees used in linguistics, see parse tree.

An abstract syntax tree for the following code for the Euclidean algorithm:

while b != 0:
    if a > b:
        a := a - b
    else:
        b := b - a
return a

An abstract syntax tree (AST) is a tree data structure used in computer science to represent 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 simply a syntax tree.

The syntax is "abstract" in the sense that it does not represent every detail of the concrete syntax, but instead represents the essential structural information of the text. For example, grouping parentheses need not be represented as separate nodes because their effect is implicit in the tree structure. Similarly, punctuation and delimiters such as braces, semicolons, and parentheses may be omitted from an AST.

This distinguishes an abstract syntax tree from a concrete syntax tree, traditionally called a parse tree. During syntax analysis, a parser may construct an AST representing the syntactic structure of the input program. The AST can then serve as an intermediate representation for subsequent compiler phases, which may use information in the AST, annotate it with additional information, or transform it.

Abstract syntax trees are also used in program analysis and program transformation systems.