Compiler

In computer science, a compiler is software capable of translating from one formal language to another, usually to translate a human readable program description to a machine readable program description. The input to a compiler is a file (or files) of source code, usually text for a high-level, human-readable language such as Java, though it could be any unambiguous representation of an algorithm, such as a flow chart or finite state machine. The output of a compiler is a file in a target language, often a machine language, though it could just as well be another high-level language.

Structure of Compilers

Like any class of software, there is a large variety of implementations. However, most compilers follow this pattern,

1. Lexical Analysis or Scanning, in which the input characters are recognized by a set of regular expressions and output as a sequence of tokens.
2. Syntactical Analysis or Parsing, in which the input tokens are recognized by a set of pushdown automatons and output a sequence of semantic actions.
3. Semantic Analysis, in which each semantic action builds an internal or intermediate representation of the source program, and context sensitive errors (any error that cannot be discriminated by a context-free language) are detected.
4. Optimization, in which the compiler attempts to replace computationally expensive portions of the program with less expensive versions, provided that no substitution affects the operation of the program.
5. Code Generation, in which the intermediate language is translated piece at a time to the target language.
6. Peephole Optimization, a final optimization pass in which analyses the output code over a small region (the peephole), searching for very localized optimizations.

In actuality, there may be multiple optimization stages scattered throughout this process. Additionally, most modern compilers repeatedly translate the language from an intermediate representation to a simpler intermediate representation in order to accomodate a wide swath of optimizations that operate on different levels of detail.

Lexical Analysis

During lexical analysis, a set of regular expressions translate the input sequence (generally characters) into an output sequence (called tokens). One popular tool to simplify the creation of lexical analyzers is a software package called lex.

Readers accustomed to programming may benefit from a few examples of errors that can be detected during this phase. A lexical analyzer could detect errors in a single token, for instance a number that has the letter 'y' in it, or a string with a missing end quote.

Syntactic Analysis

During syntactic analysis, an input sequence of tokens is matched against a set of gramatical constructs called productions. As each production is matched, a semantic action routine is called. The role of each semantic action is to build an intermediate representation of the input program, such as a list of variables and functions, and a sequence of instructions comprising each function.

Readers accustomed to programming may benefit from a few examples of errors that can be detected during this phase. A Syntactic analyzer could detect a syntactic error, such as a missing semicolon or curly brace. A syntactic analyzer cannot detect the use of an undeclared variable. This is because the declaration of a variable before its use is a context sensitive langauge requirement, though syntactic analyzers are generally context-free language recognizers.

Semantic Analysis

During semantic analysis, a compiler builds and examines an intermediate representation of the source program and checks it for consistency.

Readers accustomed to programming may benefit from a few examples of errors that can be detected during this phase. A semantic analyzer could detect errors, such as undeclared variables or functions.

Optimization

During optimization, a compiler attempts to alter its internal representation of the input program as to improve code speed, size, or many other code characteristics.

Translation Systems other than Compilers

Babelfish?

See Also

• formal language
• high-level language
• Lexical Analysis or Scanning
• Syntactical Analysis or Parsing
• Semantic Analysis
• Optimization
• Code Generation