Binted

A compiler for a statically typed, C-like language, targeting x86-64 assembly, written in Rust from scratch (no LLVM, no existing backend).

What it is

Binted takes source in a small, statically typed, C-like language and compiles it all the way down to x86-64 assembly, which is then assembled and linked into a native executable. The pipeline is fully hand-written: hand-rolled recursive-descent parser, a TACKY-style three-address IR, and a from-scratch instruction-selection/register-allocation-free codegen backend emitting AT&T-syntax assembly.

source (.bnt) -> AST -> type-checked AST -> IR (three-address code) -> assembly AST -> .s -> gcc -> executable

What it has

• Parser: full recursive-descent parser with a complete precedence chain (logical, equality, comparison, bitwise, term, factor, unary), mandatory braces, if/else, while with break/continue, function declarations and calls.
• Type checker: two-pass hoisting (supports forward references and mutual recursion), scope stack, mandatory-return-path analysis on every function, Int -> Double widening at assignment/call/var-decl boundaries.
• IR generation: a three-address/TACKY-style intermediate representation with short-circuit lowering for &&/||, full support for recursive and mutually recursive functions.
• Codegen: a complete int/bool/void/ double/char pipeline — unary/binary ops, variables, control flow, and functions — emitting real, correct x86-64 assembly that assembles and links into a working native binary.

A full multi-function test program (recursive factorial, parity check, conditionals, loops with break/continue, negative division/modulo, bitwise ops, short-circuit boolean logic) compiles, links, and runs correctly end-to-end.

What it does not have (yet)

• String type in codegen yet (parsed/checked, not yet code-generated)
• No structs
• No arrays
• No closures or first-class functions (calls are identifier-only)
• No multi-file compilation
• No optimization passes (register allocation, constant folding, dead code elimination)

What's coming

Roughly in this order:

1. Casting between numeric types
2. Structs (fixed-offset layout)
3. Multi-file compilation
4. A test suite of known-correct programs
5. An optimization pass (register allocation, constant folding, dead code elimination)

What's somewhat different

Binted's frontend deliberately departs from the "Crafting Interpreters" Lox design in a few places:

• No null — there is no null/nil value in the type system at all
• No inheritance — the AST is a plain enum, walked directly instead of through class hierarchies
• No implicit statements at the top level — a program is a sequence of function/variable declarations only, no bare top-level statements
• Mandatory braces everywhere — no dangling-if/single-statement bodies
• Constants are resolved at compile time — a const must be a literal (10, 'a', ...) or reference another const declared earlier; anything else fails to compile rather than being evaluated at runtime

Running the compiler

While in the bintedc crate:

cargo run input.bnt

This compiles a .bnt source file into a native executable named output

What happens under the hood

1. Parse — input.bnt is tokenized and parsed into an AST.
2. Type check — the AST is checked against Binted's static type rules. Function signatures (including extern declarations for the standard library) are hoisted first, so forward references and calls to library functions resolve correctly. The value of global constants are also computed and resolved in this stage.
3. IR generation — the checked AST is lowered into an intermediate representation.
4. Code generation — the IR is compiled into x86-64 assembly (output.s).
5. Assemble & link — gcc is invoked to assemble output.s and link it against libstdlib.a (Binted's standard library, providing print/println/etc.), producing a standalone native binary. Functions from this library must be declared using the extern keyword.

Requirements

• gcc must be available on your PATH (used as the assembler/linker driver).
• The compiled libstdlib.a must exist at stdlib/target/release/ build it first with:

cd stdlib && cargo build --release

Credits

This project follows two books closely, one for each half of the compiler:

• Crafting Interpreters by Robert Nystrom — frontend (lexing, parsing, the overall structure of a tree-walking interpreter, adapted here into a fully static, compiled pipeline instead)
• Writing a C Compiler by Nora Sandler — backend (IR design, instruction selection, and the assembly-AST staging approach)

Grammar

program:     declaration* EOF

declaration: varDecl | funDecl | global VarDecl | extern funDecl | statement
extern funDecl: extern "fn" TYPE IDENTIFIER "(" parameters? ")"
global varDecl: const varDecl 
varDecl:     TYPE IDENTIFIER "=" expression ";"
funDecl:     fn TYPE IDENTIFIER "(" parameters? ")" block
parameters:  TYPE IDENTIFIER ("," TYPE IDENTIFIER)*

statement:   exprStmt | block | ifStmt | whileStmt | forStmt | returnStmt | breakStmt | continueStmt
exprStmt:    expression ";"
block:       "{" declaration* "}"
ifStmt:      "if" expression block ("else" ifStmt | block)?
whileStmt:   "while" expression block
returnStmt:  "return" expression? ";"
breakStmt:   "break" ";"
continueStmt: "continue" ";"

expression:  assignment
assignment:  IDENTIFIER "=" logic_or | logic_or
logic_or:    logic_and ("||" logic_and)*
logic_and:   equality ("&&" equality)*
equality:    comparison ((!= | ==) comparison)?
comparison:  bitwise ((>= | > | <= | <) bitwise)?
bitwise:     term ((& | | | ^ | >> | <<) term)*
term:        factor ((+ | -) factor)*
factor:      unary ((* | / | %) unary)*
unary:       ((! | -) unary) | call
call:        IDENTIFIER ("(" arguments? ")")* | primary
arguments:   expression ("," expression)*
primary:     IDENTIFIER | LITERAL | "(" expression ")"