Implementing Programming Languages - Chalmers

Implementing Programming Languages

Aarne Ranta February 6, 2012

2

Contents

1 What is a programming language implementation

11

1.1 From language to binary . . . . . . . . . . . . . . . . . . . . . 11

1.2 Levels of languages . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3 Compilation and interpretation . . . . . . . . . . . . . . . . . 16

1.4 Compilation phases . . . . . . . . . . . . . . . . . . . . . . . . 18

1.5 Compiler errors . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.6 More compiler phases . . . . . . . . . . . . . . . . . . . . . . . 22

1.7 Theory and practice . . . . . . . . . . . . . . . . . . . . . . . 23

1.8 The scope of the techniques . . . . . . . . . . . . . . . . . . . 24

2 What can a grammar do for you

25

2.1 Defining a language . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Using BNFC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3 Rules, categories, and trees . . . . . . . . . . . . . . . . . . . . 30

2.4 Precedence levels . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5 Abstract and concrete syntax . . . . . . . . . . . . . . . . . . 33

2.6 Abstract syntax in Haskell . . . . . . . . . . . . . . . . . . . . 36

2.7 Abstract syntax in Java . . . . . . . . . . . . . . . . . . . . . 38

2.8 List categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.9 Specifying the lexer . . . . . . . . . . . . . . . . . . . . . . . . 42

2.10 Working out a grammar . . . . . . . . . . . . . . . . . . . . . 45

3 How do lexers and parsers work*

51

3.1 The theory of formal languages . . . . . . . . . . . . . . . . . 51

3.2 Regular languages and finite automata . . . . . . . . . . . . . 52

3.3 The compilation of regular expressions . . . . . . . . . . . . . 54

3.4 Properties of regular languages . . . . . . . . . . . . . . . . . 58

3.5 Context-free grammars and parsing . . . . . . . . . . . . . . . 61

3

4

CONTENTS

3.6 LL(k) parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.7 LR(k) parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.8 Finding and resolving conflicts . . . . . . . . . . . . . . . . . . 68 3.9 The limits of context-free grammars . . . . . . . . . . . . . . . 70

4 When does a program make sense

73

4.1 The purposes of type checking . . . . . . . . . . . . . . . . . . 73

4.2 Specifying a type checker . . . . . . . . . . . . . . . . . . . . . 75

4.3 Type checking and type inference . . . . . . . . . . . . . . . . 75

4.4 Context, environment, and side conditions . . . . . . . . . . . 76

4.5 Proofs in a type system . . . . . . . . . . . . . . . . . . . . . . 78

4.6 Overloading and type casts . . . . . . . . . . . . . . . . . . . . 79

4.7 The validity of statements and function definitions . . . . . . . 79

4.8 Declarations and block structures . . . . . . . . . . . . . . . . 81

4.9 Implementing a type checker . . . . . . . . . . . . . . . . . . . 83

4.10 Type checker in Haskell . . . . . . . . . . . . . . . . . . . . . 85

4.11 Type checker in Java . . . . . . . . . . . . . . . . . . . . . . . 88

5 How to run programs in an interpreter

95

5.1 Specifying an interpreter . . . . . . . . . . . . . . . . . . . . . 95

5.2 Side effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5.3 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.4 Programs, function definitions, and function calls . . . . . . . 99

5.5 Laziness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5.6 Debugging interpreters . . . . . . . . . . . . . . . . . . . . . . 101

5.7 Implementing the interpreter . . . . . . . . . . . . . . . . . . . 102

5.8 Interpreting Java bytecode . . . . . . . . . . . . . . . . . . . . 104

6 Compiling to machine code

109

6.1 The semantic gap . . . . . . . . . . . . . . . . . . . . . . . . . 109

6.2 Specifying the code generator . . . . . . . . . . . . . . . . . . 110

6.3 The compilation environment . . . . . . . . . . . . . . . . . . 111

6.4 Simple expressions and statements . . . . . . . . . . . . . . . 112

6.5 Expressions and statements with jumps . . . . . . . . . . . . . 115

6.6 Compositionality . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.7 Function calls and definitions . . . . . . . . . . . . . . . . . . 118

6.8 Putting together a class file . . . . . . . . . . . . . . . . . . . 121

6.9 Compiling to native code . . . . . . . . . . . . . . . . . . . . . 122

CONTENTS

5

6.10 Memory management . . . . . . . . . . . . . . . . . . . . . . . 122

7 Functional programming languages

123

8 How simple can a language be*

125

9 Designing your own language

127

10 Compiling natural language*

129

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download