All right so the second part of our handmade expression evaluator is of course the parsing stage.
So let's recap what we have so far we've taken as trng presenting a mathematical expression and we turned
it into a sequence of tokens where each token is defined in terms of its type and it's just an enumeration
here as well as the text of the token as well which we're going to need when we actually build the parsing
structure.
So now what we want to do is we wanted take the set of tokens we want to go through the tokens one by
one and we want to build an actual expression that we can hopefully evaluate.
So in order to define this we're going to be defining some object oriented structures and I'll define
some abstract base class for the kind of things that we're going to have so I'll have a structure called
element is just going to have a single function called evil which is going to actually allow us to evaluate
this expression.
Now the evaluation itself will also be using the visitor design pattern but we'll talk about it in just
a moment.
So what kind of structures do we have as we have this expression Well first of all we have individual
integers like 13 for example.
So we may as well define a structure for them that's going to be a structure called integer which is
going to be an element.
And here we'll just have the integers of value.
So notice when we have the token integer the text is a string and we need to somehow turn this string
into a value that's going to be one of the challenges.
So let's build a constructor where we simply construct the value.
And let's also implement evil.
So to go and to implement functions and implement evolve here we simply return the value itself because
an integer just evaluates to its value.
Now the more interesting structure that we're going to implement is a binary operation or a binary function.
So a binary operation is an operation like addition or subtraction.
It takes the left hand side and the right hand side and then you define the kind of operator that is
used between the left and right hand side.
Now we're only allowing plus and minus operators for this particular demo.
So let's just stick to that.
So here is a structure called binary operation which is also an element.
And we're going to define the type of the operation.
So it's either going to be addition or subtraction and this is going to be called Type.
And in addition what we'll do is we'll have the left and right hand sides.
Now I'm going to start using smart pointers here simply because the left and right hand sides well we
might want to just pass them around or something.
So shed PDR element the left hand side and right hand side.
There we go.
I'm not going to define a constructor but I will have to define the evaluation code.
So let's implement the evil function and here what we want to do is we want to check the kind of operation
that it is.
So if the type of operation is addition then what we're going to do is we're going to evaluate the left
hand side evaluate the right hand side and add them together.
Otherwise we're going to subtract them.
So let me say Otto left equals left hand side Ebell auto right.
Equals right hand side evolved.
So if type is addition then we'd turn left plus right.
Otherwise we return left minus right.
So fairly obvious stuff here.
OK.
So we have the two structures which are going to participate in the parsing process.
There is no going to be any additional structures.
Notice that the parentheses simply give us hints as to how the operations all involve one another.
They don't actually show up anywhere by themselves so we suddenly have to take care of the parentheses.
That's going to be one of the challenges when parsing but don't make any appearance in the actual code
that we defined for the parsing structures.
So let's have a parse function.
I'll have it returning a shared BVR.
So here is a function called Parus we take a vector of tokens and we need to go through each of the
tokens and return a single operation so we're going to assume that the root of this expression is a
single operation.
In this case in my example as you can see there it is a subtraction because we have the minus at the
very top level.
So the result is always going to be a binary operation.
So make binary operation.
So that's how a result.
Now when we parse the expression we need to parse the left and right hand sides and we need to take
whatever we've parsed and put it either into the left part of the result or the right part of the result
so I'm going to have a boolean flag indicating whether we have already gotten the left hand side.
Initially I said it two fold.
OK so now we can go through each other tokens.
So for it's actually use a bit of cogeneration here to generate the for loop.
So we're going to have an index going from zero to the tokens dot size.
OK.
But I will want to have a reference to the actual tokens so I'll say all Toto can equal tokens at index
I would be putting a reference in here.
OK.
And then I want to first of all find out what kind of token it actually is because the type of token
really determines what we can do with it.
So let's switch on token type.
OK.
Hopefully I can enter and generate the cases here and then we'll go through cases one by one and see
what we can do with them.
OK.
So the first case is an integer.
Now remember we have the token containing a string and we want an actual int.
So what we're going to do is we're going to get the value by using a lexical cast.
So lexical cast to and in off to conduct attacks.
That's what we're going to do.
And then we'll have the actual construction of the integer.
And I'm talking about this integer.
So we we now have a value to supply into the constructor.
So we're going to build one of these and then we're going to store it somewhere.
So Autor integer equals make shared integer with the argument value that we've just received and now
we need to determine where to put it.
So if we don't have the left hand side.
What we do is we said the left hand side.
So a result left hand side equals integer and have left hand side equals true.
Otherwise we said the right hand side result right hand side equals integer.
There we go.
OK so that's the integer part.
And next up what we're going to do is we're going to define the plus the minus operations which are
actually rather simple.
Let me just check what sea lion is saying here applying.
Oh yes the line is wrong on this one.
So let's take care of the plus and minus.
Now this simply determines what kind of operation we get.
So remember we are already working with some result.
So all we have to do is set the type of the operation so we say result type equals binary operation
addition.
And similarly here we set it to subtraction like so.
OK so that was easy.
Now what about the left parenthesis and right parenthesis.
Well first of all we're going to ignore the right parenthesis because when we hit the left we're on
the scene we're going to be looking for the right parentheses.
We're going to be looking for that substring and we're going to be trying to somehow process it with
the with the same invocation of Parr's So we're going to be doing it recursively.
We'll take everything between the round brackets and we'll stick it into parts in order to get our structures
right.
So how do we do this.
Well let me actually put some curly braces in here so we get a scope of sorts.
So what we're going to do is first of all let me copy the value of i into J.
So Jake was I.
And then we're going to have a for loop where we'll.
We're going to be looking for the right parenthesis token So we're going to be trying to find where
the some expression ends.
So imagine we are at this stage where somewhere here.
Well we're going to be looking at we're going to be looking for the closing round bracket.
Now I'm going to ignore the case where you have nested round brackets because that's a more complicated
case and this is something you can do on your own.
So let's have a for loop where we say that g goes up tokens dot size and if we hit the right parenthesis
so if tokens add j dot type is equal to token right parenthesis then we found it.
That's why I declared the variable to be outside the for loop.
So we actually know that we found the location of a closing somewhere.
OK so now that we have a J what we can do is we can basically make another vector which is a sum expression
so we make a vector which essentially contains the tokens.
Let's say we have 13 minus four unbound brackets I will take a vector which contains just this part
and then we feed the vector recursively into the parse function.
The function that we're currently in and we get the results.
So let's do that.
OK so here is a vector of token called subexpression where we start out tokens at I plus 1 and we end
tokens and J.
There we go.
So that's how subexpression what we can do is we can parse this expression so we can say auto element
equals parse subexpression and then what we can do is we can assign this element to either the left
or the right hand side once again so we don't have the left hand side.
And what we can do is we can say result left hand side equals element have left hand side equals true
otherwise result the right hand side equals element and then I'm going just said I to be equal to Jay
so that we advance on the overall loop.
So that's pretty much it.
That's all that we need to do here and what we can now do is we can continue our example and actually
try to well evaluate the whole thing basically.
So one thing we can do is we can stick everything in a try catch loop.
And the reason for that is that remember we're trying to convert numbers into what we're trying to do
with the string representation of numbers into actual numbers.
And this will sometimes fail if you make a mistake so I'll put a try catch in here so we'll say also
parsed equals parsed the tokens so we take the tokens that we got in the previous step here off to the
lexical analysis we get the tokens and we parse them and we get some sort of result.
And when we have the result what we can do is we can see out the evaluated expression so I'll see how
the input itself equals and then parsed the vowel.
And that's the function that actually evaluates the whole thing.
There we go.
And then there is some catch here just some kind of exception that we can see out what went wrong if
if indeed anything.
OK so let's try running this and seeing the complete example in action.
All right so here we are.
Here is the final result and as you can see we got the correct results all the evaluations so we have
13 minus four minus 12 plus 1.
So that's 9 minus 13 that is in fact equal to minus 4.
So this small example has demonstrated how you can build an interpreter process by yourself without
using any external frameworks or libraries.
Not particularly exciting I know but even for such a small interpreter you can see that we've had to
do quite a bit of work to actually separate the tokens that would be the lexing part and then turn those
tokens into some sort of object oriented structure that would be the parsing part.