## ← Discerning the Grammar Solution - Programming Languages

• 2 Followers
• 32 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=hp6UKZSRGMk" data-team="udacity"></div> ``` 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.