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