English subtitles

← 04-25 Computing The Closure Solution

dummy description

Get Embed Code
3 Languages

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

  1. Let's take a look at the answers together,
  2. It's going to turn out that we'll be able to compute this, fairly systematically,
  3. just by remembering the rule for how to compute the closure.
  4. We have a dot in front of the nonterminal E,
  5. so I go over to our grammar
  6. and find all of the rules that start with nonterminal E.
  7. And there are 3 of them, and I'm going to add all of them to chart[2]
  8. with a red dot right at the beginning and a from2--
  9. because that's where we currently are--1, 2--
  10. as they are little provenance information off here, to the right.
  11. So one of our rules is:
  12. (E --> int)
  13. so we will definitely add (E --> dot int from2).
  14. Again, the from2 is because we brought in
  15. or we computed the closure, starting in state[2].
  16. Another possible rule is:
  17. E --> (F).
  18. So (E --> dot (F), coming from position 2)
  19. is a valid prediction we might make.
  20. We might see parentheses right after seeing a minus sign; that's valid for this language.
  21. Now our third rule is: (E --> E - E)
  22. so this option may look very tempting.
  23. It's got the (E - E).
  24. It's got the dot in the front, but it has the wrong (from) state information.
  25. It's included from0 instead of from2.
  26. We need to remember these 2 tokens we've seen previously--the (E) and the (-).
  27. We need to know which state we were in
  28. when we decided to take the closure.
  29. This one is not correct.
  30. Over here we see one that's very similar:
  31. (E --> E - E, with a dot in front).
  32. That's very good; it's a rule that starts with (E),
  33. and we need to start with (E) because the dot is before the (E).
  34. And this one correctly has from2.
  35. We computed the closure in chart[2].
  36. And finally, this one's a bit of a ringer--
  37. it has (F --> dot string from2).
  38. Well, the from2 looks pretty good; the dot at the beginning looks very good.
  39. But our rule is: since this dot was before an (E),
  40. we take all the grammar rules that start with (E)
  41. on the left-hand side, and that's it.
  42. So (F --> string)--that's out of place.
  43. I'm not going to predict seeing a string
  44. until I've seen an open parenthesis.
  45. If you think about this grammar,
  46. the only way to get to string is after an open parenthesis.
  47. I haven't seen one of those, so this is a bad prediction.