1 00:00:03,540 --> 00:00:11,903 In this video, we're gonna to work through a couple of SLR parsing examples. So let's 2 00:00:11,903 --> 00:00:19,405 do a very simple example. Let's consider the grammar. S goes to SA, or S goes to B. 3 00:00:19,405 --> 00:00:27,470 And what does this grammar do? It produces strings of A's followed by a B. So any 4 00:00:27,470 --> 00:00:38,836 number of A's followed by a single B. And notice that the grammar is left recursive, 5 00:00:38,836 --> 00:00:43,917 and recall that that's not a problem for a bottom up parser. Slr parsers, LR parsers, 6 00:00:43,917 --> 00:00:48,754 are perfectly happy with left recursive grammars. So let's begin by working out 7 00:00:48,754 --> 00:00:53,407 what the automaton for this, grammar should be, what the parsing automaton 8 00:00:53,407 --> 00:00:58,488 should be. And recall that the first step is to add a new production to the grammar. 9 00:00:58,488 --> 00:01:03,675 We have to add a new start symbol. That all it does, it has one production that 10 00:01:03,675 --> 00:01:08,761 goes to the old start symbol. And that's, again, just for technical reasons. Now, 11 00:01:08,761 --> 00:01:13,914 the start symbol, or sorry, the start state of the NFA of the parsing automaton 12 00:01:13,914 --> 00:01:18,737 is this item. S prime, our new start symbol, goes to dot S, our old start 13 00:01:18,737 --> 00:01:24,136 symbol. And rather than build the NFA, and then do the subset of states construction. 14 00:01:24,136 --> 00:01:29,396 Let's just go ahead and work out what items must be in the first state of the 15 00:01:29,396 --> 00:01:34,527 DFA. So remember that all the epsilon moves in the, in the DF-, in the NFA, are 16 00:01:34,527 --> 00:01:39,788 due to moves that happen because we don't see a non terminal on the stack. But 17 00:01:39,788 --> 00:01:44,887 instead see something derived from that non terminal. So if we have a dot, Right 18 00:01:44,887 --> 00:01:49,715 next to a non terminal. That means that there's an epsilon move in the NFA to all 19 00:01:49,715 --> 00:01:54,184 the items that have, for all the productions, all the, all the first items, 20 00:01:54,363 --> 00:01:59,191 for the productions of that non terminal. What do I mean by that? I mean that this 21 00:01:59,191 --> 00:02:04,018 state, I mean epsilon production to S goes to dot SA. So this is the first item in 22 00:02:04,018 --> 00:02:08,965 recognizing, this production. So the dots all the way at the left, And there would 23 00:02:08,965 --> 00:02:13,874 also be an item for the other production for S, S goes to dot B. Alright, so that's 24 00:02:13,874 --> 00:02:19,006 the epsilon closure in the NFA of this start item. So this'll be the first state. 25 00:02:19,006 --> 00:02:23,980 These three things, these three items would be the first state of the DFA. And 26 00:02:23,980 --> 00:02:29,926 now we have to consider what would happen on each of the possible transitions for 27 00:02:29,926 --> 00:02:35,510 each of the symbols that we might see on the stack. So let's think about what 28 00:02:35,510 --> 00:02:41,819 happens if we see a B. So if we see a B on the stack, then the only item that's going 29 00:02:41,819 --> 00:02:47,910 to be in that state is S goes to B dot okay? So it'll be fine to see a B and this 30 00:02:47,910 --> 00:02:53,421 would be the only item that was valid for the stack contents. Now another 31 00:02:53,421 --> 00:02:59,809 possibility is that we'll see an S. So, if we see an S on the stack, what will 32 00:02:59,809 --> 00:03:09,060 happen? Well, we're going to go to a state that has two items. S prime goes to S dot, 33 00:03:09,060 --> 00:03:17,111 so that we've seen S on the stack, and we're ready to reduce by, by this 34 00:03:17,111 --> 00:03:24,459 production, possibly. And also, S goes to S. A. And now, Clearly in this state let's 35 00:03:24,459 --> 00:03:29,276 talk about his state down here. There are no more transitions possible. In all there 36 00:03:29,276 --> 00:03:34,152 is only one item in the state dots all the way at the right hand side, so that state 37 00:03:34,152 --> 00:03:38,911 is completely done. In this state the one over here on the right side. While one of 38 00:03:38,911 --> 00:03:43,787 these items is complete, the dot's all the way at the right. But the other item still 39 00:03:43,787 --> 00:03:50,641 has an A, so there could be one more transition out of this state. To the item, 40 00:03:50,641 --> 00:03:58,788 S goes to SA dot, Alright? And now if we look at this, we see that for the most 41 00:03:58,788 --> 00:04:03,574 part these states are in pretty good shape. So these two states this one down 42 00:04:03,574 --> 00:04:08,060 here and this one over here, they only have a single item, and so there's no 43 00:04:08,060 --> 00:04:12,667 possibility of a shift reduce conflict in those states. There's only one item, 44 00:04:12,667 --> 00:04:17,392 there's only one thing to do. The only possibility here in both of these states 45 00:04:17,392 --> 00:04:22,807 is to reduce. This state, the initial start state, has no reduce moves. So it's 46 00:04:22,807 --> 00:04:28,609 only shift moves here, so there can't be a shift reduce conflict, because there are 47 00:04:28,609 --> 00:04:33,774 no reduce items, No possible reduce actions. And there is to reduce, reduce 48 00:04:33,774 --> 00:04:39,505 conflicts for the same reason. The only state of interest really for the point of 49 00:04:39,505 --> 00:04:45,307 view for what who the grammar is SLR1 is this middle state. And here we can either 50 00:04:45,307 --> 00:04:51,498 reduce by s prime goes to s dot, or we could shift and A onto the stack. And the 51 00:04:51,498 --> 00:04:58,682 question is, what is in the follow of S prime? So what can follow S prime in the 52 00:04:58,682 --> 00:05:02,924 grammar? And if we look back up at our grammar, we'll see that nothing can follow 53 00:05:02,924 --> 00:05:07,165 S prime. S prime is the start symbol, and so, in fact, the only thing in the follow 54 00:05:07,165 --> 00:05:12,469 of S prime is the, And to the input. And so what that tells us is that we'll reduce 55 00:05:12,469 --> 00:05:18,109 by s prime, goes to s, if, if we're out of input. And otherwise if there is an A on 56 00:05:18,109 --> 00:05:23,545 the stack, sorry, if there's an a in the input, then we'll shift it onto the stack. 57 00:05:23,545 --> 00:05:29,049 And so this grammar is, SLR1. There are no shift reduce, or reduce, reduce conflicts 58 00:05:29,049 --> 00:05:36,548 implied by this parsing automaton. Let's do another example, slightly more complex. 59 00:05:36,548 --> 00:05:41,796 In fact, let's just extend the previous grammar. We'll have a, a production. S 60 00:05:41,796 --> 00:05:47,463 goes to SAS, okay? So now we have the non terminal twice with an A in between, Or S 61 00:05:47,463 --> 00:05:52,920 can go to B, just like before. And now let's work out the parsing automaton for 62 00:05:52,920 --> 00:06:00,130 this grammar. And, once again, We'll need to add a dummy start symbol To the grammar 63 00:06:00,130 --> 00:06:04,890 And it will go. It's only production will be to, generate the old start symbol. And 64 00:06:04,890 --> 00:06:09,594 now let's begin working out what's in the, parsing automaton, for this particular 65 00:06:09,594 --> 00:06:13,958 grammar. And, and just like before, we're not going to go through the effort of 66 00:06:13,958 --> 00:06:18,548 constructing, the NFA. That would be a systematic way to do it. One way to it is, 67 00:06:18,548 --> 00:06:22,969 is the way we sketched. Was just to construct the NFA first, and then do the 68 00:06:22,969 --> 00:06:27,677 subset of states construction. But, this grammar is small enough. And simple enough 69 00:06:27,677 --> 00:06:32,798 that we can work out directly what is in, what are in the states, what items are in 70 00:06:32,798 --> 00:06:37,855 the states of DFA. So just like before because the dart here is immediately next 71 00:06:37,855 --> 00:06:42,912 to the S, we know that we can without consuming any input at all make an epsilon 72 00:06:42,912 --> 00:06:48,403 transition in the interface to the items that start the productions for S. So these 73 00:06:48,403 --> 00:06:54,457 will be in the, also in the DFA state. And that's it. We can't add any other, 74 00:06:54,676 --> 00:07:00,530 productions here. So S is the only non terminal. And we've added all the, first 75 00:07:00,530 --> 00:07:07,338 items, initial items for S. And so that is the complete state. Okay? So just like 76 00:07:07,338 --> 00:07:13,274 before, one possibility is that we'll see a B on the stack. And so that would give 77 00:07:13,274 --> 00:07:18,916 us the item S goes to B dot. And that's the only item valid for that state. 78 00:07:18,916 --> 00:07:26,117 Another possibility is that we'll see an S on the stack. Okay? In which case, we'll 79 00:07:26,117 --> 00:07:33,406 make a transition to the state, S prime goes to S dot. And S goes to S dot AS, 80 00:07:33,406 --> 00:07:41,461 alright? So we saw that same state before, in the, in the other automaton. Now we 81 00:07:41,461 --> 00:07:47,773 could also see an A. Now what state would that take us to? And this is going to be a 82 00:07:47,773 --> 00:07:52,605 little different. In this state, we could have the item, or will have the item, SA 83 00:07:52,605 --> 00:07:57,499 dot S, and I notice that the dot is right next to S, so instead of seeing an S on 84 00:07:57,499 --> 00:08:02,087 the set, we could also see something derived from S in the next position on 85 00:08:02,087 --> 00:08:07,225 this stack. And so we have to throw in all the productions for S. There's only two of 86 00:08:07,225 --> 00:08:12,057 them. But that means we could have the item S goes to dot SAS, and S goes to dot 87 00:08:12,057 --> 00:08:16,740 P. Alright, and then out of this state, now there are a couple of different 88 00:08:16,740 --> 00:08:21,750 possible transitions, we could see an S or we could see a B. Well, if we see a B, 89 00:08:21,750 --> 00:08:27,708 then we wind up in this state over here. And if we see an S, Well, what's going to 90 00:08:27,708 --> 00:08:39,169 happen? If we see an S, then we'll wind up in another new state. Where we have, S 91 00:08:39,169 --> 00:08:47,566 goes to SAS dot. We've seen the complete right hand side of that production. Or S 92 00:08:47,566 --> 00:08:55,857 goes to SA.S. Actually, that dot's in the wrong place, so let's erase that, and 93 00:08:55,857 --> 00:09:03,940 let's put it in the right place. It's right here. Before the A, not after the A. 94 00:09:03,940 --> 00:09:08,855 Alright and now we have to think about what happens in this state. So in this 95 00:09:08,855 --> 00:09:13,963 state the only possible input is an A and if it isn't A, what's we going to have, 96 00:09:13,963 --> 00:09:19,070 we're going to have S goes to SA.S and then we're gonna have to add the initial 97 00:09:19,070 --> 00:09:24,369 productions for S again. And so that would just take us back to this state and like 98 00:09:24,369 --> 00:09:29,540 other transition labels too we go to this state on an S and we come back to that 99 00:09:29,540 --> 00:09:34,991 state, the bottom state here for the top state on an A. And I think if we hadn't 100 00:09:34,991 --> 00:09:39,780 made any mistakes that, that is the complete transition system and all the 101 00:09:39,780 --> 00:09:45,150 states for this DFA. Now the question is, is this , is this parsing automaton is it, 102 00:09:45,150 --> 00:09:50,262 this is, is this the parsing automaton of a, a solar one grammar. And in order to 103 00:09:50,262 --> 00:09:55,503 answer that question we have to look for possible reduce, reduce, and shift reduce 104 00:09:55,503 --> 00:10:00,680 conflict. Well a quick scan of all the states here will show you or convince you 105 00:10:00,680 --> 00:10:05,519 that there are not. Any states, where there are two possible reduce-moves. So 106 00:10:05,519 --> 00:10:10,997 there can't be any reduce reuse conflicts in this, in this automaton. We can ignore 107 00:10:10,997 --> 00:10:16,411 states that only have a single item or states that have no possible reduce-moves 108 00:10:16,411 --> 00:10:21,631 at all. Because, those are states in which there cannot be a shift-reduce conflict 109 00:10:21,631 --> 00:10:26,658 and that means we can ignore these two states. The two states over here at the 110 00:10:26,658 --> 00:10:32,020 extreme left. So now we're left with these three states to think about. Alright, so 111 00:10:32,020 --> 00:10:38,431 we look at this state last time. As before, the follow of S prime Is just 112 00:10:38,431 --> 00:10:47,509 equal to the dollar sign. And so there's no shift reduce conflict in this state 113 00:10:47,509 --> 00:10:53,034 Because on, on input A we can only shift. We can't reduce by S prime goes to S. All 114 00:10:53,034 --> 00:10:59,670 right, and now we're down looking at these two states. And let's just consider this 115 00:10:59,670 --> 00:11:05,677 bottom state first. Alright, so what does this state say to do? Well, this state 116 00:11:05,677 --> 00:11:11,433 says, that well first of all, observe. That, the only transitions out of this 117 00:11:11,433 --> 00:11:16,462 state are on B and S and there are no reduced moves in this state at all, so 118 00:11:16,462 --> 00:11:21,955 there's no possibility of a shift reduce conflict in this state either. That leaves 119 00:11:21,955 --> 00:11:27,183 us with just this state to think about. Now this state does have a reduced move, 120 00:11:27,183 --> 00:11:32,742 the first item here is a, is a reduction, and that says that we should reduce by S 121 00:11:32,742 --> 00:11:38,168 goes to S A S if whatever comes next is in the follow of S, so we're gonna need to 122 00:11:38,168 --> 00:11:44,191 know what's in the follow of S. Well from S prime goes to S, we know that anything 123 00:11:44,191 --> 00:11:49,327 that's in the follow of S prime is in the follow of S. So clearly dollar is in the 124 00:11:49,327 --> 00:11:54,337 follow of S. And then from this part of the grammar here, we can see that A is in 125 00:11:54,337 --> 00:11:59,399 the follow of S. And then from this occurrence here of S, we know that since 126 00:11:59,399 --> 00:12:03,487 it occurs at the, the far right side of the production, that an ything in the 127 00:12:03,487 --> 00:12:07,793 follow of the right hand side, the left hand side non terminal, is also gonna be 128 00:12:07,793 --> 00:12:12,262 in follow of S. Well, in this case they're the same. It just says that the follow of 129 00:12:12,262 --> 00:12:16,732 S is a subset of the follow of S which is trivially always true, and so it doesn't 130 00:12:16,732 --> 00:12:20,874 add anything new. And so we wind up with just the follow of S being just two 131 00:12:20,874 --> 00:12:25,344 things, dollar sign and A. But that poses a problem, because this says that if we 132 00:12:25,344 --> 00:12:31,028 see an A in the input we should reduce. And this move here says that if we see an 133 00:12:31,028 --> 00:12:37,297 A in the input, we should shift. And so, this state does have a shift-reduce 134 00:12:37,297 --> 00:12:45,140 conflict. Alright, and so this grammar is not SLR what.