1 00:00:03,680 --> 00:00:07,938 In this video, we're going to wrap up our discussion of SLR parsing, we're going to 2 00:00:07,938 --> 00:00:11,624 give the full SLR parsing algorithm, and also talk about some important 3 00:00:11,624 --> 00:00:19,231 improvements. The SLR parsing algorithm we discussed in the last video has one major 4 00:00:19,231 --> 00:00:24,225 inefficiency. And that is that most of the work that the automation does when it, 5 00:00:24,225 --> 00:00:28,844 when it reads the stack is actually redundant. And to see this, think about 6 00:00:28,844 --> 00:00:34,108 the stack. So we have our stack, and this is the bottom over here. And this is the 7 00:00:34,108 --> 00:00:38,476 top of the stack over here. And, what is going on in each step? In each step we 8 00:00:38,476 --> 00:00:43,233 might, shift something onto the stacks, we might add one symbol, or we might pop some 9 00:00:43,233 --> 00:00:47,715 symbols, and, and push one symbol onto the stack. But basically there's going to be 10 00:00:47,715 --> 00:00:52,251 some small number of symbols that change at the top of the stack at each step. But 11 00:00:52,251 --> 00:00:56,622 most of the stack stays the same. And then we rerun the automaton on the entire 12 00:00:56,622 --> 00:01:01,232 stack. And so, this work is all repeated. Everything that stayed the same From the 13 00:01:01,232 --> 00:01:05,782 previous stack is repeated work, and then we do a little bit of new work, just at 14 00:01:05,782 --> 00:01:10,275 the very top of the stack. And clearly, if we could avoid this, we could make the 15 00:01:10,275 --> 00:01:15,182 algorithm run much, much more quickly. The way to exploit the observation that most 16 00:01:15,182 --> 00:01:19,560 of the work of the automaton is repeated at each step, is to simply remember the 17 00:01:19,560 --> 00:01:23,555 state of the automaton on each stack prefix. So we're going to change the 18 00:01:23,555 --> 00:01:27,714 representation of the stack, we're going to change what goes in the stack, so 19 00:01:27,714 --> 00:01:32,037 before we just had symbols on the stack, but now we're going to have pairs. Each 20 00:01:32,037 --> 00:01:37,036 element of the stack will be a pair of a symbol, and a DFA state. Thus the stack 21 00:01:37,036 --> 00:01:41,558 now is going to be a stack of pairs and whereas before a stack would have 22 00:01:41,558 --> 00:01:46,446 consisted just of the symbols, sym1 up to sym n, now we're going to have the same 23 00:01:46,446 --> 00:01:51,395 symbols but each one of them is going to be paired with a DFA state and that DFA 24 00:01:51,395 --> 00:01:56,466 state is going to be the result of running the DFA and all the symbols to its left, 25 00:01:56,466 --> 00:02:01,599 So all the symbols below it in the stack. So if I think about my stack and if I draw 26 00:02:01,599 --> 00:02:06,674 a little picture of the stack as a line then the DFA state here. Let's call this 27 00:02:06,674 --> 00:02:11,883 state I, will be the result of running the DFA on the entire, stack contents to the 28 00:02:11,883 --> 00:02:16,724 left of that point. And again, if I look at some other point in the stack, at the 29 00:02:16,724 --> 00:02:21,320 state, stack state that's stored there. That would be running, the results of 30 00:02:21,320 --> 00:02:25,821 running the DFA on the entire stack context, contents, up to that point. And 31 00:02:25,821 --> 00:02:30,055 one small detail here is that the bottom of the stack, we have to get started. We 32 00:02:30,055 --> 00:02:34,341 need to have the start state stored at the bottom of the stack. And we just store 33 00:02:34,341 --> 00:02:39,296 that with any dummy symbol. It doesn't matter what symbol we pick. So now we're 34 00:02:39,296 --> 00:02:44,953 ready to actually give the details of the parsing algorithm. And the first step is 35 00:02:44,953 --> 00:02:50,472 to define a table go to. And this maps a state and a symbol to another state. And 36 00:02:50,472 --> 00:02:55,784 this is just the transition function of the DFA. This is the graph of the DFA 37 00:02:55,784 --> 00:03:03,552 written out as an array. Our SLR parsing algorithm will have four possible moves. A 38 00:03:03,552 --> 00:03:08,914 shift X move will push a pair on the stack. X is a DFA state, so that's named 39 00:03:08,914 --> 00:03:14,700 in the shift move now. And then the other element of the pair is the current input. 40 00:03:14,700 --> 00:03:19,289 And then we'll also have reduce moves, which are just as before. So, to recall, a 41 00:03:19,289 --> 00:03:23,819 reduce move will pop, the, a number of elements from the stack equal to the 42 00:03:23,819 --> 00:03:28,525 length of the right hand side. And then it will push the left hand side onto the 43 00:03:28,525 --> 00:03:33,232 stack. And then finally, accept an error moves for when we've successfully parsed 44 00:03:33,232 --> 00:03:38,743 the input, and for when the parser gets stuck. The second parsing table is the 45 00:03:38,743 --> 00:03:44,250 action table which tells us which kind of move to make in every possible state. The 46 00:03:44,250 --> 00:03:49,662 action table's indexed by a state of the automaton and the next input symbol. And 47 00:03:49,662 --> 00:03:55,588 then the possible moves are things like shift, reduce, accept, or error. So let's 48 00:03:55,588 --> 00:04:01,803 consider if we do shifts, if the final state of the automaton at the top of the 49 00:04:01,803 --> 00:04:08,255 stack has an item that says it would be okay to shift an A. And go to that is from 50 00:04:08,255 --> 00:04:14,707 this state we can go to state J on input A. Then the move in state I on input A 51 00:04:14,707 --> 00:04:21,001 will be to shift AJ onto the stack And th ink about what that means for a second. 52 00:04:21,001 --> 00:04:26,942 What that says is that we have a stack. And then the next input is A. And then at 53 00:04:26,942 --> 00:04:32,617 this point, it's okay to shift an A onto the stack. And furthermore, that the state 54 00:04:32,617 --> 00:04:37,548 of the automaton at this point is SI. Okay. So the state of Irarta [inaudible] 55 00:04:37,548 --> 00:04:42,343 the top of the stack is SI. The next input is A. Remember that the go to table is a 56 00:04:42,343 --> 00:04:47,197 transition function of the machine. So if we move the vertical bar over, if we shift 57 00:04:47,197 --> 00:04:51,641 that A on to the stack, well, now, we don't just put A on the stack, we have to 58 00:04:51,641 --> 00:04:56,260 put a pair on the stack. And the question is what machine state should go there. 59 00:04:56,260 --> 00:05:01,172 Well, it's going to be state that we would reach from state I from state SI on input 60 00:05:01,172 --> 00:05:06,506 A, which. The go to table tells us, in this case, is state SJ. And for that 61 00:05:06,506 --> 00:05:12,453 reason, the action, when we terminate in state I, and the next input is A, is to 62 00:05:12,453 --> 00:05:18,316 shift the pair A, J, onto the stack. The other three moves that go into the action 63 00:05:18,316 --> 00:05:23,266 table are things we've already seen. So if the final state of the automaton at the 64 00:05:23,266 --> 00:05:27,790 top of the stack has an item that says that we can reduce, and the follow up 65 00:05:27,793 --> 00:05:32,380 condition requirement is satisfied. Mainly, that the, next input can follow, 66 00:05:32,561 --> 00:05:37,390 the left hand side non terminal of the production. Then in the entry I, for, 67 00:05:37,390 --> 00:05:42,352 [inaudible] if we're in state SI and we have input a, we can reduce by the 68 00:05:42,352 --> 00:05:47,716 production x goes to alpha. And there's one exception here, we're not going to do 69 00:05:47,716 --> 00:05:53,215 that reduction, if the left-hand side is the special start symbol, the new start 70 00:05:53,215 --> 00:05:58,311 symbol that we add to the grammar, is prime. Because, in that case, if the item 71 00:05:58,311 --> 00:06:03,876 that we're going to reduce by is s-prime goes to s-dot, and we're at the end of the 72 00:06:03,876 --> 00:06:08,942 input, then we want to accept. And any other Situation is an error. So in any 73 00:06:08,942 --> 00:06:14,398 other situation, if we're in state I and we have the next the next input is A, 74 00:06:14,398 --> 00:06:19,241 well, we don't know whether to shift, reduce, or accept. And so, that is an 75 00:06:19,241 --> 00:06:24,704 error state. Finally, here is the full SLR parsing algorithm. And I'm just going to 76 00:06:24,704 --> 00:06:28,789 walk you through it, so that we can see how all of the ideas we've been di 77 00:06:28,789 --> 00:06:33,184 scussing, and all the various pieces fit together. Let's let our initial input be 78 00:06:33,184 --> 00:06:37,729 called I. And we'll just give it a name, and it's gonna be treated as an array that 79 00:06:37,729 --> 00:06:42,053 we can index. The index will be called J, and initially, it's zero so that we're 80 00:06:42,053 --> 00:06:46,709 pointing to the first token in the input string. We'll just assume that the first 81 00:06:46,709 --> 00:06:51,451 state of the DFA is called state one. And, that means our initial stack is going to 82 00:06:51,451 --> 00:06:56,176 have state one for the state of the automaton and some other dummy symbol that 83 00:06:56,176 --> 00:07:00,961 we don't care about In the, in the first position. So, the stack is just a pair 84 00:07:00,961 --> 00:07:05,745 with [inaudible] in the start state of the DFA. And now, were going to repeat the 85 00:07:05,745 --> 00:07:10,231 following loop until we've either successfully pars the input or we detect 86 00:07:10,231 --> 00:07:14,332 an error. And at its steps, what we're going to do? Well, we're going to look at 87 00:07:14,332 --> 00:07:18,628 the next input symbol and we're going to look at the final state of the automaton 88 00:07:18,628 --> 00:07:22,977 on the stack contents and that's always the state of the pair that's on the top of 89 00:07:22,977 --> 00:07:27,273 the stack and we're gonna look those two things up in the action table and that's 90 00:07:27,273 --> 00:07:31,359 gonna tell us what kind of move to make. So, let's just go through the moves in 91 00:07:31,359 --> 00:07:35,422 order. Let's consider the shift move first. So, what happens? If were, if it 92 00:07:35,422 --> 00:07:40,451 says we're supposed to shift and going to state K, then what we're going to do is 93 00:07:40,451 --> 00:07:45,666 we're going to shift the input, that means we're going to take the next input symbol 94 00:07:45,666 --> 00:07:50,695 and, or the current input symbol, excuse me, and we're going to push that on to the 95 00:07:50,695 --> 00:07:55,165 stack together with state K of the [inaudible]. That pair goes on to the 96 00:07:55,165 --> 00:07:59,822 stack, and we also bumb the input pointer so that we're looking at the next 97 00:07:59,822 --> 00:08:04,739 character of input. Now. Let me erase that so you can continue to read it. Now what 98 00:08:04,739 --> 00:08:09,631 about the reduce moves? So this one's a little bit interesting. First thing we're 99 00:08:09,631 --> 00:08:14,277 going to do is we're going to pop a number of pairs off the, off the stack that's 100 00:08:14,277 --> 00:08:18,647 equal to the length of the right-hand side. So we pop a number of items off the 101 00:08:18,647 --> 00:08:22,961 stack that's going to the right that's equal to the right-hand side of the 102 00:08:22,961 --> 00:08:27,441 production, and then what do w e push on to the stack? Well we're gonna push the 103 00:08:27,441 --> 00:08:32,032 non-terminal on the left-hand side of the stack. And now the question is: what state 104 00:08:32,032 --> 00:08:36,345 goes on to the stack? What DFA state? Well. With that we've popped the stack. We 105 00:08:36,345 --> 00:08:40,664 can look at the new top state of the stack. So the DFA state was now the top 106 00:08:40,664 --> 00:08:45,267 state. After we've done the pops we'll tell us what the final state of the DFA 107 00:08:45,267 --> 00:08:49,699 was and what is left of the stack. And then now that we're pushing X under the 108 00:08:49,699 --> 00:08:54,587 stack we want to know what state the DFA would go into on the transition labeled X. 109 00:08:54,587 --> 00:08:59,392 And so we use the Go To table to look that up, The current top state of the stack. On 110 00:08:59,392 --> 00:09:04,795 symbol X, where does the FA go? That is the state that gets pushed onto the stack. 111 00:09:04,795 --> 00:09:09,860 And then finally, if, if the move is accept, we halt normally. And if the move 112 00:09:09,860 --> 00:09:16,548 is error, we halt and report an error, or execute our error recovery procedure. One 113 00:09:16,548 --> 00:09:21,172 interesting fact about this algorithm is that it only uses the DFA state and the 114 00:09:21,172 --> 00:09:25,683 input. The stack symbols are not used in really interesting way. And so, we could 115 00:09:25,683 --> 00:09:30,365 actually get rid of the stack symbols and just do parsings with the DFA states on 116 00:09:30,365 --> 00:09:34,704 the stack. But, that of course would be throwing away the program and we still 117 00:09:34,704 --> 00:09:39,214 actually need to program for the later stages of the compiler. And so to do the 118 00:09:39,214 --> 00:09:44,567 type checking and co-generation, we need to keep the symbols around. Now simple LR 119 00:09:44,567 --> 00:09:49,668 parsing is called simple for a reason. And in fact, in practice, it's a bit too 120 00:09:49,668 --> 00:09:55,033 simple. The widely used bottom-up parsing algorithms are based on a more powerful 121 00:09:55,033 --> 00:10:00,704 class of grammars called the LR grammars. And the basic difference between the LR 122 00:10:00,704 --> 00:10:06,687 grammars and the SLR grammars is that look ahead is built into the items. So what 123 00:10:06,687 --> 00:10:12,670 does that mean? Well, a LR1 item is going to be a pair which consists of an item, 124 00:10:12,670 --> 00:10:17,425 Just like we saw before. And this means exactly the same thing as before. And a 125 00:10:17,425 --> 00:10:22,484 look-ahead, In case of an LR1 item there's just one token of look-ahead. If this was 126 00:10:22,484 --> 00:10:27,361 an LR2 item there could be two tokens of look-ahead in there. And the meaning of 127 00:10:27,361 --> 00:10:32,238 this pair is that, if we ever get aroun d to state where we have seen all of this 128 00:10:32,238 --> 00:10:36,871 production, all the right-hand side of this production. Then it's going to be 129 00:10:36,871 --> 00:10:41,675 okay to reduce, if the look-ahead at that point is Dollar that's the end of the 130 00:10:41,675 --> 00:10:46,456 input. And of course, there could be any other token in there any other terminal 131 00:10:46,456 --> 00:10:51,298 symbol in there besides dollar. And this turns out to be more accurate than just 132 00:10:51,298 --> 00:10:56,322 using follow sense recall that the point where a reduction decision is made in SLR 133 00:10:56,322 --> 00:11:01,345 parsing, we just look at the entire follow set for the symbol on the left hand side 134 00:11:01,345 --> 00:11:06,188 of the production. And this mechanism of encoding the look-ahead in to the items 135 00:11:06,188 --> 00:11:11,393 allow us to track and find the [inaudible] which look-aheads are actually possible in 136 00:11:11,393 --> 00:11:17,433 particular production sequences. And if you look at the automaton for your parser, 137 00:11:17,433 --> 00:11:23,457 actually it's not an LR1 automaton. It's an LALR1 automaton, which is something 138 00:11:23,457 --> 00:11:29,137 very close, to an LR automaton, it's a little bit of an optimization over an LR, 139 00:11:29,137 --> 00:11:34,614 a pure LR automaton, but anyway, it uses exactly the same kinds of items with this 140 00:11:34,614 --> 00:11:40,429 pair of a of a standard LR0 item in a look ahead. If you look at that automaton, you 141 00:11:40,429 --> 00:11:45,364 will see items that look like this, and that will help you in reading the 142 00:11:45,364 --> 00:11:48,340 automaton and figuring out what it is doing.