1

00:00:16,280 --> 00:00:18,330

A warm welcome to

2

00:00:18,330 --> 00:00:20,820

the compilers and formal

languages module?

3

00:00:20,820 --> 00:00:24,390

My name is Christian Urban.

Thank you for coming.

4

00:00:24,390 --> 00:00:27,644

Compilers. I guess

you use compilers

5

00:00:27,644 --> 00:00:31,680

in your daily work, be it

the C or Java compiler.

6

00:00:31,680 --> 00:00:34,245

And you might be curious

in what they do.

7

00:00:34,245 --> 00:00:35,700

But you might also be

8

00:00:35,700 --> 00:00:38,130

intimidated to look

what they do underneath

9

00:00:38,130 --> 00:00:39,900

the bonnet because they are

10

00:00:39,900 --> 00:00:42,520

quite large software systems.

11

00:00:42,520 --> 00:00:46,130

What I like to show you in

this module is that you

12

00:00:46,130 --> 00:00:49,310

do not need to be an

Überhacker to implement your own

13

00:00:49,310 --> 00:00:51,305

compiler for your

own language, say.

14

00:00:51,305 --> 00:00:54,155

So that will be the main

goal of this module.

15

00:00:54,155 --> 00:00:56,210

You will implement

your own compiler,

16

00:00:56,210 --> 00:00:58,310

of course with my help.

17

00:00:58,310 --> 00:01:02,360

What I personally like

about compilers is that

18

00:01:02,360 --> 00:01:04,580

the subject is a

perfect combination

19

00:01:04,580 --> 00:01:06,350

of theory and practice.

20

00:01:06,350 --> 00:01:07,790

I like to hack things,

21

00:01:07,790 --> 00:01:10,595

writing actual code,

but I also like theory.

22

00:01:10,595 --> 00:01:13,040

I want to understand what

my code actually does.

23

00:01:13,040 --> 00:01:17,040

So compilers are the

perfect subject for me.

24

00:01:18,040 --> 00:01:20,809

Let's have a look at the details.

25

00:01:20,809 --> 00:01:23,779

Here's an airplane

view of a compiler.

26

00:01:23,779 --> 00:01:25,850

On the left-hand side you can see

27

00:01:25,850 --> 00:01:28,745

the input program a

developer would write.

28

00:01:28,745 --> 00:01:31,955

And on the right-hand side is

the output of the compiler,

29

00:01:31,955 --> 00:01:36,360

the binary code the developer

wants to actually run.

30

00:01:36,370 --> 00:01:40,340

What makes such a project

actually feasible is that

31

00:01:40,340 --> 00:01:44,165

compilers fall neatly into

separate components.

32

00:01:44,165 --> 00:01:47,210

So you can see the lexer and the

33

00:01:47,210 --> 00:01:48,860

parser, which are often called the

34

00:01:48,860 --> 00:01:50,990

front end of the compiler.

35

00:01:50,990 --> 00:01:53,000

And the code generation is

36

00:01:53,000 --> 00:01:55,700

called the backend

of the compiler.

37

00:01:55,700 --> 00:01:57,620

And it so happens

that we will spend

38

00:01:57,620 --> 00:01:59,930

the first five weeks

on the lexer and

39

00:01:59,930 --> 00:02:04,970

the parser, and the next five

weeks on the code generator.

40

00:02:04,970 --> 00:02:09,575

The first component of the

compiler is the lexer.

41

00:02:09,575 --> 00:02:14,480

The purpose of the lexer

is to scan a flat

42

00:02:14,480 --> 00:02:16,610

string, which the

input program is at

43

00:02:16,610 --> 00:02:19,145

the beginning and separate out

44

00:02:19,145 --> 00:02:21,275

where are the words?

45

00:02:21,275 --> 00:02:23,600

You might think

in Western languages,

46

00:02:23,600 --> 00:02:24,920

that is very easy:

47

00:02:24,920 --> 00:02:26,690

you just try to

find out where are

48

00:02:26,690 --> 00:02:28,580

the whitespaces

and then you know,

49

00:02:28,580 --> 00:02:31,955

where one word stops and

where the next word begins.

50

00:02:31,955 --> 00:02:35,300

But, actually, computer

languages are more

51

00:02:35,300 --> 00:02:38,180

like ancient languages

that you see here.

52

00:02:38,180 --> 00:02:39,860

For example, ancient Greek.

53

00:02:39,860 --> 00:02:42,065

The writer wrote one word

54

00:02:42,065 --> 00:02:44,915

after the next and not

leaving any space.

55

00:02:44,915 --> 00:02:47,930

So for example, in this

very simple string here

56

00:02:47,930 --> 00:02:50,960

read n, there is no space at all.

57

00:02:50,960 --> 00:02:53,540

But the purpose of

the lexer is to

58

00:02:53,540 --> 00:02:56,570

separate it into five

different components.

59

00:02:56,570 --> 00:02:59,450

It has to first say,

well there is a read,

60

00:02:59,450 --> 00:03:01,595

then there is a left parenthesis,

61

00:03:01,595 --> 00:03:04,025

then there's an

identifier called n,

62

00:03:04,025 --> 00:03:07,715

then there's a right parenthesis,

and finally a semicolon.

63

00:03:07,715 --> 00:03:11,345

And as you can see, there

is no space here at all.

64

00:03:11,345 --> 00:03:14,150

And so the task of finding where

65

00:03:14,150 --> 00:03:17,705

are the words is actually

quite involved.

66

00:03:17,705 --> 00:03:19,460

Also the classification is

67

00:03:19,460 --> 00:03:22,055

sometimes not so straightforward.

68

00:03:22,055 --> 00:03:24,350

If, for example, a writer

69

00:03:24,350 --> 00:03:26,360

wrote "if" on its own,

70

00:03:26,360 --> 00:03:29,000

then this should be a

keyword classified as

71

00:03:29,000 --> 00:03:32,615

a keyword because it's

from the if-then-else.

72

00:03:32,615 --> 00:03:36,800

But if the developer wrote

something longer like "iffoo",

73

00:03:36,800 --> 00:03:38,030

then this might just be

74

00:03:38,030 --> 00:03:39,860

a strange variable name

and he needs to be

75

00:03:39,860 --> 00:03:44,250

classified as a variable name.

76

00:03:45,220 --> 00:03:50,720

The output of the lexer 

is a sequence of tokens.

77

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

These are essentially the words in

78

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

a sentence and their

classification:

79

00:03:56,405 --> 00:03:59,540

they are nouns,

verbs or adjectives.

80

00:03:59,540 --> 00:04:02,885

For us, of course, the

classification would be keywords,

81

00:04:02,885 --> 00:04:06,005

identifiers,

operators, and so on.

82

00:04:06,005 --> 00:04:11,480

And these tokens are the

input for the parser,

83

00:04:11,480 --> 00:04:13,085

the next component in

84

00:04:13,085 --> 00:04:17,240

our compiler. The parser

essentially takes this list

85

00:04:17,240 --> 00:04:23,300

of tokens and transforms it

into a abstract syntax tree.

86

00:04:23,300 --> 00:04:27,230

That means we have now the

sentence, we have the words.

87

00:04:27,230 --> 00:04:30,275

We have to relate

the words to each other

88

00:04:30,275 --> 00:04:33,680

in order to find out what

this sentence actually means.

89

00:04:33,680 --> 00:04:35,405

In this case here,

90

00:04:35,405 --> 00:04:38,595

we have to do a read...which

variable is affected?

91

00:04:38,595 --> 00:04:45,040

The variable n. Once we have

the abstract syntax tree,

92

00:04:45,040 --> 00:04:49,225

it can go to the next component,

to the code generator.

93

00:04:49,225 --> 00:04:52,480

Whilst it doesn't look

like this in this picture,

94

00:04:52,480 --> 00:04:54,100

the code generators is usually the

95

00:04:54,100 --> 00:04:56,080

biggest part in a compiler.

96

00:04:56,080 --> 00:04:58,720

And here we actually

have to cut corners.

97

00:04:58,720 --> 00:05:02,470

Instead of producing binary

code, which can be run

98

00:05:02,470 --> 00:05:06,820

directly on a CPU, like X86 or ARM,

99

00:05:06,820 --> 00:05:11,035

we actually target the

Java Virtual Machine, the JVM.

100

00:05:11,035 --> 00:05:13,600

This is very similar

to the Scala compiler,

101

00:05:13,600 --> 00:05:16,480

for example, which

produces JVM code.

102

00:05:16,480 --> 00:05:18,940

Or, of course, also 

the Java compiler,

103

00:05:18,940 --> 00:05:20,845

which produces JVM code.

104

00:05:20,845 --> 00:05:23,900

So here's a typical

example code which we're

105

00:05:23,900 --> 00:05:27,305

going to produce: Something

like variable 2

106

00:05:27,305 --> 00:05:30,545

gets allocated in the stack.

107

00:05:30,545 --> 00:05:32,390

You subtract ten from it.

108

00:05:32,390 --> 00:05:36,050

You test whether the

variable is 0 and if yes,

109

00:05:36,050 --> 00:05:40,170

you jump somewhere and otherwise

you reload the variable.

110

00:05:41,560 --> 00:05:45,935

Even though we cut corners

in the code generater part

111

00:05:45,935 --> 00:05:48,575

by producing code for the JVM,

112

00:05:48,575 --> 00:05:51,710

we can still obtain quite

impressive results.

113

00:05:51,710 --> 00:05:56,225

Here's a program with

a cubic runtime behaviour.