This video is available to students only

Traversing an AST

Programmatically traverse an AST and visit arbitrary nodes

In the previous lesson, we wanted to log all of the numeric values in the source code. The resulting script may have looked something like the following.

What would happen if the order of operations was swapped in the source to do the addition first, then multiplication?

Changing the order of operations will result in a different AST.

generated AST visualization

Previously, 4 and 10 were multiplied first, then added to 2. Now, 2 and 4 are added first, then multiplied with 10. Compare this tree diagram with the previous lesson.

This time, the first BinaryExpression has another BinaryExpression on the left, and a NumericLiteral on the right. Additionally, the operator is now a multiplication sign (*).

Each type of node only defines properties relevant to what it represents. For example, a BinaryExpression has an operator property to indicate either addition or multiplication. However, a NumericLiteral does not have an operator property since it represents only a number, but it does have a value property (which a BinaryExpression does not).

Each property can have several different types of values. For example, the NumericLiteral value property is always a number. Whereas the BinaryExpression left and right properties are always another node. As seen in this example, the left and right properties can be more than one type of node (NumericLiteral or another BinaryExpression).

The parser script made assumptions about the structure of the tree and the types of nodes. It assumed the first BinaryExpression had another BinaryExpression in the right property. That BinaryExpression had a NumericLiteral in the left property.

Looking at the tree above, we can see this is no longer the case. Now, expression.right will return a NumericLiteral instead of a BinaryExpression. Accessing the left property will return undefined since left doesn't exist on a NumericLiteral node. Finally, trying to access value of undefined will throw a runtime error.

To make our script more flexible, we need a way to "generically" visit a specific type of node in the tree, wherever in the hierarchy it may be.

The @babel/traverse package offers the functionality to programmatically visit nodes anywhere in the tree that represent a numeric literal.

Programmatically visiting nodes#

First, add the package in the existing project.

Then, create a new traverse.js file that's a copy of parser.js with one new import for the traverse function from the @babel/traverse package.

 

This page is a preview of Practical Abstract Syntax Trees

Start a new discussion. All notification go to the author.