Abstract syntax tree construction and traversal

Question

I am unclear on the structure of abstract syntax trees. To go "down (forward)" in the source of the program that the AST represents, do you go right on the very top node, or do you go down? For instance, would the example program

a = 1
b = 2
c = 3
d = 4
e = 5

Result in an AST that looks like this:

or this:

Where in the first one, going "right" on the main node will advance you through the program, but in the second one simply following the next pointer on each node will do the same.

It seems like the second one would be more correct since you don't need something like a special node type with a potentially extremely long array of pointers for the very first node. Although, I can see the second one becoming more complicated than the first when you get into for loops and if branches and more complicated things.

Answer 1

The first representation is the more typical one, though the second is compatible with the construction of a tree as a recursive data structure, as may be used when the implementation platform is functional rather than imperative.

Consider:

This is your first example, except shortened and with the "main" node (a conceptual straw man) more appropriately named "block," to reflect the common construct of a "block" containing a sequence of statements in an imperative programming language. Different kinds of nodes have different kinds of children, and sometimes those children include collections of subsidiary nodes whose order is important, as is the case with "block." The same might arise from, say, an array initialization:

int[] arr = {1, 2}

Consider how this might be represented in a syntax tree:

Here, the array-literal-type node also has multiple children of the same type whose order is important.