1
00:00:02,780 --> 00:00:08,153
In this video, we're going to transition
from lexical analysis to parsing and talk

2
00:00:08,153 --> 00:00:16,479
a little bit about the relationship
between those two compiler phases. We've

3
00:00:16,479 --> 00:00:21,226
already talked about regular languages and
it's worth mentioning that these are the

4
00:00:21,226 --> 00:00:25,464
weakest formal languages that are widely
used. But they have, of course, many

5
00:00:25,464 --> 00:00:29,846
applications, some of which we saw in
previous videos. The difficulty with

6
00:00:29,846 --> 00:00:34,840
regular languages is that a lot of
languages are simply not regular. And

7
00:00:34,840 --> 00:00:40,249
there's some pretty important languages
that can't be expressed using regular

8
00:00:40,249 --> 00:00:46,005
expressions or finite automata. So let's
consider this language which is the set of

9
00:00:46,005 --> 00:00:51,692
all balanced parentheses. So some elements
of this language would be at the string

10
00:00:51,692 --> 00:00:56,546
one open-paren, one close-paren, two
open-parens, two close-parens, three

11
00:00:56,546 --> 00:01:02,411
open-parens, three close-parens and so on.
And, you can imagine that this is actually

12
00:01:02,411 --> 00:01:08,455
something that's fairly representative of
lots of programming language construct. So

13
00:01:08,455 --> 00:01:14,858
for example, any kind of nested arithmetic
expression would fit into this class but

14
00:01:14,858 --> 00:01:21,190
also things like nested if and else's will
have this category, this characteristic.

15
00:01:21,190 --> 00:01:27,046
And here with the nested [inaudible] it's
just the f statement, the functions like

16
00:01:27,046 --> 00:01:32,902
an open-paren. Not every languages like
cool which has the explicit closing fee as

17
00:01:32,902 --> 00:01:38,401
well but they're implicit in many
languages and so there are lots of nesting

18
00:01:38,401 --> 00:01:43,971
structure in programming languages
constructs and those cannot be handled by

19
00:01:43,971 --> 00:01:50,903
regular expressions. So this raises the
question of what the regular languages can

20
00:01:50,903 --> 00:01:56,794
express. And, why they aren't sufficient
for recognizing arbitrary nesting

21
00:01:56,794 --> 00:02:01,698
structure. So we can illustrate the
limitations of regular languages and

22
00:02:01,698 --> 00:02:06,687
Finite Automaton by looking a simple two
state machine. So let's consider this

23
00:02:06,687 --> 00:02:12,125
machine. We have one we have start state
and then the other state is the accepting

24
00:02:12,125 --> 00:02:16,759
state. And, we'll have this machine. Just
be a machine that we've already seen

25
00:02:16,759 --> 00:02:21,679
actually and it'll recognize strings with
odd numbers of 1's. So if we see a one and

26
00:02:21,679 --> 00:02:26,365
we're in the start state, we move. We now
see an odd number of 1's. We move to the

27
00:02:26,365 --> 00:02:31,284
accepting state and we stay there until we
see another one. In which case, we've seen

28
00:02:31,284 --> 00:02:35,911
even number of 1's and then we're in the
start state. So whenever we see an odd

29
00:02:35,911 --> 00:02:40,421
number of 1's, we're in the final state.
Whenever we see an even number of 1's,

30
00:02:40,421 --> 00:02:45,048
we're in the start state. And if we feed
this a fairly long string of 1's, let's,

31
00:02:45,048 --> 00:02:49,842
let's select only seven 1's in it. Then
what's it going to do is going to go back

32
00:02:49,842 --> 00:02:54,732
and forth and back and forth between these
states. It's gonna wind up in the final

33
00:02:54,732 --> 00:02:59,562
state when it gets to the last one so
it'll accept but notice that it doesn't

34
00:02:59,562 --> 00:03:04,153
know how many times it's been to that
final state. It doesn't remember the

35
00:03:04,153 --> 00:03:08,983
length of the string; it doesn't have any
way of counting how many characters the

36
00:03:08,983 --> 00:03:13,992
string had in it. And in fact, all I can
count here is the parity. So in general

37
00:03:14,171 --> 00:03:19,300
Finite Automata can really only express
things where you can count modulus on k.

38
00:03:19,300 --> 00:03:24,951
So they can count mod k for some k where k
is the number of states in the machine.

39
00:03:24,951 --> 00:03:30,396
And so, you know if I have pre-test the
machine, I can keep track of whether the

40
00:03:30,396 --> 00:03:36,048
string length is divisible by three or
some other similar property but I can't do

41
00:03:36,048 --> 00:03:41,424
things like count to an arbitrary i so if
I need to recognize a language that

42
00:03:41,424 --> 00:03:46,593
requires counting arbitrarily high like
recognizing all strings of balance

43
00:03:46,593 --> 00:03:53,327
parentheses, we can't do that with the
finite set of states. So what does a

44
00:03:53,327 --> 00:03:59,415
parser do, it takes the sequence of tokens
as input from the lexer and it produces a

45
00:03:59,415 --> 00:04:06,592
parse tree of the program. And for example
in cool, here's an input expression that

46
00:04:06,592 --> 00:04:12,182
is input to the lexical analyzer. The
lexical analyzer produces this sequence of

47
00:04:12,182 --> 00:04:17,912
tokens as its output. That's the input to
the parser. Then the parser produces this

48
00:04:17,912 --> 00:04:23,502
parse tree where the nesting structure has
been made explicit. So, we have the, if

49
00:04:23,502 --> 00:04:28,882
and else and then the three components:
the predicate, the then branch and the

50
00:04:28,882 --> 00:04:35,287
else branch of the, if To summarize, the
lexer takes a string of character as input

51
00:04:35,287 --> 00:04:40,813
and produces a string of tokens as output.
That string of tok ens is the input to the

52
00:04:40,813 --> 00:04:46,471
parser which takes a string of tokens and
produces a Parse Tree of the program. And

53
00:04:46,471 --> 00:04:51,602
it's worth mentioning a couple of thing
here. First of all, sometimes the Parse

54
00:04:51,602 --> 00:04:57,763
Tree is only implicit. So the, a compiler
may never actually build the full Parse

55
00:04:57,763 --> 00:05:02,622
Tree. We'll talk more about that later.
Many compilers do build an explicit parse

56
00:05:02,622 --> 00:05:07,333
tree but many do not. The other thing
that's worth mentioning is that there are

57
00:05:07,333 --> 00:05:12,342
compilers that do combine these two phases
into one where everything is done by the

58
00:05:12,342 --> 00:05:16,695
parser. So, the parsing technology is
generally powerful enough to express

59
00:05:16,695 --> 00:05:21,406
lexical analysis in addition to parsing.
But most compilers still divide up the

60
00:05:21,406 --> 00:05:26,475
work this way because regular expressions
are such a good match for lexical analysis

61
00:05:26,475 --> 00:05:29,040
and then the parsing is handled
separately.