1
00:00:03,360 --> 00:00:08,463
In this video, we're going to continue our
discussion of top-down parsing algorithms

2
00:00:08,463 --> 00:00:16,500
with another strategy called predictive
parsing. So, predictive parsing is a lot

3
00:00:16,500 --> 00:00:21,417
like recursive descent. It's still a
top-down parser. But the parser is able to

4
00:00:21,417 --> 00:00:26,548
predict which production to use. And it's
never wrong. [inaudible] parser is always

5
00:00:26,548 --> 00:00:31,618
able to guess correctly which production
will yield to, will lead to a successful

6
00:00:31,618 --> 00:00:36,956
parse, if any production. Well, it lead to
a successful parse. And it does have some

7
00:00:36,956 --> 00:00:42,274
two ways; first of all it looks at the
next few tokens, so it uses look-ahead to

8
00:00:42,274 --> 00:00:47,793
try to figure out which production should
be used. So, based on what's coming up in

9
00:00:47,793 --> 00:00:53,111
the input string, but also it restricts
the grammars. So this, this is only works

10
00:00:53,111 --> 00:00:59,315
for a restricted form of grammars. And
there's, the advantage is that there's no

11
00:00:59,315 --> 00:01:04,758
back tracking involved and so the parser
is completely deterministic if you were to

12
00:01:04,758 --> 00:01:11,583
try alternatives. The predictive parsers
accept what are called the LLK grammars.

13
00:01:11,583 --> 00:01:18,576
And this is a really cryptic name, and so
let me explain it. The first L stands for

14
00:01:18,576 --> 00:01:24,559
left-to-right scan. So that means we're
starting at the left end of the input and

15
00:01:24,559 --> 00:01:29,966
reading left to right. And in fact that's
what we always do, so all the techniques

16
00:01:29,966 --> 00:01:35,507
that we looked at, look at will have an L
in the first position. The second L stands

17
00:01:35,507 --> 00:01:40,581
for a leftmost derivation. So we are
constructing a leftmost derivation. That

18
00:01:40,581 --> 00:01:46,122
means we're always working on the leftmost
non-terminal in the parse tree. And K

19
00:01:46,122 --> 00:01:54,624
here, stands for K tokens of look ahead.
And in practice, while the theory is

20
00:01:54,624 --> 00:02:00,133
developed for arbitrary 'k', in practice,
'k' is always equal to one. And so in

21
00:02:00,133 --> 00:02:05,642
fact, we'll only discuss the 'k's, 'k'
equals to one, in these videos. To review,

22
00:02:05,642 --> 00:02:11,886
in recursive descent parsing in each step,
there may be many choices of production to

23
00:02:11,886 --> 00:02:18,290
use, and so we need to use backtracking to
undo bad choices. In an LL-1 parser, in

24
00:02:18,290 --> 00:02:23,542
every step, there's only going to be one
choice of productions, of possible

25
00:02:23,542 --> 00:02:29,077
production to use. And, and what does that
mean? Well, it means that if I have an

26
00:02:29,077 --> 00:02:34,968
input string if I have a configuration of
the parser where I have some terminal

27
00:02:34,968 --> 00:02:40,858
symbols omega and a non terminal a you
know, possibly now followed by some other

28
00:02:40,858 --> 00:02:46,181
stuff there could be terminals and
nonterminals, but again a here is the

29
00:02:46,181 --> 00:02:54,569
leftmost nonterminal. And, the next input.
Is a token T Well then there is exactly

30
00:02:54,569 --> 00:03:04,736
one production A goes to alpha on input T.
Okay, there's only one possible production

31
00:03:04,736 --> 00:03:10,801
that we can use. And any other production
is guaranteed to be incorrect. Now it can

32
00:03:10,801 --> 00:03:17,009
be that, that even A goes to Alpha won't
succeed. It could be that we will be in a

33
00:03:17,009 --> 00:03:22,503
situation where there's no production we
could use. But in [inaudible] parser,

34
00:03:22,503 --> 00:03:28,569
there will always be at most one that we
could use. So in this case we would chose

35
00:03:28,569 --> 00:03:36,583
to rewrite the string to Omega Alpha Beta.
Let's take a look at our favorite grammar,

36
00:03:36,583 --> 00:03:41,451
the one we've been using for the last
couple of videos. We can see an issue here

37
00:03:41,451 --> 00:03:46,144
with using this grammar for a predictive
parser. Take a look at the first two

38
00:03:46,144 --> 00:03:51,140
productions for T. They both begin with
N's. And so if I tell you that the next

39
00:03:51,140 --> 00:03:56,524
terminal in the input stream as we're
parsing along is an integer that doesn't

40
00:03:56,524 --> 00:04:01,975
really help you in trying to distinguish
between these two productions in deciding,

41
00:04:01,975 --> 00:04:07,163
deciding which one to use. So in fact with
only one token of look ahead, I can't

42
00:04:07,360 --> 00:04:12,748
choose between these two productions. And
that is not the only problem actually, so

43
00:04:12,748 --> 00:04:18,008
we have a problem with T but the same
problem exist with E. We can see that here

44
00:04:18,008 --> 00:04:22,938
both production for E begin with the
non-terminal T, and it is really clear

45
00:04:22,938 --> 00:04:28,264
what we're to make of that because a T
against a non-terminal terminal, so how we

46
00:04:28,264 --> 00:04:33,523
even do the prediction but the fact that
they begin with the same thing suggest

47
00:04:33,523 --> 00:04:38,914
that it's not going to be easy for us to
predict which production to use based of

48
00:04:38,914 --> 00:04:44,177
only a single token of look ahead. So what
we need to do here is we need to change

49
00:04:44,177 --> 00:04:49,160
the grammar. This grammar is actually
unacceptable for predictive parsing, or at

50
00:04:49,160 --> 00:04:54,395
least for LL1 parsing. And we need to do
something that's called left factoring the

51
00:04:54,395 --> 00:05:01,037
grammar. So the idea behind left factoring
is to eliminate the common prefixes of

52
00:05:01,037 --> 00:05:06,355
multiple productions for one non terminal.
So that's a mouthful. Let's do an example.

53
00:05:06,355 --> 00:05:11,289
Let's begin with the productions for E.
And we can see, again, that E, that both

54
00:05:11,289 --> 00:05:16,607
productions for E begin with the same, the
same prefix. What we're going to do is

55
00:05:16,607 --> 00:05:21,925
just factor out that common prefix into a
single production. So we're going to have

56
00:05:21,925 --> 00:05:26,944
one production where E goes to T. And then
we're going to have multiple suffixes. So

57
00:05:26,944 --> 00:05:31,650
let's introduce a new non terminal X that
will handle the rest. So here, we have E

58
00:05:31,650 --> 00:05:36,239
goes to TX. So it says that everything
that E produces begins with T, and that's

59
00:05:36,239 --> 00:05:41,003
consistent with these two productions. And
now we have to write another production

60
00:05:41,003 --> 00:05:45,817
for X that handles the rest. And what
would that be? Well, one possibility is if

61
00:05:45,817 --> 00:05:50,790
we're in this production, we need to have
a Plus E and then in this production

62
00:05:50,790 --> 00:05:56,081
there's nothing. So that's easy to handle,
right. One possibility for X as it goes to

63
00:05:56,081 --> 00:06:01,117
Plus E and the other possibility as it
goes to Epsilon. And now you can see the

64
00:06:01,117 --> 00:06:06,026
general idea. We factor other common
prefix, we have one production that deals

65
00:06:06,026 --> 00:06:10,998
with the prefix and then we write, and
then we introduce a non terminal or the

66
00:06:10,998 --> 00:06:16,077
different suffixes. And then we just have,
multiple productions, one for each

67
00:06:16,077 --> 00:06:21,517
possible suffix. And you can see what this
is going to do. This is effectively going

68
00:06:21,517 --> 00:06:26,170
to delay the decision about which
production we're using. So instead of

69
00:06:26,170 --> 00:06:31,348
having to decide immediately which
production we're going to use for E. Here,

70
00:06:31,348 --> 00:06:36,264
in this grammar, we wait until we've
already seen the T, whatever is derived

71
00:06:36,264 --> 00:06:41,376
from the T. And then we have to decide
whether the rest of the production is a

72
00:06:41,376 --> 00:06:47,840
plus, E or the empty string. Let's do the
other, set of productions. So we have tea

73
00:06:48,012 --> 00:06:52,736
goes to, and now the common prefix is int
that we want to eliminate So we're going

74
00:06:52,736 --> 00:06:57,172
to have just one production that begins
with int and then we'll have a new, a

75
00:06:57,172 --> 00:07:01,608
non-terminal to stand for the various
possible suffixes. And now we also have

76
00:07:01,608 --> 00:07:06,159
another production that doesn't h ave
anything to do with int, and so we'll just

77
00:07:06,159 --> 00:07:11,170
leave that one alone, that production just
stays here. Because it already begins with

78
00:07:11,170 --> 00:07:15,664
something different we won't have any
trouble predicting between these two

79
00:07:15,664 --> 00:07:20,405
possible productions, these two possible
productions. And now we have to write. The

80
00:07:20,405 --> 00:07:26,810
productions for Y And again, we just take,
the suffixes of the productions that we,

81
00:07:27,038 --> 00:07:32,681
left factored and write them down as
alternatives. So one is empty and the

82
00:07:32,681 --> 00:07:41,763
other one is times T. So we wind up with
times T or epsilon. So here is the left

83
00:07:41,763 --> 00:07:48,496
factor grammar now type out neatly. And we
use this grammar to construct a parsing

84
00:07:48,496 --> 00:07:55,131
table. And let's not worry right now about
how we got this table, I'm not gonna give

85
00:07:55,131 --> 00:08:01,056
the algorithm right now. But, let's just
say that we got it somehow. And, what I'm

86
00:08:01,056 --> 00:08:06,150
going to explain is how we got the table.
So, One dimension of the table is the

87
00:08:06,150 --> 00:08:11,439
current left most, non-terminal in the par
stream. That's on the rows. And then the

88
00:08:11,439 --> 00:08:16,729
columns represent the next input token So,
the next token in the input stream. And,

89
00:08:16,729 --> 00:08:21,430
then the entry is the right hand side of
the production to use. So, which

90
00:08:21,430 --> 00:08:26,589
production that we should used at that
point in the pars. That's the production

91
00:08:26,589 --> 00:08:32,088
that's predicted. So let's do an example.
So let's look at E INT entry. So this

92
00:08:32,088 --> 00:08:37,376
entry right here. Now what this says is
that when the current nonterminal is E,

93
00:08:37,376 --> 00:08:42,868
meaning the left most nonterminal on the
parks tree and the next input is in, the

94
00:08:42,868 --> 00:08:48,157
thing that we see coming up in the input
is an integer. Then we should use the

95
00:08:48,157 --> 00:08:55,392
production E goes to TX. So we should
expand E with the children TX. Let's do

96
00:08:55,392 --> 00:09:02,189
another example. So when the current
non-terminal is Y and the current token,

97
00:09:02,189 --> 00:09:08,900
the current input is plus, then we should
use the production Y goes to epsilon.

98
00:09:08,900 --> 00:09:13,673
Okay, what that says is, it's a little bit
different situation than the previous one,

99
00:09:13,673 --> 00:09:18,045
it says look when you see a plus in the
input and your current left most

100
00:09:18,045 --> 00:09:22,761
non-terminal is y, the only way this parse
is going to succeed is if the y doesn't

101
00:09:22,761 --> 00:09:27,650
produce anything. You need to get rid of
the y and move on to a nother non-terminal

102
00:09:27,650 --> 00:09:32,424
whichever one is left-most after you get
rid of the y. If you want to have any hope

103
00:09:32,424 --> 00:09:38,036
of parsing this particular string. And
finally, notice that a lot of the entries

104
00:09:38,036 --> 00:09:43,718
are blank and those are error entries. So
let's take a look at the E star entry.

105
00:09:43,718 --> 00:09:49,256
That says that if the leftmost non
terminal is E and the next input token is

106
00:09:49,256 --> 00:09:55,082
a time symbol, a star. Well, then there is
no move that you can make. There is, there

107
00:09:55,082 --> 00:10:00,908
is no production you can use for E that's
going to successfully parse that input.

108
00:10:00,908 --> 00:10:08,112
And this is the point at which you would
raise a parsing error. In the rest of this

109
00:10:08,112 --> 00:10:13,182
video, I'm gonna give the algorithm for
parsing using a parsing table. And then in

110
00:10:13,182 --> 00:10:17,877
future videos, we'll explain how to
construct a parsing table. So the method

111
00:10:17,877 --> 00:10:22,948
for parsing using a parsing table is
similar to recursive descent. Expect that

112
00:10:22,948 --> 00:10:27,831
for the leftmost non terminal S in the
tree, we look at the next input token A.

113
00:10:27,831 --> 00:10:32,714
And then as we just illustrated with the
examples, we look up in the table the

114
00:10:32,714 --> 00:10:38,082
production to use at the low, at the, at
the entry S, A. And instead of using

115
00:10:38,082 --> 00:10:44,339
recursive functions, to trace out the
parse tree, we're going to have a stack of

116
00:10:44,339 --> 00:10:50,183
records that can, record the frontier. And
so at any point in the [inaudible] tree we

117
00:10:50,183 --> 00:10:54,655
will have some non-terminals that have yet
to be expanded. Those are always at the

118
00:10:54,655 --> 00:10:58,964
frontier at the current leaves of the
[inaudible] tree. And also there are some

119
00:10:58,964 --> 00:11:03,218
terminals that we have yet to match
against. Those will all be recorded out of

120
00:11:03,218 --> 00:11:07,799
stack. The important property of the stack
is that the left most pending terminal or

121
00:11:07,799 --> 00:11:11,998
non-terminal is always at the top of the
stack. So, either the terminal we are

122
00:11:11,998 --> 00:11:16,634
trying to match or the non-terminal we are
trying to expand will always be on top of

123
00:11:16,634 --> 00:11:21,074
our stack. We'll reject if we reach an
error state. So if we look up one of those

124
00:11:21,074 --> 00:11:25,636
empty entries in the table, we will reject
the string. And we'll accept if we reach

125
00:11:25,636 --> 00:11:29,809
the end of the input, and we have an empty
stack. Meaning we have no pending

126
00:11:29,809 --> 00:11:36,200
unmatched terminals or unexpanded non
terminals. So, here's the algorithm, we

127
00:11:36,200 --> 00:11:41,516
initialize the stack to just the start
symbol S and a special symbol $. The $ is

128
00:11:41,516 --> 00:11:46,491
not a part of the alphabet or you can
think of it we extend wherever our

129
00:11:46,491 --> 00:11:51,944
alphabet is with a new symbol $. $ Marks
the mottom of the stack and you can think

130
00:11:51,944 --> 00:11:57,396
of it also as marking the end of input.
So, this is just a way of recording where

131
00:11:57,396 --> 00:12:03,101
the end of the input is going to be. Okay,
so the, so once we've matched, something

132
00:12:03,101 --> 00:12:08,637
against S, then whatever's left, it better
be at the end of the input. That's what

133
00:12:08,637 --> 00:12:14,033
the, that stack, expresses. And now we're
at a loop, so we're gonna repeat the

134
00:12:14,033 --> 00:12:19,500
following moves until; we can't repeat
them anymore Until the stack is empty.

135
00:12:19,500 --> 00:12:23,912
Okay? And there's two possible moves.
Let's do the terminals first. So let's say

136
00:12:23,912 --> 00:12:28,216
the top of our stack is a terminal. So
here we're dividing the stack to the top

137
00:12:28,216 --> 00:12:32,575
of the stack and the rest of the stack.
So, what are we going to do if the top of

138
00:12:32,575 --> 00:12:37,042
the stack is a terminal? Well we're going
to try to match the input. So we're going

139
00:12:37,042 --> 00:12:41,455
to say well if the top of the stack, the
terminal on top of the stack, matches the

140
00:12:41,455 --> 00:12:45,659
next thing in the input, then we advance
the input. And we pop the stack. So we

141
00:12:45,659 --> 00:12:49,988
have successfully matched the input
against the, the terminal. And so that

142
00:12:49,988 --> 00:12:54,372
terminal is done, and we should progress
into the stack, and match the next thing

143
00:12:54,372 --> 00:12:58,810
that hasn't been handled yet. And if they
don't match, if the terminal that we are

144
00:12:58,810 --> 00:13:03,358
looking at doesn't match the next thing in
the input, well, that's an error. We don't

145
00:13:03,358 --> 00:13:07,742
have any backtracking here. There's no way
to parse the string, so we'll raise

146
00:13:07,742 --> 00:13:12,820
[inaudible]. Now the second class of moves
is deals with the non-terminal. So let's

147
00:13:12,820 --> 00:13:17,182
say at the top of the stack is the
non-terminal x. So remember that the top

148
00:13:17,182 --> 00:13:21,311
of the stack will be a non-terminal,
exactly when that is the left most

149
00:13:21,311 --> 00:13:26,197
non-terminal. So now what we, now what we
do is we look at our pricing table under

150
00:13:26,197 --> 00:13:30,908
the entry for x and the next input symbol
and that should give us the right hand

151
00:13:30,908 --> 00:13:35,859
side of a production. Okay? And now what
we do is we pop X off the stack, and we

152
00:13:35,859 --> 00:13:41,289
push the, the children of X i n the parse
tree under the stack. So this is the way

153
00:13:41,289 --> 00:13:46,261
we expand X. So now, the leftmost
unhandled thing in the parse is going to

154
00:13:46,261 --> 00:13:51,429
be Y1, because that's the first child of
X. And then all the other children of X

155
00:13:51,429 --> 00:13:56,532
are next. And then whatever else is in the
stack. And again, if there's no entry,

156
00:13:56,728 --> 00:14:02,224
for, the current non terminal and input in
the table, then that's an error, and the

157
00:14:02,224 --> 00:14:11,562
parsing stops. So let's through an example
using our, pricing table, and. You might

158
00:14:11,562 --> 00:14:16,258
want to refer back to the parsing table,
have not included it here, because there

159
00:14:16,258 --> 00:14:20,824
isn't space for it. But I'll work through
it, and you can go back and look at it at

160
00:14:20,824 --> 00:14:25,282
some point, and convince yourself that I'd
made the right moves. So initially, our

161
00:14:25,282 --> 00:14:29,418
stack is E$. So E was our start symbol,
and $ is our end of input symbol. And our

162
00:14:29,418 --> 00:14:33,876
input, we're gonna try to parse the input
[inaudible] times [inaudible], that's what

163
00:14:33,876 --> 00:14:37,959
we want to parse. And then, of course, we
have our new symbol $, we'll tack that

164
00:14:37,959 --> 00:14:42,310
onto the end of the input. And if all goes
well, the dollar sign on the stack will

165
00:14:42,310 --> 00:14:46,607
match up against the dollar sign at the
end of the input. Again, dollar sign here

166
00:14:46,607 --> 00:14:51,352
is just a way of marking. The end of the
input and expressing that we need to parse

167
00:14:51,352 --> 00:14:56,752
the entire input. And so now if you look
up the E int entry, so the first terminal

168
00:14:56,752 --> 00:15:02,530
in the, the next terminal in the input and
the left most [inaudible] terminal in our

169
00:15:02,530 --> 00:15:08,170
parse, you would see that we're actually
supposed to take is to use the production

170
00:15:08,170 --> 00:15:13,599
E goes to TX. And let me over here at the
same time construct our pars-trey. 'Kay,

171
00:15:13,599 --> 00:15:18,387
so initially our stack, again, the stack
is the frontier of the parstrey.

172
00:15:18,455 --> 00:15:23,850
Initially, all we have is the root of the
parstrey and that is its own frontier,

173
00:15:23,850 --> 00:15:29,380
it's just one symbol, we haven't processed
it yet. And so E is on the stack, E is

174
00:15:29,380 --> 00:15:35,112
unexpanded in the parstrey, and now we're
going to use the production E goes to TX.

175
00:15:35,112 --> 00:15:40,462
So we'll have, T and X added as children.
What happens next? Well E is popped off

176
00:15:40,462 --> 00:15:45,902
the stack. T and X are pushed on to the
stack. And now notice the frontier of the

177
00:15:45,902 --> 00:15:51,275
parse tree, is TX. So t hese is usually
unprocessed leaves Either unmatched input

178
00:15:51,275 --> 00:15:56,852
or unexpanded non-terminals And in fact
the stack records exactly which one is

179
00:15:56,852 --> 00:16:01,884
left most. So T is at the top of the
stack. X is below it, on the stack. Okay

180
00:16:01,884 --> 00:16:07,665
well we still haven't consumed any input.
And now if we look at the T, int entry it

181
00:16:07,665 --> 00:16:13,259
says to use T goes to int Y. And so now we
can expand T by [inaudible] y. And now

182
00:16:13,259 --> 00:16:19,577
what's going to happen is T is popped off
the stack. Int and Y are pushed onto the

183
00:16:19,577 --> 00:16:26,295
stack and now notice the stack is Int Y X
from top to bottom. The frontier of the

184
00:16:26,295 --> 00:16:31,149
parse tree is Int Y X. Okay? And now we
have a case where we have a terminal on

185
00:16:31,149 --> 00:16:35,640
top of the stack. And so now we're gonna
try to match it against the first terminal

186
00:16:35,640 --> 00:16:40,077
in the input and indeed they match. And so
what happens is [inaudible] just popped

187
00:16:40,077 --> 00:16:44,622
off the stack and the terminal and sorry
the input pointer advances in the input.

188
00:16:44,622 --> 00:16:48,896
Here I've recorded that by just discarding
the portion of the input that we've

189
00:16:48,896 --> 00:16:53,387
processed. So now we have [inaudible] left
to go and the inch has been removed from

190
00:16:53,387 --> 00:16:57,770
the stack. And so now what's on top of the
stack is Y. Y is indeed the leftmost

191
00:16:57,770 --> 00:17:04,478
unprocessed thing on the frontier. And,
the table says that, for non terminal Y,

192
00:17:04,478 --> 00:17:13,735
on, input times, we should use production
Y goes to times T. So let's put that in

193
00:17:13,735 --> 00:17:19,453
here. And now what's going to happen. Y is
going to be popped off the stack. Times T

194
00:17:19,453 --> 00:17:25,162
is going to be pushed on to the stack. And
now notice our stack is times T, X and the

195
00:17:25,162 --> 00:17:30,554
frontier, the unprocessed frontier of the
parse tree is times T X. Okay. So now we

196
00:17:30,554 --> 00:17:36,012
have another terminal on top of the stack,
it matches the next terminal in the input.

197
00:17:36,012 --> 00:17:41,339
So we pop the terminal off the stack, we
advance the input player. Now we have T as

198
00:17:41,339 --> 00:17:46,667
our left most nonterminal. Int is the next
thing in the input stream and the table

199
00:17:46,667 --> 00:17:57,255
says, well in this situation, we should
use the production T goes from INT Y. What

200
00:17:57,255 --> 00:18:02,245
does that mean? That means that T gets
popped of the stack. Int and Y get pushed

201
00:18:02,245 --> 00:18:07,297
onto the stack. Notice that the stack is
Int, Y, X, and the end process frontier of

202
00:18:07,297 --> 00:18:12,282
the parse t ree from left to right is Int,
Y, X. Once again we have a terminal on top

203
00:18:12,282 --> 00:18:17,206
of the stack, we match it against the next
terminal in the input string, they match.

204
00:18:17,206 --> 00:18:22,013
And now we have consumed all the input,
dollar sign is the only thing left to go

205
00:18:22,013 --> 00:18:26,788
in the input. But our stack is not empty.
Okay and so at this point what does that

206
00:18:26,788 --> 00:18:31,766
mean. Well, if the stack is not empty and
we are out of input then everything that's

207
00:18:31,766 --> 00:18:36,564
left on the stack had better generate the
empty strings. So we'd better be using

208
00:18:36,564 --> 00:18:41,722
only epsilon productions from here on and
indeed the table says that when Y is our

209
00:18:41,722 --> 00:18:46,880
next non terminal and dollar sign we are
at the end of the input we should use the

210
00:18:46,880 --> 00:18:52,736
production Y goes to epsilon. So Y goes to
epsilon that means Y just gets pop off the

211
00:18:52,736 --> 00:18:58,084
stack. Epsilon gets pushed on the stack;
epsilon is the empty string so nothing

212
00:18:58,084 --> 00:19:03,431
gets pushed on the stack. And now we're
down to X and in the situation where X is

213
00:19:03,431 --> 00:19:08,910
the next non-terminal dollar sign is,
we're at the end of the input so dollar

214
00:19:08,910 --> 00:19:14,191
sign is our next symbol. Then the table
also says to use production X goes to

215
00:19:14,191 --> 00:19:20,417
epsilon. And then what happens? Well, X
gets popped off the stack and nothing gets

216
00:19:20,417 --> 00:19:25,067
pushed on because the production was X
goes to the empty string. And now we see

217
00:19:25,067 --> 00:19:29,776
we have dollar sign on top of the stack,
dollar sign in the input. And so we have

218
00:19:29,776 --> 00:19:34,485
emptied the stack. We have, reached the
end of the input, and so we accept. That

219
00:19:34,485 --> 00:19:35,780
is a successful parse.