How a Computer Solves the Tree
When a computer solves a simple math expression, it doesn’t read it the same way a person does. People read 1 + 2 but computers read + 1 2. (That's just how x86 CPUs work) Here is the assembly code for solving 1 + 2 and putting the answer in memory:
ADC RAX, 1, 2
I use Intel assembly, so the destination register comes after the opcode.
Here's the part that gets me out of bed in the morning to write code. If you traverse the tree differently, you get the code to solve the tree. Assembly code requires you to read parent node, left node, then right node. There is a catch, unlike my earlier example, you must start at the bottom-most nodes. Purely following parent, left, right, gives you this invalid code:
ADC RAX, IMUL RBX, 2, 3, RBX, 2
For that AST we solved earlier, starting at the bottom-most parent and using RAX as the memory where we put the answer, here is the code:
IMUL RBX, 2, 3, ADC RAX, RBX, 2
The answer is in RAX now.
For another example, let’s look at Adobe PostScript. Instead of discreet pieces of memory like RAX, RBX, etc., PostScript stacks the numbers on top of each other. When you do an operation, the computer pops the top two numbers off, does the operation, and puts the answer on top of the stack. (It’s called a stack machine) You need to traverse the tree so that you get code like this:
1 2 add
Traverse the tree going left node, right node, parent node. Here is the PostScript code you get for our example tree:
2 3 mul 2 add
The answer is on top of the stack.
If you’re writing assembly, you must start at the bottom. It’s like solving each level of the tree simultaneously.
IMUL RCX, 2, 3 ADC RBX, RCX, 1 IDIV RDX, 14, 2 ADC RAX, RBX, RDX