English subtitles

← 05xps-01 Parsing States Solution

Get Embed Code
3 Languages

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

  1. Welcome to the Homework 2 solutions.
  2. In this first question we're going to go over how to reason about the state of a chart
  3. when parsing a token in a given grammar.
  4. Right here I have a grammar that identifies JavaScript function calls.
  5. Let's say I have a function, pow, which computes the power of a number
  6. to another number--doesn't really matter.
  7. The idea is that this function computes 5 to the 6th.
  8. But what we care about is the tokens right here.
  9. And to show that this string is in this grammar, we're going to walk through it.
  10. Here I've written our first starting rule, which goes to id, some parentheses,
  11. and then optional arguments.
  12. So the id in this case is pow, and then we have 2 parentheses,
  13. and the optional arguments in the case of our example is 5 and 6.
  14. We don't have to have anything here. As the title implies, it's optional.
  15. It could go right to the empty string. But we do have arguments.
  16. In this case, we're going to have some kind of expression
  17. or an expression followed by a comma with more arguments.
  18. And in this case we have 2, so the optional arguments goes to arguments.
  19. It's not empty, so it's going to go to this rule.
  20. And then from arguments we're going to go to this rule
  21. where expression is going to be 5.
  22. We have the comma. That matches our comma.
  23. The rest of the rule is going to be ARGS, which goes to--
  24. Since this is our last argument, it's just going to go straight to expression, which is 6.
  25. And we were able to match this string to the grammar
  26. using the set of replacement rules given.
  27. So I just went through that to demonstrate how this grammar matches JavaScript function calls.
  28. But that's not really what the question is asking.
  29. The question is asking about the chart.
  30. We're going to see what happens when we parse a certain set of tokens.
  31. Instead of writing the actual string, I just have the tokens that matter.
  32. And for the sake of parsing, that's all we care about.
  33. This can be matched by what I had before.
  34. But all we care about is the tokens.
  35. Now, when we parse this, what we want to ask is
  36. what is in Chart 2, the third entry in our chart?
  37. And so we're given a set of rules that may be in the chart.
  38. I'm just going to go through them real quick. So here are your choices.
  39. We're trying to figure out--as a reminder--what's in the second entry in our chart
  40. when we parse this list of tokens and this grammar.
  41. And since we're asking a question, we should remember question marks.
  42. So there's really 2 ways to solve this.
  43. The first is you work out the chart by hand.
  44. That's what we're going to do because it's easier to kind of explain what's going on.
  45. An alternative which is equally valid is to take the code that we wrote in lecture
  46. and modify it to print the chart at every given state.
  47. This is probably what you would want to do if you were asked this question more than once.
  48. But, like I said, for the sake of going over the answer, we're going to work it out by hand.
  49. Okay. Here's our input. Here is our grammar.
  50. We want to know what's in Chart 0.
  51. We haven't read anything in yet, so we're just going to be at the beginning
  52. of the start substitution rule.
  53. We introduced this in Chart State 0.
  54. So now we're on Chart 1 and we've read in 1 token, id.
  55. We're just going to shift on this rule because id is the first token in this rule.
  56. And this comes from 0 as well.
  57. So now the moment of truth, Chart 2.
  58. Let's see what we can do.
  59. We're going to see the token--that's the left parenthesis--and we're going to shift.
  60. So here there are 2 things that are possible.
  61. One is that optional arguments is empty.
  62. We don't know yet because we haven't seen the rest of the input token list.
  63. In that case, we're going to be past optional arguments.
  64. There's also the case where optional arguments isn't empty,
  65. which is actually what's going on with our input list.
  66. So let's write both those out.
  67. Here we've moved past optional arguments,
  68. presumably because it's empty by this rule right here.
  69. Then we have the other choice where optional arguments is not empty
  70. and we're going to be processing it.
  71. So regarding this first rule in our chart, we have the optional arguments being empty.
  72. So we need to make sure to add that.
  73. We introduced this in Chart State 2.
  74. We have the other case where optional arguments is not empty,
  75. and we're going to go through ARGS now.
  76. So I have written out both ARGS rules,
  77. and since we haven't read in this next token, we don't have anything
  78. to go further on in either rule,
  79. so at the beginning of each rule.
  80. And presumably, the next chart state we will shift over with the new expression.
  81. So now we have everything we need to answer the question.
  82. We're just going to check off the choices that were in our Chart State 2.