1

00:00:06,710 --> 00:00:09,225

Thanks for tuning in again.

2

00:00:09,225 --> 00:00:11,640

In this video, we want to specify

3

00:00:11,640 --> 00:00:14,370

what problem our regular

expression matcher

4

00:00:14,370 --> 00:00:16,155

is actually supposed to solve.

5

00:00:16,155 --> 00:00:18,900

The reason is that

we know that some of

6

00:00:18,900 --> 00:00:21,585

the existing regular

expression matching engines

7

00:00:21,585 --> 00:00:25,200

are not just abysmally

slow in some examples,

8

00:00:25,200 --> 00:00:27,105

as you've seen in the

previous video,

9

00:00:27,105 --> 00:00:30,570

but also produce sometimes

incorrect results.

10

00:00:30,570 --> 00:00:33,330

In order to avoid

this with our matcher,

11

00:00:33,330 --> 00:00:35,325

we need to somehow explain

12

00:00:35,325 --> 00:00:39,255

precisely what is the problem

our algorithm solves.

13

00:00:39,255 --> 00:00:41,935

This will require

a bit of theory, but

14

00:00:41,935 --> 00:00:45,335

I hope it is nevertheless

a bit of fun.

15

00:00:45,335 --> 00:00:47,915

First, we have to specify

16

00:00:47,915 --> 00:00:50,585

what we mean by a

regular expression.

17

00:00:50,585 --> 00:00:53,210

You've seen earlier some

examples. They were

18

00:00:53,210 --> 00:00:56,060

actually taken or

inspired by what

19

00:00:56,060 --> 00:00:58,850

is available in standard

regular expression matching

20

00:00:58,850 --> 00:01:02,330

engines, like star, plus and n-times.

21

00:01:02,330 --> 00:01:05,690

But for many tasks,

for our algorithm,

22

00:01:05,690 --> 00:01:10,174

we will focus only what I call

basic regular expressions.

23

00:01:10,174 --> 00:01:11,840

Since I'm lazy, I will call

24

00:01:11,840 --> 00:01:13,550

these basic regular expressions

25

00:01:13,550 --> 00:01:15,485

just as regular expressions.

26

00:01:15,485 --> 00:01:17,405

And the ones you've seen earlier

27

00:01:17,405 --> 00:01:19,400

as extended regular expressions.

28

00:01:19,400 --> 00:01:22,940

So the basic regulare expressions,

or just regular expressions,

29

00:01:22,940 --> 00:01:25,280

they will have characters.

30

00:01:25,280 --> 00:01:27,170

So you can match any character,

31

00:01:27,170 --> 00:01:31,370

a,b,c to z or 0 to 9.

32

00:01:31,370 --> 00:01:35,525

Any Ascii character. 'c' here

is just a representative.

33

00:01:35,525 --> 00:01:38,825

So we can match

single characters.

34

00:01:38,825 --> 00:01:42,440

Then we can match alternatives.

35

00:01:42,440 --> 00:01:44,930

That means a string

is either matched

36

00:01:44,930 --> 00:01:46,730

by the regular expression r1

37

00:01:46,730 --> 00:01:49,324

or by the regular expression r2.

38

00:01:49,324 --> 00:01:52,790

And for the

alternative we write +.

39

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

Then we also have sequence.

40

00:01:55,175 --> 00:01:57,410

This sequence regular

expression essentially

41

00:01:57,410 --> 00:01:59,915

says that a string needs to be matched

42

00:01:59,915 --> 00:02:02,210

the first part by

the regular expression r1

43

00:02:02,210 --> 00:02:06,275

and then the second

part by the r2.

44

00:02:06,275 --> 00:02:10,190

And then we have also the

star regular expression,

45

00:02:10,190 --> 00:02:12,980

which says the regular

expression needs to match

46

00:02:12,980 --> 00:02:16,520

the string with zero

or more copies.

47

00:02:16,520 --> 00:02:18,140

And then we also have some

48

00:02:18,140 --> 00:02:20,060

slightly strange

regular expressions.

49

00:02:20,060 --> 00:02:22,505

We have the regular expression 1,

50

00:02:22,505 --> 00:02:25,910

which can only match

the empty string.

51

00:02:25,910 --> 00:02:29,075

I'm using here the

notation 1 for that

52

00:02:29,075 --> 00:02:31,340

and in my writing I will always

53

00:02:31,340 --> 00:02:33,440

make sure that for the

regular expression

54

00:02:33,440 --> 00:02:35,765

I will write the

1 in a bold font.

55

00:02:35,765 --> 00:02:38,510

So whenever you see

a 1 in bold font,

56

00:02:38,510 --> 00:02:40,395

this is not the 1, but

57

00:02:40,395 --> 00:02:44,300

the regular expression which

can match the empty string.

58

00:02:44,300 --> 00:02:48,050

And we also have the

regular expression 0,

59

00:02:48,050 --> 00:02:50,315

which cannot match

anything at all.

60

00:02:50,315 --> 00:02:51,695

You might think, well,

61

00:02:51,695 --> 00:02:54,635

that's not much use if it cannot

match anything at all,

62

00:02:54,635 --> 00:02:58,130

but you will see why that

one is important later on.

63

00:02:58,130 --> 00:03:00,785

So our basic regular expressions,

64

00:03:00,785 --> 00:03:02,375

they will be 0,

65

00:03:02,375 --> 00:03:08,390

1, characters, alternatives,

sequences and stars.

66

00:03:08,390 --> 00:03:12,170

And these are all the

basic regular expressions.

67

00:03:12,170 --> 00:03:16,280

If this definition is a

bit too abstract for you,

68

00:03:16,280 --> 00:03:18,560

we can also look at

the concrete code,

69

00:03:18,560 --> 00:03:23,060

how that would pan out when

actually writing some Scala.

70

00:03:23,060 --> 00:03:28,040

I promised you, I show

you always my code in Scala.

71

00:03:28,040 --> 00:03:29,480

So here you would have

72

00:03:29,480 --> 00:03:32,885

first an abstract class

for regular expressions.

73

00:03:32,885 --> 00:03:37,580

Then you have one regular

expression for 0, 

74

00:03:37,580 --> 00:03:41,540

one regular expression for 1, 

75

00:03:41,540 --> 00:03:42,875

one regular expression, which

takes an argument,

76

00:03:42,875 --> 00:03:45,050

the character you want to match,

77

00:03:45,050 --> 00:03:47,915

the characters a,b, c and so on.

78

00:03:47,915 --> 00:03:50,945

Then we have an alternative

regular expression,

79

00:03:50,945 --> 00:03:53,480

which takes the first

alternative and

80

00:03:53,480 --> 00:03:56,435

the second alternative

as arguments.

81

00:03:56,435 --> 00:03:59,690

And we have a sequence

regular expression. Again,

82

00:03:59,690 --> 00:04:01,850

which takes the

first component and

83

00:04:01,850 --> 00:04:04,730

the second component

as two arguments.

84

00:04:04,730 --> 00:04:07,249

And we have the star

regular expression,

85

00:04:07,249 --> 00:04:10,880

which just take one regular

expression as argument.

86

00:04:10,880 --> 00:04:16,115

And all these reg expressions

extend our abstract class.

87

00:04:16,115 --> 00:04:20,300

For whatever I do in

this module here I have

88

00:04:20,300 --> 00:04:23,300

the convention that all

the regular expressions

89

00:04:23,300 --> 00:04:25,550

are written with capital letters.

90

00:04:25,550 --> 00:04:26,885

As you can see that here,

91

00:04:26,885 --> 00:04:31,685

O, 1,  character, these will be

always regular expressions.

92

00:04:31,685 --> 00:04:34,370

They have all capital letters.

93

00:04:34,370 --> 00:04:36,484

Let's for a moment,

94

00:04:36,484 --> 00:04:38,720

play around with this definition.

95

00:04:38,720 --> 00:04:41,945

I'm using here the

Ammonite REPL.

96

00:04:41,945 --> 00:04:46,950

And I can evaluate

this definition.

97

00:04:53,430 --> 00:04:55,810

And now I can start to

98

00:04:55,810 --> 00:04:58,570

define particular

regular expressions.

99

00:04:58,570 --> 00:05:00,340

For example, if I need

a regular expression

100

00:05:00,340 --> 00:05:02,860

which can recognise

the character a,

101

00:05:02,860 --> 00:05:06,025

then I would write

something like this.

102

00:05:06,025 --> 00:05:08,710

So this regular expression

takes an argument,

103

00:05:08,710 --> 00:05:13,615

the character 'a'  to specify

which character to match.

104

00:05:13,615 --> 00:05:16,945

We do this obviously also with 'b'.

105

00:05:16,945 --> 00:05:19,405

And I can do that with

106

00:05:19,405 --> 00:05:22,975

'c'. So now we have three

regular expressions.

107

00:05:22,975 --> 00:05:25,570

If you look very carefully

at this definition,

108

00:05:25,570 --> 00:05:27,070

you can actually see

109

00:05:27,070 --> 00:05:29,940

these regular

expressions are trees.

110

00:05:29,940 --> 00:05:33,365

So no matter what we

write down on paper,

111

00:05:33,365 --> 00:05:36,755

they are behind the

scenes always trees.

112

00:05:36,755 --> 00:05:40,010

And you can see that

actually in this definition.

113

00:05:40,010 --> 00:05:44,330

If you define two regular

expressions r1 and r2.

114

00:05:44,330 --> 00:05:49,310

They are essentially