1 00:00:03,740 --> 00:00:08,880 In this video, we're finally going to give an actual bottom up parsing algorithm. In 2 00:00:08,880 --> 00:00:13,648 particular, we'll talk about SLR, or simple LR parsing, which will build on the 3 00:00:13,648 --> 00:00:18,726 ideas of valid items, and viable prefixes that we've been discussing in our recent 4 00:00:18,726 --> 00:00:27,211 videos. The first thing we're going to do is to define a very weak bottom up parsing 5 00:00:27,211 --> 00:00:32,572 algorithm called LR0 parsing. And the basic idea here is that we're going to 6 00:00:32,572 --> 00:00:38,215 assume a stack contains a contents alpha, and that the next input is token T And 7 00:00:38,215 --> 00:00:43,858 that the DFA, this is the DFA that recognizes, the viable prefixes. On input 8 00:00:43,858 --> 00:00:49,290 alpha, that is, when it reads the stack contents, it terminates in some state S. 9 00:00:49,290 --> 00:00:55,107 [sound] And There's only gonna be two things that this that this parsing 10 00:00:55,107 --> 00:01:00,629 algorithm needs to do. So if S, if the final state of the DFA contains the item X 11 00:01:00,629 --> 00:01:05,346 goes to beta dot. Well, what does that say? That says we've seen the complete 12 00:01:05,346 --> 00:01:10,417 right hand side, of X goes to beta on the top of the stack, and that furthermore, 13 00:01:10,417 --> 00:01:15,364 everything that's below the stack still says that x goes to beta dot is a valid, 14 00:01:15,364 --> 00:01:20,497 or a viable, sorry, is a valid item for this state. Meaning its okay to reduce by 15 00:01:20,497 --> 00:01:25,382 X goes to beta. So if we see a complete production dot all the way in the right 16 00:01:25,382 --> 00:01:30,329 hand side in the final state of the DFA, then we're just going to reduce by that 17 00:01:30,329 --> 00:01:36,203 production. The other possible move is a shift. If we wind up in a state, where, X 18 00:01:36,203 --> 00:01:41,887 goes to beta .t, and then some other stuff is a valid item, what does that say? That 19 00:01:41,887 --> 00:01:47,572 says that it would be okay at this point to add a T to the stack. And if T is our 20 00:01:47,572 --> 00:01:54,873 input, well, then we should do a shift move [sound]. Now, when does LR0 parsing 21 00:01:54,873 --> 00:01:59,623 get into trouble? Well, there are two possible problems it could have. It might 22 00:01:59,623 --> 00:02:04,109 not be able to decide. Between two possible reduced moves. So, if any state 23 00:02:04,109 --> 00:02:08,772 of DFA has two possible reductions, meaning it seem two complete productions 24 00:02:08,772 --> 00:02:13,680 and it could reduce by either one then there's not enough information to decide 25 00:02:13,680 --> 00:02:18,527 which reduction to perform and the parts won't be completely deterministic, and 26 00:02:18,527 --> 00:02:22,761 this is called a reduced, reduced co nflict. So again, this happens if a 27 00:02:22,761 --> 00:02:27,608 particular state has two separate items indicating two separate reductions. The 28 00:02:27,608 --> 00:02:32,332 other possibility is that the final state of the DFA, after reading the stack 29 00:02:32,332 --> 00:02:38,200 contents, might have An item that says to reduce and another item that says to 30 00:02:38,200 --> 00:02:43,840 shift. And this is called a shift-reduce conflict. So in this case, there would 31 00:02:43,840 --> 00:02:48,616 only be a conflict in a state where T was the next item in the input. But in that 32 00:02:48,616 --> 00:02:53,273 situation, we wouldn't know whether to shift T onto the stack, or to reduce by X 33 00:02:53,273 --> 00:03:00,548 goes to beta [sound]. Let's take a look at the DFA for recognizing viable prefixes 34 00:03:00,548 --> 00:03:06,084 that we've been using for the last couple of ideas, and in fact this particular DFA 35 00:03:06,084 --> 00:03:11,353 does have some conflicts. So, let's take a look at this state right here, here we 36 00:03:11,353 --> 00:03:16,822 could either reduced by E goes to T you are in this state or if the next input is 37 00:03:16,822 --> 00:03:21,892 a plus we could do a shift and. In, so in this particular situation, if the next 38 00:03:21,892 --> 00:03:27,131 input is plus, we could either shift and use this item or we can reduce and use 39 00:03:27,131 --> 00:03:35,061 that item. So this particular state has a shift reduced conflict. Now, that's not 40 00:03:35,061 --> 00:03:41,480 the only conflict in this in this grammar, though. In this state here, we have a very 41 00:03:41,480 --> 00:03:47,033 similar problem. Here we could shift if the next input is a times. Or we could 42 00:03:47,033 --> 00:03:52,370 reduce by T goes to [inaudible]. And so this state also has a shift reduce 43 00:03:52,370 --> 00:03:59,905 conflict. It turns out that it's not difficult to improve on LR0 parsing, and, 44 00:03:59,905 --> 00:04:05,875 we'll present one such improvement in this video called SLR or simple LR parsing. And 45 00:04:05,875 --> 00:04:11,915 this is going to improve on LR0 by adding some heuristics that will refine when we 46 00:04:11,915 --> 00:04:18,235 shift and when we reduce, so that fewer states have conflicts. The modification to 47 00:04:18,235 --> 00:04:24,538 LR0 parsing that gives us SLR parsing is really quite small. We just add one new 48 00:04:24,538 --> 00:04:30,368 condition to the reduction case. So before, if we saw it, X goes to beta dot, 49 00:04:30,604 --> 00:04:37,144 in the final state of our DFA, recall what that means. That means beta is on the top 50 00:04:37,144 --> 00:04:43,155 of the stack, and it is viable And so it's fine to reduce. Now, We do have a little 51 00:04:43,155 --> 00:04:47,855 bit more information. So, so notice that the automaton her e doesn't take any 52 00:04:47,855 --> 00:04:52,133 advantage of what's coming up in the input. This is based entirely, this 53 00:04:52,133 --> 00:04:56,833 decision here is based entirely on the stack contents. But it might be that it 54 00:04:56,833 --> 00:05:01,834 doesn't make sense to reduce based on what the next input symbol is. And how can we 55 00:05:01,834 --> 00:05:06,715 take advantage of that? Well, if you think about it, what's going to happen? We have 56 00:05:06,715 --> 00:05:11,766 our stack contents. And, it ends in a beta, and now we're going to make a move 57 00:05:11,766 --> 00:05:16,889 where we're going to replace that by X. Okay. And if the next input symbol is t, 58 00:05:16,889 --> 00:05:21,789 so remember we have a vertical bar here and a t following, what does that mean? 59 00:05:21,789 --> 00:05:27,129 Well, that means that x has to come before t in the derivation. Or in another words, 60 00:05:27,129 --> 00:05:32,217 t is gonna follow x. And if t can't follow x, if t is a terminal symbol that can't 61 00:05:32,217 --> 00:05:37,430 come after the non-terminal x than it makes no sense to do this reduction. So we 62 00:05:37,430 --> 00:05:42,330 only do the reduction if t is in the follow of x. We just add that restriction 63 00:05:42,330 --> 00:05:48,229 and that is the only change to the parsing algorithm. So if there are any conflicts 64 00:05:48,229 --> 00:05:53,120 under these rules either shift reduce or reduce, reduce, then the grammar is not an 65 00:05:53,120 --> 00:05:58,130 slr grammar. Just notice that these rules amount to a heuristic, for detecting the 66 00:05:58,130 --> 00:06:02,782 handles. So, we take into account two pieces of information. The contents of the 67 00:06:02,782 --> 00:06:07,614 stack, that's that the DFA, does for us, and it tells us what items are possible 68 00:06:07,614 --> 00:06:12,445 when we get to the top of the stack, and also what's coming up in input, and we can 69 00:06:12,445 --> 00:06:16,739 use that to define our reduction decisions. And for those grammars where 70 00:06:16,739 --> 00:06:21,333 there are no conflicts, meaning there is a, there is a unique move, in every 71 00:06:21,333 --> 00:06:25,986 possible state, under those rules. Then this heuristic is exact, you know, for, 72 00:06:25,986 --> 00:06:30,520 for those grammars. And we just define those grammars to be the SLR grammars. 73 00:06:30,520 --> 00:06:35,202 Let's consider how things have changed for our running example. The deterministic 74 00:06:35,202 --> 00:06:39,826 automaton for recognizing the viable prefixes of the grammar we've been looking 75 00:06:39,826 --> 00:06:44,623 at for several videos now. Recall that we had shift reduced conflicts under LR zero 76 00:06:44,623 --> 00:06:48,795 rules in two states. So now let's look at this state first, the upper state. So 77 00:06:48,795 --> 00:06:52,766 here, we 're going to shift if there's a plus in the input. That's what this item 78 00:06:52,766 --> 00:06:56,736 tells us to do. It tells us there's if there's a plus, then the right move is to 79 00:06:56,736 --> 00:07:01,241 shift. And so Now the question is, when are we going to reduce? Well we're only 80 00:07:01,241 --> 00:07:05,994 going to reduce if the input is in the follow of E. And what is the follow of E? 81 00:07:05,994 --> 00:07:11,230 We computed that a long time ago, but just to remind you remember that E here is the 82 00:07:11,410 --> 00:07:16,344 original start symbol of the grammar so certainly dollar sign will wind up in the 83 00:07:16,344 --> 00:07:21,219 follow of E. And the other possibility for the follow of E is close paren, because 84 00:07:21,219 --> 00:07:26,414 here at this point in the grammar close paren comes after E. And that's the only 85 00:07:26,414 --> 00:07:31,472 two possibilities. So what that says now, what that means is that, in this 86 00:07:31,472 --> 00:07:36,939 particular state, we are going to reduce, if either we're out of input. Or if the 87 00:07:36,939 --> 00:07:42,083 next I, the next, token in the input is a closed paren, and will shift if the next 88 00:07:42,083 --> 00:07:47,104 token in the input is a plus. And in any other situation, we will report a parsing 89 00:07:47,104 --> 00:07:51,814 error. And so there's no longer any shift reduced conflict in this state, and 90 00:07:51,814 --> 00:07:56,400 there's always a unique move for every possible input. The situation is 91 00:07:56,400 --> 00:08:01,420 similarly, similarly improved, for the other state. So here, we're going to shift 92 00:08:01,420 --> 00:08:06,440 in there's a times in the input, and we're going to reduce if the input is in the 93 00:08:06,440 --> 00:08:12,799 follow of T. And what is the follow of T? [sound]. Recall, We computed this again a 94 00:08:12,799 --> 00:08:17,398 long time ago and I just happen to know what it is. And so I'll just tell you. 95 00:08:17,398 --> 00:08:23,143 Well it included everything in the follow of e. So a dollar sign in close paren are 96 00:08:23,143 --> 00:08:28,953 in the follow of T. But also, a plus is in the follow of T because of this usage over 97 00:08:28,953 --> 00:08:33,923 here in the grammar where plus appears really after T. But those are the only 98 00:08:33,923 --> 00:08:38,893 things in the follow of T. And so now we're going to reduce, only if we're out 99 00:08:38,893 --> 00:08:44,122 of input or if the next input item is a close paren or a plus and there's also a 100 00:08:44,122 --> 00:08:49,157 no shift reduce, no longer any shift reduce conflict in this state. And so this 101 00:08:49,157 --> 00:08:55,769 grammar, is an SLR1 grammar. Now many grammars are not SLR. To emphasize that 102 00:08:55,769 --> 00:09:01,414 SLR is an improvement on LR0 but it 's still, not a really very general class of 103 00:09:01,414 --> 00:09:07,273 grammars. So All ambiguous grammars for example are not SLR. We can improve a 104 00:09:07,273 --> 00:09:12,989 little bit on the SLR situation. We can make SLR parsers even more grammarous, by 105 00:09:12,989 --> 00:09:18,778 using precedence declarations to tell it how to resolve conflicts. So let's revert 106 00:09:18,778 --> 00:09:22,857 to the most natural and also most ambiguous grammar for plus and times over 107 00:09:22,857 --> 00:09:27,204 the integers, and we've looked at this grammar before. If you build the DFA for 108 00:09:27,204 --> 00:09:31,444 this grammar, if you go through and build the DFA for the viable prefix of this 109 00:09:31,444 --> 00:09:36,580 grammar, you will discover that there is a state. That has the following two items in 110 00:09:36,580 --> 00:09:42,696 it, one says that if we see E times E that we have seen E times E on a stack, and 111 00:09:42,696 --> 00:09:48,527 that we can now reduce by ecos E times E. The other one will say that if there's a 112 00:09:48,527 --> 00:09:54,429 plus coming up in the input we should shift. And notice that this is exactly the 113 00:09:54,429 --> 00:09:59,984 question. Of whether, times has higher precedence than plus. When you're in this 114 00:09:59,984 --> 00:10:05,079 situation, should you. Reduce, thereby grouping the two E's together here, 115 00:10:05,079 --> 00:10:10,982 Grouping the multiplication operation first. Or should you shift the plus, in 116 00:10:10,982 --> 00:10:17,066 which case you'll be working on that for a sentence at the top of the stack. So, in 117 00:10:17,066 --> 00:10:22,483 this situation, the declaration times has higher precedence than plus resolves the 118 00:10:22,483 --> 00:10:27,900 conflict in favor of the reduction. So we would not do the shift, and we would wind 119 00:10:27,900 --> 00:10:34,582 up with no shift-reduce conflict. Note that the term precedence declaration is 120 00:10:34,582 --> 00:10:38,968 actually quite misleading. These declarations don't define precedence. They 121 00:10:38,968 --> 00:10:43,451 don't. Do that directly at all. What they really define are conflict resolution. 122 00:10:43,451 --> 00:10:48,052 They say, make this move instead of that move. It happens that in this particular 123 00:10:48,052 --> 00:10:52,595 case. Because we're dealing with a national grammar, simple grammar for plus 124 00:10:52,595 --> 00:10:57,398 and times that the conflict resolution has exactly the effect of enforcing the 125 00:10:57,398 --> 00:11:02,322 precedence declaration that we want. But in more complicated grammars where there 126 00:11:02,322 --> 00:11:07,125 are more interactions between various pieces of the grammar, these declarations 127 00:11:07,125 --> 00:11:11,867 might not do what you expect in terms of enforcing precedence, fortuna tely, you 128 00:11:11,867 --> 00:11:16,776 can always print out the automaton. The tools provide, Usually a way for you to 129 00:11:16,776 --> 00:11:21,837 inspect the parsing automaton. And then you can see exactly how, the conflicts are 130 00:11:21,837 --> 00:11:26,717 being resolved, and whether those are the resolutions that you had intended. And I 131 00:11:26,717 --> 00:11:31,356 recommend when you're building parsers, especially if it's a, a fairly complex 132 00:11:31,356 --> 00:11:36,056 parser, that you do examine the parsing automaton to make sure that it's doing 133 00:11:36,056 --> 00:11:41,443 what you expect. So now we're ready to give the algorithm for SLR parsing. So 134 00:11:41,443 --> 00:11:46,161 [inaudible] automaton, our parsing automaton that recognizes viable prefixes. 135 00:11:46,340 --> 00:11:51,238 The initial configuration is going to be with the vertical bar all the way to the 136 00:11:51,238 --> 00:11:55,956 left so the stack is empty. This is our full input and we [inaudible] dollar to 137 00:11:55,956 --> 00:12:00,137 indicate the end of the input. And now we're going to repeat until the 138 00:12:00,137 --> 00:12:05,094 configuration has just the start symbol on the stack, and dollar in the input. 139 00:12:05,094 --> 00:12:09,752 Meaning all the input is gone and we've reduced the entire input to the start 140 00:12:09,752 --> 00:12:14,342 symbol. So. An [inaudible] configuration will be written as alpha-omega; where 141 00:12:14,342 --> 00:12:19,000 alpha is the contents of the stack and omega is the remaining input, and what 142 00:12:19,000 --> 00:12:24,141 we're going to do is we're going to run M, run the machine on the current stack alpha 143 00:12:24,141 --> 00:12:28,860 and if M rejects alpha, if M says that alpha is not a viable prefix, then we're 144 00:12:28,860 --> 00:12:33,606 going to report a parsing error. We're gonna stop right there. Now, if M accepts 145 00:12:33,606 --> 00:12:38,643 alpha, and it accepts it in a state, if it ends in a state with items I, then we're 146 00:12:38,643 --> 00:12:43,617 gonna look at the next input, call that A, and what are we going to do? Well, we're 147 00:12:43,617 --> 00:12:49,408 going to shift. Yes, there's an item. In I that says, it would be okay to see the 148 00:12:49,408 --> 00:12:54,790 terminal A. Next. Okay? So that's just our shift move. And then we're going to reduce 149 00:12:54,790 --> 00:13:00,499 if there's a reduction item, in the in the set of valid items. And the next input can 150 00:13:00,499 --> 00:13:05,946 follow the non-terminal on the left hand side. So these are just the two rules that 151 00:13:05,946 --> 00:13:11,065 we discussed before. And then we'll report a parsing error if neither of these 152 00:13:11,065 --> 00:13:15,984 applies. Okay, now one interesting thing about this algorithm, if you read it 153 00:13:15,984 --> 00:13:21,034 carefully and you th ink about it for awhile. You'll realize that this step is 154 00:13:21,034 --> 00:13:26,203 actually not needed, that we don't need to check here For whether M accepts the 155 00:13:26,203 --> 00:13:31,414 stack, or not. Because this staff down here, where we report a parsing error, if 156 00:13:31,609 --> 00:13:36,755 neither of these steps applies, this already implies that we will never form an 157 00:13:36,755 --> 00:13:42,096 invalid stack, That our, their stacks will always be viable. The parsing errors will 158 00:13:42,096 --> 00:13:47,568 be caught at this line, and we won't pollute the stack with symbols that can't 159 00:13:47,568 --> 00:13:52,648 possibly result in viable prefixes. So in fact, this error check here, is not 160 00:13:52,648 --> 00:13:58,432 needed, M is always going to accept the stack. If there are any conflicts in the 161 00:13:58,432 --> 00:14:03,620 last step, meaning, it's not clear whether to shift or reduce in some state for some, 162 00:14:03,807 --> 00:14:08,745 input symbol, then the grammar is not, SLRK. And K, again, is the amount of look 163 00:14:08,745 --> 00:14:13,745 ahead. In practice, we just use one token of look ahead, So typically, just looking 164 00:14:13,745 --> 00:14:16,120 at the next token in the input stream.