Implementing_Programming_Languages_2012_Ranta.pdf

(714 KB) Pobierz
Implementing
Programming Languages
Aarne Ranta
February 6, 2012
2
Contents
1 What is a programming language implementation
1.1 From language to binary
. . . . . . . . . . . . . . .
1.2 Levels of languages
. . . . . . . . . . . . . . . . . .
1.3 Compilation and interpretation
. . . . . . . . . . .
1.4 Compilation phases
. . . . . . . . . . . . . . . . . .
1.5 Compiler errors
. . . . . . . . . . . . . . . . . . . .
1.6 More compiler phases
. . . . . . . . . . . . . . . . .
1.7 Theory and practice
. . . . . . . . . . . . . . . . .
1.8 The scope of the techniques
. . . . . . . . . . . . .
2 What can a grammar do for you
2.1 Defining a language
. . . . . . .
2.2 Using BNFC
. . . . . . . . . . .
2.3 Rules, categories, and trees
. . .
2.4 Precedence levels
. . . . . . . .
2.5 Abstract and concrete syntax
.
2.6 Abstract syntax in Haskell
. . .
2.7 Abstract syntax in Java
. . . .
2.8 List categories
. . . . . . . . . .
2.9 Specifying the lexer
. . . . . . .
2.10 Working out a grammar
. . . .
11
11
14
16
18
20
22
23
24
25
25
27
30
32
33
36
38
41
42
45
51
51
52
54
58
61
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 How do lexers and parsers work*
3.1 The theory of formal languages
. . . .
3.2 Regular languages and finite automata
3.3 The compilation of regular expressions
3.4 Properties of regular languages
. . . .
3.5 Context-free grammars and parsing
. .
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
3.6
3.7
3.8
3.9
LL(k) parsing
. . . . . . . . . . . .
LR(k) parsing
. . . . . . . . . . . .
Finding and resolving conflicts
. . .
The limits of context-free grammars
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
CONTENTS
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
62
65
68
70
73
73
75
75
76
78
79
79
81
83
85
88
95
95
96
98
99
101
101
102
104
4 When does a program make sense
4.1 The purposes of type checking
. . . . . . . . . . . .
4.2 Specifying a type checker
. . . . . . . . . . . . . . .
4.3 Type checking and type inference
. . . . . . . . . .
4.4 Context, environment, and side conditions
. . . . .
4.5 Proofs in a type system
. . . . . . . . . . . . . . . .
4.6 Overloading and type casts
. . . . . . . . . . . . . .
4.7 The validity of statements and function definitions
.
4.8 Declarations and block structures
. . . . . . . . . .
4.9 Implementing a type checker
. . . . . . . . . . . . .
4.10 Type checker in Haskell
. . . . . . . . . . . . . . .
4.11 Type checker in Java
. . . . . . . . . . . . . . . . .
5 How to run programs in an interpreter
5.1 Specifying an interpreter
. . . . . . . . . . . . . .
5.2 Side effects
. . . . . . . . . . . . . . . . . . . . . .
5.3 Statements
. . . . . . . . . . . . . . . . . . . . . .
5.4 Programs, function definitions, and function calls
5.5 Laziness
. . . . . . . . . . . . . . . . . . . . . . .
5.6 Debugging interpreters
. . . . . . . . . . . . . . .
5.7 Implementing the interpreter
. . . . . . . . . . . .
5.8 Interpreting Java bytecode
. . . . . . . . . . . . .
6 Compiling to machine code
6.1 The semantic gap
. . . . . . . . . . . .
6.2 Specifying the code generator
. . . . .
6.3 The compilation environment
. . . . .
6.4 Simple expressions and statements
. .
6.5 Expressions and statements with jumps
6.6 Compositionality
. . . . . . . . . . . .
6.7 Function calls and definitions
. . . . .
6.8 Putting together a class file
. . . . . .
6.9 Compiling to native code
. . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
109
. 109
. 110
. 111
. 112
. 115
. 118
. 118
. 121
. 122
CONTENTS
5
6.10 Memory management
. . . . . . . . . . . . . . . . . . . . . . . 122
7 Functional programming languages
8 How simple can a language be*
9 Designing your own language
10 Compiling natural language*
123
125
127
129

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin