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-[*]--11sin(0) |
| | | |
14-[+]---440---[-]--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.classAST:
pass

Value

classValue(AST):
def__init__(self, value: int|float):
self.value=value

Variable

classVariable(AST):
def__init__(self, name: str):
self.name=name

FuncCall

classFuncCall(AST):
def__init__(self, name: str, args: list[AST]):
self.name=nameself.args=args

BinaryOp

classBinaryOp(AST):
def__init__(self, left: AST, right: AST, op: str):
self.left=leftself.right=rightself.op=op

UnaryOp

classUnaryOp(AST):
def__init__(self, item: AST, op: str):
self.item=itemself.op=op

---

Back: Goals | Chapters | Next: Parser Layout