structure.md

Chapter 2: Structure & AST

Back: Goals | Overview | Next: Parser Layout

---

Let's use this expression as an example:
2 * 7 + 4 * (5 + 6) + (sin(4 - 4) - 4)

If we were to solve this manually - ignoring term manipulation - it would look something like this:

2 * 7 + 4 * (5 + 6) + (sin(4 - 4) - 4)
  |     |      |        |    |      |
  |     4-[*]--11      sin ( 0 )    |
  |        |               |        |
  14-[+]---44              0---[-]--4
      |                         |
      58-----------[+]--------(-4)
                    |
                   54

From this we can see a few patterns emerging:

• First we solve the brackets and functions (applying the other rules in the smaller environment there)
• then we resolve multiplication/division
• then we resolve addition/subtraction

In fact this looks like a tree structure! This is why that is also referred to as an Abstract Syntax Tree (AST). We can represent this structure with some classes, the AST nodes.

Class (extending AST)	Fields
Value	value: int
Variable	name: str
FuncCall	name: str, args: list[AST]
BinaryOp	left: AST, right: AST, op: str
UnaryOp	item: AST, op: str

You may have noticed that there is no corresponding class for bracketed expressions. This is because brackets simply change the shape of the tree:

a * (b + c) | BinaryOp with: left = a,     right = b + c, op = "*"
(a * b) + c | BinaryOp with: left = a * b, right = c    , op = "+"

You may also have noticed that these structures are recursive: Multiple AST nodes hold AST nodes themselves. This means that the parser, aswell as the evaluation also needs to be recursive!

Let's start by implementing the AST structures. While we may not know yet how we generate those, it'll help us implement the right structures.

AST

# Just a dummy base class.
# In other languages, you would put 
# your abstract methods here.
class AST:
    pass

Value

class Value(AST):
    def __init__(self, value: int|float):
        self.value = value

Variable

class Variable(AST):
    def __init__(self, name: str):
        self.name = name

FuncCall

class FuncCall(AST):
    def __init__(self, name: str, args: list[AST]):
        self.name = name
        self.args = args

BinaryOp

class BinaryOp(AST):
    def __init__(self, left: AST, right: AST, op: str):
        self.left = left
        self.right = right
        self.op = op

UnaryOp

class UnaryOp(AST):
    def __init__(self, item: AST, op: str):
        self.item = item
        self.op = op

---

Back: Goals | Chapters | Next: Parser Layout