Compiler Construction
Compiler construction is the engineering discipline of building compilers — programs that translate source code written in high-level programming languages into executable machine code or intermediate representations. The field divides the compilation process into phases: lexical analysis (tokenization), syntax analysis (parsing), semantic analysis (type checking and scope resolution), intermediate code generation, optimization, and target code generation. Each phase transforms the program representation while preserving its meaning, and the composition of these phases produces a translation pipeline that is one of the most complex software systems routinely built by humans.
The field was founded by the ALGOL project, which demonstrated that programming language translation could be systematic rather than ad hoc. The development of Backus-Naur form and formal parsing algorithms (LL, LR, LALR) in the 1960s provided the theoretical foundation for automated parser construction, and parser generators like Yacc and Bison became standard tools. Modern compiler construction, however, extends far beyond parsing: it encompasses static analysis, optimization passes that transform code for performance, and the management of complex runtime systems including garbage collection, exception handling, and concurrency.
The gap between theory and practice in compiler construction remains wide. The formal methods of parsing are well-understood, but the semantic analysis phase — type checking, name resolution, overload resolution — is typically implemented with ad hoc logic that is hard to verify. The optimization phase operates on heuristics and profiling data rather than formal guarantees. And the target code generation phase must contend with the quirks of real hardware, from instruction scheduling to memory hierarchy effects. The compiler is a formal system in its front end and a craft in its back end.
Compiler construction is the oldest branch of software engineering and the one that has most stubbornly resisted formalization. We can prove that a parser recognizes a grammar, but we cannot prove that a compiler preserves the meaning of the programs it translates. The gap between "parses correctly" and "translates correctly" is the gap between syntax and semantics, and it is the same gap that separates a proof from a program in the Calculus of Constructions. The compiler writer's dream — a verified compiler, a translation pipeline with formal guarantees — has been realized only for toy languages. The real languages we use every day remain translated by systems that are correct by testing, not by proof.