🦆 duckBASIC: A Modern 16-bit BASIC Compiler — Design & Implementation
🦆 Introduction
This series documents the design and implementation of duckBASIC, a compiler for a modern dialect of BASIC. The Philosophy is to create a usable teachable tool for students or hobyists who are interested in Compiler and interpreter writing. DuckBASIC targets both C (for portability) and 16-bit real-mode MS-DOS via NASM assembly (.COM executables). The project was built iteratively, feature by feature, with a test suite that validates both backends in parallel against identical source programs.
Old timers who have soiled their hands with QBASIC/GWBASIC/BASICA/VB may find similar environment but in C style 🦆🦆🦆
Over the course of development, duckBASIC grew from a simple expression evaluator into a compiler with:
- Two full backends (C transpiler and NASM 16-bit assembler emitter)
- Structured types: structs, struct parameters, arrays of structs, local structs, nested structs
- Fixed-point Q16:16 arithmetic implemented in hand-written x86 assembly
- A locked byte layout for SERIALIZE/DESERIALIZE that guarantees cross-backend binary compatibility
- A real file I/O API (
SYS_OPEN,SYS_READ,SYS_WRITE,SYS_SEEK, etc.) - Cross-platform keyboard primitives (
INKEY$,INPUT$(n)) and array parameters (INT[],FLOAT[],CHAR[],STRUCT[]) - 75+ tests running on both backends, most of which are verified by running the resulting
.COMfile inside DOSBox and comparing output byte-for-byte
The project is interesting not because it implements a compiler — plenty of toy compilers exist — but because it implements two of them simultaneously, with a shared test suite, and verifies they produce identical output on real 16-bit hardware.
Part 1 — Architecture Overview
The pipeline
Every compiler is a pipeline, and duckBASIC’s is deliberately simple:
Source (.dkb)
↓
Lexer (tokens)
↓
Parser (AST + symbol table)
↓
Semantic resolution (function calls)
↓
Type checker (evalType annotations)
↓
Code generation (two backends)
↓
├── C source (.c) → gcc → native binary
└── NASM source (.asm) → nasm → .com → DOSBox
The top-level structure
The compiler is a single executable, duckbas, built from ~15 C files. The entry point in main.c orchestrates the phases:
// Phase 1: Lexical analysis
lexer_init(&compiler_lexer, source_code);
// Phase 2: Parsing
symtable_init(&compiler_table);
parser_init(&compiler_parser, &compiler_lexer, &compiler_table);
ASTNode *program_tree = parser_parse_program(&compiler_parser);
// Phase 2.5: Semantic resolution (function calls)
resolve_function_calls(program_tree, &compiler_table);
// Phase 2.75: Type checking
int tc_errors = typecheck_program(&compiler_parser, program_tree);
// Gate: if any phase errored, stop before codegen
if (g_error_count > 0) { ... exit(1); }
// Phase 5: Code generation
if (opt.target == TARGET_C) {
gen_c_program(program_tree, &compiler_table, output_path);
} else {
gen_nasm_program(program_tree, &compiler_table, output_path);
}
Three global counters (g_error_count, g_warning_count, g_verbosity) coordinate diagnostics across phases.
The two backends
The C backend transpiles duckBASIC AST to C source, which is then compiled by gcc. This is the “reference” backend — anything that works here is by definition semantically correct. It’s also the fast one to iterate on: change a C emitter, recompile with gcc, done in 2 seconds.
The NASM backend emits 16-bit x86 assembly for MS-DOS .COM executables. This is the “authentic” backend — every feature must be implemented in raw assembly or wrapped around DOS/BIOS interrupts. It’s the hard one: fixed_mul is 60 lines of hand-rolled signed multiplication, _read_str uses BIOS INT 21h, AH=0Ah, SYS_OPEN wraps INT 21h, AH=3Dh.
The two backends share nothing at the codegen level. They each have their own AST walkers (gen_c_stmt.c, gen_c_expr.c vs gen_nasm_stmt.c, gen_nasm_expr.c). But they share the entire front end — parser, symbol table, type checker — which is what guarantees semantic consistency.
The test harness
The test suite (tests/*.dkb) runs each program through both backends and compares:
- C backend output — compile to
.c,gcc, run, capture stdout. - NASM backend assembles —
nasm -f bin, verify it produces a.com. - NASM output in DOSBox — run
.cominside DOSBox, capture output, compare byte-for-byte with C output.
For interactive tests (INKEY$, keyboard input), DOSBox runs with a scripted keystroke file.
The suite currently has 75 tests, 72 pass, 0 fail, 3 skip. The skipped tests are Phase 2 features (graphics, sound, etc.) that aren’t implemented yet.
No comments:
Post a Comment