UP | HOME

Abstract Syntax Tree

Table of Contents

Definition

An Abstract Syntax Tree (AST) is a tree-shaped data structure that represents the structure of a program, stripped of surface-syntax details (parentheses, whitespace, operator precedence rules). Each node in the tree represents a syntactic construct; child nodes represent sub-expressions.

In PLAI (Ch.2, Ch.3)

PLAI defines ASTs using define-type, which creates an algebraic datatype with named variants. For the arithmetic language: 

(define-type ArithC
  [numC (n : number)]
  [plusC (l : ArithC) (r : ArithC)]
  [multC (l : ArithC) (r : ArithC)])

Variants numC, plusC, multC correspond to the three grammatical forms of the language. plusC and multC carry two ArithC children — the recursive structure of the AST mirrors the recursive grammar of the language.

In Tolk (Common Lisp / CLOS)

Tolk uses a defclass hierarchy instead of define-type. Methods on these classes are defined using defmethod-bind (see also closer-mop for why the classes must be in an eval-when block): 

(defclass ast-node () ())

(defclass num (ast-node)
  ((n :type number   :initarg :n)))

(defclass arith-binary-op (ast-node)
  ((op :type function :initarg :op)
   (l  :type ast-node :initarg :l)
   (r  :type ast-node :initarg :r)))

(defclass plus (arith-binary-op) ((op :initform #'+)))

(defclass mult (arith-binary-op) ((op :initform #'*)))

Key differences from PLAI's define-type:

  • An intermediate abstract class arith-binary-op captures the shared structure of binary operations. PLAI has no equivalent.
  • The op slot stores the operation as a function object, enabling a single interpret method to cover both plus and mult.
  • CLOS dispatch (defmethod) replaces type-case for branching on node type.

PLAI ↔ Tolk correspondence

PLAI define-type variant Tolk class
numC num
plusC plus
multC mult
(no equivalent) arith-binary-op (shared superclass)

Object equality for testing

Tolk defines eqo (object equality) in tests/object-equality.lisp: two AST nodes are eqo when they are of the same class and all their corresponding slot values are also eqo. For non-AST objects, eqo defaults to eql. This is necessary because make-instance always creates a fresh object, so structural equality cannot use eq or eql.

Sources

Related