Hello and welcome.
In this lecture, we're going to make expressions.
So by the end of this lecture, we'll be able to do something like this.
And this will become an expression node whose left operand is a number and whose right operand is a
number and whose operator is in addition.
So that's what we're going to be doing in this lecture.
Head back to parse, dot C, scroll all the way to the top.
We're going to create what I call the history system.
So the history system is simply a structure called history, and it has flags and that's it for now.
We will add to this later on.
Just put it by here.
And the whole point of the history system is that we want to be able to pass down commands through recursive
functions and stuff like that.
This can be hard to do unless we're passing things down the scope.
So by creating some sort of struct history that we pass down the scope, it ensures that we're able
to pass commands to functions that we're calling.
So what we're going to do here, we're going to create some functions for the history.
We're going to say struct history, history begin.
And that's also going to take some flags and flags and we're just going to go struct history.
History equals calc one size of struct history and we're just going to go history flags equals flags
and we're going to return the history and we're going to do the same again called history down, history
down.
But this is going to take an existing history and it's also going to take some flags.
And essentially we're going to go struct history, history, new history, sorry, equals one size of
struct history.
And we're going to say, man, copy, new history, history, size of struct history.
So we're basically copying the existing history that's passed to us into a new history object.
So we're basically cloning it.
Yeah.
And we're going to go new history flags equals flags.
So we'll always overwrite the flags with the ones that you provided here.
But the rest of the history stuff will stay the same.
And here we're just going to go return new history.
Okay, so that's our basic history system.
We will be improving it as we go through the course.
So just go to parse next and this past single token to know we're going to get rid of that now and we're
going to instead do parse expression and we're going to go history begin and we're just going to pass
in a zero here because we don't really want to set any flags.
Right.
And here we're going to say void, parse, expression, level, struct, history, history.
And now just by here, we're going to say in it, pause, impressionable single struct history.
History.
Okay, so back in here, we're going to say, well, parse expression, double single history equals
zero.
And that will be that.
So essentially what powers expression will do when we finished implementing Powers Expression will single
it will basically go through all of the tokens, create nodes out of them, and it will try to form
an expression from the nodes it's created.
So that's what the powers expression of will function does, suggesting powers expression but single
we're going to say struct token token equals token peak next.
And if the token is null, we're just going to return minus one because there's nothing for us to do.
We've already parsed the entire input file, right?
So there's nothing more.
We're now going to set a flag on our history called node flag inside expression.
So just go to compile that page because we're going to need to make that just under here.
We're going to say enum
node, flag inside expression equals zero.
Be one, two, three, four, five, six, seven, eight.
And we're just going to put a one at the end there.
So that should be seven zeros.
And then the eighth here will be a one, because we're going to use this as a bit as a bit mask.
It's a flag, essentially.
Okay.
So go back to parse that dot C can see that now works.
So in case you didn't realize already, this flag when set in a history means that we're inside an expression.
So essentially no flag inside expression just basically tells anyone who has this history object that
we are currently inside of an expression such as 50 plus 20, for example.
So here we're going to say in address equals minus one return race and we're just going to say switch
token type and we're just going to go case token type number for now.
We're just going to do a number for the time being and we're just going to go past singles token to
Node OC.
And we're going to go rest squad zero because that was a successful operation.
Right.
Okay.
But now we're going to do something clever.
We're going to say KS token type operator, because we obviously want to handle operators, right?
Because we're trying to make an expression here.
So just press equals zero here and we're just going to say pause exp and we're just going to put history
there.
So just by here we're going to say init pause, exp struct history, history
and what we should actually be doing here, we should be seeing rare sequence paths, expression not
race equals zero and just returns zero and parse expression.
So this function will be responsible for basically parsing an operator and merging it with the right
operand.
So later on there's going to be many different ways of doing expressions, so we're going to have many
different functions.
So for now, I just want us to call another function parse expression normal, which will basically
for normal expressions, you know, like 50 plus 20, stuff like that.
And just by here, we're going to make a new function for that.
So all about breaking the problem down in programming, as you know.
And we're just going to return zero here.
And I'll tell you what, we'll make that a void because we'll probably end up killing the program if
there's an error at this point in time somewhere in here.
Okay.
So the first thing we do is we check for the next token.
So we go struct token up token equals token peak next and we extract the operator from that token.
We know it's stored in the asphalt because during lexical analysis we set it up that way.
So we're now going to go struct node node left equals node p expression double or null.
And we haven't created that function yet.
So let's just head over to nodes C to make this function.
So got a node that C and just under node pop we're going to say struck node that's going to return a
node pointer node P expression double or null.
And we're just going to say struct node last node equals node peak or null.
And then here's the clever bit.
We say return node is expression level.
We haven't created that function yet.
Laughs Node then return last node.
Otherwise return null.
So that's a ternary, right?
So what does node is?
Expression will do well it returns true whenever the given node you pass to it can be put into an expression,
otherwise it will return false.
So that's what that function does.
So we're going to write that now.
So we're just going to say ball node is impressionable struck node node and we're just going to say
return node type is equal to no type expression or node type is equal to node type expression, parenthesis
or node type is equal to node type unitary or node type is equal to node type identifier or no type
is equal to node type number or node type is equal to node type string.
So there all of our expression, double nodes that can be put into an expression.
So while this function says no peak expression or null, it basically says peak, the peak to the last
node on the stack.
If it's something we can put in an expression, then return it.
Otherwise, return null.
So if we peak here and it's a function node or something, obviously we can't put that.
We can't put a function into an expression.
Right.
Can you imagine that?
Right.
So we just return null here to basically say, no, we couldn't find anything.
So let's just copy and paste this into the header file.
And.
Yeah.
We're just going to have the prototypes, basically.
Right?
So just get rid of these.
Just like that.
And now if we go back to parse it out, see, we can continue writing parse expression normal.
So if the node left is null, then we just return because there's nothing we can really do with that.
Right?
They've passed us a function or something we don't understand.
So we can't really do anything with it.
The last node was incompatible with an expression, so we just returned here.
So the next step is to pop off the operator token.
So we're just going to token next.
We already know what it is because we peaked for it here and we'll put a common there as well.
Just so it's not confusing.
And then we also need to pop off the left node.
Again, we peaked by here.
So we pop it off here and I'll explain all this to you when we've done it.
So don't worry.
So we're going to go node left flags or equals, node flag inside expression.
So obviously the node left is inside an expression, right?
So we want to make that very clear.
So we set the flags for the left node by here.
Right.
And at this point, we would probably check for like an expression like parenthesis or something to
see if there's anything nested.
But we'll implement that as we go through the course because I don't want to give you too much at once.
So we're going to create another function by here called void parse expression label for OP.
And that's going to take a history and it's going to take a conch char up, which is the operator.
Right.
This separation is kind of essential because at some point we're going to check things like operator
sensitivity.
So like multiplication always has priority over addition, for example, right?
We don't have that implemented yet.
We will be implementing it, which is why I'm breaking the problem down into these separate functions
here, because we will be managing that soon.
But for now we'll just go parse expression table and we'll just pass in the history just like that.
And we will need to take the prototypes here and just copy and paste them to the top of this file.
Just like that.
Just so it's recognized throughout the whole parse of script, right?
Parse expression or single parse expression.
But if we just paste the prototypes there, all our functions, we had to call them.
So we're just going to say parse expression label for OP.
We're going to say history down.
History.
Zero.
And no, they'll actually be history flags.
So not zero.
And the operator will be the OP.
So now we're going to pop off the right node that we just passed here.
So we're going to say struck node, right node equals no pop.
And then we have the right node that we just passed.
From his expression on before upright.
And again, we're going to say right note flags or equal, no flag inside expression, because we want
it to be clear that those nodes are part of an expression.
Right.
And then we're just going to say, make expression node, which we haven't created yet.
Node left, no, right and operator.
And then we'll have another node on the stack and we're going to pop that off.
And that's called the node expression, which will be composed of the left node and the right node.
Once make expression, node has joined them and created its own node expression and we should call expression
node really.
And here you'll see we did right node.
Just change that to no right.
Let's just keep consistency.
So we got no right and node left.
Perfect.
So once we have our expression node, we would reorder the expression with the associative T that I
spoke to you about where multiplication has priority over addition.
But we're not going to do that yet because that's for another last lesson in the course.
So we're just going to leave a comment there now.
And once it's been reordered, we're going to push it back to the tree, back to the stack.
So that's how that works.
Right.
So simply put, what's happening is we call parse expression level when we are at token 58272.
Right.
That then calls pause expression single, which will peak for the next token.
It'll see that it's a number.
So we just create a single token to a node.
Yeah.
And as we know, no create pushes to the stack.
So at this point in time, we have the number 58272 on the node stack.
We have nothing else on there.
Again, because this is a wild loop, we then end up parsing the next part, which is an operator,
a plus operator by here.
Right.
So then what happens is that calls parse expression, which calls parse expression normal, which then
peaks to see what that operator is.
And we see that it's a plus.
And then we look on the node stack to see what the last node was that was pushed.
Well, as I just explained, we've pushed 58272 onto the stack when we converted it from a token to
a node.
Right.
Because no create always pushes to the node stack.
Right.
So now node left is equal to that 5827 to number node.
So here we pop off the the token operator, the plus and we pop off the left node that we've just picked.
We now assign the flags just to let everyone know it's an expression.
And then we parse the right node.
Now, remember, the right node hasn't been parsed yet.
We've only parsed the left node and the operator.
So we parse the right note here with parse expression for up, which causes which calls parse expression
label, which will then call parse single token to node and it will create a number token.
So now we end up with only the right nodes on the stack because we've popped off the left node already.
Okay.
So we only have the right node on the stack now, the 2000.
So what we then do is we pop off the 2000.
The node stack is now empty, completely empty.
But we are aware of the node left and the node right because they're in memory and we're also aware
of the operator because it's in memory.
We've also popped off the entire input stream at this point because we reached end of file here.
So then what we do is we call make expression, which creates an expression no with no left and with
no right.
And with this operator, it pushes that no type expression to the stack.
And then we pop that off, reorder it, which we haven't done yet, and we push that back to the stack,
and then we end up simply with a node type expression, essentially a node of no type expression like
that.
And what we're now going to do is we're going to change our structure node to accommodate for no type
expression.
So this is very simple.
What we're going to do is we're going to create another union.
And inside the union we're going to say struct expression and we're going to name that expression and
then we're going to have struck node left struck no right const char up, nice and simple.
So just go to node C and just by here we're going to say struck node, make expression node and we're
just going to say struct node.
Left node struck, node right node const char up.
We're going to assert that the left node is not null, and we're also going to assert that the right
node is not null.
And then we're just going to go, no, create ampersand struck node dot type equals node type expression
dot expression dot left equals left node expression right equals right node to expression op equals
op.
Simple as that.
And we're actually going to return a void here as well.
Okay.
So yeah, that creates a node of type expression, type node expression.
It sets the left node to the left node they provided and the right nodes of the right node, they provide
it and the operator, the operator, they provide it.
Very nice.
So just copy and paste that and we're going to put it in the header file.
Just send a note.
Create.
Problem solved.
So we're now going to do we're just going to go to no see scroll up to no pop because there's a slight
bug you'll see.
Vector back pointer just put vector back pointer on null node.
Okay.
Because just because the node vector is an empty doesn't necessarily mean our root vector won't be empty.
Right.
So just to back pointer or null and then we're going to go to parse the dot C and scroll down.
And remember we did reg equals parse expression should actually just two s equals zero.
Just like that.
Okay.
So if we now go to the terminal and we do make clean make.
You can see that ad compiles fine.
So let's now open.
JDB We're going to go JDB Main, and we're just going to break on pause and we're going to go run.
All right.
And now we're going to go next.
Next, next.
Next.
Just keep pressing enter to keep doing it.
And then when you're at pause.
ALL Okay.
We finished pausing.
So now we're going to go print as Chris note and look what that does gives us it gives us a know with
the operators plus and it has left and right expressions set.
So if we do node expression left, we see 58272.
If we do node expression right, we see 2000.
So look at that.
We just created our very first abstract syntax tree.
Okay, now we have some sort of tree where instead of just this input here we have actual nodes.
So we have an entity called no type number that has a value of 58272.
We have an entity, entity of operator which has a value of plus and we have another entity of 2000
which is also a number node.
So we can see there, join together, imagine some lines drawn between them.
Right.
That's how it's working.
Right.
And this is fantastic because nodes can just nest infinitely.
We can nest expressions infinitely, we can nest functions to body nodes to have function arguments.
And then it'll be really easy to go through it later on because we essentially just loop through all
the nodes or we have a node type expression, Oh, what was the operator of that expression?
And all we have to do is literally just say print node expression dot up and we know exactly what the
operator is for that expression.
So this is why performing, parsing and creating abstract semantics trees is so efficient in compiler
development.
So as we go through the course, you know, we're going to create function nodes, nodes for switches,
and so we can pass the C programming language.
So thanks so much for watching.