Compilers translate source programs into lower-level code while preserving meaning and improving efficiency. This cheat sheet summarizes the main stages of language implementation, from scanning characters to optimizing intermediate code. College students need these ideas to understand programming language design, compiler construction, interpreters, and performance tools.
The stages are often taught separately, but real compilers connect them through shared data structures and error handling.
Key Facts
- A typical compiler pipeline is source code -> lexer -> parser -> AST -> semantic analyzer -> IR -> optimizer -> code generator.
- Lexing groups characters into tokens using regular expressions, such as identifier = letter (letter or digit)*.
- A context-free grammar production has the form Nonterminal -> symbols, such as Expr -> Expr + Term | Term.
- An abstract syntax tree stores the essential structure of a program while removing punctuation and grammar-only details.
- Semantic analysis checks meaning, including type rules such as if x has type int and y has type int, then x + y has type int.
- Three-address code commonly has the form x = y op z, x = op y, x = y, goto L, or if x relop y goto L.
- Control-flow graphs represent basic blocks as nodes and possible jumps between blocks as directed edges.
- Constant folding replaces expressions known at compile time, such as x = 3 * 4 becoming x = 12.
Vocabulary
- Lexer
- A lexer scans source characters and groups them into tokens such as identifiers, keywords, operators, and literals.
- Parser
- A parser checks whether tokens match the grammar of the language and builds a parse tree or abstract syntax tree.
- Abstract Syntax Tree
- An abstract syntax tree is a simplified tree representation of a program's syntactic structure.
- Symbol Table
- A symbol table records information about names in a program, including variables, functions, scopes, and types.
- Intermediate Representation
- An intermediate representation is a compiler-internal program form designed to be easier to analyze and transform than source code.
- Optimization Pass
- An optimization pass is a compiler transformation that improves code speed, size, or resource use while preserving program behavior.
Common Mistakes to Avoid
- Confusing lexing with parsing is wrong because lexing recognizes token patterns, while parsing recognizes grammatical structure among tokens.
- Keeping every parse tree detail in the AST is wrong because an AST should remove unnecessary punctuation and grammar artifacts while preserving program meaning.
- Ignoring scope when building a symbol table is wrong because the same name can legally refer to different declarations in different blocks or functions.
- Applying an optimization without proving behavior is preserved is wrong because transformations must not change observable program output, exceptions, or required side effects.
- Assuming all errors can be caught by the parser is wrong because many errors, such as undeclared variables or type mismatches, require semantic analysis.
Practice Questions
- 1 Given the source line total = count + 42;, list a reasonable token sequence produced by the lexer.
- 2 For the grammar Expr -> Expr + Term | Term and Term -> number, draw or describe the AST for 2 + 3 + 4.
- 3 Convert the expression a = (b + c) * d into three-address code using temporary variables.
- 4 Why is an intermediate representation useful even when a compiler could theoretically translate source code directly to machine code?