English subtitles

← 03-32 To The Rescue

dummy description

Get Embed Code
3 Languages

Showing Revision 1 created 05/04/2012 by Amara Bot.

  1. As the previous example suggests, we can use parentheses to control ambiguity.
  2. Here I've taken our expression grammar from before and updated it with a new rewrite rule.
  3. Now expression can be replaced by open parentheses, expression, close parentheses.
  4. This should totally remind us up the P goes to open P close rule from before for balanced parentheses.
  5. It's going to behave mostly the same way.
  6. With this new grammar, both of these utterances--
  7. open 1 minus 2 plus 3 and 1 minus open 2 plus 3 close--
  8. both of them are in the language of this grammar.
  9. However, while both of these are okay, so is this one.
  10. It doesn't forbid the ambiguous one.
  11. It just allows us to have more precise renditions.
  12. We've solved some of the problem.
  13. If we're thinking ahead, we can use parentheses, but we're still allowing ambiguous phrasing.
  14. Here I've drawn our favorite utterance from before--1 minus 2 plus 3--
  15. and I've written out two different parse trees for it.
  16. This one corresponds to 1 minus 2 plus 3.
  17. At the top level we're subtracting, and then the 2 plus 3 are grouped together.
  18. This one corresponds to 1 minus 2 plus 3.
  19. At the top level we're adding, and the 1 minus 2 is grouped together.
  20. Formally, we say that a grammar is ambiguous if there is at least one string in it--
  21. 1 minus 2 plus 3 and that single string has more than one parse tree.
  22. Here I've drawn very stylized versions of the parse trees.
  23. If you can find even one string for which this is true,
  24. officially the whole grammar is ambiguous.