English subtitles

← 04xps-03 Making Ambiguity Solution

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. Here we have a grammar that represents some made-up language,
  2. kind of a cross between--I don't know--Python and JavaScript.
  3. It has a lot of keywords that are found in a lot of languages.
  4. Let's say we add a new rule.
  5. The question we need to answer is whether adding this new rule to this grammar
  6. creates an ambiguous grammar.
  7. As a reminder, an ambiguous grammar is one that given a string in that language,
  8. there are 2 parse trees, there are 2 ways to traverse the grammar and create that string.
  9. As we'll see later, this is really bad for languages that we want to interpret
  10. because it can result in the situation where 1 string, 1 program,
  11. 1 HTML document has 2 valid meanings.
  12. And so you can't really choose one,
  13. and that's not what we like.
  14. We use these precise languages such as HTML and JavaScript
  15. so that we know exactly what we want to be displayed
  16. or the exact actions that we want to be performed. We don't want ambiguity.
  17. Computers don't handle ambiguity very well. Their little brains explode.
  18. We can sit and stare and think about this for a while,
  19. but I'll just give you an example string that actually shows that adding this rule
  20. makes the grammar ambiguous.
  21. That gets us a check. Let's go over that.
  22. Here I have the string, and what we need to do is show that there's 2 ways
  23. using this grammar to generate the string.
  24. One way is using the if-then-else construct
  25. where this if, this then, and this else match here, here, and here.
  26. That means this part of the string corresponds to this C,
  27. this one goes here, and this one is from the E right there. That's 1 way to do it.
  28. The second way is using the if-then, do these 2 symbols,
  29. and then the if-then-else here,
  30. meaning that this corresponds to that S,
  31. this corresponds to that E,
  32. and then we have an if-then-else as that S.
  33. So here's 2 valid ways using this grammar to generate the same string.
  34. This shows that the grammar is ambiguous when we add this rule.
  35. Let's do another.
  36. Let's say we add this rule.
  37. B goes to a B and then a B.
  38. This is also ambiguous.
  39. Say we have print 4; print 4.
  40. So now we have 2 ways to create this.
  41. One way is to start with a B.
  42. From there we go to S and B.
  43. From here we can do print 4.
  44. We can replace the B--oh, I forgot to add that.
  45. We can replace the S with the print 4.
  46. An alternative way is basically do something very similar
  47. where we start with the B and we go to B B,
  48. but this time we replace each B with the S;
  49. That's our second way.
  50. Here there are 2 more rules.
  51. Neither of these rules makes the grammar ambiguous.
  52. When we add the keyword int, this is the only way to get an int.
  53. So there's not going to be a second way to generate strings with int.
  54. The same basic logic applies to the parentheses as well.
  55. This is the only way I have parentheses,
  56. and there's not going to be a second way there.
  57. All it does is add parentheses on the outside of a statement.
  58. And we can do it as many times as we want,
  59. but given x number of parentheses, you just apply this x number of times.
  60. Not a whole lot of fancy stuff going here.
  61. The fact that they match also is kind of a key contributor to this.
  62. If you had a parenthesis on 1 side and you had another rule with the other side,
  63. then you could maybe get some ambiguity depending on how you word it.
  64. But that's how this is. Let's go on to the last one.
  65. This should look familiar.
  66. I believe we went over this in lecture or something very similar to this,
  67. and this is definitely ambiguous.
  68. I'll come up with 1 example.
  69. Say we have 1 + 2 + 3. We can do this in 2 ways.
  70. We have E goes to E + E goes to 1, and this eventually goes to 2 + 3.
  71. An alternative way is that we have the 2 on the left-hand side and then we have the 3.
  72. Although the meaning of a plus, the associativity of addition
  73. allows us to do it in any order, from the perspective of a language of strings,
  74. perspective of determining whether or not the context-free grammar is ambiguous,
  75. the meaning of a plus is irrelevant here.