GupShup Study
 
  
Compiler Design Lecture Notes, Ebook, and Class Notes pdf Download
Ravi Chopra

Compiler Design Lecture Notes, Ebook, and Class Notes pdf Download

Ravi Chopra | 11-Mar-2016 |
Basics of Compiler Design , Introduction , Lexical Analysis , Syntax Analysis , Scopes and Symbol Tables , Interpretation , Type Checking , Intermediate-Code Generation , Machine-Code Generation , Register Allocation , Function calls , Analysis and optimisation , Memory management , Bootstrapping a compiler ,

Hi friends, here Ravi Chopra uploaded notes for Compiler Design with title Compiler Design Lecture Notes, Ebook, and Class Notes pdf Download. You can download this lecture notes, ebook by clicking on the below file name or icon.

Basics of Compiler Design

Contents
1 Introduction 1
1.1 What is a compiler? . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The phases of a compiler . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Why learn about compilers? . . . . . . . . . . . . . . . . . . . . 4
1.5 The structure of this book . . . . . . . . . . . . . . . . . . . . . . 5
1.6 To the lecturer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.7 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.8 Permission to use . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Lexical Analysis 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Regular expressions . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Shorthands . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Nondeterministic finite automata . . . . . . . . . . . . . . . . . . 15
2.4 Converting a regular expression to an NFA . . . . . . . . . . . . . 18
2.4.1 Optimisations . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Deterministic finite automata . . . . . . . . . . . . . . . . . . . . 22
2.6 Converting an NFA to a DFA . . . . . . . . . . . . . . . . . . . . 23
2.6.1 Solving set equations . . . . . . . . . . . . . . . . . . . . 23
2.6.2 The subset construction . . . . . . . . . . . . . . . . . . . 26
2.7 Size versus speed . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.8 Minimisation of DFAs . . . . . . . . . . . . . . . . . . . . . . . 30
2.8.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.8.2 Dead states . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.9 Lexers and lexer generators . . . . . . . . . . . . . . . . . . . . . 35
2.9.1 Lexer generators . . . . . . . . . . . . . . . . . . . . . . 41
2.10 Properties of regular languages . . . . . . . . . . . . . . . . . . . 42
2.10.1 Relative expressive power . . . . . . . . . . . . . . . . . 42
2.10.2 Limits to expressive power . . . . . . . . . . . . . . . . . 44
i
ii CONTENTS
2.10.3 Closure properties . . . . . . . . . . . . . . . . . . . . . 45
2.11 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3 Syntax Analysis 53
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Context-free grammars . . . . . . . . . . . . . . . . . . . . . . . 54
3.2.1 How to write context free grammars . . . . . . . . . . . . 56
3.3 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.1 Syntax trees and ambiguity . . . . . . . . . . . . . . . . . 60
3.4 Operator precedence . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.1 Rewriting ambiguous expression grammars . . . . . . . . 64
3.5 Other sources of ambiguity . . . . . . . . . . . . . . . . . . . . . 66
3.6 Syntax analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.7 Predictive parsing . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.8 Nullable and FIRST . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.9 Predictive parsing revisited . . . . . . . . . . . . . . . . . . . . . 73
3.10 FOLLOW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.11 A larger example . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.12 LL(1) parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.12.1 Recursive descent . . . . . . . . . . . . . . . . . . . . . . 80
3.12.2 Table-driven LL(1) parsing . . . . . . . . . . . . . . . . . 81
3.12.3 Conflicts . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.13 Rewriting a grammar for LL(1) parsing . . . . . . . . . . . . . . 84
3.13.1 Eliminating left-recursion . . . . . . . . . . . . . . . . . 84
3.13.2 Left-factorisation . . . . . . . . . . . . . . . . . . . . . . 86
3.13.3 Construction of LL(1) parsers summarized . . . . . . . . 87
3.14 SLR parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.15 Constructing SLR parse tables . . . . . . . . . . . . . . . . . . . 90
3.15.1 Conflicts in SLR parse-tables . . . . . . . . . . . . . . . 94
3.16 Using precedence rules in LR parse tables . . . . . . . . . . . . . 95
3.17 Using LR-parser generators . . . . . . . . . . . . . . . . . . . . . 98
3.17.1 Declarations and actions . . . . . . . . . . . . . . . . . . 99
3.17.2 Abstract syntax . . . . . . . . . . . . . . . . . . . . . . . 99
3.17.3 Conflict handling in parser generators . . . . . . . . . . . 102
3.18 Properties of context-free languages . . . . . . . . . . . . . . . . 104
3.19 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
CONTENTS iii
4 Scopes and Symbol Tables 113
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.2 Symbol tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.2.1 Implementation of symbol tables . . . . . . . . . . . . . . 115
4.2.2 Simple persistent symbol tables . . . . . . . . . . . . . . 115
4.2.3 A simple imperative symbol table . . . . . . . . . . . . . 117
4.2.4 Efficiency issues . . . . . . . . . . . . . . . . . . . . . . 117
4.2.5 Shared or separate name spaces . . . . . . . . . . . . . . 118
4.3 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5 Interpretation 121
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.2 The structure of an interpreter . . . . . . . . . . . . . . . . . . . 122
5.3 A small example language . . . . . . . . . . . . . . . . . . . . . 122
5.4 An interpreter for the example language . . . . . . . . . . . . . . 124
5.4.1 Evaluating expressions . . . . . . . . . . . . . . . . . . . 124
5.4.2 Interpreting function calls . . . . . . . . . . . . . . . . . 126
5.4.3 Interpreting a program . . . . . . . . . . . . . . . . . . . 128
5.5 Advantages and disadvantages of interpretation . . . . . . . . . . 128
5.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6 Type Checking 133
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.2 The design space of types . . . . . . . . . . . . . . . . . . . . . . 133
6.3 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4 Environments for type checking . . . . . . . . . . . . . . . . . . 135
6.5 Type checking expressions . . . . . . . . . . . . . . . . . . . . . 136
6.6 Type checking of function declarations . . . . . . . . . . . . . . . 138
6.7 Type checking a program . . . . . . . . . . . . . . . . . . . . . . 139
6.8 Advanced type checking . . . . . . . . . . . . . . . . . . . . . . 140
6.9 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7 Intermediate-Code Generation 147
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.2 Choosing an intermediate language . . . . . . . . . . . . . . . . . 148
7.3 The intermediate language . . . . . . . . . . . . . . . . . . . . . 150
7.4 Syntax-directed translation . . . . . . . . . . . . . . . . . . . . . 151
7.5 Generating code from expressions . . . . . . . . . . . . . . . . . 152
7.5.1 Examples of translation . . . . . . . . . . . . . . . . . . . 155
iv CONTENTS
7.6 Translating statements . . . . . . . . . . . . . . . . . . . . . . . 156
7.7 Logical operators . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.7.1 Sequential logical operators . . . . . . . . . . . . . . . . 160
7.8 Advanced control statements . . . . . . . . . . . . . . . . . . . . 164
7.9 Translating structured data . . . . . . . . . . . . . . . . . . . . . 165
7.9.1 Floating-point values . . . . . . . . . . . . . . . . . . . . 165
7.9.2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.9.3 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.9.4 Records/structs and unions . . . . . . . . . . . . . . . . . 171
7.10 Translating declarations . . . . . . . . . . . . . . . . . . . . . . . 172
7.10.1 Example: Simple local declarations . . . . . . . . . . . . 172
7.11 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8 Machine-Code Generation 179
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
8.2 Conditional jumps . . . . . . . . . . . . . . . . . . . . . . . . . . 180
8.3 Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.4 Exploiting complex instructions . . . . . . . . . . . . . . . . . . 181
8.4.1 Two-address instructions . . . . . . . . . . . . . . . . . . 186
8.5 Optimisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
8.6 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
9 Register Allocation 191
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.2 Liveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
9.3 Liveness analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 193
9.4 Interference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.5 Register allocation by graph colouring . . . . . . . . . . . . . . . 199
9.6 Spilling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
9.7 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
9.7.1 Removing redundant moves . . . . . . . . . . . . . . . . 205
9.7.2 Using explicit register numbers . . . . . . . . . . . . . . 205
9.8 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
10 Function calls 209
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10.1.1 The call stack . . . . . . . . . . . . . . . . . . . . . . . . 209
10.2 Activation records . . . . . . . . . . . . . . . . . . . . . . . . . . 210
10.3 Prologues, epilogues and call-sequences . . . . . . . . . . . . . . 211
CONTENTS v
10.4 Caller-saves versus callee-saves . . . . . . . . . . . . . . . . . . 213
10.5 Using registers to pass parameters . . . . . . . . . . . . . . . . . 215
10.6 Interaction with the register allocator . . . . . . . . . . . . . . . . 219
10.7 Accessing non-local variables . . . . . . . . . . . . . . . . . . . 221
10.7.1 Global variables . . . . . . . . . . . . . . . . . . . . . . 221
10.7.2 Call-by-reference parameters . . . . . . . . . . . . . . . . 222
10.7.3 Nested scopes . . . . . . . . . . . . . . . . . . . . . . . . 223
10.8 Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
10.8.1 Variable-sized frames . . . . . . . . . . . . . . . . . . . . 226
10.8.2 Variable number of parameters . . . . . . . . . . . . . . . 227
10.8.3 Direction of stack-growth and position of FP . . . . . . . 227
10.8.4 Register stacks . . . . . . . . . . . . . . . . . . . . . . . 228
10.8.5 Functions as values . . . . . . . . . . . . . . . . . . . . . 228
10.9 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
11 Analysis and optimisation 231
11.1 Data-flow analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 232
11.2 Common subexpression elimination . . . . . . . . . . . . . . . . 233
11.2.1 Available assignments . . . . . . . . . . . . . . . . . . . 233
11.2.2 Example of available-assignments analysis . . . . . . . . 236
11.2.3 Using available assignment analysis for common subexpression
elimination . . . . . . . . . . . . . . . . . . . . 237
11.3 Jump-to-jump elimination . . . . . . . . . . . . . . . . . . . . . 240
11.4 Index-check elimination . . . . . . . . . . . . . . . . . . . . . . 241
11.5 Limitations of data-flow analyses . . . . . . . . . . . . . . . . . . 244
11.6 Loop optimisations . . . . . . . . . . . . . . . . . . . . . . . . . 245
11.6.1 Code hoisting . . . . . . . . . . . . . . . . . . . . . . . . 245
11.6.2 Memory prefetching . . . . . . . . . . . . . . . . . . . . 246
11.7 Optimisations for function calls . . . . . . . . . . . . . . . . . . . 248
11.7.1 Inlining . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
11.7.2 Tail-call optimisation . . . . . . . . . . . . . . . . . . . . 250
11.8 Specialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
11.9 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
12 Memory management 257
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
12.2 Static allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
12.2.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . 258
12.3 Stack allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
vi CONTENTS
12.4 Heap allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
12.5 Manual memory management . . . . . . . . . . . . . . . . . . . 259
12.5.1 A simple implementation of malloc() and free() . . . . 260
12.5.2 Joining freed blocks . . . . . . . . . . . . . . . . . . . . 263
12.5.3 Sorting by block size . . . . . . . . . . . . . . . . . . . . 264
12.5.4 Summary of manual memory management . . . . . . . . 265
12.6 Automatic memory management . . . . . . . . . . . . . . . . . . 266
12.7 Reference counting . . . . . . . . . . . . . . . . . . . . . . . . . 266
12.8 Tracing garbage collectors . . . . . . . . . . . . . . . . . . . . . 268
12.8.1 Scan-sweep collection . . . . . . . . . . . . . . . . . . . 269
12.8.2 Two-space collection . . . . . . . . . . . . . . . . . . . . 271
12.8.3 Generational and concurrent collectors . . . . . . . . . . 273
12.9 Summary of automatic memory management . . . . . . . . . . . 276
12.10Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
13 Bootstrapping a compiler 281
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
13.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
13.3 Compiling compilers . . . . . . . . . . . . . . . . . . . . . . . . 283
13.3.1 Full bootstrap . . . . . . . . . . . . . . . . . . . . . . . . 285
13.4 Further reading . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
A Set notation and concepts 291
A.1 Basic concepts and notation . . . . . . . . . . . . . . . . . . . . . 291
A.1.1 Operations and predicates . . . . . . . . . . . . . . . . . 291
A.1.2 Properties of set operations . . . . . . . . . . . . . . . . . 292
A.2 Set-builder notation . . . . . . . . . . . . . . . . . . . . . . . . . 293
A.3 Sets of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
A.4 Set equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
A.4.1 Monotonic set functions . . . . . . . . . . . . . . . . . . 295
A.4.2 Distributive functions . . . . . . . . . . . . . . . . . . . . 296
A.4.3 Simultaneous equations . . . . . . . . . . . . . . . . . . 297
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

 

Free Download Basics of Compiler Design Lecture Notes, Ebook, and Class Notes pdf

    Attachment Lists

    If download doesn't start in application like IDM then press Alt + click on download button to start download
  • basics_Compiler.pdf (Size: 1435.93KB) Dowland
Share With Friends :  

No any Comment yet!