LC-3 Virtual Machine and Compiler

A LC-3 ecosystem: a compiler for a simple high-level language and a virtual machine to execute the compiled programs.

Why This Project?

Understanding how computers actually work can feel abstract. This project makes it concrete:

• Virtual Machine → Learn computer architecture: CPU, registers, memory, instruction cycle
• Compiler → Learn compilation principles: lexing, parsing, AST, intermediate representation, code generation

Both components are implemented in single C files, making them easy to read and modify. By studying this project, you'll understand:

1. How CPU executes instructions (fetch → decode → execute)
2. How instructions are encoded and implemented (ADD, LD, BR, etc.)
3. How a parser builds an Abstract Syntax Tree (AST)
4. How intermediate representation (Three-Address Code)
5. How code generation translates to target architecture

Quick Start

make                    # Build compiler and VM
./compiler "x = 5; y = 3; z = x + y; print(z);"
./lc3 output.obj        # Output: 8

Components

Virtual Machine (lc3.c)

An LC-3 simulator based on jmeiners.com/lc3-vm.

Architecture:

┌─────────────────────────────────────────────┐
│                    CPU                      │
│  ┌─────────────────────────────────────┐    │
│  │ Registers: R0-R7, PC, COND          │    │
│  └─────────────────────────────────────┘    │
│  ┌─────────────────────────────────────┐    │
│  │ ALU, ADD, AND, NOT, MUL             │    │
│  └─────────────────────────────────────┘    │
└──────────────────┬──────────────────────────┘
                   │ 16-bit bus
┌──────────────────┴──────────────────────────┐
│              Memory (64KB)                  │
│  0x0000-0x2FFF  System/Trap routines        │
│  0x3000-0xFDFF  User program space          │
│  0xFE00-0xFFFF  Memory-mapped I/O           │
└─────────────────────────────────────────────┘

Execution Cycle:

while (running) {
    uint16_t instr = mem_read(reg[R_PC]++);   // 1. Fetch
    uint16_t op = instr >> 12;                // 2. Decode (extract opcode)
    switch (op) { /* execute */ }             // 3. Execute
}

Instruction Format (16-bit):

15 14 13 12 | 11 10 9 | 8 7 6 | 5 | 4 3 2 1 0
   opcode   |   DR    |  SR1  |   |   SR2/imm5

Custom Extensions:

• MUL (opcode 8): Multiply two registers
• CMP (opcode 13): Compare two registers, set condition codes

Compiler (compiler.c)

A multi-stage compiler that transforms high-level code into LC-3 machine code.

Pipeline:

Source Code
    │
    ▼
┌─────────┐   "x = 5;"  →  [IDENT(x), ASSIGN, NUM(5), SEMI]
│  Lexer  │   Breaks source into tokens
└────┬────┘
     ▼
┌─────────┐        x =
│ Parser  │          └── 5
└────┬────┘   Builds Abstract Syntax Tree (AST)
     ▼
┌─────────┐   t0 = 5
│   TAC   │   x = t0
└────┬────┘   Three-Address Code (platform independent)
     ▼
┌─────────┐   AND R0, R0, #0
│ CodeGen │   ADD R0, R0, #5
└────┬────┘   ST R0, VAR_x
     ▼
┌───────────┐
│ Assembler │   Two-pass: 1) Build symbol table  2) Encode instructions
└─────┬─────┘
      ▼
   output.obj (binary)

Supported Syntax:

• Variable assignment: x = 5;
• Arithmetic: +, -, * (with precedence and parentheses)
• Comparison: >, <, ==
• Conditional: if (a > b) { ... } else { ... }
• Output: print(expr); (single digit 0-9)
• Input: input(var); (reads single digit, auto-converts ASCII to number)

Examples

# Arithmetic
./compiler "a = 2; b = 4; c = a * b; print(c);"
./lc3 output.obj   # Output: 8

# Conditionals
./compiler "x = 7; if (x > 5) { print(1); } else { print(0); }"
./lc3 output.obj   # Output: 1

# User Input (enter two digits, outputs their sum)
./compiler "input(x); input(y); z = x + y; print(z);"
./lc3 output.obj   # Type: 3 5 → Output: 8

# Parentheses priority
./compiler "a = 2; b = 1; c = 2; d = a * (b + c); print(d);"
./lc3 output.obj   # Output: 6 (2 * (1 + 2) = 6)

# Input + Arithmetic + Conditional
./compiler "input(a); input(b); c = a * b; if (c > 8) { print(1); } else { print(0); }"
echo "35" | ./lc3 output.obj   # Output: 1 (3 * 5 = 15 > 8)

Run 2048 Game

A pre-built LC-3 version of the 2048 game is included:

./lc3 2048.obj

Use W/A/S/D keys to move tiles.

Files

File	Description
compiler.c	Compiler: lexer, parser, AST, TAC, code generator, assembler
lc3.c	LC-3 Virtual Machine
2048.obj	Pre-built 2048 game for LC-3
output.asm	Generated assembly (intermediate)
output.obj	Generated machine code (binary)

Limitations

• Numbers: -16 to 15 (LC-3 5-bit immediate)
• print(): Only displays single digit (0-9)
• input(): Only reads single digit (0-9)

Build

make            # Build all
make run        # Build and run example
make test-all   # Run all 14 automated tests
make clean      # Remove artifacts

License

• lc3.c (Virtual Machine): MIT License, based on justinmeiners/lc3-vm by Justin Meiners
• compiler.c (Compiler): MIT License