1
00:00:03,220 --> 00:00:07,523
In this video, we're going to continue our
discussion of the construction of

2
00:00:07,523 --> 00:00:14,339
[laugh](1) parsing tables by taking a look
at how we build the follow sets. So here's

3
00:00:14,339 --> 00:00:19,649
the definition of follow of x, and recall
that the follow set for a given symbol in

4
00:00:19,649 --> 00:00:24,511
the grammar isn't really about what that
symbol can generate, really, doesn't

5
00:00:24,511 --> 00:00:29,501
depend necessarily at all on what the
symbol can generate. It depends on where

6
00:00:29,501 --> 00:00:34,747
that symbol can appear, where that symbol
is used in the grammar. And we say that t

7
00:00:34,747 --> 00:00:39,802
is in the follow of x if there is some
place in the grammar, some derivation,

8
00:00:39,802 --> 00:00:44,408
where that terminal t can appear
immediately after the symbol x. Okay, so

9
00:00:44,408 --> 00:00:52,500
for all such. E. They make up the follow
set of x. And here's some intuition about

10
00:00:52,500 --> 00:00:59,984
how we would compute follow sets. Let's
say we have a situation where X goes to

11
00:00:59,984 --> 00:01:07,651
two symbols A, B, right? And then anything
that B can produce in the first position

12
00:01:07,651 --> 00:01:14,564
will clearly be in the follow of A. So if
we have X goes to AB. And then through

13
00:01:14,564 --> 00:01:20,839
some more, steps, we can get something
like, this A goes, B goes to T beta, then

14
00:01:20,839 --> 00:01:26,523
we have a situation where the T comes
immediately after the A, and so clearly,

15
00:01:26,523 --> 00:01:32,429
something that was in the first of B, is
in the follow of A. So, so the basic rule

16
00:01:32,429 --> 00:01:38,334
is that you have two symbols that are
adjunct somewhere, the first of the second

17
00:01:38,334 --> 00:01:46,891
one is in the follow of the first one. Hm,
now Another interesting effect here is

18
00:01:46,891 --> 00:01:51,815
that, if we have, a symbol at the end of a
production. Let's take a look at the B

19
00:01:51,815 --> 00:01:56,738
here for a moment, okay? And a claim here
that anything that's in the follow of the

20
00:01:56,738 --> 00:02:01,542
left hand side is gonna be in the follow
of B. In this case, that the follow of X

21
00:02:01,542 --> 00:02:06,285
is a subset of the follow of B. And let's
take a look at that. Let's say that we

22
00:02:06,285 --> 00:02:10,908
have, a situation where we have a
derivation from the start symbol, okay? We

23
00:02:10,908 --> 00:02:16,243
wind up with X followed by T. It can, it
can be other stuff around the [inaudible]

24
00:02:16,243 --> 00:02:21,840
let's ignore that for the moment, let's
just focus on the XT. Then we can use this

25
00:02:21,840 --> 00:02:27,576
production X goes to AB and in one step we
can get to ABT. And then we see T was in

26
00:02:27,576 --> 00:02:32,344
the follow of X a nd also, T is in the
follow of B as a result, Okay. So,

27
00:02:32,344 --> 00:02:37,866
anything in the follow of X would also be
in the follow of B. And we can generalize

28
00:02:37,866 --> 00:02:42,556
this observation about what occurs at the
end of a production. So anything that

29
00:02:42,556 --> 00:02:47,483
occurs at the end of the production, it,
its follow set will include the follow set

30
00:02:47,483 --> 00:02:52,351
of the symbol on the left hand side of the
production. Well, what is the end of the

31
00:02:52,351 --> 00:02:57,219
production? If, if B can go to epsilon, if
B can disappear, then A will appear at the

32
00:02:57,219 --> 00:03:01,850
end of the production. Okay, so if B can
go to epsilon, then it will also happen

33
00:03:01,850 --> 00:03:06,658
that the follow of X, would be in the
follow of A. And following up here in our

34
00:03:06,658 --> 00:03:12,055
example, so we. Or up here we start with
the start symbol. We got to XT. In one

35
00:03:12,055 --> 00:03:17,955
step we got to ABT and so T was in the
follow of B. But now, B can go into

36
00:03:17,955 --> 00:03:24,420
epsilon and so we can also get to AT and
therefore T is also in the follow of A.

37
00:03:24,860 --> 00:03:29,723
And finally there's one special case.
Remember that we have our special symbol

38
00:03:29,723 --> 00:03:35,085
marking the end of the input, and what can
that follow? Well the end of the input is

39
00:03:35,085 --> 00:03:39,699
in the follow of the start symbol,
alright? And this is just a way again of

40
00:03:39,699 --> 00:03:44,625
keeping track of what we're going to do
when we run out of input. And we'll see

41
00:03:44,625 --> 00:03:49,862
how that's used when we built the parsing
tables but we always add as an initial

42
00:03:49,862 --> 00:03:55,268
condition, that dollar sign is in the
follow of the start symbol. So now, let's

43
00:03:55,268 --> 00:04:01,305
take a look at and sketch of the algorithm
for computing follows. So that's, as we

44
00:04:01,305 --> 00:04:07,294
just said, the dollar sign is in the
follow of the start symbol. And now we

45
00:04:07,294 --> 00:04:12,413
take a look at each production. Okay, A
goes to alpha X beta, we're, we're

46
00:04:12,413 --> 00:04:17,161
focusing here on the X. Okay, if we look
at every production and we look at every

47
00:04:17,161 --> 00:04:22,207
symbol on the right hand side of that
production. And the first of beta, okay,

48
00:04:22,207 --> 00:04:28,405
the thing that can follow x in this in
this production, the first of that will be

49
00:04:28,405 --> 00:04:33,891
in the follow of x, and also we just
subtract out epsilon if it was in the

50
00:04:33,891 --> 00:04:39,590
first sub-beta. We're not interested
anymore in the epsilons for the purposes

51
00:04:39,590 --> 00:04:45,361
of follow sites, epsilon never appears in
follow sites, so follow sites are always

52
00:04:45,361 --> 00:04:50,832
just sets of terminals. And now the second
part of the algorithm is it if we have

53
00:04:50,832 --> 00:04:56,317
some suffix of a production beta that can
go to Epsilon, so Epsilon is in the first

54
00:04:56,317 --> 00:05:01,142
beta. Alright, this suffix of the
production can completely disappear, then

55
00:05:01,142 --> 00:05:06,626
as we saw on the previous slide the follow
of left hand side symbol will be in the

56
00:05:06,626 --> 00:05:12,838
follow of X. And that's it in terms of the
rules for computing follow sets. So now

57
00:05:12,838 --> 00:05:17,904
let's work through an example. So here's
our grammar again. And we're going to

58
00:05:17,904 --> 00:05:23,232
compute, the follow sets for each of the
symbols of the grammar. So let's begin,

59
00:05:23,429 --> 00:05:28,791
with the, with the start symbol. We'll
start with the follow of E. And by

60
00:05:28,791 --> 00:05:35,003
definition, we know that dollar is in the
follow of E. So we get that one easily.

61
00:05:35,003 --> 00:05:40,996
And now the question is what else could be
in the follow of E, Alright? So in order

62
00:05:40,996 --> 00:05:46,623
to figure that out we have to look at
where E is used in the grammar, Alright?

63
00:05:46,623 --> 00:05:52,543
So remember always at follow sets are
about where the symbol is used. Not what

64
00:05:52,543 --> 00:05:58,009
it produces. Alright? So here. Is a place
where E is used, and we can see that it is

65
00:05:58,009 --> 00:06:03,494
merely followed by a terminal symbol, so
certainly close paren is in the follow of

66
00:06:03,494 --> 00:06:08,462
E, right? And there's one other place
where E is used, and that's over here. And

67
00:06:08,462 --> 00:06:13,172
it appears that the right end of the
production, and so then we know that

68
00:06:13,172 --> 00:06:18,592
anything that's in the follow of X is also
gonna be in the follow of E. And that's a

69
00:06:18,592 --> 00:06:23,883
constraint, and so we'll right that down
over here 'coz this is just a property of

70
00:06:23,883 --> 00:06:28,723
the relationship. That the follow sets,
will have when we're done computing them.

71
00:06:28,723 --> 00:06:33,561
This doesn't immediately tell us anything
new that's in the follow of E. But we know

72
00:06:33,561 --> 00:06:38,169
that as we go along, and we learn about
things that are in the follow of X, we'll

73
00:06:38,169 --> 00:06:42,692
have to add them to the follow of E. And
let me just divide up. The slide here so

74
00:06:42,692 --> 00:06:46,870
we will put our properties that we know
about relationships between fallocates

75
00:06:46,870 --> 00:06:51,102
over on the left hand side and we'll put
the actual fallocates over here on the

76
00:06:51,102 --> 00:06:55,259
right side. So, now to make, that's the
only two places, those are the only two pl

77
00:06:55,259 --> 00:06:59,512
aces where E is used in the grammar and to
make further progress we need to know

78
00:06:59,512 --> 00:07:03,743
something about the follow of X. Okay, if
we want to make further progress on the

79
00:07:03,743 --> 00:07:07,922
follow of E then we need to figure out
what's in the follow of X. So, let's focus

80
00:07:07,922 --> 00:07:12,206
on that for a minute. So, where's X used
in the grammar, well it's used in only one

81
00:07:12,206 --> 00:07:17,538
place and that's here, Okay? Where it
appears at the right end of a production.

82
00:07:17,538 --> 00:07:23,829
And what, and so therefore, the symbol on
the left hand side will be a subset of the

83
00:07:23,829 --> 00:07:30,121
follow set of X. So we're gonna know that
the follow of E is a subset of the follow

84
00:07:30,121 --> 00:07:35,866
of X. Alright? And what does that mean?
Well, so follow of X is a subset of follow

85
00:07:35,866 --> 00:07:40,700
of E. And follow of E is a subset of the
follow of X. So that really means that

86
00:07:40,700 --> 00:07:45,962
these two sets are equal. The follow of X
and the follow of E, whatever they wind up

87
00:07:45,962 --> 00:07:51,018
being, are gonna have to be the same set.
And now we've looked at all the places

88
00:07:51,018 --> 00:07:56,010
where E is used in the grammar. We've
looked at all the places where X is used

89
00:07:56,010 --> 00:08:01,579
in the grammar. We can't learn anything
more about what is in the sets, the follow

90
00:08:01,579 --> 00:08:06,955
sets of E and X. We're not forced to add
anything else, to either set, and so we're

91
00:08:06,955 --> 00:08:11,947
done. And so we can close off this set.
And we know the follow of E consists of

92
00:08:11,947 --> 00:08:18,266
dollar sign and closed paren. And we also
know that X. Has the same set, the same

93
00:08:18,266 --> 00:08:29,798
follow set. Alright, so now let's move on
to the follow of T, All right. So what's

94
00:08:29,798 --> 00:08:34,670
going to be in the follow of T? Well we,
again we have to look at where T is used

95
00:08:34,670 --> 00:08:39,359
in the grammar. So T is used in two
places. The first one is here in the first

96
00:08:39,359 --> 00:08:44,353
production. And so what's going to be in
the follow of T? Well it could be anything

97
00:08:44,353 --> 00:08:48,859
that is in the first of X. Okay? Cuz X
comes immediately after T. And if you

98
00:08:48,859 --> 00:08:53,975
recall from the previous video, there were
only two things in the first of X. One was

99
00:08:53,975 --> 00:08:59,317
plus. So this plus is definitely in the
follow of T and let's just review. [cough]

100
00:08:59,317 --> 00:09:05,610
Excuse me. How that can happen, so we can
go from E. To TX, okay? I'm using the

101
00:09:05,610 --> 00:09:11,248
first production. And now we see the X
comes after the T. And then in one more

102
00:09:11,248 --> 00:09:16,886
step, we can go to T plus E. And now we
have a derivation where plus follows T.

103
00:09:16,886 --> 00:09:22,624
And that's how we, that's, that's Y pluses
in the follow of T. Alright? So the other

104
00:09:22,624 --> 00:09:27,235
thing that was in the first of X was
epsilon, because there's an epsilon

105
00:09:27,235 --> 00:09:32,423
production for X over here. But remember
that we're not interested in, we don't

106
00:09:32,423 --> 00:09:37,738
include epsilon in follow sets. And so X
doesn't contribute anything else, to the,

107
00:09:37,930 --> 00:09:42,989
to the follow of T. But since X can go to
epsilon, remember what that means. That

108
00:09:42,989 --> 00:09:48,305
means that over here, looking back at this
first use of T again in the grammar, this

109
00:09:48,305 --> 00:09:53,835
X can disappear. Right and that means that
anything it is in the follow of E is also

110
00:09:53,835 --> 00:09:59,008
in the follow of T. Now we already know
the follow of E. So we can just add those

111
00:09:59,008 --> 00:10:03,533
things in. Okay? And let me write that
down over here, just so that we don't

112
00:10:03,533 --> 00:10:09,325
forget it. So, to follow. Of, of E is a
subset of the follow of T. We won't really

113
00:10:09,325 --> 00:10:15,287
need this fact again but, useful to write
it down, perhaps. Alright and now we are

114
00:10:15,287 --> 00:10:20,341
done with this use of x. We've included
everything implied by this production that

115
00:10:20,341 --> 00:10:25,765
we can in the follow of T and so now have
to look at the other place where T is used

116
00:10:25,765 --> 00:10:31,578
and that's over here. Okay, and so here
we're going to see that T is in the right

117
00:10:31,578 --> 00:10:37,859
end of a production, so anything that is
in the follow Y can also be in the follow

118
00:10:37,859 --> 00:10:43,057
of T, alright? So the follow of Y. Is
going to be a subset of the follow of T,

119
00:10:43,057 --> 00:10:48,360
alright. So now we can go off and work on
the follow of Y. We have to in order to

120
00:10:48,360 --> 00:10:53,664
figure out what the follow of T is going
to be, we're gonna have to know the follow

121
00:10:53,664 --> 00:10:58,712
of Y. So where is Y used in the grammar?
Well there is only one place and that's

122
00:10:58,712 --> 00:11:03,951
over here. And also Y appears in the right
hand of production which means that the

123
00:11:03,951 --> 00:11:09,403
left hand side symbol it's follow set will
be included in the follow of Y. >> And so

124
00:11:09,403 --> 00:11:15,120
the follow of t will be a subset of the
follow of y. All right? And now again, we

125
00:11:15,120 --> 00:11:21,054
have two follow sets that are subsets of
each other. Follow of y is a subset of

126
00:11:21,054 --> 00:11:26,843
follow of t, and follow of t is a subset
of follow of y. And so these two sets, we

127
00:11:26,843 --> 00:11:33,523
know are going to have to be equal. Okay?
So we can write down here. At the follow

128
00:11:33,523 --> 00:11:40,728
of Y, includes plus, dollar, enclose
parette. Just like the follow of T. And

129
00:11:40,728 --> 00:11:46,560
now we're done. We've, we've, follow of T,
and follow of Y. We've followed all the

130
00:11:46,560 --> 00:11:52,824
implications of, how the follow of T gets
things into, what can be included in the

131
00:11:52,824 --> 00:11:58,512
follow of T. We've worked out all the
places where Y is used in the grammar, and

132
00:11:58,512 --> 00:12:04,704
added all the things that we can, based
on, it's context. And there's nothing more

133
00:12:04,704 --> 00:12:10,536
that we're forced to add either said. So
we can go ahead and close these sets off.

134
00:12:10,536 --> 00:12:15,506
They're finished, Alright. So now We've
done the follow of E, X, T, and Y. So

135
00:12:15,506 --> 00:12:19,660
we've taken care of all the terminal
symbols. But, I'm sorry, All the

136
00:12:19,660 --> 00:12:24,806
non-terminal symbols. But we still need to
compute the follow sets for the terminal

137
00:12:24,806 --> 00:12:29,828
symbols. And unlike the case with first
sets, the follow sets for terminal symbols

138
00:12:29,828 --> 00:12:34,912
can actually be interesting. So let's take
a look, at the follow of open paren. Okay,

139
00:12:34,912 --> 00:12:39,562
what can follow an open paren in a
derivation? Well open paren is only used

140
00:12:39,562 --> 00:12:44,796
in one places. It's here. Okay. And so,
what can follow in open parens is whatever

141
00:12:44,796 --> 00:12:50,450
is in the first of E. And remember that
the first of E, was the same as the first

142
00:12:50,450 --> 00:12:56,240
of T, because T always produces something
in the first position. And the first of T

143
00:12:56,240 --> 00:13:02,872
was what? It was open paren. An int, 'kay?
And if you think about this for a minute,

144
00:13:02,872 --> 00:13:08,018
this makes complete sense. What can come
after an at any valid, at any valid string

145
00:13:08,018 --> 00:13:13,038
in this grammar, while it's going to be
another nested parenthize expression, or

146
00:13:13,038 --> 00:13:17,682
is it going to be an integer. In
particular, you couldn't have a times or a

147
00:13:17,682 --> 00:13:22,953
plus immediately after an and you couldn't
absolutely have the end of the input, you

148
00:13:22,953 --> 00:13:28,099
couldn't have the input stop after an and
have a valid string. So now let's take a

149
00:13:28,099 --> 00:13:34,374
look at the follow of. Okay? So what's in
that set? Again, we look at where the

150
00:13:34,374 --> 00:13:40,221
symbol is used. It's only used here, in
this one production. So and, because it

151
00:13:40,221 --> 00:13:45,683
appears at the right end of the
production, we know that whatever is in

152
00:13:45,683 --> 00:13:51,684
the follow of T is going to be in the
follow of ), all right. And so what was in

153
00:13:51,684 --> 00:13:57,933
the follow of T, [cough], that was +$),
Okay. So, now let's move on and take a

154
00:13:57,933 --> 00:14:04,916
look at the operators. Let's look at the
follow of plus. So where's plus used?

155
00:14:04,916 --> 00:14:10,623
Well, it's only used here. So whatever's
in the first of E is going to be in the

156
00:14:10,623 --> 00:14:16,113
follow of plus. And we already know what
the first of E was. That was an open

157
00:14:16,113 --> 00:14:22,341
[inaudible], An int, Okay. And remember
also that E cannot go to Epsilon. So, E

158
00:14:22,341 --> 00:14:27,363
cannot ever disappear completely because T
always produces at least one terminal.

159
00:14:27,363 --> 00:14:32,199
Therefore, only the things that are in the
first of year in the follow of plus.

160
00:14:32,199 --> 00:14:37,220
Because E can't go to Epsilon, we only
have to include the things that are in the

161
00:14:37,220 --> 00:14:42,118
first of E, in the follow of plus. Again,
if you think about it for a minute this

162
00:14:42,118 --> 00:14:46,458
makes complete sense. What could come
after a plus? Well, it could be an

163
00:14:46,458 --> 00:14:51,108
integer, the second argument to an
addition, or it could be the beginning of

164
00:14:51,108 --> 00:14:56,229
another nested expression. And it couldn't
be a times. It certainly couldn't be the

165
00:14:56,229 --> 00:15:01,422
end of the input cuz you always have to
have an argument after the plus. And, >>

166
00:15:01,422 --> 00:15:09,380
And I think that's it. I think that's all
the other possibilities. >> Okay, Alright.

167
00:15:10,980 --> 00:15:16,253
Now let's take a look at the follow of
times. What can come after a times. Where

168
00:15:16,253 --> 00:15:21,306
is times used, it's used here. So things
that are in the first of t. Are gonna be

169
00:15:21,306 --> 00:15:25,183
in the follow of times again, alright?
[inaudible] we already know what that is.

170
00:15:25,183 --> 00:15:29,259
That's the same as the first of E. That's
open paren and ints. And again, this makes

171
00:15:29,259 --> 00:15:32,838
complete sense. What can come after a
times? It's either the beginning of

172
00:15:32,838 --> 00:15:36,715
another [inaudible] expression or an
integer. It's certainly not a plus or the

173
00:15:36,715 --> 00:15:40,343
end of the input, okay? And again, T
cannot go to epsilon, and so that's the

174
00:15:40,343 --> 00:15:44,469
only thing. Those are the only things that
can be in the follow of times. And now we

175
00:15:44,469 --> 00:15:50,213
just have one more symbol to go. We have
to look at the follow of an integer, of an

176
00:15:50,213 --> 00:15:55,966
int. Okay, where is that used in the
grammar? Well, it's right here, Alright.

177
00:15:55,966 --> 00:15:59,948
So the, what's gonna be in the follow
[inaudible], what 's going to include

178
00:15:59,948 --> 00:16:04,908
everything in the first of Y. Okay. What's
in the first of Y, well times was in the

179
00:16:04,908 --> 00:16:09,781
first of Y, and epsilon was in the first
of Y but remember, we don't include

180
00:16:09,781 --> 00:16:14,718
epsilons in follow sets. So, Y contributes
times to the follow of int. But now,

181
00:16:14,718 --> 00:16:19,916
because Y could go to the epsilon and
epsilon could [inaudible], that means that

182
00:16:19,916 --> 00:16:25,049
this int could wind up being at the right
end of this production. Okay, it could,

183
00:16:25,049 --> 00:16:30,311
the Y could disappear and then whatever
could follow the T could also follow the

184
00:16:30,311 --> 00:16:35,255
int. Right, so we have to include the
things in the follow of T. In the follow

185
00:16:35,255 --> 00:16:41,260
of it, and what was in the follow of T
where that was a plus. It was a dollar.

186
00:16:41,260 --> 00:16:46,385
And it was a close paren, okay? And what
does that tell us? Well it tells us, okay

187
00:16:46,385 --> 00:16:52,030
for most anything to follow an int but as
an open paren cannot follow an int. So you

188
00:16:52,030 --> 00:16:57,156
can't have another nesit expression with
a, begin right after an int without an

189
00:16:57,156 --> 00:17:02,217
intervening operator, Alright? And that
completes the computation of the follow

190
00:17:02,217 --> 00:17:03,840
sets for this example.