Syntax Trees

Expression: 3 + (5 * 2)

Animation StatusStep 0 / 0

Click 'Evaluate AST' to evaluate: 3 + (5 * 2)

What are Syntax Trees?

An Abstract Syntax Tree (AST), or just Syntax Tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code.

ASTs are widely used in compilers to check code for accuracy (syntax analysis) and to convert the code into machine language or intermediate code (code generation). They are "abstract" because they do not represent every detail appearing in the real syntax, but rather just the structural or content-related details.

Visual Example

An Abstract Syntax Tree for the expression: 3 + (5 * 2)

How It Works in Compilers

1. Lexical Analysis

Source code is converted into a stream of tokens. For example, 3 + 5 becomes tokens: NUMBER(3), PLUS, NUMBER(5).

2. Syntax Analysis (Parsing)

The parser takes the tokens and arranges them into an Abstract Syntax Tree based on the rules of the programming language's grammar.

3. Evaluation or Compilation

The AST is traversed (usually post-order) to evaluate the result (in interpreters) or generate target machine code (in compilers).

Key Takeaways

Operator precedence is naturally enforced by the structure of the AST (operators lower in the tree are evaluated first).
ASTs strip away syntax details like parentheses, semi-colons, and whitespace that aren't strictly necessary for execution.

algorithm.txt

12345678910111213141516171819202122232425262728293031// A simple AST Node and Evaluator in JS
structure ASTNode
  initialize(value, left = null, right = null)
    this.value = value
    this.left = left
    this.right = right

algorithm evaluateAST(node)
  // If it's a leaf node (a number), return its numeric value
  if  NOT node.left  AND   NOT node.right then
    return parseFloat(node.value)

  // Evaluate left and right subtrees
  leftVal ← evaluateAST(node.left)
  rightVal ← evaluateAST(node.right)

  // Apply the operator
  switch (node.value) 
    case '+': return leftVal + rightVal
    case '-': return leftVal - rightVal
    case '*': return leftVal * rightVal
    case '/': return leftVal / rightVal
    default: throw new Error("Unknown operator " + node.value)

// Representing the expression: 3 + (5 * 2)
root ← new ASTNode('+', 
  new ASTNode('3'),
  new ASTNode('*', new ASTNode('5'), new ASTNode('2'))
)

console.log("Result:", evaluateAST(root)); // Output: 13

Syntax Trees Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
Earn stars based on your final score (max 5 stars)

Explore other Tree Applications

Heap Sort

Efficient sorting algorithm based on binary heap.

Huffman Coding

Data compression using Huffman Trees.

Decision Trees

Machine learning decision-making workflows.