Compiler

A compiler is a computer program that translates a computer program written in one computer language (called the source language) into a program written in another computer language (called the output or the target language).

Usually the translation is from a source code (generally a high level language) to a target code (generally a low level object code or machine language) that may be directly executed by a computer or a virtual machine. However, a compiler from a low level language to a high level one is also possible; this is normally known as a decompiler if it is reconstructing a high level language which (could have) generated the low level language. Compilers also exist which translate from one high level language to another, or sometimes to an intermediate language that still needs further processing; these are sometimes known as cascaders.

Typical compilers output so-called objectss that basically contain machine code augmented by information about the name and location of entry points and external calls (to functions not contained in the object). A set of object files, which need not have all come from a single compiler provided that the compilers used share a common output format, may then be linked together to create the final executable which can be run directly by a user.

Table of contents

1 Types of compilers 2 Compiler design 3 Compiler front end 4 Compiler back end 5 Compiled vs. Interpreted languages 6 Further reading

Types of compilers

Compiler design

Compiler front end

The compiler front end consists of multiple phases itself, each informed by formal language theory:

1. Lexical analysis - breaking the source code text into small pieces ('tokens' or 'terminals'), each representing a single atomic unit of the language, for instance a keyword, identifier or symbol names. The token language is typically a regular language, so a finite state automaton constructed from a regular expression can be used to recognize it. This phase is also called lexing or scanning.
2. Syntax analysis - Identifying syntactic structures of source code. It only focuses on the structure. In other words, it identifies the order of tokens and understand hierarchical structures in code. This phase is also called parsing.
3. Semantic analysis is to recognize the meaning of program code and start to prepare for output. In that phrase, type checking is done and most of compiler errors show up.
4. Intermediate language generation - an equivalent to the original program is created in an intermediate language.

1. Optimization - the intermediate language representation is transformed into functionaly equivalent but faster (or smaller) forms.
2. Code generation - the transformed intermediate language is translated into the output language, usually the native machine language of the system. This involves resource and storage decisions, such as deciding which variables to fit into registers and memory and the selection and scheduling of appropriate machine instructions.

Many people divide higher level programming languages into two categories: compiled languages and interpreted languages. However, in fact most of these languages can be implemented either through compilation or interpretation, the categorisation merely reflecting which method is most commonly used to implement that language. (Some interpreted languages, however, cannot easily be implemented through compilation, especially those which allow self-modifying code.)

Further reading

Compilers: Principles, Techniques and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman (ISBN 0201100886) is considered to be the standard authority on compiler basics, and makes a good primer for the techniques mentioned above. (It is often called the Dragon book because of the picture on its cover showing a Knight of Programming fighting the Dragon of Compiler Design.) [1]

Understanding and Writing Compilers: A Do It Yourself Guide (ISBN 0333217322) by Richard Bornat is an unusually helpful book, being one of the few that adequately explains the recursive generation of machine instructions from a parse-tree. Having learnt his subject in the early days of mainframes and minicomputers, the author has many useful insights that more recent books often fail to convey.

During the 1990s a large number of free compilers and compiler development tools have been developed for all kinds of languages, both as part of the GNU project and other open-source initiatives. Some of them are considered to be of high quality and their free source code makes a nice read for anyone interested in modern compiler concepts.

See also: assembler, interpreter (computer software), linker, Abstract interpretation, Parsing, Top-bottom parsing, Bottom-up parsing