Technical note

Summarizing Compiler Design — Notes and Bullet Points (Part 1)

Condensed notes on compilers: source language, lexical analysis, symbol tables, and the structure of a compiler — part one of a series.

A compiler is a translator from one language, the input or source language, to another language, the output or target language.

A compiler program written in a high-level language is called the source language.

A loader is a program that places programs into memory and prepares them for execution.

Preprocessors are normally fairly simple, as in the C language, providing primarily the ability to include files and expand macros.

Assembly code is a mnemonic version of machine code, in which names — rather than binary values — are used for machine instructions and memory addresses.

An assembler needs to assign memory locations to symbols (called identifiers) and use the numeric location address in the target machine language produced.

The conceptually simplest way to avoid conflicts among identifiers and their addresses is to make two passes over the input. During the first pass, each time a new identifier is encountered, an address is assigned, and the pair (identifier, address) is stored in a symbol table. During the second pass, whenever an identifier is encountered, its address is looked up in the symbol table, and this value is used in the generated machine instruction.

The Structure of a Compiler

  1. Lexical Analysis (or Scanning)
  2. Syntax Analysis (or Parsing)
  3. Semantic Analysis
  4. Intermediate code generation
  5. Code optimization
  6. Code generation
  7. Symbol-Table Management
  8. The Grouping of Phases into Passes

The first phase of a compiler is lexical analysis, also known as linear analysis, in which the stream of characters making up the source program is read left to right and grouped into tokens — sequences of characters having a collective meaning.

The main task of a lexical analyzer is to take a token sequence from the scanner and verify that it is a syntactically correct program. Secondary tasks include processing declarations and setting up symbol table information accordingly, in preparation for semantic analysis. It also constructs a syntax tree in preparation for intermediate code generation.

A lexeme is a sequence of characters in the source program that is matched by the pattern for a token.

A language denoted by a regular expression is said to be a regular set.

A sentinel is a special character that cannot be part of the source program. Normally, we use EOF as the sentinel — this speeds up the lexical analyzer.

Error-recovery actions in a lexical analyzer:

  • Deleting an extraneous character
  • Inserting a missing character
  • Replacing an incorrect character with a correct character
  • Transposing two adjacent characters

Recognizers are machines that accept strings belonging to a certain language. If the valid strings of that language are accepted, the corresponding language is said to be accepted by that machine; otherwise, it is rejected.

A compiler produces a target program, whereas an interpreter performs the operations implied by the source program directly.

A buffer pair is a specialized buffering technique used to reduce the overhead of processing an input character. The buffer is divided into two N-character halves, using two pointers. It's used when the lexical analyzer needs to look ahead several characters beyond the lexeme for a pattern before a match is announced.

Tokens are sequences of characters that have a collective meaning.

There is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern, associated with the token.

Operations on languages:

  • Union: L ∪ M = {s | s is in L or s is in M}
  • Concatenation: LM = {st | s is in L and t is in M}
  • Kleene Closure: L* (zero or more concatenations of L)
  • Positive Closure: L+ (one or more concatenations of L)

Regular expression for an identifier: letter (letter | digit)*

Hierarchical analysis, or parsing, is the process in which tokens are grouped hierarchically into nested collections with collective meaning.

In semantic analysis, certain checks are performed to ensure that components of a program fit together meaningfully — it mainly performs type checking.

← All writing