Textbook in PDF format

In order to reduce the complexity of designing and building computers, nearly all of these are made to execute relatively simple commands (but do so very quickly). A program for a computer must be built by combining these very simple commands into a program in what is called machine language. Since this is a tedious and error-prone process, most programming is done using a high-level programming language. This language can be very different from the machine language that the computer can execute, so some means of bridging the gap is required. This is where the compiler comes in.
A compiler translates (or compiles) a program written in a high-level programming language that is suitable for human programmers into the low-level machine language that is required by computers. During this process, the compiler will also attempt to detect and report obvious programmer mistakes.
Using a high-level language for programming has a large impact on how fast programs can be developed. The main reasons for this are:
Compared to machine language, the notation used by programming languages is closer to the way humans think about problems.
The compiler can detect some types of programming mistakes.
Programs written in a high-level language tend to be shorter than equivalent programs written in machine language.
Another advantage of using a high-level language is that the same program can be compiled to many different machine languages, and hence be brought to run on many different machines.
On the other hand, programs that are written in a high-level language and automatically translated to machine language may run somewhat slower than programs that are hand-coded in machine language. Hence, some time-critical programs are still written partly in machine language. A good compiler will, however, be able to get very close to the speed of hand-written machine code when translating well-structured programs. Additionally, what code is optimal may change when a new version of a processor is made, so to remain optimal, a hand-written machine language program may need to be rewritten, whereas a program in a high-level language just needs to be recompiled using a compiler that optimizes for the new version of the processor.
The third edition of this textbook has been fully revised and adds material about the SSA form, polymorphism, garbage collection, and pattern matching. It presents techniques for making realistic compilers for simple to intermediate-complexity programming languages. The techniques presented in the book are close to those used in professiona.l compilers, albeit in places slightly simplified for presentation purposes. "Further reading" sections point to material about the full versions of the techniques.
All phases required for translating a high-level language to symbolic machine language are covered, and some techniques for optimising code are presented. Type checking and interpretation are also included.
Aiming to be neutral with respect to implementation languages, algorithms are mostly presented in pseudo code rather than in any specific language, but suggestions are in many places given for how these can be realised in different language paradigms.
Since writing a compiler is a nontrivial task, it is a good idea to structure the work. A typical way of doing this is to split the compilation into several phases with well-defined interfaces between them. Conceptually, these phases operate in sequence (though in practice, they are often interleaved), each phase (except the first) taking the output from the previous phase as its input. It is common to let each phase be handled by a separate program module. Some of these modules are written by hand, while others may be generated from specifications. Often, some of the modules can be shared between several compilers.
The intermediate language is translated to assembly language (a textual representation of machine code) for a specific machine architecture. The assembly language code is translated into binary representation and addresses of variables, functions, etc., are determined. Assembly and linking are typically done by programs supplied by the machine or operating system vendor, and are hence not part of the compiler itself. We will not further discuss these phases in this book, but assume that a compiler produces its result as symbolic assembly code.
An interpreter is another way of implementing a programming language. Interpretation shares many aspects with compiling. Lexing, parsing and type-checking are in an interpreter done just as in a compiler. But instead of generating code from the syntax tree, the syntax tree is processed directly to evaluate expressions, execute statements, and so on. Compilation and interpretation may be combined to implement a programming language. For example, the compiler may produce intermediate-level code which is then interpreted rather than compiled to machine code