Language Implementation Patterns

Pattern 9

Homogeneous AST

Purpose

A homogeneous tree implements an abstract syntax tree (AST) using a single node data type and a normalized child list representation.

Discussion

The key idea behind an AST is the operator-operand tree structure, not the node data type. The node data type is really just how we implement ASTs. An AST contains the essence of the input token stream and the relationships between operator and operand tokens.

We don’t need to use the type system of our implementation language to distinguish between nodes. Nodes in any AST derive from tokens, so we can use the token type to identify nodes. In fact, homogeneous ASTs are the only convenient choice for non-object-oriented languages like C. To implement Pattern 10, ​Normalized ...