[D. Evans] The answer is the first one. This is just the number 3.
And we can get 3 from expression by following this rule,
starting from expression, replacing with number,
and then replacing number with the number 3.
The second one is not valid, and the way to see that is if we start from expression,
we only have 3 choices.
We can replace it with expression, operator, expression,
we can replace it with number,
or we can replace it with a left paren, expression, right paren.
Since the expression we're trying to match starts with a left paren,
the only way to get a left paren is to eventually have this rule
that replaces expression with left paren.
When we use that rule what we get is the left paren
followed by expression.
Now we have expression here.
From here we've matched the far left paren and the far right paren.
What we have left is this.
We can replace this expression with paren, expression,
and we have paren that's replacing this expression using this rule,
and then we still have the second right paren that we had before.
This isn't going to match here because we need 2 right parens to match.
And the essence of this rule is that every time we open a parentheses
we have to eventually close it.
We can't produce expressions where the parentheses aren't balanced,
so this is not a valid Python expression.
We can produce the third one
This has many nested expressions.
We have 3 parens that are open, but we have balancing closed parens.
And the way we could derive this expression,
we'll start with 1 expression. That's our starting point.
We use this rule to replace it with paren, expression, paren.
Now we have an expression that starts with a 1,
so we want to replace this expression with expression, operator, expression.
We still have the outer parens that we had before.
Now we're working on this part.
We want to replace this expression with a number and then with the number 1.
We're going to replace the op.
Following the operator it goes to rule. That's going to be replaced with .
And now we've got to replace this expression.
We're trying to produce this whole thing, so we're going to replace this
with using the parentheses rule.
We can keep going.
We're going to replace this expression with expression, operator, expression,
eventually get the 2 and then do that replacement with parens again
to get the 3 4.
I'm not going to fill in all the steps here because they won't fit on the screen,
but I hope you get the basic idea that we can keep doing those replacements,
making complex expressions like this one.
The fourth possibility is not a valid expression.
There's no way that we can get an operator in front with this rule.
There actually are rules in Python that allow us to have an expression go to
operator, expression, but we'd have 2 expressions here if there's a 3 space 3.
If it was just the number 33, this would actually be a valid Python expression--
not something that we can produce with this grammar, though.
And the fifth one is valid.
It's not sensible or necessary to have nested parentheses like this,
but we can always keep using this rule.
So we can derive that expression starting from expression,
using the last rule with the parens.
We're going to end up with paren, expression, paren, closed paren.
We can use that rule again.
We're going to replace the middle expression with expression, paren, expression,
replacing this expression with the last rule.
That will give us expression surrounded by parens,
and we still have the 2 outer parens on each side.
So we can have as many nested parens as we want.
It's not necessary. It doesn't make a lot of sense.
We would never actually want to write code that way,
but it's still a valid Python expression.
Recursive grammar rules like these are very powerful.
We only need a few simple rules to describe a big language,
and the whole Python language that we're going to learn in this course
can be described this way.
We're not going to describe the entire Python language this way,
but what I hope is that you have a good sense for how grammars work
and you can see that even as we introduce constructs somewhat more informally
as we go on that they could be broken down
into these kinds of formal replacement rules.