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

1. Title:
   05xps-01 Parsing States Solution
2. Description:

3. 0 0:00 - 0:02
   Welcome to the Homework 2 solutions.
4. 2000 0:02 - 0:06
   In this first question we're going to go over how to reason about the state of a chart
5. 6000 0:06 - 0:09
   when parsing a token in a given grammar.
6. 9000 0:09 - 0:13
   Right here I have a grammar that identifies JavaScript function calls.
7. 13000 0:13 - 0:18
   Let's say I have a function, pow, which computes the power of a number
8. 18000 0:18 - 0:20
   to another number--doesn't really matter.
9. 20000 0:20 - 0:23
   The idea is that this function computes 5 to the 6th.
10. 23000 0:23 - 0:27
    But what we care about is the tokens right here.
11. 27000 0:27 - 0:30
    And to show that this string is in this grammar, we're going to walk through it.
12. 30000 0:30 - 0:35
    Here I've written our first starting rule, which goes to id, some parentheses,
13. 35000 0:35 - 0:37
    and then optional arguments.
14. 37000 0:37 - 0:41
    So the id in this case is pow, and then we have 2 parentheses,
15. 41000 0:41 - 0:45
    and the optional arguments in the case of our example is 5 and 6.
16. 45000 0:45 - 0:48
    We don't have to have anything here. As the title implies, it's optional.
17. 48000 0:48 - 0:51
    It could go right to the empty string. But we do have arguments.
18. 51000 0:51 - 0:54
    In this case, we're going to have some kind of expression
19. 54000 0:54 - 0:58
    or an expression followed by a comma with more arguments.
20. 58000 0:58 - 1:02
    And in this case we have 2, so the optional arguments goes to arguments.
21. 62000 1:02 - 1:04
    It's not empty, so it's going to go to this rule.
22. 64000 1:04 - 1:08
    And then from arguments we're going to go to this rule
23. 68000 1:08 - 1:10
    where expression is going to be 5.
24. 70000 1:10 - 1:12
    We have the comma. That matches our comma.
25. 72000 1:12 - 1:16
    The rest of the rule is going to be ARGS, which goes to--
26. 76000 1:16 - 1:21
    Since this is our last argument, it's just going to go straight to expression, which is 6.
27. 81000 1:21 - 1:25
    And we were able to match this string to the grammar
28. 85000 1:25 - 1:28
    using the set of replacement rules given.
29. 88000 1:28 - 1:33
    So I just went through that to demonstrate how this grammar matches JavaScript function calls.
30. 93000 1:33 - 1:35
    But that's not really what the question is asking.
31. 95000 1:35 - 1:38
    The question is asking about the chart.
32. 98000 1:38 - 1:43
    We're going to see what happens when we parse a certain set of tokens.
33. 103000 1:43 - 1:46
    Instead of writing the actual string, I just have the tokens that matter.
34. 106000 1:46 - 1:49
    And for the sake of parsing, that's all we care about.
35. 109000 1:49 - 1:51
    This can be matched by what I had before.
36. 111000 1:51 - 1:54
    But all we care about is the tokens.
37. 114000 1:54 - 1:57
    Now, when we parse this, what we want to ask is
38. 117000 1:57 - 2:01
    what is in Chart 2, the third entry in our chart?
39. 121000 2:01 - 2:05
    And so we're given a set of rules that may be in the chart.
40. 125000 2:05 - 2:08
    I'm just going to go through them real quick. So here are your choices.
41. 128000 2:08 - 2:12
    We're trying to figure out--as a reminder--what's in the second entry in our chart
42. 132000 2:12 - 2:17
    when we parse this list of tokens and this grammar.
43. 137000 2:17 - 2:20
    And since we're asking a question, we should remember question marks.
44. 140000 2:20 - 2:22
    So there's really 2 ways to solve this.
45. 142000 2:22 - 2:26
    The first is you work out the chart by hand.
46. 146000 2:26 - 2:29
    That's what we're going to do because it's easier to kind of explain what's going on.
47. 149000 2:29 - 2:34
    An alternative which is equally valid is to take the code that we wrote in lecture
48. 154000 2:34 - 2:37
    and modify it to print the chart at every given state.
49. 157000 2:37 - 2:41
    This is probably what you would want to do if you were asked this question more than once.
50. 161000 2:41 - 2:46
    But, like I said, for the sake of going over the answer, we're going to work it out by hand.
51. 166000 2:46 - 2:48
    Okay. Here's our input. Here is our grammar.
52. 168000 2:48 - 2:51
    We want to know what's in Chart 0.
53. 171000 2:51 - 2:54
    We haven't read anything in yet, so we're just going to be at the beginning
54. 174000 2:54 - 2:57
    of the start substitution rule.
55. 177000 2:57 - 3:02
    We introduced this in Chart State 0.
56. 182000 3:02 - 3:06
    So now we're on Chart 1 and we've read in 1 token, id.
57. 186000 3:06 - 3:11
    We're just going to shift on this rule because id is the first token in this rule.
58. 191000 3:11 - 3:14
    And this comes from 0 as well.
59. 194000 3:14 - 3:18
    So now the moment of truth, Chart 2.
60. 198000 3:18 - 3:20
    Let's see what we can do.
61. 200000 3:20 - 3:24
    We're going to see the token--that's the left parenthesis--and we're going to shift.
62. 204000 3:24 - 3:27
    So here there are 2 things that are possible.
63. 207000 3:27 - 3:30
    One is that optional arguments is empty.
64. 210000 3:30 - 3:34
    We don't know yet because we haven't seen the rest of the input token list.
65. 214000 3:34 - 3:37
    In that case, we're going to be past optional arguments.
66. 217000 3:37 - 3:40
    There's also the case where optional arguments isn't empty,
67. 220000 3:40 - 3:43
    which is actually what's going on with our input list.
68. 223000 3:43 - 3:45
    So let's write both those out.
69. 225000 3:45 - 3:48
    Here we've moved past optional arguments,
70. 228000 3:48 - 3:51
    presumably because it's empty by this rule right here.
71. 231000 3:51 - 3:55
    Then we have the other choice where optional arguments is not empty
72. 235000 3:55 - 3:57
    and we're going to be processing it.
73. 237000 3:57 - 4:03
    So regarding this first rule in our chart, we have the optional arguments being empty.
74. 243000 4:03 - 4:05
    So we need to make sure to add that.
75. 245000 4:05 - 4:07
    We introduced this in Chart State 2.
76. 247000 4:07 - 4:10
    We have the other case where optional arguments is not empty,
77. 250000 4:10 - 4:12
    and we're going to go through ARGS now.
78. 252000 4:12 - 4:15
    So I have written out both ARGS rules,
79. 255000 4:15 - 4:17
    and since we haven't read in this next token, we don't have anything
80. 257000 4:17 - 4:19
    to go further on in either rule,
81. 259000 4:19 - 4:21
    so at the beginning of each rule.
82. 261000 4:21 - 4:28
    And presumably, the next chart state we will shift over with the new expression.
83. 268000 4:28 - 4:32
    So now we have everything we need to answer the question.
84. 272000 4:32 -
    We're just going to check off the choices that were in our Chart State 2.