1 00:00:02,780 --> 00:00:08,773 In this video, we're going to use our example automaton for recognizing viable 2 00:00:08,773 --> 00:00:16,861 prefixes, to introduce one more idea, The idea of a valid item. To refresh your 3 00:00:16,861 --> 00:00:20,569 memory, here's where we left off last time. This is the complete 4 00:00:20,569 --> 00:00:25,630 nondeterministic automaton for recognizing the viable prefixes of the example grammar 5 00:00:25,630 --> 00:00:30,517 [sound]. And Using the standard subset of states construction, we can build a 6 00:00:30,517 --> 00:00:35,424 deterministic automaton that is equivalent to the non-deterministic automaton. So 7 00:00:35,424 --> 00:00:40,392 here's the deterministic automaton that recognizes exactly the same language. This 8 00:00:40,392 --> 00:00:44,693 automa, this deterministic automaton notices the viable prefixes, of our 9 00:00:44,693 --> 00:00:49,661 example grammar. But now notice that each state is a set of items. So there's a set 10 00:00:49,661 --> 00:00:54,689 of non-deterministic automaton states, in each of these states. And recall that what 11 00:00:54,689 --> 00:00:59,535 that means is that the non-deterministic automaton could be in any one of these 12 00:00:59,535 --> 00:01:06,213 states. And in particular, this state here is the start state because it has the item 13 00:01:06,213 --> 00:01:13,024 S prime goes to dot E. The states of this deterministic automaton are called 14 00:01:13,024 --> 00:01:17,860 variously cananugal collections of items or the cananugal collections of LR zero 15 00:01:17,860 --> 00:01:22,875 items. If you look in the dragon book it gives another way of constructing the LR 16 00:01:22,875 --> 00:01:28,010 zero items than the one that I gave. Mine is somewhat simplified but I think also a 17 00:01:28,010 --> 00:01:32,775 little easier to understand if you are seeing this for the first time. Now we 18 00:01:32,775 --> 00:01:40,049 need another definition. We'll say that a given item is valid for a viable prefix 19 00:01:40,300 --> 00:01:46,451 alpha beta. If the following is true, that beginning from the start symbol, this is 20 00:01:46,451 --> 00:01:53,177 our extra start symbol, and by a series of right-most derivation steps, we can get to 21 00:01:53,177 --> 00:01:59,231 a configuration, alpha-x-omega, and then in one step, x can go to beta-gamma. And, 22 00:01:59,455 --> 00:02:05,569 what this says is after parsing alpha and beta, after seeing. Alpha and beta on the 23 00:02:05,569 --> 00:02:10,913 stack, the valid items are the possible tops of the stack of items. That, that we 24 00:02:10,913 --> 00:02:15,280 could, that this item, could be the determination state of the 25 00:02:15,280 --> 00:02:21,300 nondeterministic automaton. A simpler way of explaining the same idea is that for a 26 00:02:21,300 --> 00:02:27,128 given viable prefix alpha the items that are valid in that prefix are exactly the 27 00:02:27,128 --> 00:02:32,682 items that are in the final state of the DFA after it reads that prefix. So these 28 00:02:32,682 --> 00:02:38,674 are the items that describe the state after you've seen the stack alpha. Now, an 29 00:02:38,674 --> 00:02:45,433 item is often valid for many, many prefixes. So, for example, the item T goes 30 00:02:45,433 --> 00:02:52,631 to open paren .e closed paren is valid for all sequences of open parens. And to see 31 00:02:52,631 --> 00:02:57,626 that, We can just look at our automaton and confirm that if we see an open paren, 32 00:02:57,626 --> 00:03:02,061 remember, this is the start state. So if we see an open paren, we take this 33 00:03:02,061 --> 00:03:07,043 transition, we wind up in this state here. And then every open paren we see, we just 34 00:03:07,043 --> 00:03:12,085 go round and round in this state. So if I have a sequence of five open parens as my 35 00:03:12,085 --> 00:03:16,642 input, then I'll have transitions one, two, three, four, five, all looping in 36 00:03:16,642 --> 00:03:22,472 this state. And notice that this item. Is, in, is one of the items in that state. And 37 00:03:22,472 --> 00:03:28,060 that just says that this item is valid for any prefix, or for, excuse me, any 38 00:03:28,060 --> 00:03:29,780 sequence of open parens.