1
00:00:00,000 --> 00:00:05,556
[inaudible] Welcome back. This is the
first video in our long series of the

2
00:00:05,556 --> 00:00:13,236
implementation of compilers, The call from
last time that a compiler has five phases.

3
00:00:13,236 --> 00:00:17,796
We're gonna begin by talking about lexical
analysis and this will probably take us

4
00:00:17,796 --> 00:00:22,246
three to four videos to get through at
least and then we'll, we will be moving on

5
00:00:22,246 --> 00:00:28,902
in order to the other phases. Let's start
by looking at a small code fragment. The

6
00:00:28,902 --> 00:00:34,110
goal of lexical analysis is to divide this
piece of code up. Into lexical units so

7
00:00:34,110 --> 00:00:39,529
things like the keyword if the variable
names i, n, j and the relational operator

8
00:00:39,529 --> 00:00:44,881
double-equals and so on. Now as a human
being this is. As we discussed last time

9
00:00:44,881 --> 00:00:50,436
this is a very easy thing to do because
there are all kinds of visual clues about

10
00:00:50,436 --> 00:00:55,787
where the units lie Where the boundaries
between the different units lie but a

11
00:00:55,787 --> 00:01:00,609
program like lexical analyzer. It doesn't
have that kind of luxury. In fact what

12
00:01:00,609 --> 00:01:05,277
the, what the likes of analyzer will see
is something that looks more like this. So

13
00:01:05,277 --> 00:01:09,946
here I overwritten, the code out just as a
string, with all the white space symbols

14
00:01:09,946 --> 00:01:13,931
included and is from, from this
representation, this is a linear string,

15
00:01:13,931 --> 00:01:18,770
you can think of this as bytes in the file
that the lexical analyzer has to work and

16
00:01:18,770 --> 00:01:23,040
it's going to mark through, placing
dividers between the different units. So,

17
00:01:23,040 --> 00:01:27,594
it will recognize that there's a division
there, between the white space and the

18
00:01:27,594 --> 00:01:32,466
keyword. Then a division after the keyword
and there's more a wide space, the open

19
00:01:32,466 --> 00:01:37,004
paren, the i, another wide space, double
equals and so on and it goes through

20
00:01:37,004 --> 00:01:42,446
drawing these lines diving up. The, the
string into its lexical unit, So I won't

21
00:01:42,446 --> 00:01:49,606
finish the whole thing but you should get
the idea. Now, it doesn't just place these

22
00:01:49,606 --> 00:01:56,823
dividers in the string however. It doesn't
just recognize the substrings. It also

23
00:01:56,823 --> 00:02:04,220
needs to classify the different elements
of the string according to their role. We

24
00:02:04,220 --> 00:02:11,346
call these token classes. Or sometimes,
I'll just call it the class of the token.

25
00:02:11,346 --> 00:02:18,320
And in English, these roles are things
like noun, verb, adjective. Okay and there

26
00:02:18,320 --> 00:02:24,427
is, ther e are many more or at least or
some more. And in the programming

27
00:02:24,427 --> 00:02:30,620
language, the classes, the token classes
would be things like identifiers,

28
00:02:31,320 --> 00:02:44,171
Keywords. I, and then individual pieces of
syntax like an open paren or a close

29
00:02:44,171 --> 00:02:53,350
paren, those are the classes by
themselves. A, numbers. And again, there

30
00:02:53,350 --> 00:02:59,043
are more classes but there's a thick set
of classes and each one of these

31
00:02:59,043 --> 00:03:05,769
corresponds to some set of strings that
could appear in a program. So token

32
00:03:05,769 --> 00:03:13,631
classes correspond to sets of strings, And
[inaudible] strings can be described

33
00:03:13,631 --> 00:03:19,676
relatively straightforwardly so for
example. The token class of identifiers in

34
00:03:19,676 --> 00:03:24,564
most programming languages might be
something like strings of letters or

35
00:03:24,564 --> 00:03:29,720
digits, starting with a letter. So for
example, a variable name or identifier

36
00:03:29,720 --> 00:03:35,344
could be something like a1 or it could be
f00 or it could be, b17, all of those

37
00:03:35,344 --> 00:03:40,633
would be, be valid identifiers and often,
often they'll be additional characters

38
00:03:40,633 --> 00:03:45,720
that allowed identifiers but that's the
basic idea, Very, very often The main

39
00:03:45,720 --> 00:03:51,126
restriction identifiers that they have to
start, with a letter, An integer and

40
00:03:51,126 --> 00:03:56,672
typical definition of an integer is a
non-empty string of digits. So, something

41
00:03:56,672 --> 00:04:02,503
like zero or twelve. Okay. One followed by
two I should say is actually a string of

42
00:04:02,503 --> 00:04:08,120
number in this case. And, and yeah, it is
actually whether admit some numbers you

43
00:04:08,120 --> 00:04:13,951
might not think of. Things like 001 would
be a valid representation of a number or

44
00:04:13,951 --> 00:04:20,972
even 00 could be a valid integer according
to this definition. Keywords are typically

45
00:04:20,972 --> 00:04:27,643
just a fix set of reserved words and so
here I've listed a few, else, if, begin,

46
00:04:27,643 --> 00:04:33,153
and so on. And then white space as itself
a token class so we actually have to say

47
00:04:33,339 --> 00:04:38,415
in that string which is the representation
of the program what every character in

48
00:04:38,415 --> 00:04:43,678
that string, what token or what token
class it's a part of. What every substring

49
00:04:43,678 --> 00:04:48,940
is a part of and that includes the white
space. So, for example if we have a series

50
00:04:48,940 --> 00:04:53,770
of three blanks, if I say if and then an
open paren and I have three blanks in

51
00:04:53,770 --> 00:05:03,732
here, these three blank s would be grouped
together as white space. So the goal of

52
00:05:03,732 --> 00:05:09,923
lexical analysis is to classify substrings
of the program according to their role.

53
00:05:09,923 --> 00:05:15,963
This is the, the token class, okay? Is it
a keyword, a variable identifier, And then

54
00:05:15,963 --> 00:05:21,776
to communicate these tokens, to the
parser. So, drawing a picture here, let's

55
00:05:22,003 --> 00:05:33,446
switch colors. The lexical analyzer
communicates with the parser. Okay and the

56
00:05:33,446 --> 00:05:40,006
functionality here is that, the lexical
analyzer takes in a string. Typically

57
00:05:40,006 --> 00:05:46,367
stored up, also just a sequence of bytes
and then when [inaudible] to the parser is

58
00:05:46,367 --> 00:05:53,635
sequence or pairs which are the token
class. And substring which I would say

59
00:05:53,635 --> 00:05:59,977
string here, that, that, of which is the
sets of string which is a part of the

60
00:05:59,977 --> 00:06:06,784
input along with the class the role that
it plays in the in the language, and this

61
00:06:06,784 --> 00:06:15,770
pair together is called a token. So for
example, if my string is that f00 = 42,

62
00:06:15,770 --> 00:06:24,805
all right, then that will go to the
lexical analyzer and that will come, I'll

63
00:06:24,805 --> 00:06:39,878
write down here, three tokens. And these
would be identifier. Who? Operator say

64
00:06:40,454 --> 00:06:54,171
equals. And. Integer, excuse me 42. And
here I just left these things as strings

65
00:06:54,171 --> 00:06:59,331
to, to emphasize that these are strings.
So this is not the number 42 at this point

66
00:06:59,331 --> 00:07:04,806
in time, it's, it's the string 42 which is
a plays an integer role in the programming

67
00:07:04,806 --> 00:07:09,400
language. And then these, and when the
price that takes this input is this

68
00:07:09,588 --> 00:07:15,126
sequence of pairs. So the lexical analyzer
essentially runs over the input string and

69
00:07:15,126 --> 00:07:20,286
chunks it up into the sequence of pairs
where each pair is a token class and a

70
00:07:20,286 --> 00:07:27,258
substring of the original input. As we
turn to the example from the beginning of

71
00:07:27,258 --> 00:07:32,358
the video, here it is written out as a
string. And our goal now is to lexically

72
00:07:32,358 --> 00:07:37,589
analyze this fragment of code. We want to
go through and identify the substrings

73
00:07:37,589 --> 00:07:42,559
that are tokens and also their token
classes. So, to do this, we're gonna need

74
00:07:42,559 --> 00:07:47,136
some token classes. So let's give
ourselves some of those to work with.

75
00:07:47,136 --> 00:07:55,496
We'll need white space. And, and so this
is sequences of blanks, new lines tab,

76
00:07:55,496 --> 00:08:04,786
things like that with the keywords. And
we'll need variables which we'll call

77
00:08:04,786 --> 00:08:16,522
identifiers. And we'll need integers and
now I'll call those numbers. Here and then

78
00:08:16,522 --> 00:08:22,983
we're going to have some other operations
some other classes things like open paren

79
00:08:23,185 --> 00:08:28,771
close paren, and semi colon and these are
interesting. These three ae interesting

80
00:08:28,771 --> 00:08:34,290
because they're single character token
classes that is, is a set of strings but

81
00:08:34,290 --> 00:08:39,472
is only, is only one string in the set so
the open paren corresponds to exact

82
00:08:39,472 --> 00:08:45,260
[inaudible] strings that contain only open
paren. So often the punctuation marks of

83
00:08:45,260 --> 00:08:50,893
the language are in token classes all by
themselves. Another piece of punctuation

84
00:08:50,893 --> 00:08:56,093
that we'll add here is, is assignments.
That will be a token class by itself

85
00:08:56,093 --> 00:09:01,760
because it's such an important operation.
But, the double equals will class as a

86
00:09:01,960 --> 00:09:08,024
relational operator with this class as an
operator put it up here. Alright, So now

87
00:09:08,024 --> 00:09:14,137
what we're going to do is we're gonna go
through and tokenized this string and I'm

88
00:09:14,137 --> 00:09:20,348
going to write down for each substring.
What class it is. You know, I'm just gonna

89
00:09:20,348 --> 00:09:26,619
use the first letter here of the class.
It's indicated just to save time so I

90
00:09:26,619 --> 00:09:33,133
don't have to write everything up. Hence,
we change colors so we can do this in a

91
00:09:33,133 --> 00:09:39,241
different color. So, the first token here
is white space token and then that

92
00:09:39,241 --> 00:09:44,876
followed by the F keyword. So, okay, And
then we have a blank here which is another

93
00:09:44,876 --> 00:09:50,061
white space and then the open paren which
is its own token class so I'll just leave

94
00:09:50,061 --> 00:09:57,758
it to identify itself there and then we
have an identifier. Okay, White space and

95
00:09:57,758 --> 00:10:03,079
then an operator, the double-equals.
Another blank so that's white space

96
00:10:03,079 --> 00:10:09,373
followed by another identifier followed by
close parens, Again, a punctuation mark in

97
00:10:09,373 --> 00:10:15,592
a token class by itself. And then we have
three white space characters so those are

98
00:10:15,592 --> 00:10:23,144
group together as a white space token,
Followed by another identifier and more

99
00:10:23,144 --> 00:10:31,094
white space and then another single
character token, the assignment operator,

100
00:10:31,094 --> 00:10:37,928
white space and a number, And then sem i
colon again and punctuation mark and a

101
00:10:37,928 --> 00:10:44,215
token class by itself. Two white space
characters can group together. What

102
00:10:44,215 --> 00:10:50,742
follows in is a keyword, so it gets
classified as in the keyword token class.

103
00:10:50,742 --> 00:10:57,825
Another run of white space characters and
then another identifier. There's actually

104
00:10:57,825 --> 00:11:05,158
a blank there where we almost covered it
up without marks. The assignment operator

105
00:11:05,158 --> 00:11:11,913
by itself in a token class, white space, a
number, and finally the semi colon by

106
00:11:11,913 --> 00:11:18,755
itself. And there is our tokenization.
We've identified the substrings and we've

107
00:11:18,755 --> 00:11:26,743
also labeled each one with its token
class. To summarize, lexical analysis

108
00:11:26,743 --> 00:11:32,398
implementation has to do two things. The
first job is to recognize the substrings

109
00:11:32,398 --> 00:11:38,052
in the input that correspond to tokens.
And here's a little bit of compiler lingo

110
00:11:38,261 --> 00:11:44,265
these substrings are called the lexemes.
So the words of the program are called the

111
00:11:44,265 --> 00:11:50,129
lexemes. And then the second job is at for
each lexeme we have to identify its token

112
00:11:50,129 --> 00:11:55,993
class. And then the output of the lexical
analyzer is a series of pairs which are

113
00:11:55,993 --> 00:12:02,070
the token class. And lexing, Okay, And
this whole thing, one of these pairsis

114
00:12:02,076 --> 00:12:04,380
called A token.