English subtitles

← Discerning the Grammar Solution - Programming Languages

Get Embed Code
2 Languages

Showing Revision 5 created 05/25/2016 by Udacity Robot.

  1. In this problem, we're given an input string and
  2. the parse chart that was created from parsing that string.
  3. And we're tasked with finding the grammar on which
  4. that token was parsed. So let's look at the problem.
  5. Here we have the given string, and here we
  6. have the parse chart. Our strategy is going to go
  7. through each line of the parse chart and look through
  8. the rules that explicitly appear for the first time. Say,
  9. this one right here that indicates E goes
  10. to parenthesis E parenthesis, is explicitly in the
  11. grammar. Add those to the grammar. Run the
  12. parsing algorithm. And then we're going to see if
  13. using that grammar on this token generates this
  14. exact parse chart. So let's get started. Looking at
  15. chart state zero, we see six rules right here. Each of these six rules has to be
  16. in the grammar because no tokens have been read, and we're at
  17. the beginning of each of them. So let's add those to the
  18. grammar. Okay, here's the six rules we were given in the first
  19. state of the parsing chart. And if we run this through our parser,
  20. we'll see the chart that it generates is not exactly the same.
  21. So we're missing something. Let's keep going. Here, we have the continuation of
  22. five rules. And if you look closely, there are no new rules
  23. here. These are all just shifts of the rules that we found in
  24. chart state zero. The minus comes from the minus, the
  25. plus comes form the plus, and so on. So let's
  26. move on to chart two. Here we go. A goes
  27. to nothing, that's new. A goes to NA, also new. And
  28. lastly, we have the two rule, two rules for NA.
  29. So let's put that into our grammar. If we run
  30. this grammar in our parser with that token, we'll see
  31. that we get the same exact chart that we were given,
  32. meaning that we found the answer.