Understanding Ambiguity in If-Else Grammars: An Explanation and Analysis

[SpiffyEh]

Homework Statement

Consider the following If-Else Grammar:


<stmt> => if <expr> then <stmt>

| if <expr> then <stmt> else <stmt>
| ... (assume other types of <stmt>s, not part of exercise


Show that this grammar is ambiguous.

Homework Equations

The Attempt at a Solution

I don't really understand what ambiguous means, I have the definition

A grammar is ambiguous if and only if it generates two or more distinct parse trees of same type (derivation) for same sentence

But I don't see how this works. Can someone please explain to me how this grammer could generate 2 or more distinct parse trees for the same derivation of a sentence? I just don't see how it could.

 

[Hurkyl]

Have you tried generating sentences using these production rule, to get an idea for the grammar?


(I suppose you can't actually generate a sentence, but you can at least generate various intermediates)

 

[SpiffyEh]

all i can generate is an if then and an if then else

 

[Hurkyl]

Ah, that isn't all you can produce from a <stmt> symbol! Each of the two things you produced have more <stmt> symbols in them, so you can produce more than just two intermediates from <stmt> using those two production rules.

 

[SpiffyEh]

umm.. I can produce, if then if then as many times as needed, or if then if then... else or if then else if then else... and so on?

 

[Hurkyl]

It's probably worth trying to play with the production rules in systematic and/or creative ways, to see what can be produced. Experimentation is often useful when faced with something new.

(Also, if you do wind up enumerating all short ways of applying the production rules a small number of times, you will stumble across an example of the ambiguity -- this particular ambiguity is relatively simple)

 

[SpiffyEh]

I don't understand what you mean, by if you do wind up enumerating all short ways of applying the production rules a small number of times, you will stumble across an example of the ambiguity.
I was never actually given an example fo ambiguity so I'm confusedm from the defination it seems that if i can come up with two different ways of coming up with the same sentence its ambiguous? But I don't see how I would do that

 

[Hurkyl]

from the defination it seems that if i can come up with two different ways of coming up with the same sentence its ambiguous?

Right. If you go through and apply the production rules in different ways and get the same sentence, it's an example of ambiguity.

Technically you're going to produce the same intermediate in two different ways (because you don't have a production rule that turns intermediate symbols into final symbols), but that's good enough for this exercise.

But I don't see how I would do that

That's why I said "stumble" rather than "proceed knowing exactly how things are going to work out"!

 

[SpiffyEh]

<stmt> => if <expr> then <stmt>
=> if <expr> then if <expr> then <stmt> else <stmt>

and

<stmt> => if <expr> then <stmt> else <stmt>
=> if <expr> then if <expr> then <stmt> else <stmt>


I got those two, they go two differnt routes but end up the same.
Now I need to rewrite the grammar to remove the ambiguity.
I came up with:
<stmt> => if <expr> then <block>

<block> => <stmt>
| <stmt> else <stmt>

 

[Hurkyl]

When you say rewrite the grammar, do you mean that it should generate exactly the same sentences? Some programming languages deal with the ambiguity by changing things a bit; e.g.

<stmt> => if <expr> then <stmt> else <stmt> end if​

Anyways, have you tried generating strings from your new grammar in systematic and creative ways? I grant that it's obvious anything from the original grammar can be generated, but does your grammar allow new strings the original didn't?

 

[SpiffyEh]

When you say rewrite the grammar, do you mean that it should generate exactly the same sentences??

I'm not exactly sure, that's all I was told by the assignment.

Some programming languages deal with the ambiguity by changing things a bit; e.g.

<stmt> => if <expr> then <stmt> else <stmt> end if​

Anyways, have you tried generating strings from your new grammar in systematic and creative ways? I grant that it's obvious anything from the original grammar can be generated, but does your grammar allow new strings the original didn't?

I don't see it allowing anything else

 

[Hurkyl]

I don't see it allowing anything else

I think you're right on this point. (I made an error earlier)

Now the real test... is your example free of ambiguity? It contains pretty much exactly the same ambiguity as the original one, doesn't it?

 

[SpiffyEh]

hmm... I'm not sure what can be done to make it not have any