Construction of Syntax Trees

Parse tree (concrete tree): mirrors the grammar exactly. Every non-terminal (E, T, F) and every symbol — including punctuation like parentheses — becomes a node.

Abstract Syntax Tree (AST): a condensed tree that keeps only the operators (as internal nodes) and the operands (as leaves). It drops two kinds of clutter:

• Punctuation like ( and ) — the tree shape already encodes the grouping.
• Single-child chains like E → T → F — there is nothing to choose, so the chain collapses to one node.

The one running example

Throughout this topic we build the AST for a single input.

We are building this expression's syntax tree — its structure — not computing its value. Notice the input has parentheses; in the finished AST they will be gone, because their only job is to force grouping, and the tree shape captures that.

We give every grammar symbol X a synthesized attribute X.node — a pointer to the root of the AST subtree built for X. "Synthesized" means it is computed from the children, bottom-up, which is exactly what a bottom-up (LR) parser produces as it reduces.

Two helper functions do all the work. Each allocates one node and returns a pointer to it.

mkleaf(id, lexval) — makes and returns a leaf node for a number or identifier. lexval is the leaf's value (here, the digit itself).

mknode(op, left, right) — makes and returns an internal node labelled op, with pointers to its two child subtrees left and right.

Syntax-tree semantic rules

Two patterns:

• Operator rules (E → E + T, T → T \* F) call mknode — they create a node.
• Single-symbol rules (E → T, T → F, F → ( E )) just copy the child's pointer up — no new node. This is why F → ( E ) makes the parentheses vanish from the AST.

The parser reduces bottom-up, so the nodes are created in the order the operands and operators are recognized. Listing the helper calls in order:

The root is p7, the last node allocated. The parentheses never produced a node — F → ( E ) simply forwarded p5.

The finished AST

The parentheses from the input are gone — the tree shape alone says "evaluate 3 \* 5 + 2 first, then multiply by 2."

Directed Acyclic Graph (DAG): like an AST, but an identical node is stored once and shared by every parent that needs it, instead of being duplicated.

In our input the constant 2 appears twice. The plain AST above built it twice — p4 = mkleaf(2) and p6 = mkleaf(2) are two separate nodes. A DAG returns the same pointer for the second mkleaf(2):

Now the single 2 leaf has two parents (p5 and p7):

The only change is that mkleaf / mknode first check a table: if a node with the same label (and children) already exists, return it instead of allocating a new one. This is the basis of common subexpression elimination.

• An AST keeps operators as internal nodes and operands as leaves; it drops punctuation (parentheses) and single-child chains that the parse tree carries.
• X.node is a synthesized pointer attribute built bottom-up — perfect for an LR parser.
• mkleaf makes an operand leaf; mknode makes an operator node from two child pointers. The root is the last node allocated.
• F → ( E ) copies the pointer up, so parentheses leave no node in the AST.
• A DAG shares identical subexpressions — the repeated 2 becomes one leaf with two parents — enabling common subexpression elimination.