Course contentsShow
← Computer Science
Lesson 1978 of 2,87244. Lexical Analysis and ParsingFree lesson

AST Representation of Expressions

Build ASTs for arithmetic and boolean expressions, showing how operators become internal nodes and operands become leaves.

AST Representation of Expressions

What You'll Learn

You'll learn how arithmetic and boolean expressions map to tree structures where operators become internal nodes and operands become leaves.

From Expressions to Trees

When a parser processes an expression like 3 + 5 * 2, it doesn't just evaluate it—it builds a tree representation that captures the structure and precedence. This is the Abstract Syntax Tree (AST).

How Operators and Operands Map

In an AST for expressions:

  • Operators (+, -, *, /, &&, ||, etc.) become internal nodes
  • Operands (numbers, variables, boolean literals) become leaf nodes
  • The tree structure encodes precedence and associativity

Example: 3 + 5 * 2

      +
     / \
    3   *
       / \
      5   2

The multiplication happens "lower" in the tree (closer to the leaves), reflecting that * has higher precedence than +. To evaluate, you'd compute leaves first, work upward: 5 * 2 = 10, then 3 + 10 = 13.

Boolean Expressions Work the Same Way

For x > 5 && y < 10:

       &&
      /  \
     >    <
    / \  / \
   x  5 y  10

Each comparison operator becomes a node with its operands as children, and the logical && combines them.

Why This Structure Matters

The AST naturally represents evaluation order: process children before parents. It strips away syntactic details (like parentheses) while preserving semantic meaning. Later compiler phases traverse this tree to generate code, optimize, or perform type checking.

Key Takeaway: In AST representation of expressions, operators form the internal branching structure while operands sit at the leaves, creating a tree that directly models precedence and evaluation order.