
Title:
Python Expressions Solution  Intro to Computer Science

Description:

So, the answer is the first one. This is just

a number three. And we can get three from expression

by following this rule. Starting from expression, replacing with number,

and then replacing number with the number three. The second one

is not valid. And the way to see that is

if we start from expression, we only have three 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 it 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 two right

parens to match. And the essence of this rule

is that every time we open a parenthesis we

have to eventually close it. So we can't product

expressions where the parenthesis aren't balanced. So this

is not a valid Python expression. We can

produce the third one, this has many nested

expressions. We have three perens that are open, but

we have balanced and closed perens. And the

way we can derive this expression, we'll start

with one expression that's our starting point. We

use this rule to replace it paren expression, paren.

Now, we have an expression that starts with a one,

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 to

replace this expression with a number and then with the

number one. We're going to replace the Op, the following

operator goes to times rule. That's going to be replaced

with times 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. And we can keep going,

we're going to replace this expression

with expression operator expression. Eventually get

the two times and then do that replacement with parens again,

to get the three times four. And 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 the replacements, making complex expressions like this one. So 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

have two expressions here. There's a three space three. 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 first one is valid It's

not sensible, or necessary, to have er, nested

parentheses like this, but we could always keep using

this rule, so we can derive that expression starting

from expression using the last rule with the parens,

and we're going to end up with paren,

expression, paren, close 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'll give us expression surrounded by parens, and we still have

the two outer parens on each side. So we can have

as many necessary 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. So 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 or placement rules.