Introduction to Compilers

Learning Objectives

• Define what a compiler is and contrast it with an interpreter
• List the six major phases of a compiler in the correct order
• Explain what each phase receives as input and produces as output
• Identify tokens produced by lexical analysis in a code snippet
• Articulate why studying compiler design improves programming and systems thinking

Quick Answer

A compiler is a program that translates source code written in a high-level language — such as C or Java — into machine code that a processor can execute directly. The translation happens in six sequential phases: lexical analysis turns characters into tokens, syntax analysis checks grammar and builds a parse tree, semantic analysis verifies types and scope, intermediate code generation produces a platform-independent form, optimization improves efficiency, and code emission outputs the final machine instructions. Each phase specializes in one job, making the overall system modular and easier to debug.

What is a Compiler?

A compiler is a program that translates source code written in a high-level programming language (like Python or Java) into machine code that can be executed directly by the computer's processor. In other words, it converts human-readable code into binary instructions that the computer understands.

Key Components of a Compiler

1. Lexical Analyzer (Scanner):

   • Reads the source code character by character
   • Identifies tokens (keywords, identifiers, symbols)
   • Outputs a sequence of tokens

2. Syntax Analyzer (Parser):

   • Analyzes the stream of tokens produced by the lexical analyzer
   • Checks if the input adheres to the rules of the programming language
   • Constructs a parse tree representing the syntactic structure of the program

3. Semantic Analyzer:

   • Performs type checking and scoping
   • Ensures that the program satisfies semantic constraints

4. Intermediate Code Generator:

   • Translates the parse tree into intermediate code
   • May produce assembly code or low-level machine code

5. Optimizing Code Generator:

   • Improves the efficiency of the generated code
   • May involve techniques like dead code elimination, constant propagation, etc.

6. Code Emitter:

   • Converts the optimized intermediate code into machine code
   • Generates object code or executable files

Why Study Compiler Design?

Understanding compiler design is crucial for several reasons:

1. It helps in developing more efficient programs
2. It improves code optimization skills
3. It enhances problem-solving abilities in programming
4. It opens doors to advanced topics in computer science

Basic Concepts in Compiler Design

Lexical Analysis

Lexical analysis is the process of breaking down the source code into individual tokens. Here's a simple example:

Consider the following source code:

int x = 5;

The lexical analyzer would break this code into tokens like:

• int: Keyword
• x: Identifier
• =: Operator
• 5: Constant
• ;: Symbol

Key Terms

Term	Definition	Related Concept
Compiler	Program that translates source code to machine code	Interpreter
Lexical Analysis	Breaking source text into tokens	Scanner
Token	Smallest meaningful unit (keyword, identifier, symbol)	Lexeme
Syntax Analysis	Checking grammatical structure of token streams	Parser
Parse Tree	Tree showing grammatical structure of a program	Abstract Syntax Tree
Semantic Analysis	Verifying meaning, types, and variable scope	Symbol table
Intermediate Code	Platform-independent representation between source and machine code	IR
Code Optimization	Techniques to make generated code run faster or use less memory	Dead code elimination

Common Mistakes

Misconception: A compiler and an interpreter do the same thing. Why it's wrong: A compiler translates the entire program into machine code before any execution. An interpreter reads and executes source code line by line without producing a standalone executable. Correct understanding: Compilers produce output files you can run repeatedly. Interpreters execute immediately but must re-process source on every run.

---

Misconception: Lexical analysis is the same as syntax analysis. Why it's wrong: Lexical analysis only identifies individual tokens — it does not check whether those tokens are arranged correctly. Syntax analysis is the phase that validates token order against grammar rules. Correct understanding: Lexical analysis says "these characters form a keyword," while syntax analysis says "this keyword appears where the grammar allows it."

---

Misconception: Optimization always makes a program correct. Why it's wrong: Optimization assumes the program is already correct and only changes how efficiently it runs. A logically wrong program produces wrong results whether optimized or not. Correct understanding: Optimization transforms correct code to run more efficiently — it never fixes bugs.

Comparison and Connections

Phase	Input	Output	Key Task
Lexical Analysis	Source characters	Token stream	Tokenization
Syntax Analysis	Token stream	Parse tree	Grammar checking
Semantic Analysis	Parse tree	Annotated tree	Type and scope checking
IR Generation	Annotated tree	Intermediate code	Platform-neutral translation
Optimization	Intermediate code	Optimized IR	Efficiency improvements
Code Emission	Optimized IR	Machine code	Final output

Practice Questions

Recall

1. What are the six phases of a compiler in order? Answer guidance: Lexical analysis, syntax analysis, semantic analysis, IR generation, optimization, code emission. Each feeds the next.

2. What does the lexical analyzer output? Answer guidance: A stream of tokens — categories like keyword, identifier, operator, literal, and symbol.

Understanding

3. Why is the compiler organized into separate phases rather than one big transformation? Answer guidance: Separation of concerns — each phase has a single responsibility, making the design easier to test, debug, and extend. Errors are also caught as early as possible.

4. Why does semantic analysis follow syntax analysis rather than preceding it? Answer guidance: You cannot check type compatibility until you know the grammatical structure of expressions. Syntax builds the tree that semantic analysis annotates.

Application

5. Tokenize this line: float result = x + 2.5; Answer guidance: float (keyword), result (identifier), = (operator), x (identifier), + (operator), 2.5 (literal), ; (symbol). Seven tokens.

6. A compiler reports "undeclared variable." Which phase detected this? Answer guidance: Semantic analysis, specifically scope resolution in the symbol table. Lexical and syntax phases do not track variable declarations.

Analysis

7. Compare how a compiler and an interpreter handle a program with a syntax error on line 50. Answer guidance: A compiler reports the error before running anything. An interpreter executes lines 1-49 successfully before hitting the error — potentially causing side effects.

8. Why might an optimized program produce different timing but identical output compared to the unoptimized version? Answer guidance: Optimization changes instruction order, register use, and redundant operations but must preserve observable behavior. Identical output with different performance is the goal.

FAQ

Why do we need an intermediate representation at all? The intermediate representation decouples the front-end (which understands the source language) from the back-end (which understands the target hardware). By targeting IR from the front end, one compiler can support multiple target architectures by only changing the back end. This is why LLVM, for example, powers compilers for C, Rust, Swift, and many other languages simultaneously.

What is a symbol table and why is it important? A symbol table is a data structure maintained throughout compilation that records every identifier — variables, functions, classes — along with their types, scope, and memory location. Semantic analysis adds entries and looks them up to verify that variables are declared before use and that types are compatible. Without the symbol table, the compiler would have no memory of what x meant three lines above.

Can a program compile successfully but still crash at runtime? Yes. Compilation only catches static errors — those that can be detected from the program text alone. Runtime errors like dividing by zero, accessing an out-of-bounds array index, or dereferencing a null pointer are not detectable at compile time in most languages. This is why testing and runtime checks are still necessary even after compilation succeeds.

What is the difference between a one-pass and a multi-pass compiler? A one-pass compiler reads source code once and generates machine code directly, which is fast but limits optimization. A multi-pass compiler processes the code several times, each pass refining the result. Most modern compilers use multiple passes so they can apply aggressive optimizations that require global information about the whole program.

Why does Go compile so much faster than C++? Go's designers intentionally simplified the language to avoid compilation bottlenecks — no header files to repeatedly parse, simpler syntax, and explicit dependency management. C++ requires enormous amounts of template instantiation and header inclusion that the compiler must resolve for every translation unit. Language design decisions made decades before runtime have direct consequences on how quickly the compiler can do its job.

Quick Revision

• A compiler translates source code to machine code; an interpreter executes source code directly
• The six compiler phases are: lexical analysis, syntax analysis, semantic analysis, IR generation, optimization, code emission
• The lexical analyzer produces tokens; the parser produces parse trees
• Semantic analysis checks types, scope, and meaning using a symbol table
• The intermediate representation is platform-independent and enables multi-target compilation
• Optimization techniques include dead code elimination, constant propagation, and register allocation
• Syntax errors are caught in the syntax analysis phase; type errors in semantic analysis
• A single front-end targeting IR can support multiple target architectures

Related Topics

Prerequisites: Finite automata, regular expressions, context-free grammars, basic data structures

Related Topics: Formal language theory, programming language design, operating systems

Next Topics: Advanced parsing (LALR, Earley), LLVM architecture, interpreter design, just-in-time compilation