Introduction
A compiler reads a program in a source language and translates it into an equivalent program in a target language, reporting the errors it finds in the source. An interpreter instead executes the source operations directly on the inputs, without producing a separate target program. A compiled target program usually runs faster; an interpreter usually gives better error diagnostics, because it executes the source statement by statement.
Every question in this subject is about one stage of the translation: what the lexical analyser emits, which grammars a parser accepts, what attributes a translation computes, how a procedure call is laid out in memory, which intermediate code is generated, and what an optimiser may change. This note fixes the vocabulary and the order of the stages, so that each later note can say exactly where it sits.
Prerequisites
- Familiarity with a C-like language: declarations, expressions, assignments and statements.
- No other note is required. Regular expressions and context-free grammars appear here only as the formal tools of the first two phases.
Core concepts
The language-processing system
A source program passes through several programs before it runs.
| Program | Input | Output | Typical job |
|---|---|---|---|
| Preprocessor | Source with directives | Pure source | Macro expansion, file inclusion, conditional compilation |
| Compiler | Source program | Assembly (or machine) code | All the phases below |
| Assembler | Assembly code | Relocatable machine code | Translate mnemonics, build object file |
| Linker | Object files and libraries | Executable file | Resolve external references, combine code |
| Loader | Executable file | Program in memory | Place code and data in memory for execution |
The C preprocessor is covered in The C Preprocessor. In C translation phases, source text is first decomposed into preprocessing tokens; macro expansion operates on those tokens. Expanded preprocessing tokens are subsequently converted into language tokens for compilation. Macro expansion precedes analysis by the compiler proper, not preprocessing-token formation.
Analysis and synthesis
The compiler has two parts.
- Analysis (front end). Breaks the source into pieces, imposes grammatical structure, checks it, and builds an intermediate representation and the symbol table. It depends on the source language and is largely independent of the target machine.
- Synthesis (back end). Builds the target program from the intermediate representation and the symbol table. It depends on the target machine and is largely independent of the source language.
A machine-independent optimiser may sit between them. Separating the two halves through a common intermediate representation means that source languages and target machines need front ends and back ends, components, instead of complete compilers.
The phases
| Phase | Input | Output | Formal tool |
|---|---|---|---|
| Lexical analysis (scanning) | Character stream | Token stream | Regular expressions, finite automata |
| Syntax analysis (parsing) | Token stream | Parse tree or syntax tree | Context-free grammars, pushdown automata |
| Semantic analysis | Syntax tree | Annotated (type-checked) syntax tree | Attribute rules, type systems |
| Intermediate code generation | Annotated tree | Intermediate code, for example three-address code | Syntax-directed translation |
| Machine-independent optimisation | Intermediate code | Improved intermediate code | Data-flow analysis |
| Code generation | Intermediate code | Target code | Instruction selection, register allocation |
| Machine-dependent optimisation | Target code | Improved target code | Peephole optimisation |
Two components serve every phase:
- Symbol table. One record per name (variable, function, type) with its attributes: type, storage location, scope, and for procedures the number and types of arguments and the return type. Lexical analysis may enter a name; later phases add attributes and look names up. It is usually a hash table, with one table per scope or a chain of scopes.
- Error handler. Each phase reports the errors it can detect and, where possible, recovers so that analysis can continue.
Phases versus passes. A phase is a logical stage; a pass is one reading of a representation of the whole program. Several phases can be grouped in one pass (a one-pass compiler interleaves lexing, parsing, checking and code emission, driven by the parser). The number of passes is an implementation decision, not part of the definition of the phases.
How it works
One statement through every phase
Take the assignment
total = base + rate * 4where total, base and rate are declared as floating-point variables and 4 is an integer constant.
Lexical analysis. The scanner groups characters into lexemes and emits one token per lexeme. Blanks are discarded. Identifiers are entered in the symbol table (entries 1, 2, 3).
<id,1> <=> <id,2> <+> <id,3> <*> <num,4>That is 7 tokens: three identifiers, the operators =, + and *, and one number. The symbol table now holds 3 names.
Syntax analysis. The parser builds a tree in which * is below + (higher precedence) and = is at the root, because the grammar for expressions encodes precedence by levels.
Semantic analysis. The type checker sees float * int and inserts a conversion, so the right operand of * becomes inttofloat(4). Undeclared names, type mismatches and wrong argument counts are reported here.
Intermediate code generation. A post-order walk of the checked tree emits three-address code, one operator per instruction, with compiler temporaries t1, t2, t3:
t1 = inttofloat(4)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3That is 4 instructions.
Optimisation. The conversion of a constant can be done at compile time (4 becomes 4.0), and the final copy can be absorbed into the instruction that computes t3. The result has 2 instructions:
t1 = id3 * 4.0
id1 = id2 + t1Code generation. Each instruction becomes a load, an operation or a store on the target machine, with registers assigned to the values that are used.
Why the lexical analyser is a separate phase
- Simpler design. The parser works on tokens, so its grammar never mentions blanks, comments or the spelling of identifiers.
- Efficiency. Reading characters is the most time-consuming part of the front end; a specialised scanner with input buffering makes it fast.
- Portability. Device-specific input peculiarities are confined to the scanner.
The scanner usually runs as a subroutine of the parser: each time the parser needs the next token it calls the scanner, which reads just enough characters to return one token.
Important properties and observations
Which phase detects which error
| Error | Phase that detects it | Why |
|---|---|---|
A character that cannot start any token, for example @ in C outside strings and comments | Lexical | No pattern matches |
| Unterminated string literal or comment | Lexical | The lexeme never ends |
Missing semicolon, unbalanced parentheses, else without if | Syntax | Token sequence not in the grammar |
Undeclared variable, type mismatch, wrong number of arguments, break outside any enclosing loop or switch | Semantic | Conventionally checked in semantic analysis using enclosing-statement context; a larger CFG can enforce break placement |
| Division by zero with run-time values, array index out of bounds | Run time | Values unknown at compile time |
Misspelt keyword versus lexical error. In whlie (x) y = 1; the scanner reports nothing: whlie is a perfectly good identifier. The parser then sees whlie (x) as a function call followed by y with no operator or semicolon between them, which is a syntax error. A misspelling that still parses, such as whlie (x);, is caught only by semantic analysis as a call to an undeclared function. A lexical error needs characters that no token pattern can match.
Declaration before use is semantic. The language "every identifier is declared before it is used" is not context-free, so the parser cannot enforce it; semantic analysis does, using the symbol table.
Front end versus back end
| Question | Front end | Back end |
|---|---|---|
| Depends mainly on | Source language | Target machine |
| Phases | Lexical, syntax, semantic analysis, intermediate code generation | Code generation, machine-dependent optimisation |
| Creates | Symbol table entries, intermediate code | Target code, register assignment |
Machine-independent optimisation works on intermediate code and is often placed with neither or with both, depending on the textbook. Questions that ask which phase is "machine independent" expect lexical, syntax and semantic analysis, intermediate code generation and machine-independent optimisation.
Compiler-construction tools
| Tool | Builds | From |
|---|---|---|
| Scanner generator (Lex, Flex) | Lexical analyser | Regular-expression patterns with actions |
| Parser generator (Yacc, Bison) | Syntax analyser, LALR(1) | Grammar with semantic actions |
| Syntax-directed translation engine | Intermediate code | Attribute rules attached to the parse tree |
| Code-generator generator | Code generator | Rules mapping intermediate operations to machine instructions |
| Data-flow analysis engine | Optimiser analyses | Transfer functions and meet operators |
Related material. A cross-compiler runs on one machine and produces code for another. Bootstrapping writes a compiler for a language in that same language, then compiles it with an earlier compiler. Just-in-time compilers translate intermediate code (for example bytecode) to machine code during execution. These terms appear in general questions but are not named in the syllabus.
GATE examination perspective
- Order of phases. Lexical, syntax, semantic, intermediate code, optimisation, code generation. A question that lists them in another order usually swaps semantic analysis and intermediate code generation, or places optimisation after code generation only.
- Output of each phase. Tokens; parse or syntax tree; annotated tree; three-address code; improved three-address code; target code. Match the output to the phase, not the tool.
- Which tool or automaton. Lexical analysis uses regular expressions and DFAs; parsing uses context-free grammars and the stack of a pushdown automaton; type checking uses the symbol table and attribute rules.
- Error classification. Undeclared identifiers and type errors are semantic; misspelt keywords are usually not lexical; illegal characters and unterminated literals are lexical.
- Token counting. Counted after the preprocessor and before parsing; comments and whitespace produce no tokens. The note Lexical Analysis gives the full rules and traps.
- Symbol table. Created and filled across phases, used by all of them; its typical implementation is a hash table.
- Passes. One pass can contain several phases. A single-pass compiler needs declarations before use, or backpatching for forward jumps.
Summary
Sources
- A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers, Principles, Techniques, and Tools, 2nd ed., Pearson Addison-Wesley, 2007: Section 1.1 (language processors), Section 1.2 (the structure of a compiler: the phases, symbol-table management, grouping of phases into passes, compiler-construction tools), Section 3.1.1 (lexical analysis versus parsing).