Skip to main content
Definition Website Computer and Technology

Abstract Syntax Tree

Subject: Computer and Technology noun /ˈæb.strækt ˈsɪn.tæks triː/ 1 definition

  1. Definition (noun)

    Entry #81 · Updated

    An Abstract Syntax Tree (AST) is a hierarchical, tree-structured representation of the syntactic structure of source code produced by a parser. Unlike a concrete syntax tree that preserves every punctuation mark, delimiter, and intermediate grammar rule from raw text, an AST omits surface formatting details such as grouping parentheses and semicolons to retain only the essential semantic constructs—such as expressions, statements, operators, and declarations—and their parent-child nesting. Because it captures program structure and operator precedence cleanly in memory, an AST serves as the primary intermediate representation for semantic analysis, type checking, linting, optimization, and code generation.

    Common Forms

    • Untyped AST: The initial syntax tree emitted directly by a parser, capturing structural constructs and source-location spans before identifier resolution or type checking.

    • Typed (Decorated) AST: An AST enriched during semantic analysis with resolved symbol bindings, scope information, and inferred or verified data types for downstream compilation passes.

    • Homogeneous AST: An implementation form in which every node shares a single uniform data structure distinguished by a kind tag and child list, simplifying generic tree traversals and serialization.

    • Heterogeneous AST: A strongly typed implementation form defining distinct node classes or algebraic variants for each language construct—such as IfStatement or BinaryExpression—to enforce structural validity.

    Example

    When a JavaScript toolchain such as Babel parses const total = (a + b) * 2;, it omits the semicolon and parenthesis tokens and constructs an AST in which a VariableDeclaration node wraps a multiplication BinaryExpression with an addition subtree (a + b) on the left and the literal 2 on the right. A linter or transpiler can then walk that tree directly to flag unused identifiers, down-level modern syntax, and generate updated source code without relying on fragile text-based regular expressions.