Language Implementation Patterns

Building Abstract Syntax Trees

Rather than simply taking what the parser can give us for free (parse trees), let’s take a second to design what we actually want in an IR. The critter that we end up with is called an abstract syntax tree (AST).

To figure out what ASTs should look like, let’s start with a list of design guidelines. An IR tree should be the following:

• Dense: No unnecessary nodes

• Convenient: Easy to walk

• Meaningful: Emphasize operators, operands, and the relationship between them rather than artifacts from the grammar

The first two points imply that it should be easy and fast to identify patterns in the tree. Language applications that use intermediate trees usually make multiple passes over the trees in order to analyze or build ...