Introduction to Compilers

Programs, Interpreters and Translators

A program is something that computes. A program is written in some language.

An interpreter is a program whose input is a program P and some other data x; it "executes" P on x:

That is, I(P,x) = P(x). The fact that a single interpreter exists that is capable of executing all possible programs (Turing-computable functions) is a very deep and significant discovery of Turing's.

Note that a CPU is, essentially, an interpreter for its machine language programs.

A translator is a program which takes as input a program in some language S and outputs a program in a language T such that the two programs have the same "semantics."

where forall x, P(x) = Q(x).

Some translators have really strange names

Assembler

Translates assembly language programs into machine language programs

Compiler

Translates programs in a "high-level" language into programs in a lower-level language

Sometimes we translate (compile) source code all the way down to something interpretable, such as machine language, for example:

However, there are also languages that allow you to execute code during compilation time and compile new code at run time.

Translators exist for many kinds of languages, for example:

Conventional Programming Languages
Text Formatting Languages
Database Query Languages
Scripting Languages
Machine Languages
Assembly Languages
Device Controller Languages
Abstract Machine Languages

Programs related to translators include

Preprocessors
Linkers
Loaders
Debuggers
Profilers

Translator Notation

There're three languages involved in translation:

Exercise: Explain how to use a self-compiler and a cross-compiler to port a compiler to an architecture that has no compiler.

Exercise: A compiler is called an optimizing compiler if it works really hard to produce the most efficient target code that is feasibly possible. What can you use an optimizing self-compiler for?

Translation Phases

Translation consists of analysis and synthesis phases.

There are two reasons for this:

We can't help but doing it any other way. Word for word transation just doesn't work
It makes good engineering sense: if we need to write translators for M source languages and N target languages, we need only write M + N simple programs (half-compilers) rather than writing M × N complex programs (full-compilers).

Exercise: Give the most outrageous example you can think of where word-for-word translation between two natural languages comes out "so wrong".

Why Study Compilers

Even if you never write a complete production compiler, compiler technology is good to know because its concepts are used everywhere, for example:

Text formatters
Database Query Languages
Advanced Computer Architectures
Generalized optimization tasks
Graphics interfaces
Scripting Languages
Translation of human languages

Also, you learn how to write better programs since writing a compiler for a language means you better understand its intricacies and obscurities. Studying general principles of translation also makes you a better language designer. Does it really matter how "cool" your language is if it can't be implemented efficiently?

Compiler technology spans many different areas of computer science:

Formal Language Theory
- Grammars
- Parsing
- Computability
Programming Languages
- Syntax
- Semantics
  - Static semantics vs. dynamic semantics
- Language Paradigms
  - block-structured, object-oriented, functional, logic, ...
- Abstract Languages
- Fancy Terms
  - e.g. scope, extent, volatile, const, subtype, inheritance, polymorphism, parameter modes
Computer Architecture
- Instruction sets
- RISC vs. CISC
- Clock cycles, etc.
Algorithms and Data Structures
Software Engineering
- because compilers are generally large and complex

Also keep this in mind:

A compiler course is really just a Programming Languages II course. In Programming Languages I you learn about specifying and using languages. In Programming Languages II you learn about desgining and implementing languages. Implementation is interpretation and translation.

Designing a Compiler

Some issues in designing a real compiler:

Source Language Issues
iIs the source language easy to compile? Is there a preprocessor? How are types handled? Are there source language libraries?
Grouping of compiler passes
Single or multipass?
Degree of optimization desired
Quick and dirty translation with little or no optimization may be okay. Lots of optimization will slow the compiler down but the better runtime code make be worth it.
Degree of error recovery desired
Can the compiler just stop on the first error? When should it stop? Would you trust the compiler to fix the errors for you? (??) (????)
Availability of tools
Unless the source language is very, very small, scanner and parser generators are a must. There do exist code generator generators too, but they are not as common.
Kind of target code to generate
Choose among pure machine code, augmented machine code, virtual machine code. Or are you just writing a front end, and targeting something like C, RTL, or the JVM?
Format of target code
Choose among assembly language, relocatable machine code, memory image machine code.
Retargetability
... is a good thing sometimes.