Language Implementation Patterns

Pattern 10

Normalized Heterogeneous AST

Purpose

This pattern implements an abstract syntax tree (AST) using more than a single node data type but with a normalized child list representation.

Discussion

This pattern is a variation on Pattern 9, ​Homogeneous AST​. All we’re doing differently is distinguishing between nodes with our implementation language’s type system. Because this pattern also uses a normalized child list, we can derive heterogeneous nodes using AST from Pattern 9, ​Homogeneous AST​ as a base class.

This pattern makes the most sense when we need to store node-specific data and plan on using Pattern 13, ​External Tree Visitor​. The normalized child list makes it much easier to build external visitors. If you need lots of node-specific ...