Handwritten Java Compiler — From Lexical Analysis to MIPS Code Generation

Level: S-Tier Core Project
Origin: Compiler Principles Course Design (undergraduate)
Domain: Compiler Construction · Formal Languages · LR Parsing · Code Generation
Stack: Java · MIPS Assembly · LR(1) Parsing · Three-Address Code · Quaternion IR

---

Overview

A complete compiler pipeline built entirely from scratch in Java (~8,000 lines), translating a C/Java-like source language to MIPS32 assembly — without using parser generators (ANTLR/Yacc/JavaCC). Demonstrates deep understanding of formal language theory, automata construction, intermediate representation design, and target code generation.

---

Architecture

graph LR
    subgraph Frontend["Frontend"]
        SRC["Source Code<br/>(.txt)"] --> LEX["Lexer<br/>Handwritten DFA"]
        LEX --> TOK["Token Stream"]
        TOK --> PARSE["LR(1) Parser<br/>Bottom-Up"]
    end
    
    subgraph IR["Intermediate Representation"]
        PARSE --> IR["InterCode Gen<br/>Syntax-Directed"]
        IR --> TAC["Three-Address Code<br/>Quaternions"]
    end
    
    subgraph Backend["Backend"]
        TAC --> OBJ["ObjectCode Gen<br/>Register Allocation"]
        OBJ --> MIPS["MIPS32 Assembly<br/>(.asm)"]
    end
    
    subgraph Runtime["Runtime"]
        MIPS --> MARS["MARS Simulator"]
        MARS --> EXEC["Execution Result"]
    end

    style Frontend fill:#e1f5fe
    style IR fill:#fff3e0
    style Backend fill:#e8f5e9
    style Runtime fill:#fce4ec

Loading

---

Project Structure (Progressive Stages)

handwritten-java-compiler/
├── stage1-lexer/            # Lexical Analysis
│   └── Lexer, Token, SymbolType
├── stage2-parser-a/         # LR(1) Parsing (simplified grammar)
│   └── CFGA (12 productions), LRTable
├── stage2-parser-b/         # LR(1) Parsing (full grammar)
│   └── CFGBlock (47 productions), Parser, LR1Automata
├── stage3-ir-a/             # Intermediate Code Gen (basic)
│   └── Syntax-directed translation to TAC
├── stage3-ir-b/             # Intermediate Code Gen (full)
│   └── Quaternion, InterCode, backpatching
├── stage4-codegen-a/        # MIPS Code Gen (baseline)
│   └── Hardcoded MIPS templates
├── stage4-codegen-b/        # MIPS Code Gen (complete) ★
│   └── Full pipeline: Lexer→InterCode→ObjectCode→MIPS
├── compile.bat / compile.sh  # Build scripts
├── README.md
└── README_CN.md

Stage 4B is the most complete version, covering all phases.

---

Supported Language Features

Feature	Support	Example
Variable declaration	✅	int m, n;
Assignment	✅	x = 10;
Arithmetic (+, -, *, /, %)	✅	a = b + c * 2;
Comparison (<, >, <=, >=)	✅	if (x < y)
Equality (==, !=)	✅	if (x == 0)
Logic (&&, ||)	✅	if (a && b)
If-else statements	✅	if (cond) { ... } else { ... }
While loops	✅	while (i < n) { ... }
Input	✅	getint()
Output	✅	printf("result=%d\n", a);
Code blocks	✅	{ ... }
Single-line comments	✅	// comment

---

Quick Start

Prerequisites

• JDK 8+
• MARS MIPS Simulator (for running generated code)

Build & Run

# Clone
git clone https://github.com/lakeart/handwritten-java-compiler.git
cd handwritten-java-compiler

# Download MARS (optional, for running generated MIPS code)
# Visit: http://courses.missouristate.edu/KenVollmar/MARS/

# Compile the most complete version
./compile.sh stage4-codegen-b      # Linux/macOS
# or
compile.bat stage4-codegen-b       # Windows

# Run the compiler (reads testfile.txt → outputs mips.txt)
cd stage4-codegen-b
java -cp . Compiler

# Run generated MIPS code in simulator
java -jar ../Mars.jar mips.txt

Test Input Example (stage4-codegen-b/testfile.txt)

int m, n;
m = getint();
n = getint();
while (n != 0) {
    int t;
    t = n;
    n = m % n;
    m = t;
}
printf("gcd=%d\n", m);

This is a GCD (Greatest Common Divisor) calculation — compiled and executed entirely through the handwritten pipeline.

---

Key Technical Achievements

1. Handwritten LR(1) Parser

• Full LR(1) automaton construction from CFG
• 47 production rules covering expressions, statements, blocks
• Hardcoded LR(1) parsing table in LRTable.java (~1,000 lines, 53KB)
• LR_table.txt: textual representation for debugging

2. Three-Address Code with Backpatching

• Quaternion IR format: (op, arg1, arg2, result)
• Backpatching technique for if/while control flow
• Scope stack for symbol table management

3. MIPS32 Code Generation

• Register allocation: $t0-$t3 for temporaries, $v0 for syscalls
• .data section for string constants and variables
• .text section with label-based control flow
• 4 syscall types: print_int, print_string, read_int, exit

4. Progressive Learning Design

• 6 stages demonstrate the complete compiler construction process
• Each stage builds upon the previous one
• Ideal for educational understanding of compiler internals

---

Technical Challenges

1. LR(1) state explosion: A full LR(1) automaton for a 47-production grammar generates dozens of states; carefully designed item set kernel merging to keep the table manageable
2. Backpatching control flow: Implementing if/while requires deferred jump target resolution — implemented via a backpatch list that fills in target labels after code emission is complete
3. Register allocation without liveness analysis: Used a simple 4-register pool (t0-t3) with spill-to-memory when exhausted, a minimal but functional approach
4. Type system limitations: The language supports only int type — handling type inference or multiple types would require significant grammar and semantic analysis extensions

---

Interview FAQs

1. Why LR(1) instead of recursive descent?
   LR(1) provides deterministic bottom-up parsing for a broader class of grammars. While recursive descent is simpler to implement, LR(1) handles left-recursive productions naturally and catches syntax errors earlier (at the point of the invalid token rather than deeper in the parse tree).

2. What is the difference between LR(0), SLR(1), LR(1), and LALR(1)?
   They differ in lookahead usage: LR(0) uses no lookahead (most restrictive), SLR(1) uses FOLLOW sets for lookahead, LR(1) computes full item-specific lookahead sets (most powerful), LALR(1) merges LR(1) states with identical cores (compromise used in yacc/bison).

3. How does backpatching work in the compiler?
   When generating code for if (cond) stmt1 else stmt2, the jump at the end of cond and stmt1 cannot be resolved until stmt2 is emitted. A backpatch list records these incomplete jumps; after stmt2 is emitted, the recorded addresses are updated with the correct target label.

4. What are quaternions in intermediate representation?
   Quaternions (four-address code) are a form of three-address code: (op, arg1, arg2, result). They're a compact IR representation that's closer to assembly while maintaining platform independence. Each quaternion typically maps to one or two MIPS instructions.

5. How would you extend this compiler to support functions?
   Key changes: (1) Add function declaration/definition to the grammar; (2) Implement a call stack in the symbol table; (3) Add call/return quaternions; (4) Implement calling convention (argument passing via registers/stack, frame pointer management, return value handling).

---

Origin

This project was developed as the Compiler Principles course design at university. It demonstrates the complete compiler construction workflow through progressive stages, from lexical analysis to target code generation, all implemented from scratch without parser generators.

Personal Contributions

• Complete compiler implementation: Independently designed and implemented all six stages of the compiler pipeline (lexing, parsing, IR generation, code generation), totaling ~8,000 lines of Java
• LR(1) parser construction: Hand-built the LR(1) automaton, First/Follow set computation, and parsing table — without using ANTLR, Yacc, or JavaCC
• Backpatching-based code generation: Designed the quaternion-based intermediate representation and implemented backpatching for control flow (if/while)
• MIPS target backend: Implemented register allocation and MIPS32 assembly code generation with syscall support

Third-Party Components

Component	Purpose	License
MARS (MIPS Assembler and Runtime Simulator)	Running generated MIPS code	MIT

Known Limitations

1. Subset language: Supports only a subset of C/Java (no functions, arrays, pointers, structs, for-loops, break/continue)
2. Single data type: Only int type is supported; no type checking or type inference
3. No optimization: No constant folding, dead code elimination, or peephole optimization
4. Error recovery: Basic error reporting with termination on first error; no panic-mode recovery
5. Hardcoded LR tables: The LR(1) table is manually initialized in code rather than generated from a separate grammar file; grammar changes require code edits
6. No AST: Uses syntax-directed translation directly (no intermediate AST construction), which limits reusability for multi-pass compilation

---

Repository Info

Field	Value
Repo Name	handwritten-java-compiler
Chinese Title	手写Java编译器——从词法分析到MIPS代码生成
One-liner (EN)	A complete compiler pipeline (~8K lines) from lexical analysis to MIPS32 code generation, built from scratch without parser generators
GitHub Topics	compiler lr-parser mips lexer code-generation three-address-code compiler-design java education
Gitee Tags	编译器 LR分析 MIPS 词法分析 代码生成 Java
Pin	✅ Yes
License	MIT