Why do most AST trees use classes instead of vectors

implementationsprogramming-languages

I've noticed that most AST tree implementations use classes for nodes instead of something like a vector. I want to ask, why do most people use classes? Are there issues to using vectors to make AST trees?

Best Answer

To add to the existing answer, the classes (or algebraic types) represent the "node of the tree". Or rather, they represent the kind of node in the tree.

Being able to have more than one type of a node means that language implementors can allow for lots of variety. That means a tree's definition can be defined recursively with something like:

expr := Func(expr) | Num

A user's program can be:

  • a number : 7
  • a function on a number: f(7)
  • a function on a function on a number: f(g(7))
  • etc.

Any part of the compiler or interpreter that walks the tree simply needs to implement the expr as being either a function or a number. So for classes, that can be done with inheritance and polymorphism; for algebraic types, that means pattern matching.

Now consider your alternative proposal: vectors mean that the kind of node must be homogeneous. No way for an expression to be either a function or number.

Related Topic