YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 04-22 Building The Chart

dummy description

Get Embed Code
3 Languages

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

  1. It turns out that if we could just build this chart correctly--
  2. and that's not going to be easy, but it's going to within our power--
  3. then we've solved parsing.
  4. Let's say that our grammar has some special start symbol S.
  5. So goes to E, and then E could be many things.
  6. The state we really want to be in is this one.
  7. I have seen everything. S goes to E, and there's nothing more. We are totally done.
  8. I mentioned before that we have to augment all of our parse states with this starting add information.
  9. Just to be a little more specific, I have seen S goes to E,
  10. and there was no additional previous information.
  11. Starting from zero tokens of input,
  12. I have seen enough to make the judgement S goes to E based on this input string.
  13. So if the input is T tokens long, we just look to see if S goes to E dot starting at zero
  14. is in chart T.
  15. If it is, our input is in the language of the grammar.
  16. If it's not, our input is not.
  17. Parsing totally solved assuming we can build the chart,
  18. but building the chart is going to be tricky--tricky but possible.