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?
Understanding Compilers and Language Implementation
A compiler must keep track of where every piece of source text came from. Tokens and later tree nodes usually carry a source location. This lets the compiler point to the right line when it reports an error.
Good error messages need more than saying that a rule failed. They should explain what the compiler expected, show the relevant location, and continue far enough to find other mistakes. Error recovery matters in editors because students expect warnings while they are still typing incomplete code.
Lexers must handle details such as comments, escape sequences in strings, and the rule that a keyword like while is not treated as an ordinary name. Parsers must resolve precedence and associativity so that multiplication groups before addition and repeated subtraction groups in the intended direction.
Meaning depends on context, not just on the shape of an expression. A name can refer to different variables in different blocks. The compiler uses symbol tables to connect each use of a name to its declaration.
Scope rules prevent an inner variable from accidentally changing an unrelated outer variable. Type checking catches cases where an operation has no valid meaning, such as using a text value where a numeric index is required. Some languages infer types from assignments and function calls.
Others require explicit declarations. More advanced checks track whether a variable was initialized before use, whether every function path returns a value, and whether private data is accessed legally. These checks are why two programs that look structurally similar can be accepted or rejected for different reasons.
Intermediate forms make later work less tied to the original programming language or the target processor. A compiler may turn a complex expression into small temporary steps, then divide code into blocks that run straight through without a jump in the middle. The connections between blocks reveal branches, loops, and unreachable code.
This structure supports analyses such as finding which values are still needed at each point. That information helps the compiler reuse processor registers instead of repeatedly storing values in memory. A common design gives each temporary value one definition.
This makes it easier to trace where a value came from, especially after branches join. The compiler may insert special merge values at those joins so later passes can reason about each possible path.
Optimization is constrained by program behavior. Replacing a calculation with a known result is safe only when the original calculation has no required side effect. A function call might print text, change a file, update shared memory, or throw an exception.
Removing it would change the program even if its returned value is unused. Floating point arithmetic needs extra care because changing the order of calculations can slightly change rounding. Debug builds often use fewer transformations so that breakpoints and variable displays remain understandable.
In real life, these ideas appear in code editors, browser JavaScript engines, mobile apps, database query planners, and security tools that inspect programs. When learning this topic, follow one small program through each representation. Pay attention to what information is added, removed, or preserved at every step.