
Title:
04xps03 Making Ambiguity Solution

Description:

Here we have a grammar that represents some madeup language,

kind of a cross betweenI don't knowPython and JavaScript.

It has a lot of keywords that are found in a lot of languages.

Let's say we add a new rule.

The question we need to answer is whether adding this new rule to this grammar

creates an ambiguous grammar.

As a reminder, an ambiguous grammar is one that given a string in that language,

there are 2 parse trees, there are 2 ways to traverse the grammar and create that string.

As we'll see later, this is really bad for languages that we want to interpret

because it can result in the situation where 1 string, 1 program,

1 HTML document has 2 valid meanings.

And so you can't really choose one,

and that's not what we like.

We use these precise languages such as HTML and JavaScript

so that we know exactly what we want to be displayed

or the exact actions that we want to be performed. We don't want ambiguity.

Computers don't handle ambiguity very well. Their little brains explode.

We can sit and stare and think about this for a while,

but I'll just give you an example string that actually shows that adding this rule

makes the grammar ambiguous.

That gets us a check. Let's go over that.

Here I have the string, and what we need to do is show that there's 2 ways

using this grammar to generate the string.

One way is using the ifthenelse construct

where this if, this then, and this else match here, here, and here.

That means this part of the string corresponds to this C,

this one goes here, and this one is from the E right there. That's 1 way to do it.

The second way is using the ifthen, do these 2 symbols,

and then the ifthenelse here,

meaning that this corresponds to that S,

this corresponds to that E,

and then we have an ifthenelse as that S.

So here's 2 valid ways using this grammar to generate the same string.

This shows that the grammar is ambiguous when we add this rule.

Let's do another.

Let's say we add this rule.

B goes to a B and then a B.

This is also ambiguous.

Say we have print 4; print 4.

So now we have 2 ways to create this.

One way is to start with a B.

From there we go to S and B.

From here we can do print 4.

We can replace the Boh, I forgot to add that.

We can replace the S with the print 4.

An alternative way is basically do something very similar

where we start with the B and we go to B B,

but this time we replace each B with the S;

That's our second way.

Here there are 2 more rules.

Neither of these rules makes the grammar ambiguous.

When we add the keyword int, this is the only way to get an int.

So there's not going to be a second way to generate strings with int.

The same basic logic applies to the parentheses as well.

This is the only way I have parentheses,

and there's not going to be a second way there.

All it does is add parentheses on the outside of a statement.

And we can do it as many times as we want,

but given x number of parentheses, you just apply this x number of times.

Not a whole lot of fancy stuff going here.

The fact that they match also is kind of a key contributor to this.

If you had a parenthesis on 1 side and you had another rule with the other side,

then you could maybe get some ambiguity depending on how you word it.

But that's how this is. Let's go on to the last one.

This should look familiar.

I believe we went over this in lecture or something very similar to this,

and this is definitely ambiguous.

I'll come up with 1 example.

Say we have 1 + 2 + 3. We can do this in 2 ways.

We have E goes to E + E goes to 1, and this eventually goes to 2 + 3.

An alternative way is that we have the 2 on the lefthand side and then we have the 3.

Although the meaning of a plus, the associativity of addition

allows us to do it in any order, from the perspective of a language of strings,

perspective of determining whether or not the contextfree grammar is ambiguous,

the meaning of a plus is irrelevant here.