Skip to content
Search

Compiler

lastmod 2025-11-11created 2014-10-029 edits

A compiler is a program that translates a document written in one programming language into another programming language. The original document is called source code, and the output document is called object code. Object code is mostly output in a form that is easy for other programs or hardware to process, but in some cases it is translated into human-readable document files, image files, and so on. The process of translating source code into object code is called compiling (compile).

A compiler is distinguished from an interpreter, which reads a source program and outputs results immediately. However, since many modern interpreters perform compilation in real time with techniques such as JIT compilation, the technical distinction between compilers and interpreters is fading.

Source code is mostly compiled to produce an executable machine language program from a high-level language that is easy for people to understand. A compiler in the narrow sense mainly refers to a program that translates source code written in a high-level language into a low-level language (assembly language, machine language, etc.).

Categories

Tokenizer vs Lexer vs Parser vs ASTAST

A compiler converts source code into machine language.

In doing so, it goes through parsing -> optimization -> code generation -> linking.

During parsing, the source code passes through the Tokenizer, Lexer, and Parser in order; today we'll look at this part.

Tokenizer

As the name says, the Tokenizer tokenizes a piece of syntax.

Here a token means a unit of lexical analysis, defined as a meaningful unit such as a word, phrase, or string.

Tokens help represent elements structurally.

Lexer

The Lexer analyzes the meaning of the tokens split up by the Tokenizer.

The whole process of being split into meaningful units by the Tokenizer and having the meaning of the result analyzed by the Lexer is called Lexical Analyze.

Example

Let's take analyzing the command "return" as an example.

  1. In the word return, r, e, t, u, r, n each have no meaning on their own
  2. Through the Tokenizer it becomes the meaningful word return -> tokenization
  3. Through the Lexer, its meaning is analyzed: this token is a command to return something!
  4. The token is analyzed into something like {type: command, value: "return", child: []} and passed to the Parser

Parser

The Parser represents the Lexical Analyzed data structurally.

In this process it also verifies that the data is correct; all of this together is called Syntax Analyze.

If you actually plan to implement something using the Tokenizer, Lexer, and Parser concepts, I think it's good to implement it so that an Error is thrown when incorrect data is found where the Parser performs its task.

The result produced by the Parser is generated in the form of an AST (Abstract Syntax Tree).

AST (Abstract Syntax Tree)

As the name says, an AST is a data structure that represents the syntax analyzed through the above process as a tree.

You can think of it as a tree that turns the analyzed source into a structure the computer can understand.

Common misconceptions about compilers

Misconceptions about compiler optimization
Optimization gives you the optimal program?
  • Compilers do not aim to generate the optimal program, but to improve a simplified program.
  • Code size optimization is feasible, but execution time optimization is hard because of difficulty of measurement, lack of optimal substructure, inaccurate hardware models, and so on.
  • Unlike code size, execution time is hard to measure precisely, is affected by many factors, and has no optimal substructure. For example, even if you optimize two loops individually, optimizing the whole program may require merging the two loops. Also, optimization is hard because there is no accurate model of the target hardware. For example, goSLP generates globally optimal SLP-vectorized code, but because the hardware model is inaccurate, the generated program is not only non-optimal but can be slower than LLVM.
Misconceptions about branch prediction
Branch weights are used by the CPU's branch predictor?
  • On the x86 architecture, compilers do not generate branch hints.
  • Branch weights are used for the compiler's code block placement. (e.g. if a branch is likely, place the target block right below the current block to improve instruction cache locality)
  • Branch hints have recently become relevant again in Intel's Redwood Cove architecture, but compilers rarely generate such hints in practice.
Misconceptions about optimization levels
-O3 generates much faster code than -O2?
  • For Clang, the performance difference between -O2 and -O3 is not large; for GCC, -O2 is less aggressive than Clang's, so there is a slight difference.
  • -O3 barely considers code size, so instruction cache problems can occur.
  • It's best to check by benchmarking.
Misconceptions about Javascript interpreters and JIT compilers
Javascript interpreters JIT-compile at runtime because they can't know in advance which paths are hot?
  • Knowing the hot paths is not enough; type information is also needed.
  • Type information is only known at runtime, so the JIT compiler compiles code at runtime.
Misconceptions about the relationship between compilers and interpreters
If you have a compiler, you don't need an interpreter?
  • For C/C++ interpreters aren't useful, but in cases like WebAssembly, interpreters can offer benefits such as ease of development and use, debugging, and security.
Misconceptions about the compiler middle stage
The middle stage (middle-end) is target/platform independent?
  • In LLVM, the middle stage is not completely target/platform independent.
Misconceptions about data locality optimization
Compilers optimize data locality?
  • Compilers optimize instruction cache locality, but rarely optimize data locality.
  • Data locality optimization requires large-scale changes to code, and C/C++ compilers cannot make such changes.
  • To improve data locality, you need techniques such as data-oriented design.
Misconceptions about compilation speed
-O0 gives fast compilation?
  • -O0 generates debuggable and predictable code, but does not always guarantee fast compilation.
  • -O0 is generally faster than -O2, but it can vary with project size and compiler.
  • For fast compilation, you can consider bypassing the standard compilation pipeline (e.g. TinyCC) or generating LLVM IR directly.
Misconceptions about template compilation speed
Templates are slow to compile?
  • C++ templates compile slowly because of C++'s compilation model.
  • Templates themselves do not greatly slow down compilation.
  • Dlang's standard library Phobos uses many templates but compiles quickly.
Misconceptions about the usefulness of separate compilation
Separate compilation is always worth it?
  • Separate compilation can lead to long link times.
  • In many projects, unity builds (including all code in a single file) give better performance.
  • Unity builds offer benefits such as whole-program optimization, faster compilation, and better error logs.
  • Cases where separate compilation is better than a unity build are rare.
Misconceptions about link-time optimization (LTO)
Why does link-time optimization (LTO) happen at link time?
  • LTO is performed for whole-program optimization.
  • In theory it makes more sense to perform whole-program optimization in the middle stage, but it is performed at link time because of practical problems with C/C++ build systems (difficulty finding source files and working out call relationships).
  • The linker can find all object files, so the compiler includes an intermediate language representation such as LLVM IR in the object files so the linker can access it.
Misconceptions about inlining optimization
Inlining is useful mainly because it removes function call instructions?
  • Removing function call instructions is a benefit, but the biggest benefit of inlining is enabling other optimizations.
  • Inlining enables interprocedural optimization.
  • When inlining merges the code of several functions into one function, existing intraprocedural optimization techniques can be applied.
Misconceptions about the role of the inline keyword
Is the inline keyword related to inlining optimization?
  • C++'s inline keyword was originally used as a hint to the optimizer, but since C++98 it has come to mean "multiple definitions allowed."
  • In LLVM, the inline keyword adds the inlinehint attribute and raises the inlining threshold, but its effect is small.
  • To always inline a function, you must use the always_inline specifier.
Misconceptions about compiler learning resources
LLVM is the best compiler to learn from?
  • LLVM has educational aspects, but it is complex and huge because it supports many use cases.
  • To learn compiler development, it's better to first look at smaller, simpler compilers such as the Go compiler, LDC, and DMD.
Misconceptions about undefined behavior (Undefined Behavior)
Undefined behavior only enables optimizations?
  • Undefined behavior can also disable optimizations.
Compilers can "simply" define undefined behavior?
  • Compilers can define undefined behavior, but it can affect performance.
  • It would be ideal for the compiler to define all undefined behavior as the platform's behavior, but it's not easy in practice.
Misconceptions about AI-based code generation
Code generation with 99% accuracy is fine?
  • 99% accuracy in compiler-generated code is hard to use in practice.
  • A 1% error in code causes great difficulty in debugging and maintenance.
  • In large projects, a 1% error can cause very serious problems.
  • Current LLMs are very slow compared to compilers, so they are not suitable for online code generation.

See also

Favorite site

Online Tools

  • [Recommended] Compiler Explorer - Outputs C++ compilation results (ASM) for comparison. Supports many languages.

Articles

author Zer0 sitemap