1
00:00:00,000 --> 00:00:07,518
[inaudible] Welcome back. At this video,
we're going to talk about how [inaudible]

2
00:00:07,518 --> 00:00:12,746
expressions are used to construct a full
lexical specification on the programming

3
00:00:12,746 --> 00:00:23,595
language. Before we get started, I want to
quickly summarize the notation for regular

4
00:00:23,595 --> 00:00:30,205
expressions. One of the shorthand?s we
talked about last time is a+ which means a

5
00:00:30,205 --> 00:00:36,816
sequence of at least 1a or the language
aa<i>. Sometimes you'll see a vertical bar</i>

6
00:00:36,816 --> 00:00:42,985
used instead of unions or a + b. Can also
be written a vertical bar b and optional a

7
00:00:42,985 --> 00:00:48,555
is abbreviation for the regular expression
a + epsilon. And then we have character

8
00:00:48,555 --> 00:00:54,125
ranges which allows us to do a big union,
a bunch of characters in order. And then

9
00:00:54,125 --> 00:00:59,282
one more that's used, that's, that's
actually fairly important but we didn't

10
00:00:59,282 --> 00:01:04,783
discussed last time is the compliment of
the character range. So this expression

11
00:01:04,783 --> 00:01:12,198
here means any character except the
characters a through z. So the last

12
00:01:12,198 --> 00:01:17,254
lecture, we talked about a specification
for the following predicate. Given a

13
00:01:17,254 --> 00:01:22,510
string s, is it in the language as the
function l of a regular expression. As we,

14
00:01:22,510 --> 00:01:27,101
we define the language of regular
expressions and talked about their

15
00:01:27,101 --> 00:01:32,477
semantics in terms of sets of strings. And
so for any given regular expression, we

16
00:01:32,477 --> 00:01:37,775
could reason out by hand whether a given
string was in that language or not, and

17
00:01:37,775 --> 00:01:43,073
this turns out not to be enough for what
we wanted to do. So just to review, what

18
00:01:43,073 --> 00:01:48,503
is it we wanted to do when we're given an
input, which is a bunch of characters, so

19
00:01:48,503 --> 00:01:53,269
here's a string of characters And it can
be much longer than just setting

20
00:01:53,269 --> 00:01:58,448
characters and. But we actually wanted to
do is to partition the string. We want to

21
00:01:58,448 --> 00:02:03,628
drop lines in the strings, divide up into
the words of language. Now of course each

22
00:02:03,628 --> 00:02:08,553
one of these words are to be The language
at some regular expression. But just

23
00:02:08,553 --> 00:02:13,099
having a, a, a definition or a yes no
answers, not quite the same thing as

24
00:02:13,099 --> 00:02:18,340
having a method for partitioning a string
into its constituting parts. And so we're

25
00:02:18,340 --> 00:02:23,265
gonna have to adapt regular expressions,
to this problem and, and this requires

26
00:02:23,265 --> 00:02:28,609
some small extensions and that's what this
video is all about. So let's talk about

27
00:02:28,609 --> 00:02:32,826
how to do this. The first thing we're
going to do, when we want to design the

28
00:02:32,826 --> 00:02:37,319
lexical specification of the language is
we have to write the regular expression,

29
00:02:37,319 --> 00:02:41,813
for the lexing to be to the [inaudible]
classes and we, we talked about how to do

30
00:02:41,813 --> 00:02:46,252
this last time. So, for the numbers we
might use digit plus desire as our regular

31
00:02:46,252 --> 00:02:50,801
expression and we might have a category of
keywords which is just the list of all

32
00:02:50,801 --> 00:02:55,240
the, keywords in the language. We would
have some category perhaps of identifiers.

33
00:02:55,240 --> 00:03:00,162
There is the, definitely we talked about
it last time. Sequences of letters or

34
00:03:00,162 --> 00:03:05,340
digits that begin with, with the letter
and then we're having a bunch of. Bunch of

35
00:03:05,340 --> 00:03:10,006
punctuations, things like open parens,
close parens, etc. So we write down a

36
00:03:10,006 --> 00:03:15,184
whole set of regular expressions. One for
each syntactic category in the language

37
00:03:15,184 --> 00:03:19,927
and that's the starting point for our
lexical specification. The second step,

38
00:03:19,927 --> 00:03:24,523
what we're going to do is we're going to
construct a gigantic regular expression

39
00:03:24,523 --> 00:03:29,288
which just matches all the lexings for all
the tokens and this is just the union, of

40
00:03:29,288 --> 00:03:33,997
all the regular expressions, that we wrote
out on the previous slides. So we'll just

41
00:03:33,997 --> 00:03:38,253
take the union of all those regular
expressions and that forms, the lexical

42
00:03:38,253 --> 00:03:42,848
specification of the language. And, we'll
just write this out, we don't really care

43
00:03:42,848 --> 00:03:47,217
what these regular expressions are but
they're just some, set r1, r2 and so on

44
00:03:47,217 --> 00:03:55,663
and the whole thing we're going to call r.
And now, here's the heart of how we

45
00:03:55,663 --> 00:04:01,675
actually use this bicycle's specification
to perform lexical analysis. So, let's

46
00:04:01,675 --> 00:04:07,576
consider an input. We input the string x1
up to xn. And now for every prefix of that

47
00:04:07,576 --> 00:04:12,403
input, okay. We're going to check whether
it's in the language of the regular

48
00:04:12,403 --> 00:04:17,612
expression. So we're gonna look at some
prefix trying with the first character and

49
00:04:17,612 --> 00:04:22,630
we're gonna ask ourselves is it in the
language of that big regular expression.

50
00:04:22,630 --> 00:04:27,712
And if it is, if it is in the language,
well then we know in particular that, that

51
00:04:27,712 --> 00:04:32,540
prefix is in the language of one in the
constituen t regular expressions cuz

52
00:04:32,540 --> 00:04:38,749
remember that r =. The sum of all the
different talking classes of our language,

53
00:04:38,749 --> 00:04:45,140
okay. So we know that this prefix x1
through xi is in the language of sum rj.

54
00:04:45,140 --> 00:04:50,358
Okay And so that we know that, that's a
word. In our language is one of. Is in one

55
00:04:50,358 --> 00:04:55,054
of the talking classes that we're
interested in, And so what we do is we

56
00:04:55,054 --> 00:05:00,077
simply delete that prefix from the input
and then we go back to three and we

57
00:05:00,077 --> 00:05:05,426
repeat. And in this way we keep biting off
prefixes of the input and we'll do this

58
00:05:05,426 --> 00:05:10,840
until the string is empty and then we have
[inaudible] analyzed the entire program.

59
00:05:12,660 --> 00:05:17,594
Now this algorithm has a couple of
ambiguities or a couple of things that are

60
00:05:17,594 --> 00:05:22,528
under specified and those are actually
interesting. So let's take a moment and

61
00:05:22,528 --> 00:05:27,726
talk about those. The first question is
how much input is actually used? So, let's

62
00:05:27,726 --> 00:05:33,926
consider the following situation. Let's
say that, we have, the x1 to xi, is in the

63
00:05:33,926 --> 00:05:40,127
language of our lexical specification. And
let's say there's a different prefix,

64
00:05:40,127 --> 00:05:46,720
that's also in the language of our lexical
specification and of course your I is, is

65
00:05:46,720 --> 00:05:52,537
not equal to J. What does that look like?
Well, it would look like the following

66
00:05:52,537 --> 00:05:58,134
kind of situation; we would have our input
string. And we have two different prefixes

67
00:05:58,134 --> 00:06:03,157
of the input that are both valid talking
classes and the question is which one of

68
00:06:03,157 --> 00:06:07,629
these do we want? And, you know just be
kind of [inaudible] here to have a

69
00:06:07,629 --> 00:06:12,015
concrete example, let's consider. What
happens when a =,,,, = is at the, is at

70
00:06:12,015 --> 00:06:16,801
the beginning of the input. After we
chopped off a bunch of other input and

71
00:06:16,801 --> 00:06:22,034
perhaps we have this sub-string or this
prefix of the input that we're looking at

72
00:06:22,034 --> 00:06:27,203
and the question is, you know should this
be regarded as a single = which would be

73
00:06:27,203 --> 00:06:32,181
an assignment operator in most languages
or would it be regards to =,,,, = which in

74
00:06:32,181 --> 00:06:37,240
some language is a comparison operator?
And, and this is an example we've looked

75
00:06:37,240 --> 00:06:42,059
at before and discussed, and there's
actually a well defined answer to this

76
00:06:42,059 --> 00:06:46,942
question. And, it is, that we should
always take the longer one and this has a

77
00:06:46,942 --> 00:06:53,712
name that's c alled the maximal munch. So
the rule is that when faced with a choice

78
00:06:53,712 --> 00:06:59,003
of two different prefixes of the input,
either which would be a valid token, we

79
00:06:59,003 --> 00:07:04,633
should always choose the longer one. And,
the reason for this is that's just the way

80
00:07:04,633 --> 00:07:09,653
humans themselves read things so when we
see =,,,, = we don't see two different

81
00:07:09,653 --> 00:07:14,911
equal operators, we see =,,,, = and if I.
Look at, you know that the sentence that I

82
00:07:14,911 --> 00:07:20,532
wrote up here, you know when we look at
HOW, we don't see three letters. We gather

83
00:07:20,532 --> 00:07:26,294
that altogether in one long token. We go
as far as we can until we see a separator

84
00:07:26,294 --> 00:07:31,845
and so because this is the way humans
work; we make the tools work the same way

85
00:07:31,845 --> 00:07:38,942
and this normally or almost always does
the right thing. Second question is which

86
00:07:38,942 --> 00:07:44,691
token should be used if more than one
token matches? So what do I mean by that?

87
00:07:44,691 --> 00:07:50,218
Well, again we have our prefix of the
input and it's in the language of our

88
00:07:50,218 --> 00:07:55,967
lexical specification and just remember
that the lexical specification itself

89
00:07:55,967 --> 00:08:01,790
again is made up as the union, a bunch of
regular expressions for token classes.

90
00:08:01,790 --> 00:08:06,837
Now, since that, since this prefix, is in
the language of the lexical, lexical

91
00:08:06,837 --> 00:08:11,817
specification, that means that it again,
it must be in the language of some

92
00:08:11,817 --> 00:08:17,269
particular token class, rj. But nothing
says that it isn't also in the language of

93
00:08:17,269 --> 00:08:22,047
a completely different token class.
Meaning, at the same string could be

94
00:08:22,047 --> 00:08:27,162
interpreted as a, as one of two different
tokens and the question is if this

95
00:08:27,162 --> 00:08:32,973
happens, which one should we pick? So, for
example just to make this concrete, Recall

96
00:08:32,973 --> 00:08:42,134
that we could have a lexical specification
for key words which would be things like

97
00:08:42,134 --> 00:08:52,660
if and else, and so on, and also for
identifiers. And then the identifier was

98
00:08:52,660 --> 00:09:05,587
the letter Followed by a letter or a
digit. Repeat it, okay. And if you look at

99
00:09:05,587 --> 00:09:14,028
these two specifications, you'll see that
the string if, IF is both of them. So IF

100
00:09:14,028 --> 00:09:22,780
is in the language of keywords, And it's
also in the language of the identifiers.

101
00:09:24,180 --> 00:09:28,945
And so should we treat it as a keyword or
an identifier. Now the normal rule in most

102
00:09:28,945 --> 00:09:33,483
languages is that if it's a keyword then i
t's always a keyword and you know the

103
00:09:33,483 --> 00:09:38,498
identifier is actually don't include the
keywords. And but actually it's a real

104
00:09:38,498 --> 00:09:44,810
pain to write out the identifiers in such
a way that you explicitly exclude the key

105
00:09:44,810 --> 00:09:50,144
words. This is a much more natural
definition I've written here for the

106
00:09:50,144 --> 00:09:55,854
identifiers. And so the way this gets
resolved is by a priority ordering and

107
00:09:55,854 --> 00:10:04,647
typically the rule is to choose the one
Listed first. Okay. So when there is a

108
00:10:04,647 --> 00:10:10,277
choice, when there is more than one token
class which the string might be long, the

109
00:10:10,277 --> 00:10:15,632
one that is listed first is given higher
priority. So in our file defining our

110
00:10:15,632 --> 00:10:21,330
lexical specification we would put the key
words before the identifiers just as we

111
00:10:21,330 --> 00:10:29,821
have done here. The final question is what
to do if no rule matches. What if I have

112
00:10:29,821 --> 00:10:37,956
the prefix of the input? That is not in
the language Of my lexical specification.

113
00:10:37,956 --> 00:10:43,210
Now this can actually arise. Certainly
there are lots and lots of strings that

114
00:10:43,210 --> 00:10:48,600
are not gonna be in the language of the
lexical specification of most languages.

115
00:10:48,600 --> 00:10:53,325
And the question is how to handle that
situation? So it's very important for

116
00:10:53,325 --> 00:10:58,362
compilers to do good error handling. They
can't simply crash. They need to be able

117
00:10:58,362 --> 00:11:03,150
to give the user, the programmer a
feedback about where the error is and what

118
00:11:03,150 --> 00:11:07,689
kind of error it is so we do need to
handle this gracefully. And the best

119
00:11:07,689 --> 00:11:13,652
solution for lexical analysis is to not do
this so don't let this ever happen. And so

120
00:11:13,652 --> 00:11:21,393
what we wanted to do instead is to write a
category of arrow strings, So, all of the

121
00:11:21,393 --> 00:11:33,686
strings. Not in the lexical specification
of the language. So we write out a regular

122
00:11:33,686 --> 00:11:39,765
expression. Again this is another regular
expression here. For all the possible

123
00:11:39,765 --> 00:11:45,844
error strings, all the possible erroneous
strings that could occur as you know

124
00:11:45,844 --> 00:11:52,694
invalid lexical input and then we put it
last. Put it last in priority. So that it

125
00:11:52,694 --> 00:11:58,330
will match after everything else matches
and, and the reason for putting it last.

126
00:11:58,330 --> 00:12:02,804
Is that, this actually allows us to be a
little bit sloppy in, in how we define the

127
00:12:02,804 --> 00:12:07,060
error strings. It can actually overlap,
with earlier regular expressi ons. We can

128
00:12:07,060 --> 00:12:11,480
include things in the error strings that
are in fact not errors. But, if we put it

129
00:12:11,480 --> 00:12:16,064
last in priority, then it will only match
if no earlier regular expression match and

130
00:12:16,064 --> 00:12:20,538
so in fact, they will only catch the error
strings. Then the action that we'll take

131
00:12:20,538 --> 00:12:24,904
when we match the error string will be the
prints in the error message and give

132
00:12:24,904 --> 00:12:31,120
device a feedback like where it is in the
file and such. To wrap up this video,

133
00:12:31,120 --> 00:12:36,653
regular expressions are very nice and
concise notation for string patterns but

134
00:12:36,653 --> 00:12:41,906
to use them in lexical analysis requires a
couple of small extensions. Some

135
00:12:41,906 --> 00:12:47,579
particulars, a couple of ambiguities we
have to resolve, we want our matches to be

136
00:12:47,579 --> 00:12:56,084
as long as possible. So we take. As much
input at a time as we can and we also want

137
00:12:56,084 --> 00:13:05,625
to choose the highest Priority match. So,
the regular expressions are given a

138
00:13:05,625 --> 00:13:10,148
priority. The different token classes have
priorities and, when there's tie, when the

139
00:13:10,148 --> 00:13:14,508
same, prefix of the input could match more
than one, we pick the one that has the

140
00:13:14,508 --> 00:13:18,922
highest priority. Typically this has done
just by listing them in order in a file

141
00:13:18,922 --> 00:13:23,063
and the ones listed first have higher
priority over the ones listed later. I

142
00:13:23,063 --> 00:13:27,477
just wanna warn you that when you go to
right lexical specifications, when you go

143
00:13:27,477 --> 00:13:31,401
to actually implement, lexor for a
language, the interaction of these two

144
00:13:31,401 --> 00:13:35,706
rules that we take longest possible
matches and we break ties and favor of the

145
00:13:35,706 --> 00:13:40,939
highest priority rules. That this lead to
some tricky situations and it's not always

146
00:13:40,939 --> 00:13:46,027
obvious that you're getting exactly what
you want, You have to think carefully

147
00:13:46,027 --> 00:13:50,946
about the Ordering of the rules and it's
actually how you write the rules so that

148
00:13:50,946 --> 00:13:55,687
you get the behavior that you desire. And
finally to handle errors, we typically

149
00:13:55,687 --> 00:14:00,653
write out. Catch all regular expression
that soaks up all the possible erroneous

150
00:14:00,653 --> 00:14:05,840
strings and give it the lowest priority so
that it only triggers if no valid token

151
00:14:05,840 --> 00:14:10,839
class matches some piece of the input. If
I leave, we haven't discussed these yet

152
00:14:10,839 --> 00:14:16,025
but they are very good algorithm to know
for implementing all of these and in fact

153
00:14:16,025 --> 00:14:20,774
we'll be able to do it in only single pass
over the input and with very few

154
00:14:20,774 --> 00:14:25,897
operations per character. Just a few, Just
a simple table look up and this would be

155
00:14:25,897 --> 00:14:27,960
the subject of our future videos.