Compiler Construction Principles And Practice

Building a Compiler Actually Works Like Building a Pipeline

I spent a solid summer in grad school writing a compiler for a subset of C. I expected it to be this towering intellectual challenge. It turned out to mostly be a series of increasingly annoying edge cases strung together with enough data structures to make you regret not using a library. Compiler Construction Principles And Practice isn't about memorizing algorithms. It is about understanding how data flows through each stage and making sure whatever comes out of stage three looks like exactly what stage four expects. If that mapping breaks anywhere, everything downstream breaks with it. This is where most people lose their minds. The pipeline has five stages you need to get right. Lexical analysis, parsing, semantic analysis, intermediate code generation, and optimization plus code generation. Each one transforms an input representation into something more useful. The lexifier turns characters into tokens. The parser turns tokens into a tree. The semantic analyzer checks whether the tree makes sense. The backend turns it into machine code or bytecode.

Here is the thing nobody tells you. The parser is not the hard part. The hard part is everything around it. Getting a recursive descent parser to handle left recursion is well documented and you will find plenty of examples online. But handling error recovery without corrupting your AST? That is where the real work starts. And debugging your code generator when it silently produces wrong assembly instead of crashing? Forget about it.

How the Lexical Analysis Stage Actually Works

Tokenization seems trivial until your language has multiline string literals with escape sequences. Then it is not trivial at all. I built a lexer using a hand-rolled finite state machine because I wanted the control. It handled keywords, identifiers, numbers, operators, and comments. The moment I needed to support interpolated strings, the FSM approach became unmaintainable and I had to rewrite three hundred lines of lexer code over a weekend. The standard approach for tokenization uses regular expressions compiled into a DFA. Flex is the tool everyone references. It generates efficient tokenizers that can process a megabyte of source in milliseconds on modern hardware. If you are building a production compiler, use a lexer generator. Do not write one by hand unless you are teaching yourself the mechanics. One thing that comes up constantly and nobody warns you about is lookahead. Your lexer needs to know when a token ends. With most languages this is obvious because whitespace or punctuation terminates tokens. But what happens when your language allows ambiguous sequences like == vs = followed by =? You need a tokenizer that can look ahead by at least two characters. If you ever find yourself writing look-ahead logic that goes past four characters, step back and reconsider whether your grammar is the problem instead of your lexer.

Parsing Is Where Things Get Real

There are two main camps. Hand-written recursive descent parsers and parser generators that produce tables. Recursive descent gives you full control and readable error messages. Table-driven parsers like those produced by Yacc, Bison, or ANTLR are faster to build but error recovery is significantly worse. I have seen production compilers switch from hand-written to table-driven and immediately regret it when users started filing bug reports about cryptic parse errors on valid code. The grammar you write for your parser has to be unambiguous. Any grammar that produces parse conflicts is broken and will fail unpredictably. Left recursion is the classic problem. A rule like expr -> expr + term will cause an infinite loop in a recursive descent parser. You rewrite it as expr -> term {+ term} to handle it. This transformation is mechanically routine but the first time you do it manually you will question your life choices. Semitop-down parsers like Pratt parsers deserve more attention than they get. They handle operator precedence natively without the grammar gymnastics that top-down LL parsers require. I switched my compiler project to a Pratt parsing approach for expressions and cut the expression grammar rules from roughly forty to about twelve. The precedence handling became transparent. If you are writing a parser for anything with complex expressions, look into Pratt parsing before you waste days untangling left-recursion workarounds.

Common Pitfalls Nobody Mentions

The AST you build during parsing should be as simple as possible. I made the mistake of encoding type information directly into my early AST nodes. This meant I had to update the AST in three different passes and any inconsistency between passes was a silent bug. Once I separated the AST from semantic annotations and kept type information in a parallel symbol table, the whole backend became dramatically simpler. Keep your parse tree pure. Do not embed semantics in it. Another thing that catches people. Your error messages need to come from multiple stages simultaneously. A parse error alone tells the user nothing useful if the actual problem was a missing semicolon two hundred lines earlier that shifted every token after it. I ended up implementing a panic mode recovery strategy in my parser where it would consume tokens until it found a synchronization point. Combined with error tokens that propagated through semantic analysis, this reduced useless error cascades by about eighty percent in my testing.

Semantic Analysis and the Symbol Table

This is where you figure out if the code actually means something. Type checking, scope resolution, name binding. The symbol table is the data structure that tracks every identifier in the program and its properties. Scope nesting means your symbol table needs to support lookups that search outward through enclosing scopes. A hash map per scope stacked together works fine for most languages. One counter-intuitive detail. Name overloading requires a symbol table that stores not just names but signatures. If your language allows function overloading, your symbol table entry for a name must be a list of candidate declarations, not a single pointer. Resolving the correct overload happens during name binding and requires type information that may not be fully available until later passes. This creates a dependency ordering problem that many introductory treatments skip over entirely. I ran into a specific issue with module visibility that took me three days to track down. My compiler supported packages with selective imports like import math.{sqrt, pi}. The symbol table was resolving names correctly but the generated code was referencing private members that should have been inaccessible. The bug was in my scope analysis pass where I was merging imported symbols into the local scope too eagerly. The fix was to keep imported symbols in a separate namespace within each scope and only resolve them during name binding rather than during scope construction. Once I made that change, the visibility errors disappeared and the compiler correctly rejected code that tried to access module internals.

Intermediate Representations Matter More Than You Think

Writing a code generator directly from the AST is possible for simple languages. For anything with meaningful optimization requirements you need an intermediate representation. Three-address code is the most common starting point. Each instruction has at most three operands, usually in the form x = y op z or x = op y. It is simple enough to generate mechanically and structured enough to optimize effectively. SSA form is the industry standard IR for optimization passes. Variables get a single assignment, with phi functions handling merges at control flow join points. Getting SSA construction right is nontrivial. The standard algorithm uses a dominance frontier computation to place phi functions, and the naive implementation has quadratic complexity in the number of blocks. I implemented the efficient version using a worklist algorithm and a reverse postorder traversal, and it cut my SSA construction time from several seconds per function to under fifty milliseconds for typical code sizes. Here is an uncomfortable truth about optimization. Most programs do not benefit from aggressive optimization in a compiler you are building for learning or small-scale use. Constant folding, dead code elimination, and strength reduction will give you measurable improvements on benchmark code but the average program your compiler sees will run within five to ten percent of optimal even with a naive code generator. Don't spend months building a sophisticated optimizer before you have a working backend that produces correct code. Getting the code right comes first. Optimizing comes later if it matters.

Code Generation Is Just Assignment with Extra Steps

Once you have a good IR, code generation is mostly about register allocation and instruction selection. The register allocation problem is NP-complete in the general case. Graph coloring is the standard approach. Build a register interference graph where nodes represent live ranges and edges connect ranges that overlap. Color the graph with as many colors as you have physical registers. If you cannot color it, spill the least costly range to memory. I spent about a week implementing a linear scan register allocator instead of graph coloring because it is simpler and runs in linear time. It is not optimal but for a compiler project it produces code that is usually within twenty percent of what graph coloring would produce, and the implementation is a fraction of the complexity. If you are building a learning compiler, use linear scan. If you are building something that needs to compete with production compilers, use graph coloring and spend the time it deserves. The instruction selection pass maps IR instructions to target machine instructions. This is often implemented as pattern matching on the IR using a tree pattern matcher. You define patterns for each machine instruction and match them against your IR tree. The goal is to select the cheapest instruction sequence that produces the correct result. This is where platform-specific knowledge matters. Your compiler needs to know whether the target architecture has a multiply instruction, whether it supports conditional moves, and what the calling convention looks like. Each of these decisions affects code quality significantly.

The Specific Problem That Nearly Broke My Compiler

My code generator was producing correct assembly for simple functions but generating segfaults on any function that used more than eight registers. The problem was in my prologue and epilogue generation. I was saving and restoring callee-saved registers but I had misidentified which registers on the target architecture were actually callee-saved. The x86-64 calling convention designates RBP, RBX, R12 through R15 as callee-saved. My reference documentation had listed them differently, and I copied the wrong table. Functions with few register pressure never triggered the bug because they never needed to spill to those registers. Only complex functions with high register demand exposed the corruption. The fix was straightforward once I found it. I rewrote the prologue generator to emit explicit register save sequences based on liveness analysis rather than assuming a fixed set of callee-saved registers. This made the code generator correct for all function sizes, not just small ones. It also added about two hundred lines of code and two days of debugging that I will never get back.

What You Should Actually Build

If you want to learn compiler construction, build a compiler for a language that is slightly smaller than you think you need. A functional language with pattern matching and higher-order functions teaches you more about semantics and code generation than a C-like language with complex type systems. The syntax is simpler so you spend less time on parsing and more time on the parts that matter. A minimal ML-like language with let bindings, functions, integers, and pairs is a sufficient target. Your compiler should target an intermediate representation rather than raw machine code. WebAssembly is a reasonable target because it is stack-based, has a simple instruction set, and runs everywhere. If you want to go deeper, target a fictional machine with a few registers, a stack, and basic arithmetic and jump instructions. It forces you to think about register allocation and calling conventions instead of relying on a complex target infrastructure. The complete pipeline from source to execution should work end to end. I tested mine by writing a factorial function, compiling it, running the output, and comparing the result against a reference implementation. Then I wrote a quicksort, compiled it, ran it on a random array, and verified the output. These tests caught more bugs than anything else in the development process. A compiler that compiles hello world but crashes on a sorting algorithm is not a compiler. It is a proof of concept that failed the proof.

Tools and Resources That Actually Help

Flex and Bison are the standard tools for lexing and parsing. ANTLR is better if you want a more modern parser generator with decent error recovery and a Java or Cbackend. Roslyn is worth studying if you want to understand how a production compiler is structured, even if you never use it directly. Dragon Book remains the theoretical reference but it is dense and not always the best starting point. "Engineering a Compiler" by Cooper and Torczon is more practical and covers the same material with better examples. For debugging, write a pretty printer for your AST and IR early. Being able to dump the intermediate representation in readable form saves hours of debugging compared to tracing through opaque data structures. Add a flag that prints each stage's output. Your future self will thank you when you need to figure out why a particular input is producing incorrect output. A final note on scope. The first version of any compiler is always worse than you think it will be. It will not optimize well. It will produce verbose code. It will have subtle bugs that only appear with specific input patterns. This is normal. A working compiler that handles a limited language correctly is far more valuable than an incomplete one that attempts to support everything. Get the basic pipeline working. Make it correct. Then make it better.