How Compilers Work: From Source Code to AST, LLVM, and Machine Code

Every software engineering ecosystem relies on compilers. Whether you are building a web server in C++, compiling a mobile application in Swift, or executing a Rust binary, a compiler serves as the invisible bridge translating human-readable source code into high-performance machine instructions.

To many developers, compilers feel like black boxes that transform text files into executables. In reality, modern compilers are highly structured pipelines built on computer science principles, mathematical formal languages, and computer architecture.

This guide breaks down compiler architecture, explains lexical and syntactic analysis, compares parser implementations, explores Abstract Syntax Trees (ASTs), details intermediate code generation and the LLVM framework, and demonstrates interactive tools like the mitos.dev AST Explorer and mitos.dev C Compiler Explorer.

1. What is a Compiler?

A compiler is a specialized program that translates source code written in a high-level programming language (such as C, C++, Rust, or Swift) into an equivalent program in a lower-level target language (such as x86-64 assembly, ARM machine code, or WebAssembly) without altering the program's functional logic.

1785472303875-ix6f0p.jpg

Compiler vs. Interpreter

  • Compilers: Translate the entire source code into native machine code before execution. The resulting binary runs directly on hardware at maximum speed.
  • Interpreters: Read, analyze, and execute source code line-by-line at runtime (e.g., classic Python or Ruby engines).
  • Just-In-Time (JIT) Compilers: Combine both approaches by compiling dynamic bytecode into machine code at runtime (e.g., V8 in JavaScript, JVM in Java).

2. High-Level Compiler Architecture

Modern industrial compilers split their workflow into three distinct phases: the Front-End, the Middle-End, and the Back-End.

1785472248693-dpx3vi.jpg

  1. Front-End: Understands the source language. Reads raw text files, checks syntax, verifies type safety, and builds an internal representation called an Abstract Syntax Tree (AST).
  2. Middle-End: Language- and hardware-agnostic. Converts the AST into an Intermediate Representation (IR) and runs optimization passes (dead code elimination, loop unrolling, constant folding).
  3. Back-End: Hardware-dependent. Translates optimized IR into target-specific assembly or machine code tailored for CPU architectures like x86-64, ARM, or WebAssembly.

3. Phase 1: Lexical Analysis (The Lexer)

The first step in compilation is Lexical Analysis, handled by a Lexer (or Scanner).

A lexer reads raw, unstructured source code character-by-character and groups them into meaningful sequence units called Lexemes. It then assigns a semantic label to each lexeme, producing a flat stream of structured Tokens.

Example Lexing Process

Given this line of source code:

int total = count + 10;

The lexer breaks the character stream into discrete tokens while discarding non-semantic whitespace and comments:

Lexeme Token Category Attributes
int KEYWORD Data Type Keyword
total IDENTIFIER Variable Name: "total"
= OPERATOR Assignment Operator
count IDENTIFIER Variable Name: "count"
+ OPERATOR Addition Operator
10 LITERAL_INT Integer Value: 10
; PUNCTUATION Statement Terminator

How Lexers Work Under the Hood

Lexers rely on Regular Expressions (Regex) to define token rules and Deterministic Finite Automata (DFA) state machines to scan characters efficiently in $O(N)$ linear time.

4. Phase 2: Syntax Analysis (The Parser) & AST

Once the token stream is generated, it flows into the Parser for Syntax Analysis.

The parser checks whether the sequence of tokens conforms to the formal grammar rules of the programming language, usually defined using Context-Free Grammars (CFG) or Backus-Naur Form (BNF).

Token Stream ---> [ Parser Engine ] ---> Abstract Syntax Tree (AST)

Types of Parsing Algorithms

Parsing techniques fall into two major families:

1. Top-Down Parsers

Top-down parsers build the parse tree starting from the root grammar rule (e.g., Program) down to the leaves (tokens).

  • Recursive Descent Parsers: A hand-written parsing technique where each grammar rule corresponds to a function in code. Simple to write, debug, and maintain (used by Clang and GCC).
  • LL(k) Parsers: Left-to-right scan, Leftmost derivation using $k$ lookahead tokens. Predictive parsers that do not require backtracking.

2. Bottom-Up Parsers

Bottom-up parsers start at the leaf tokens and shift values onto a stack until they can reduce them into higher-level grammar rules.

  • LR(k) Parsers: Left-to-right scan, Rightmost derivation in reverse. Handles complex grammars cleanly.
  • LALR Parsers (Look-Ahead LR): Compact versions of LR parsers used by automated parser generators like yacc and bison.

Abstract Syntax Trees (ASTs)

The primary output of the parser is an Abstract Syntax Tree (AST). An AST is a hierarchical tree structure representing the logical control flow of your code, omitting unnecessary syntactic noise like semicolons, parentheses, and braces.

For example, consider the mathematical expression:

x = a + b * 5

The parser constructs the following hierarchical tree structure:

          [ AssignmentStmt ]
             /          \
      Identifier(x)    [ BinaryExpr (+) ]
                        /            \
                Identifier(a)    [ BinaryExpr (*) ]
                                   /          \
                            Identifier(b)   LiteralInt(5)

Visualizing ASTs Online

Understanding how a parser translates raw source code into structural nodes is far easier when viewed interactively. You can write source code and inspect the generated AST structure in real-time using the mitos.dev AST Explorer.

5. Phase 3: Semantic Analysis & Intermediate Representation (IR)

Semantic Analysis

Having correct syntax does not guarantee meaningful code. For instance, int x = "hello" / 0; is syntactically valid but semantically broken.

The Semantic Analyzer traverses the AST to enforce language rules:

  • Type Checking: Ensures variables match assigned values and operators act on compatible types.
  • Scope Resolution: Ensures variables are declared before use within their lexical block scope.
  • Symbol Table Construction: Maintains a database tracking variable names, types, memory offsets, and function signatures.

Intermediate Representation (IR)

After semantic verification, the AST is converted into Intermediate Representation (IR) code.

Why not translate AST straight to machine code? If a compiler supports $M$ source languages (C, Rust, Swift) and $N$ CPU targets (x86, ARM, WebAssembly), translating directly requires $M \times N$ separate compilers. By translating all languages to an intermediate representation, we only need $M$ front-ends and $N$ back-ends ($M + N$).

1785472515147-a431l5.jpg

Common IR forms use Three-Address Code (TAC) or Static Single Assignment (SSA), where every variable is assigned exactly once, simplifying compiler optimization routines.

6. Phase 4: Code Generation & The LLVM Framework

Back-End Code Generation

The back-end takes optimized IR code and generates executable assembly or binary instructions for the target CPU architecture:

  1. Instruction Selection: Translates high-level IR operations into equivalent hardware machine instructions.
  2. Register Allocation: Maps an infinite number of virtual IR variables into a small, fixed set of physical CPU registers (e.g., rax, rbx, rdi).
  3. Instruction Scheduling: Reorders instructions to prevent hardware stalls and maximize CPU instruction pipelining efficiency.

The LLVM Infrastructure

In modern compiler engineering, building every phase from scratch is rarely necessary thanks to LLVM (originally Low Level Virtual Machine).

LLVM provides a modular, language-independent compiler framework:

[ Clang / rustc / swiftc ] ---> ( LLVM IR ) ---> [ LLVM Optimizer & Back-End ] ---> Machine Code
  • LLVM IR: A strongly-typed, assembly-like intermediate language with an infinite register set.
  • Reusability: Compiler authors write a front-end parser that generates LLVM IR. LLVM then handles all optimization passes and code generation across x86, ARM, RISC-V, and WebAssembly automatically.

7. Try Interactive Compiler Tools on Mitos.dev

Exploring compiler phases firsthand helps connect abstract theoretical concepts with practical code execution.

1. Visualize Code Syntax Trees

Use the visual AST inspector to explore how high-level syntax maps into hierarchical node relationships:

👉 AST Explorer Tool on mitos.dev

+-----------------------------------------------------------------------------------+
| MITOS.DEV AST EXPLORER WORKFLOW                                                   |
|                                                                                   |
| [ Input Source Code ] ---> [ Live Parser Engine ] ---> [ Interactive Tree View ]  |
|                                                                                   |
|                        đź”’ 100% Client-Side Processing                            |
+-----------------------------------------------------------------------------------+

2. Inspect Assembly & Compilation Output

Analyze how high-level C code compiles down through LLVM IR, x86 assembly, and WebAssembly bytecode using a side-by-side interactive compiler:

👉 C Compiler Explorer Tool on mitos.dev

+-----------------------------------------------------------------------------------+
| MITOS.DEV C COMPILER EXPLORER WORKFLOW                                            |
|                                                                                   |
| [ Write C Functions ] ---> [ Tweak Compiler Flags ] ---> [ View Generated Assembly]|
|                                                                                   |
|                       đź”’ 100% Client-Side Compilation                             |
+-----------------------------------------------------------------------------------+

Compilers represent one of computer science's greatest engineering achievements. By breaking down translation into modular phases—from lexical token streams and AST generation to IR optimization and native register allocation—compilers ensure software remains portable, maintainable, and fast across physical hardware architectures.

Inspect syntax trees and observe live machine code generation directly in your browser using the mitos.dev AST Explorer and mitos.dev C Compiler Explorer!