1
00:00:03,300 --> 00:00:07,943
In the next few videos, we're gonna talk
about how to construct LL1 parsing tables.

2
00:00:07,943 --> 00:00:12,700
And in this particular video, we're gonna
begin by looking at how be build something

3
00:00:12,700 --> 00:00:17,405
called first sets. Before we get into the
main topic of this video, which is

4
00:00:17,575 --> 00:00:22,159
something called First Sets, we need to
say a little bit about how we're going to

5
00:00:22,159 --> 00:00:26,290
construct parsing tables, or what the
conditions are for constructing LL1

6
00:00:26,290 --> 00:00:30,365
parsing tables. And so what we're
interested in knowing, we're building a,

7
00:00:30,365 --> 00:00:34,780
we're building a parsing table. And we
want to know, for a given non terminal A.

8
00:00:34,780 --> 00:00:39,793
Kay, this is the leftmost non terminal.
And a given input symbol, the next input

9
00:00:39,793 --> 00:00:44,807
symbol T, [cough]. We want to know what
con-, under what conditions we will make

10
00:00:44,807 --> 00:00:50,014
the move A goes to alpha. We'll replace A,
the non terminal by the right hand side,

11
00:00:50,014 --> 00:00:54,533
alpha. Alright and that means that the
entry, in th, the AT entry in the table

12
00:00:54,533 --> 00:00:58,844
would be Alpha and there are two
situations in which we would like to do

13
00:00:58,844 --> 00:01:04,233
this. Alright? So the first one is if
alpha can derive T in the first position,

14
00:01:04,233 --> 00:01:09,821
That means that beginning with alpha,
there is some derivation, some sequence of

15
00:01:09,821 --> 00:01:15,551
moves, could be zero or more moves, that
will result in a T appearing in the first

16
00:01:15,551 --> 00:01:20,746
position of the string that's derived. And
if there is such a derivation, then using

17
00:01:20,746 --> 00:01:25,203
the move, A goes to alpha, at this point,
when T is the next input symbol, would be

18
00:01:25,203 --> 00:01:29,660
a good idea. Because then we would be able
to match the T. Eventually, alpha could

19
00:01:29,660 --> 00:01:34,061
generate the T, and then we'd be able to
match the T, and then continue with our

20
00:01:34,061 --> 00:01:38,499
parsing of the rest of the input. Alright,
so in this situation, when alpha can

21
00:01:38,499 --> 00:01:43,167
generate a T in the first position, we say
that T is an element of the first of

22
00:01:43,167 --> 00:01:47,835
alpha. T is one of the things, there may
be more things. But T is at least one of

23
00:01:47,835 --> 00:01:52,857
the things that alpha can produce, in the
very first position. One of the terminals,

24
00:01:52,857 --> 00:01:57,356
I should say, that alpha can produce in
the very first position. Now, there's

25
00:01:57,356 --> 00:02:02,338
another situation, a slightly, more
complicated situation, in which we might

26
00:02:02,338 --> 00:02:07,708
want to make the move, or we wou ld want
to make the move, That if we see A as the

27
00:02:07,708 --> 00:02:13,014
leftmost non terminal, and T as the next
input that we'd like to replace A by, A

28
00:02:13,014 --> 00:02:19,791
goes to alpha. Alright? And the situation
here that we're going to consider is what

29
00:02:19,791 --> 00:02:26,613
if, alpha, cannot derive T? So alpha
cannot, in any sequence of moves, derive

30
00:02:26,613 --> 00:02:32,746
T. So, in fact, what does that mean? That
means T is not. Gonna be in the first of

31
00:02:32,746 --> 00:02:37,850
alpha, okay? So, and our next input symbol
is T. We're still looking at the situation

32
00:02:37,850 --> 00:02:42,581
where we have A as the leftmost non
terminal, and T as the next input symbol.

33
00:02:42,581 --> 00:02:47,242
Now, This doesn't sound very promising.
Because we have an input symbol T that we

34
00:02:47,242 --> 00:02:51,945
want to match And the leftmost non
terminal that we've got, up next, that we

35
00:02:51,945 --> 00:02:56,682
have to do a derivation for, can't
generate the T. And so, but it turns out

36
00:02:56,682 --> 00:03:02,359
that, this, that it's not hopeless. That
we actually may still be able to parse the

37
00:03:02,359 --> 00:03:07,965
string, even in that situation, provided
that alpha can go to epsilon. So if alpha

38
00:03:07,965 --> 00:03:13,712
can derive epsilon, if alpha can go away
completely, and we can basically erase the

39
00:03:13,712 --> 00:03:19,389
alpha, then it could be that some other
part of the grammar can come in and match

40
00:03:19,389 --> 00:03:23,380
the T. Alright and so, in what situation
would that be? Well, here are the

41
00:03:23,380 --> 00:03:27,830
conditions. So, if A goes to Alpha as a
production and alpha can go to epsilon via

42
00:03:27,830 --> 00:03:31,950
zero or more moves. Alright, so alpha can
eventually be completely wiped out.

43
00:03:31,950 --> 00:03:38,431
Alright, and. If T can come immediately
after A in the grammar, so there has to be

44
00:03:38,431 --> 00:03:43,682
a derivation for this to make sense, there
should be a derivation where we are using

45
00:03:43,682 --> 00:03:48,684
the A, okay? With the A as an important
piece of the derivation you know, from the

46
00:03:48,684 --> 00:03:53,811
start symbol. And what comes immediately
after the A is the next input symbol that

47
00:03:53,811 --> 00:03:58,922
we are expecting. So in this situation, if
we could get rid of the A, Then by having

48
00:03:58,922 --> 00:04:04,152
a go at the epsilon then we'll still be on
track cuz potentially some other piece of

49
00:04:04,152 --> 00:04:09,104
grammar could come in and match the T.
Alright. So in that case, we would say

50
00:04:09,300 --> 00:04:14,398
what, what do we have to test for? What,
under what conditions can we do it? Well

51
00:04:14,398 --> 00:04:19,497
we want to be able to do this if T can
come after A in the grammar and we say

52
00:04:19,497 --> 00:04:24,791
that T is in the follow of A. T is one of
the things that can come after A in the

53
00:04:24,791 --> 00:04:29,889
grammar. Now this is an important point,
and a place where people sometimes get

54
00:04:29,889 --> 00:04:35,188
confused and so I want to, to emphasize
this, notice that. We are not talking

55
00:04:35,188 --> 00:04:41,686
about A deriving T. A does not produce T.
T appears in a derivation After A, okay?

56
00:04:41,686 --> 00:04:46,775
So the A and the T here it, it doesn't
have anything to do with what A produces.

57
00:04:46,775 --> 00:04:51,926
This has to do with where A can appear in
derivations, alright? So if the T can come

58
00:04:51,926 --> 00:04:56,891
after the A in a derivation, then we say
the T is in the follow of A. Right. So in

59
00:04:56,891 --> 00:05:01,855
this video we're gonna focus on, only this
first part, the first sets. In the next

60
00:05:01,855 --> 00:05:06,634
video, we'll look at the follow sets, and
then the video after that, we'll talk

61
00:05:06,634 --> 00:05:13,903
about how to put it all together to build
this parcing table. [sound] All right,

62
00:05:13,903 --> 00:05:18,440
let's focus now on our main topic for this
video, the computation of first sets. So

63
00:05:18,440 --> 00:05:22,700
here, first of all, we have to have a
definition of what a first set is. And so

64
00:05:22,700 --> 00:05:27,181
we're going to say, for an arbitrary,
string. This is actually, x here is a

65
00:05:27,181 --> 00:05:31,109
string. Could be a ter-, could be a single
terminal, it could be a single

66
00:05:31,109 --> 00:05:35,565
non-terminal, or it could be a string of
grammar symbol. All right, and if that If

67
00:05:35,565 --> 00:05:41,052
that X, can derive T in the first position
through some sequence of moves, then we

68
00:05:41,052 --> 00:05:46,147
say that T, T is a terminal here, is in
the first of X, okay? So all the possible

69
00:05:46,147 --> 00:05:51,700
terminals that can be derived in the first
position will be in the first, of X Now

70
00:05:51,700 --> 00:05:57,078
For technical reasons that will become
clear in a minute we also need to keep

71
00:05:57,078 --> 00:06:02,250
track of whether x can produce epsilon.
Now so even though epsilon is not a

72
00:06:02,250 --> 00:06:07,973
terminal symbol, if x can go to epsilon be
a zero or more steps then we'll say that

73
00:06:07,973 --> 00:06:13,283
epsilon is in the first of x and this
turns out to be needed. We need to keep

74
00:06:13,283 --> 00:06:18,662
track of whether x whether things can
produce epsilon in order to compute all

75
00:06:18,662 --> 00:06:24,763
the terminals that are in the first set of
a given grammar symbol. Alright so now

76
00:06:24,763 --> 00:06:30,029
here's a sketch of the algorithm. So first
of all for any terminal symb ol the only

77
00:06:30,029 --> 00:06:34,846
thing the terminals can produce are
themselves. So every terminal symbol in

78
00:06:34,846 --> 00:06:41,369
here I should just say T is the terminal.
So for every terminal symbol, it is in,

79
00:06:41,369 --> 00:06:47,608
it's first set just consists of a the site
containing only that terminal. All right,

80
00:06:47,608 --> 00:06:52,860
so now let's consider a non terminal X,
okay so here X is a non terminal, and what

81
00:06:52,860 --> 00:06:58,178
it would be in the conditions when epsilon
is in the first of X, well, if there's a

82
00:06:58,178 --> 00:07:03,624
epsilon production, if X goes immediately
to epsilon, then, obviously, X can produce

83
00:07:03,624 --> 00:07:08,812
epsilon, epsilon should be in the first of
X But also, if X can produce any other

84
00:07:08,812 --> 00:07:13,932
right hand side Alright, Where everything
on the right hand side can go to epsilon.

85
00:07:13,932 --> 00:07:18,369
Well, then the whole right hand side can
go to epsilon. So, in that case also

86
00:07:18,369 --> 00:07:23,339
epsilon is in the first of X. I noticed
that this will only happen if this, it can

87
00:07:23,339 --> 00:07:28,309
only, it can only potentially happen if
all the EIS here are non-terminal symbols

88
00:07:28,309 --> 00:07:32,805
themselves. Obviously if there's any
terminal symbols on the right hand side

89
00:07:32,805 --> 00:07:37,301
then that production can never go
completely to the empty string. Okay. It

90
00:07:37,301 --> 00:07:42,051
will always produce at least that, that
terminal But if every non-terminal. On the

91
00:07:42,051 --> 00:07:46,133
right-hand side can produce epsilon.
Meaning epsilon's in the first of all

92
00:07:46,133 --> 00:07:50,110
those non-terminals. And there are no
terminals on the right hand side. Then,

93
00:07:50,413 --> 00:07:58,376
Then, epsilon will be in the first of X.
Alright there's one other situation and

94
00:07:58,376 --> 00:08:04,627
here's where we make use of the fact that
we are keeping track of where epsilon can

95
00:08:04,627 --> 00:08:10,878
be produced alright. So let's say that we
have a production like this okay and let's

96
00:08:10,878 --> 00:08:16,906
say the first N symbols A1 through AN here
can all go to epsilon. So this can all

97
00:08:16,906 --> 00:08:23,157
disappear and can be replaced by the empty
string. What does that mean, so if we have

98
00:08:23,157 --> 00:08:28,879
derivation like this? Okay were, to some
number of moves it goes to Alpha, well

99
00:08:28,879 --> 00:08:34,821
that means that X can through a bunch of
moves here to derive Alpha itself, okay.

100
00:08:34,821 --> 00:08:40,837
So, X will go to Alpha by wiping out all
of the AIs, and I forgot to put the alpha

101
00:08:40,837 --> 00:08:46,629
here on the end, there should be an Alpha
after As have been there. Okay? And wh at

102
00:08:46,629 --> 00:08:51,584
does this mean? Well this means that
anything that is in the first of alpha is

103
00:08:51,584 --> 00:08:56,666
going to also be in the first of X. All
right? So, if any prefix of the right-hand

104
00:08:56,666 --> 00:09:01,621
side can disappear then the remaining
suffix, the alpha, it doesn't matter what

105
00:09:01,621 --> 00:09:07,212
the alpha is, is left. Then the first of
alpha will be a subset of the non-terminal

106
00:09:07,212 --> 00:09:12,275
on the right, left hand side of X in this
case. All right? Okay? Alright. So that is

107
00:09:12,275 --> 00:09:17,107
a definition of a first sets and how you
compute them. Okay. And we have to, we

108
00:09:17,107 --> 00:09:22,127
have to compute them for the terminals and
for the non-terminals, alright? That's

109
00:09:22,127 --> 00:09:27,021
what these; these second two rolls here
cover the non-terminals. I just noticed,

110
00:09:27,210 --> 00:09:32,041
as I mentioned here at the beginning that
this is well defined for any other

111
00:09:32,230 --> 00:09:36,183
Grammar, sequence as well. I mean, excuse
me, any other string in the grammar as

112
00:09:36,183 --> 00:09:39,988
well. It doesn't, if I, if I know how to
compute it for terminals, I know how to

113
00:09:39,988 --> 00:09:43,941
compute it for non terminals. Then I can
compute it for arbitrary strings in the

114
00:09:43,941 --> 00:09:51,317
grammar, as well. Let's analyze, do an
example. Let's take a look at this grammar

115
00:09:51,317 --> 00:09:57,276
and let's see if we can compute the first
sets. Let's start with the easy stuff.

116
00:09:57,276 --> 00:10:04,425
Let's do the terminal symbols. Alright So,
for the terminals, it's really, you know,

117
00:10:04,425 --> 00:10:11,548
extremely straightforward. The first of
plus is plus. The first of times Is just

118
00:10:11,548 --> 00:10:17,329
times every terminal is in a, has its
first set, the first set of every terminal

119
00:10:17,329 --> 00:10:23,255
is just the second term in that terminal
and so on for the others, and this is not

120
00:10:23,255 --> 00:10:30,049
worth writing out. So it'll be the first
of open paren will just be open paren, the

121
00:10:30,049 --> 00:10:35,975
first of close paren will be just close
paren and I think that is all. Now we have

122
00:10:35,975 --> 00:10:41,322
to do ants as well, okay? Alright, so
these are the first sets for the terminal

123
00:10:41,322 --> 00:10:46,353
symbols. And now let's look at something
more interesting; let's talk about the

124
00:10:46,353 --> 00:10:54,674
first of the non terminal symbols. So What
about the first of E? Well, if we look at

125
00:10:54,674 --> 00:11:01,470
the production for E, let's remember our
rules. So we know that anything that's in

126
00:11:01,470 --> 00:11:08,054
the first of T will also be in the first
of E. So the first of T Is a subset of th

127
00:11:08,054 --> 00:11:12,849
e first of E. Okay so in order to know
what the first of E is we have to know

128
00:11:12,849 --> 00:11:18,155
what the first of T is. At least to know
part of the first of E we have to know the

129
00:11:18,155 --> 00:11:23,343
first of T. So let's move on then to first
computing. The first of T Let's, let's try

130
00:11:23,343 --> 00:11:28,211
to get that set. Now the first of T is
actually pretty easy because if we look at

131
00:11:28,211 --> 00:11:33,200
the productions for T we can see that they
produce terminals in the first position.

132
00:11:33,200 --> 00:11:38,309
All right? So the only possibility in the,
the only possibilities in the first of T

133
00:11:38,309 --> 00:11:43,298
are open per en and int. And since there
are only two productions for T and both of

134
00:11:43,298 --> 00:11:47,746
them have a terminal in the very first
position, there's no other terminal

135
00:11:47,746 --> 00:11:52,615
symbols that could be produced in the
first position by T. So we can just read

136
00:11:52,615 --> 00:11:58,780
off the first of T directly from the
grammar. And it's the open paren in int.

137
00:11:59,680 --> 00:12:06,266
Okay? Now, let's return to thinking about
the first of E. So remember there was

138
00:12:06,266 --> 00:12:11,152
another case that we need to keep track
of. Or, sorry, that we have to consider.

139
00:12:11,152 --> 00:12:16,228
So, it could be, or, clearly everything in
the first of T is in the first of E and

140
00:12:16,228 --> 00:12:21,368
we've already noted that down. But if T
can go to epsilon then things that are in

141
00:12:21,368 --> 00:12:26,518
the first of X Could also be in the first
of E. And now we've computed the first of

142
00:12:26,518 --> 00:12:31,828
T and we see that epsilon is not in there.
The first of T always generates at least

143
00:12:31,828 --> 00:12:36,953
one terminal symbol, and so there'll never
be a situation in which X can contribute

144
00:12:36,953 --> 00:12:41,522
to the first of E because T is always
guaranteed to generate at least one

145
00:12:41,522 --> 00:12:46,585
terminal. So in fact this subset that we
wrote up here is not a subset at all, it's

146
00:12:46,585 --> 00:12:51,340
an inequality. The first of T and the
first of E are equal. So the first of E is

147
00:12:51,340 --> 00:12:56,280
also open per rand and Nth. All right? So
now let's take a look at the first of X.

148
00:12:56,920 --> 00:13:02,218
Okay? So, the first effects well clearly
pluses in the first of X because one

149
00:13:02,218 --> 00:13:07,795
production per X plus immediately in the
first positions, so we must add plus to

150
00:13:07,795 --> 00:13:13,651
the first of X. And then X has an epsilon
production so it can also go to epsilon so

151
00:13:13,651 --> 00:13:20,983
that means epsilon is also in the first of
X And what about the first of Y. Well, the

152
00:13:20,983 --> 00:13:24,482
fir st of Y, it's a similar structure to
the productions request, we see we have

153
00:13:24,482 --> 00:13:28,116
one production here in the [inaudible] of
the terminal in the first position, and

154
00:13:28,116 --> 00:13:32,914
that's times. So the first of y has times
in it. And then, y also has an epsilon

155
00:13:32,914 --> 00:13:37,907
production. Y can go directly to epsilon,
so epsilon is also in the first of y.

156
00:13:37,907 --> 00:13:43,223
Alright? And that's actually it for this
grammar. These are the complete first sets

157
00:13:43,223 --> 00:13:48,540
for all of the symbols of the grammar. The
terminals just have themselves in their

158
00:13:48,540 --> 00:13:53,533
first sets and then the non-terminals we
computed have these sets. So that

159
00:13:53,533 --> 00:13:58,914
concludes our discussion of first sets and
in the next video, we're going to take a

160
00:13:58,914 --> 00:14:00,860
look at computing follow sets.