Compiler Design Fundamentals

This cheat sheet covers core concepts in compiler design, including lexical analysis, parsing, syntax-directed translation, intermediate code generation, and runtime environments. It highlights key definitions, processes, and data structures essential for understanding how source code is transformed into executable programs.

Core Principles

Lexical analysis identifies tokens (lexemes) from source code.
Parsing checks grammatical structure using CFGs and builds parse trees or ASTs.
Syntax-directed translation attaches semantic rules to grammar productions.
Intermediate code generation creates machine-independent representations.
Code optimization improves intermediate code for efficiency.
Code generation translates optimized code into target machine code.
Symbol tables store identifier information throughout compilation.
Runtime environments manage procedure calls and local variables via activation records.

Key Terms

Lexeme: A sequence of characters in the source program that matches a pattern for a token; the actual string forming a token.
Token: A category representing a lexeme (e.g., keyword, identifier, operator).
Finite Automaton (FA): A mathematical model/state machine used in lexical analysis to recognize tokens (patterns).
Context-Free Grammar (CFG): A formal grammar where production rules are of the form A → α, used for syntax analysis.
Ambiguity: A grammar is ambiguous if a string has more than one parse tree or derivation.
Left Recursion: A grammar where a non-terminal A derives a string starting with A itself; problematic for LL parsers.
Activation Record (Stack Frame): A block of memory on the runtime stack for a procedure call, storing necessary information.
Symbol Table: A data structure used to store and manage information about identifiers.
Directed Acyclic Graph (DAG): A data structure representing intermediate code where common subexpressions are shared.
Basic Block: A maximal sequence of consecutive three-address statements with single entry and exit points.

Timeline

Early 1950s: First compilers developed (e.g., FORTRAN).
Late 1950s - 1960s: Development of parsing techniques (e.g., LL, LR parsers) and formal grammars (e.g., Chomsky hierarchy).
1970s: Introduction of intermediate representations like three-address code and optimization techniques.
1980s: Rise of compiler construction tools like LEX and YACC, enabling easier parser generation.
1990s - Present: Focus on advanced optimization, parallel compilation, domain-specific compilers, and Just-In-Time (JIT) compilation.