Welcome back, guys! So by this moment we may handle multiple statements and multiple
expressions but so far our literals are pretty much useless, for example the number 42 - we
cannot do anything with this number, and the first operation which we can start doing
are the mathematical operations. So in today's lecture we'll talk about binary expressions,
specifically about additive expression, multiplicative, and also about primary expression.
And let's start away from the test, I'm writing the math-test, okay for mathematical expressions,
and let's do the program "2 + 2". Such expression is known as a Binary Expression. What is binary
expression? - it has two operands: the left-hand side and the right-hand side.
In this case the left-hand side and right-hand side are both numeric literals so that's the
simplest binary expression. As you can see we also captured the operator of this binary expression
and in this case it's "+". And we also may have chained binary expressions, for example
"3 + 2 + 2" and from the first glance it might seem it's not a binary expression, right since we
have here three operands, but in fact it's still the binary expression. In fact, if we take a look
the left hand side here is just the complex expression itself and also the binary expression,
that's pretty much it. And we should also say that in math the "+" operator is left-associative. What
this means is, this expression should look as "3 + 2" and only after that "+ 2", right so
if we use parenthesis it would look like this. Now with the "+" operator it doesn't make much
difference but it can make difference for the minus "-" operator, for example if we put
minus here this might change semantics. So the AST note for this program should be
the minus "-" operator, which left hand side is the complex expression itself
and it's still the binary expression with a plus "+" operator "3 + 2" and "- 2".
Sounds great, and let's again put here the left hand side is "3 + 2" and right "2", okay
so let's go ahead and implement this. And if we take a look again at the expression
"2 + 2", we see that the literals here that is 2 and 2 has the higher precedence than
the "+" operator itself, that is in order to evaluate the binary expression that is the sum,
we have to first go and evaluate its operands which might be arbitrary complex. So going back
to our Expression, we're going to refactor it, currently as you see it returns the Literal but
in fact it will return the AdditiveExpression that is the sum, "+" operator or the "-" and as we said
the Literal should go inside the Additive that is the Literal has the higher precedence
than the Additive. We should also say the rule: the closer production is to
the starting symbol - in this case to the Expression - the lower precedence it has.
Since here the AdditiveExpression is directly returned from the Expression this means the
Additive has the lower precedence than the Literal which is not returned directly from the
Expression, and again here we use the recursive rule,
the AdditiveExpression is either one Literal, and this will allow propagating to just one number,
or it might be the actual "+" operator or the "-" and let's call it ADDITIVE_OPERATOR,
so it might be multiple literals separated by the "+" or "-" and again as we said we
don't work with left recursion so basically we rewrite it and expand to Literal + Literal.
So the way it works is, we first parse the left hand side which is Literal and then depending
whether we have "+" as the lookahead, right we obtain the operator, we may go and parse
the right hand side if it's present, and since we need to have the chained binary expressions,
this should be a while loop, right while the lookahead is the ADDITIVE_OPERATOR, first of all
we're going to consume the operator, right and then we're going to parse the right hand side.
What is the right hand side here? - well it's again the Literal. And as we said, we also need
to enforce a left-associativity, that is the left hand side if it's the complex expression
is recursively becoming the left-hand side of each sub-expression. And then we just return
the the topmost left-hand side which again either will be just the Literal or the BinaryExpression.
Sounds great, let's add our math test to the test runner, let's execute and yes - correctly
it says the "+" token is not supported in the tokenizer, so let's go ahead and add it,
okay so I'm adding the mathematical operators, "+" and "-" and just have the ADDITIVE_OPERATOR,
okay let's get back and execute - and still have some issue, let's see,
oh we actually have to take the value of the "+" token, not the token itself but just the value,
so the additive operator that value which will be the "+", okay let's execute, and yes - now it's
passed. So congratulations, we now have the "+" operator and it might be chained. Now let's check
that the single number still works, right when we go to Additive and the to the first sub production
which is just Literal, and that should be also returned, and yes - as we can see for the "2".
Let's manually test the addition "42 + 23", yes - we got the BinaryExpression. Let's
chain it "42 + 23 - 10", and yes - as you can see the left hand side here is the complex expression
that is we've got left associative operators. Okay, sounds great, but also we may use
multiplication "2 + 2 * 2" which in this case should gives us the answer 6 because
the multiplication has the higher precedence than the "+" and in this case the evaluation
would be first the right hand side, again because of the higher precedence. So let's go ahead and
add the MULTIPLICATIVE_OPERATOR right away to the tokenizer, sounds great and let's write the test
"2 + 2 * 2" again take a look at the precedence, the "+" correctly has the lower precedence that
is before we are able to evaluate "+" we have to go first and evaluate the left hand side and right
hand side, and the right hand side here is the "*" operator right that is the "*" will be evaluated
first that's why it has the higher precedence. Let's do the simple test "2 * 2" which is just
the binary, and let's also show when we have the same precedence that is "2 * 2 * 2" we still got
the left-associative "*" so the left hand side here should be the binary of the "*" operator.
Sounds great, let's take a look again at the expression "2 + 2 * 2" - so previously the
operands of the "+" were just the literals but in this case the operands of the "+" operator
would be the MultiplicativeExpression, right we first need to evaluate "2 * 2" and that would be
exactly the operand for the "+", so let's get back to AdditiveExpression and refactor it,
right the AdditiveExpression will be either the Multiplicative
or multiple MultiplicativeExpression, and the MultiplicativeExpression itself
would be exactly the same, right it would be accepting the Literal
but let's actually call it PrimaryExpression because besides the literals we will have some
other primary expressions. And once again it's exactly the same handling just we get
the MULTIPLICATIVE_OPERATOR and parse the PrimaryExpression. And for now let's keep
the PrimaryExpression as just the Literal. Sounds great, okay let's get back to test and execute,
and yes - it works. So take a look at the "+" operator here, it has lower precedence
which is correct that is the right hand side here the complex multiplicative expression
which is also binary, let's put "2 * 2 * 2", in this case the left hand side here
should be the complex expression because of the same precedence, and that is exactly correct.
But also in mathematical expression we may put grouping parentheses and in this case they have
higher precedence than the "*" operator, that is evaluation of this example which gives us 8
instead of 6, right we first do "(2 + 2)" and only after that "* 2" so let's go ahead and execute,
and correctly it says parentheses "(" ")" are not supported, let's go ahead and add them
to the tokenizer, right open parenthesis "(" and the closing parenthesis ")"
and let's also add the test, all right so "(2 + 2) * 2" should be the left hand side the complex
expression all right for the "+" operator and the right hand side is just the literal.
And those grouping parentheses, let's call them ParenthesizedExpression
would be exactly the PrimaryExpression, right this is how we achieve the ParenthesizedExpression and
the Literal to have the higher precedent than the MultiplicativeExpression,
and again here we got the help from our lookahead token, right since we build predictive parsing,
so if the lookahead is the open parenthesis "(" we have to parse ParenthesizedExpression, otherwise
let's default it just to Literal yet, and later we will add more primary expressions. Sounds great,
so what is ParenthesizedExpression? - well it should start with the open parenthesis "(" and
should be closed with the closing parenthesis ")" What is inside? - inside may go any expression,
right the very basic Expression, it might be Additive, Multiplicative or just a simple number,
so it's the very basic Expression itself. And the way we handle it is pretty much simple,
right we just eat the open parenthesis "(" then we parse the Expression, and eat the closing
parenthesis ")" As the result we do not return an explicit AST node but just the expression which is
inside the group in parentheses. What this means is, inside the AST we will not see any grouping
parentheses but we will see correct precedence which this parentheses enforced. And that should
be pretty much it, let's get back and execute, and yes - now we got correctly the "+" operator
has the higher precedence just because it was put into grouping parentheses. Let's return back
and again the "*" has the higher precedence. Let's also show that inside the grouping parentheses we
may have any expression, for example simple number, okay it works, or for example "2 + 2"
and it also works, and again as you can see there are no any grouping parentheses in the AST
but there is correct precedence. Sounds great, now we have mathematical expressions
which is pretty cool. One slight thing, if we take a look at the AdditiveExpression and
into Multiplicative - they handle pretty much very similar, right so let's slightly
refactor and move the same parts into helper function, let's call it "_BinaryExpression",
the only difference is, the AdditiveExpression builds the
Multiplicative and consumes the ADDITIVE_OPERATOR and MultiplicativeExpression builds the Primary
and consume MULTIPLICATIVE_OPERATOR, so the helper function would consume the actual builder name
and the operator and we will just dynamically call the builder and the operator is passed
from the parameter. And now we may refactor the Multiplicative to be the Binary which constructs
PrimaryExpression separated by the MULTIPLICATIVE_OPERATOR, with the
same success we factor the AdditiveExpression which again constructs the BinaryExpression
consisting of MultiplicativeExpression separated by ADDITIVE_OPERATOR. Okay, looks nice and clear,
let's go ahead and do some extra tests, let's execute, and yes - it works. So to reiterate,
we now have mathematical expressions which already makes our language more useful.
However we still cannot store these expressions anywhere. So in the next lectures we'll start
introducing variables and assignment expressions. That's it for today, thanks and see in the class.