1

00:00:06,240 --> 00:00:11,050

Welcome back. This video

is about regular expressions.

2

00:00:11,050 --> 00:00:14,230

We want to use regular

expressions in our lexer.

3

00:00:14,230 --> 00:00:16,165

And the purpose of the

lexer is to find

4

00:00:16,165 --> 00:00:18,070

out where the words in

5

00:00:18,070 --> 00:00:21,070

our programs are. However

regular expressions

6

00:00:21,070 --> 00:00:23,875

are fundamental tool

in computer science.

7

00:00:23,875 --> 00:00:27,910

And I'm sure you've used them

already on several occasions.

8

00:00:27,910 --> 00:00:30,370

And one would expect that about

9

00:00:30,370 --> 00:00:31,750

regular expressions since they are

10

00:00:31,750 --> 00:00:33,850

so well-known and well studied,

11

00:00:33,850 --> 00:00:37,915

that everything under the

sun is known about them.

12

00:00:37,915 --> 00:00:41,080

But actually there's

still some surprising

13

00:00:41,080 --> 00:00:44,465

and interesting

problems with them.

14

00:00:44,465 --> 00:00:47,945

And I want to show you

them in this video.

15

00:00:47,945 --> 00:00:50,720

I'm sure you've seen

regular expressions

16

00:00:50,720 --> 00:00:52,445

many, many times before.

17

00:00:52,445 --> 00:00:55,100

But just to be on the same page,

18

00:00:55,100 --> 00:00:57,110

let me just recap them.

19

00:00:57,110 --> 00:00:59,210

So here in this line,

20

00:00:59,210 --> 00:01:01,790

there is a regular expression

which is supposed to

21

00:01:01,790 --> 00:01:05,285

recognize some form

of email addresses.

22

00:01:05,285 --> 00:01:07,745

So an e-mail address

23

00:01:07,745 --> 00:01:11,000

has part which is

before the @ symbol,

24

00:01:11,000 --> 00:01:13,400

which is the name of the person.

25

00:01:13,400 --> 00:01:16,880

And that can be

any number between

26

00:01:16,880 --> 00:01:20,195

0 and 9, and letters between a and z.

27

00:01:20,195 --> 00:01:24,155

Let's say we avoiding

here capital letters.

28

00:01:24,155 --> 00:01:26,045

There can be underscores.

29

00:01:26,045 --> 00:01:29,405

There can be a dot and

there can be hyphens.

30

00:01:29,405 --> 00:01:35,390

And after the @ symbol

comes the domain name.

31

00:01:35,390 --> 00:01:37,310

So as you can see here,

32

00:01:37,310 --> 00:01:40,640

we use things like star to

33

00:01:40,640 --> 00:01:44,314

match letters

zero or more times.

34

00:01:44,314 --> 00:01:45,985

Or we have a plus,

35

00:01:45,985 --> 00:01:47,420

which means you have to match

36

00:01:47,420 --> 00:01:52,489

at least once or more

times. Then we have.

37

00:01:52,489 --> 00:01:55,790

question mark, which says you

38

00:01:55,790 --> 00:01:59,105

match either it is there

or it is not there.

39

00:01:59,105 --> 00:02:01,340

You are also regular

expressions which

40

00:02:01,340 --> 00:02:03,755

match exactly n-times.

41

00:02:03,755 --> 00:02:08,720

Or this is a regular expression

for between n and m times.

42

00:02:08,720 --> 00:02:12,065

You can see in

this email address,

43

00:02:12,065 --> 00:02:13,730

the top-level domain

44

00:02:13,730 --> 00:02:16,130

name can be any letter 

45

00:02:16,130 --> 00:02:19,265

between a to z,

and contain dots,

46

00:02:19,265 --> 00:02:22,340

but can only be two

characters long

47

00:02:22,340 --> 00:02:25,685

up till six characters

and not more.

48

00:02:25,685 --> 00:02:29,240

Then you also have

something like ranges.

49

00:02:29,240 --> 00:02:31,220

So you can see, letters between a

50

00:02:31,220 --> 00:02:33,635

and z and 0 to 9 and so on.

51

00:02:33,635 --> 00:02:36,545

Here you also have regular

expressions which can

52

00:02:36,545 --> 00:02:40,070

match something which

isn't in this range.

53

00:02:40,070 --> 00:02:42,560

So for example, if

you want for example match,

54

00:02:42,560 --> 00:02:44,030

letters but not numbers,

55

00:02:44,030 --> 00:02:45,800

you would say, well, if

56

00:02:45,800 --> 00:02:48,990

this is a number that

should not match.

57

00:02:49,090 --> 00:02:52,804

Typically you also

have these ranges.

58

00:02:52,804 --> 00:02:55,565

Lowercase letters,

capital letters.

59

00:02:55,565 --> 00:02:58,550

Then you have some

special regular expressions

60

00:02:58,550 --> 00:03:02,195

like this one is only

supposed to match digits.

61

00:03:02,195 --> 00:03:05,674

A dot is supposed to

match any character.

62

00:03:05,674 --> 00:03:07,370

And then they have also something

63

00:03:07,370 --> 00:03:09,800

called groups which

is supposed to be

64

00:03:09,800 --> 00:03:12,799

used when you are

trying to extract

65

00:03:12,799 --> 00:03:15,605

a string you've matched.

66

00:03:15,605 --> 00:03:19,925

Okay, so these are the

typical regular expressions.

67

00:03:19,925 --> 00:03:23,075

And here's a particular one

68

00:03:23,075 --> 00:03:25,820

trying to match something

69

00:03:25,820 --> 00:03:28,770

which resembles

an email address.

70

00:03:29,590 --> 00:03:33,065

Clearly that should be all easy.

71

00:03:33,065 --> 00:03:36,230

And our technology should

be on top of that.

72

00:03:36,230 --> 00:03:37,865

That we can take a

73

00:03:37,865 --> 00:03:41,015

regular expressions and

we can take a string,

74

00:03:41,015 --> 00:03:43,340

and we should have programs to

75

00:03:43,340 --> 00:03:45,680

decide whether this

string is matched

76

00:03:45,680 --> 00:03:50,330

by a regular expression or

not and should be easy-peasy, no?

77

00:03:50,330 --> 00:03:56,150

Well, let's have a

look at two examples.

78

00:03:56,150 --> 00:04:00,860

The first regular expression

is a star star b.

79

00:04:00,860 --> 00:04:02,990

And it is supposed

to match strings of

80

00:04:02,990 --> 00:04:05,825

the form 0 or more a's,

81

00:04:05,825 --> 00:04:10,385

followed by a b. The parentheses

you can ignore.

82

00:04:10,385 --> 00:04:11,990

And a star star

83

00:04:11,990 --> 00:04:14,120

also doesn't

make any difference

84

00:04:14,120 --> 00:04:16,505

to what kind of strings

that can be matched.

85

00:04:16,505 --> 00:04:21,635

It can only make 0 more

a's followed by a b.

86

00:04:21,635 --> 00:04:23,900

And the other regular expression

87

00:04:23,900 --> 00:04:26,990

is possibly a character a,

88

00:04:26,990 --> 00:04:32,930

n times, followed by character

a axactly n-times.

89

00:04:32,930 --> 00:04:35,570

And we will try out

90

00:04:35,570 --> 00:04:38,360

these two regular expressions

with strings of the form a,

91

00:04:38,360 --> 00:04:39,890

aa, and so on,

92

00:04:39,890 --> 00:04:45,770

and up to the length of n. And

93

00:04:45,770 --> 00:04:49,130

this regular expression should

actually not match any of

94

00:04:49,130 --> 00:04:53,315

the strings because the

final b is missing.

95

00:04:53,315 --> 00:04:56,150

But that is

okay. For example

96

00:04:56,150 --> 00:04:57,425

if you have a regular expression

97

00:04:57,425 --> 00:05:00,110

that is supposed to

check whether a string is

98

00:05:00,110 --> 00:05:01,490

an email address and the user

99

00:05:01,490 --> 00:05:03,380

gives some random

strings in there,

100

00:05:03,380 --> 00:05:06,545

then this regular expression

should not match that string.

101

00:05:06,545 --> 00:05:08,420

And for this regular expression

102

00:05:08,420 --> 00:05:11,195

you have to scratch a

little bit of your head,

103

00:05:11,195 --> 00:05:12,620

what it can actually match.

104

00:05:12,620 --> 00:05:14,720

But after a little bit

of head scratching,

105

00:05:14,720 --> 00:05:18,260

you find out can match

any string which is of

106

00:05:18,260 --> 00:05:22,580

the length n a's up

to 2n of a's.

107

00:05:22,580 --> 00:05:24,290

So anything in this range,

108

00:05:24,290 --> 00:05:27,185

this regular expression

can actually match.

109

00:05:27,185 --> 00:05:30,395

Okay, let's

take a random tool,

110

00:05:30,395 --> 00:05:32,630

maybe for example Python.

111

00:05:32,630 --> 00:05:35,240

So here's a little

Python program.

112

00:05:35,240 --> 00:05:38,690

It uses the library

function of Python to

113

00:05:38,690 --> 00:05:42,935

match the regular expressions of

a star star b.

114

00:05:42,935 --> 00:05:46,805

And we measure the time with longer

and longer strings of a's.

115

00:05:46,805 --> 00:05:48,770