Precedence: Chapter 2

Last time we talked about how a program is converted into a Syntax Tree. We ended with a huge cliffhanger, though: what do you actually do with a Syntax Tree.

Today, we’ll talk about that. We need to cover one thing really quickly, though. Stacks.

What is a Stack?

Stacks are one of the simplest data structures in programming, but they can be incredibly powerful (as you’ll see). With stacks, you only have two options, take an item, or leave an item, often called pop and push, respectively. The item you take is the last item you left. So, if you leave 5, and then you take an item, it’ll be 5. If you leave 7, 3, and 9, and then you take an item, it’ll be 9. See? The last item you left is the next item you’ll take. One more example: say you leave ten through twenty, and then you take three values. The three values will be 20, 19, and 18. Simple, right? And it turns out it’s a very important part of how code is evaluated.

Evaluation: A Step by Step Guide

Okay, so let’s evaluate some code. We’ll use a simple tree from before. 1 + 5 Here it is again:

In the INH interpreter, evaluating a node follows these general rules:

Start at the root
Evaluate left
Evaluate right
Evaluate self

So, following rule 1, we start at the root, which is ‘+’. Our left is 1, and our right is 5. We need to evaluate left nodes first, so we evaluate 1. What does it mean to “evaluate 1”? It just means we put a 1 on our value stack.

1 - push the number 1 to the value stack

Next we evaluate right nodes. We’ve got a 5, so we evaluate that and put a 5 on our value stack:

5 - push the number 5 to the value stack

Alright, now finally, we evaluate self, which is a ‘+’. This one’s a bit more complex. A plus is an operator which requires two values. Where does it get the values? It pops them off the stack. Once it’s done plussing, it pushing the result onto the value stack:

‘+’ - pop 5 and 1 off value stack, add them, push new value to stack

And voila, we’ve added two numbers together!

A More Complicated Example

Now, that may’ve seemed like a crazy way to go about adding 1 and 5, but this tree concept is a simple framework that can handle a vast array of operations, both mathematical and logical. And the beauty of it is that no matter how complex your tree is, you evaluate it by following these simple rules. Let’s take this one as an example:

First step, parsing:

You recognize our little friend 1 + 5 in the lower left? Okay, let’s go through it. Start at the root. That’s ‘*’. Next, we evaluate left, which is the tree 1 + 5. We already did that before, and we know it’s 6:

Now evaluate right, which is the number 7, so we put that on our value stack:

Now for our grand finale we evaluate ‘*’, which pops two values and multiplies them. 6*7=42. Great! But oh wait, not so fast. 1+5*7 is not 42, it’s 36!

Now you’re caught up! This is the issue we ran up against. Now we’ll talk about how to fix it!