1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Ambiguity in grammars?

  1. Sep 4, 2010 #1
    1. The problem statement, all variables and given/known data

    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.


    2. Relevant equations



    3. 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.
     
  2. jcsd
  3. Sep 4, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  4. Sep 4, 2010 #3
    all i can generate is an if then and an if then else
     
  5. Sep 4, 2010 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  6. Sep 4, 2010 #5
    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?
     
  7. Sep 4, 2010 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  8. Sep 4, 2010 #7
    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
     
  9. Sep 4, 2010 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

    That's why I said "stumble" rather than "proceed knowing exactly how things are going to work out"!
     
  10. Sep 4, 2010 #9
    <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>
     
  11. Sep 4, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  12. Sep 4, 2010 #11
    I'm not exactly sure, thats all I was told by the assignment.
    I don't see it allowing anything else
     
  13. Sep 4, 2010 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  14. Sep 4, 2010 #13
    hmm... i'm not sure what can be done to make it not have any
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Ambiguity in grammars?
  1. Ambiguous questions (Replies: 2)

  2. Context-Free Grammar (Replies: 3)

Loading...