207: Trees: AST: Abstract Syntax Tree. A Simple Example.

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 t