Language Implementation Patterns

Pattern 11

Irregular Heterogeneous AST

Purpose

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

Discussion

This pattern only differs from Pattern 10, ​Normalized Heterogeneous AST​ in the implementation of its child pointers. Instead of a uniform list of children, each node data type has specific (named) child fields. In this sense, the child pointers are irregular. In some cases, named fields lead to more readable code. For example, methods can refer to left and right instead of, say, children[0] and children[1].

When building trees from scratch, most programmers follow this pattern. It’s very natural to name the fields of a class, in this case naming ...