An abstract syntax tree can help your code make sense of what a user provides.
Listen to the full episode as I describe how to build an abstract syntax tree starting with a simple idea and then how that idea needs to change. You can also read the full transcript below.
Transcript
Have you ever had somebody give you instructions that were all jumbled up and barely made any sense? Maybe they would forget things and go back to an earlier point to clarify. Or maybe they would give you instructions that were unnecessary.
A good way to make sure you understand is to try to make sense of what the other person is saying and then repeat the instructions. You can make things more organized and your friend will be amazed at how simple and straightforward the instructions have become.
In a way, what you’re doing is creating an abstract syntax tree. Usually we think of something abstract as being hard to visualize and understand. Something that has no form and is more of an idea than anything else.
Well, I’m not sure of the origin of the term abstract syntax tree, but the way I understand it is that you’re building a very specific tree that abstracts your code away from the confusing world of information provided. So instead of thinking of them as abstract, syntax trees, I think of them as abstract syntax, trees. Notice where I put the mental pause. To me, it’s the syntax that’s abstract and then the tree comes along and makes things better.
Let’s say that I ask you to solve 5 + 3 * 2. You could add 5 and 3 to get 8 and then multiply by 2 to get 16. Or you could first multiply 3 by 2 which gives 6 and then add 5 to get 11. Given just the original formula of 5 + 3 * 2, the correct way to do this is to realize that multiplication has a higher order of precedence than addition and should be done first. That means 11 is the correct answer.
You can change this by adding parentheses around 5 + 3. Since parentheses have a higher order of precedence than multiplication, then the 5 + 3 will be done first and the answer will be 16.
What happens if you add parentheses around the 3 * 2 part? Well, all this says is that parentheses has a higher order of precedence than addition. The parentheses won’t change anything since the multiplication already has a higher order of precedence than addition. You can still add them if you want in case you want to be extra specific. But they’re not needed.
Once you understand the order that things should be done, whether by using parentheses or not, you can build an abstract syntax tree which will make it clear exactly what should be done.
I’ll walk you through the design considerations and you’ll learn how your understanding of a problem can change over time. Let’s examine the normal case without any parentheses in this episode.
You’ll need code that can read the input provided. This is called the parser. The parser cares about things like parentheses and should also catch errors. So if the formula said 5 + + 3 * 2, then the parser should return an error because the extra plus sign doesn’t make any sense. Now it may not return an error right away the moment it sees the second plus sign. But it should eventually figure out that something’s not right.
Okay, the first thing that parser can do is add the 5 to a stack. Because the parser needs to read the input in a single direction, it doesn’t know what to do with a 5 just yet. So it remembers it by adding it to a stack of values. Listen to the previous episode for more information about stacks.
This is where you can learn to start thinking like a programmer by coming up with rules to follow. As humans, we know that the processing just began and that nothing came before the 5. We also know that there’s more to this problem than just the 5. This knowledge can trip us up when programming. Because remember the computer is just following exactly what we tell it to do. We never told it that the 5 was the first thing or that it should expect more. In fact, we’re writing code that should be able to work with any formula. If the code only needed to work with this one situation and nothing else, then why are you writing a program? Use your calculator!
Instead of creating some special case bool variables called firstValue and lastValue or something, let’s see if we can make a rule that will work regardless. In other words, come up with a system that will work the first time, the second time, and all times.
In general, what do we want to happen when we find a value like 5? Well, all we can do is remember the values. Until we see an operator, like a plus sign, we don’t know what to do with any value. That’s why I said that the 5 should be placed on a stack. We can easily get the 5 off the stack whenever it’s needed and we want to work with the most recent values. Don’t worry, none of your values will complain if they’ve been sitting in the stack longer than other values.
Now that the 5 is safely stored on the stack, we can move on. The next thing the parser sees is the plus sign. Again, we can’t do anything with just a plus sign because we don’t have the second value yet. We have found our first operator and this is a good opportunity to check if there’s already been a complete sequence. In other words, we need to check if we already have two values and an operator.
Because all we’ve seen so far is a single 5 value, we just put the plus sign on top of another stack. Let’s call this the operator stack. Now we can remember all the values we’ve seen and all the operators and each one will make the most recent values and operators available on the top of the stack.
All we have so far is a single value and a single operator. Let’s continue reading. The next thing is a 3. Remember, the whole formula we’re working with is 5 + 3 * 2.
Alright, we just got our second value. That means we have two values and an operator. What do we do with them? Well, nothing yet. Why? Because what we really need to do is see what comes next. If whatever comes next has a higher precedence than the operator we already have, then working with what we have now and adding 5 plus 3 would be the wrong thing to do.
You should start to see a pattern develop by now. Single values like the 5 or 3 just go straight on the value stack. And whenever we get to an operator like a plus sign, we need to compare it with previous operators to see which has the highest precedence.
As humans, we just do all this almost without thinking. At least as adults, anyway. Just watch a child when first learning about operator precedence though. That child will struggle for a while and need to think hard about each problem. Over time, it’ll become easy. What’s actually happening is that our brains are writing a program for solving formulas like this. Each time we encounter a new situation, we need to reconcile that with our internal program. Eventually, we get good enough that we can solve things like this “without thinking”. What that really means is that we’ve developed our internal program enough so that we can simply follow our instructions. This is just what a computer does. Only computers can’t program themselves yet.
Anytime we see an operator, what we want to do is look at the operator currently sitting on the top of the operator stack. Some stacks might have a top method that will let you look at the top item without popping it. If not, don’t worry. A top method is just a shortcut, a nice shortcut, but not essential. You can get the same result by popping the item, looking at it, and then pushing it back on the stack if you want it to remain on the stack. Having a top method lets you look at the top item directly.
We can then compare the current operator with the previous top operator. If the current operator has a higher precedence, then it gets pushed on the operator stack. This has the effect of temporarily covering up the previous operator. The old operator is still there and will be dealt with later. But for right now, we found an operator that’s more important.
The other case to handle is what to do when the previous operator has a higher precedence or the same precedence as the current operator. If we end up here, then we can finally do something. I’ll get back to this case in just a moment.
In our example of 5 + 3 * 2, we’ve just read the 3 and put it on the value stack. Let’s continue and read the next thing which is the multiplication sign. Based on what I just described, we compare the precedence of the multiplication sign with the plus sign and determine that the addition should not be done yet. So we just push the multiplication on to the operator stack and continue reading.
The next thing we read is the 2. What do we do with values? They go onto the value stack and we keep reading.
Here’s where we reach the end of the input. There’s nothing else to read. And we haven’t done anything with the formula yet. We certainly don’t have an answer. All we have are a couple stacks with some items.
It might seem like this is a lot of work for very little results. But we’ve actually accomplished a lot. We don’t have a full abstract syntax tree yet but I’m about to explain how to finish it.
In a way, we can treat the end of the input as the lowest operator ever. In effect, it says, don’t do anything else and just process whatever you’ve already done.
Let’s do that by popping the top operator from the operator stack. This is exactly what needs to happen anytime we find an operator with a lower or equal precedence than what’s already on the stack.
We need to turn this operator into an expression. In our example, we need to isolate the 3 * 2 portion so it will result in a value all by itself.
Here’s where things get a bit different though. If we were interested in finding the answer to the formula, then we could do the multiplication, get the value 6, and then put that value back on the value stack. This would get it ready to later be added to the 5 which is still sitting in the value stack.
We want to build an abstract syntax tree which will preserve the structure so that we can do other things with it later. That means we don’t want to actually do the multiplication because that would remove knowledge about the multiplication. We want a value that represents the entire expression of 3 * 2.
So let’s change our idea of what makes up a value to allow expressions too. We’ll need a class that will represent a value but call it by a more general name of expression. Then we can have derived classes that understand the exact operation being done.
Our value stack needs to become an expression stack. Simple values like 5 can also be expressions. As can more complicated values like 3 * 2.
Okay, so by removing the multiplication operator from the operator stack, we can then use it to create a multiplication expression. This multiplication expression will remove the top two expressions from the expression stack which are currently 2 followed by 3. The expressions are in the opposite order but that’s okay. We know that multiplication needs a left hand side value and a right hand side value. So we set properties on the multiplication expression equal to the 3 for the left and the 2 for the right. Then we take this expression and put it back on the expression stack.
We’re almost done. We keep doing this until there are no more operators. The last operator in our example is the plus sign. So we do the same thing and pop it from the operator stack, look at what kind of operator it is and construct an addition expression. Addition also needs two values. So we pop the top two values from the expression stack which gives us the multiplication expression that was just pushed there as well as the 5 which was placed there in the very beginning.
We put these two expressions. Remember that the value 5 is also an expression now. We put these two expressions into the addition expression and then push it onto the expression stack.
You can now see how the expressions sitting in the expression stack are getting more complicated. Since there are no more operators, we’re done.
The last expression remaining in the expression stack is our abstract syntax tree. What does it look like?
It’s a tree because each node can be an expression containing its own nodes. In our case, we have an addition expression at the root of the tree with the simple value expression equal to 5 as its first child. The second child is a multiplication expression with two nodes of its own. These are the simple value expressions 3 and 2.
For this example, an abstract syntax tree might seem overkill. And I’d agree. Abstract syntax trees are much more useful in very complicated scenarios. I kept the example simple here so it could be described. This is already a long episode. And it’s much harder to explain with audio only.
If you want to go beyond audio, or even get extra audio podcasts, then consider supporting Take Up Code on Patreon. You can find the link by visiting takeupcode.com and clicking the link to “Become a Patron“. For $1 per month you’ll get access to an extra podcast episode each month. And there are other rewards. Each reward is reasonably priced and I always keep you in mind when deciding what would have the most direct benefit to you. Go ahead and support the podcast and get some great rewards at the same time!
I’ll end this episode with a short discussion of what would have happened if the formula had a mistake such as two plus signs like 5 + + 3 * 2. How would this have been detected?
The 5 would be turned into a simple value expression and pushed onto the expression stack like normal. Then the first plus sign would be pushed onto the operator stack because there are no previous operators to compare with. Then the second plus sign would be read and compared with the plus sign on top of the stack. Because both operators have the same precedence, then we need to turn the existing plus sign into an expression. This requires two expressions for the left and right side of the addition. But there’s only the single value 5 in the expression stack to work with. This is where the error would be detected when we tried to pop two expressions from the expression stack but it only contains the single expression. Your code could check for things like this to make sure that the stack doesn’t throw an exception. Or, you could let it throw and handle the exception someplace else.