Spec M1 — lexer, token table, Pratt, AST, dumps, constant-expression codegen

Scope: i64 main() { return 40 + 2; } compiles to .o, links and exits with 42. All of the front-end infrastructure and the back-end skeleton are born here in their final shape. Out of scope (M2+): variables, parameters, calls, if/loop, memory, globals, strings, #include.

Read all of docs/plan.md first. Files: stage0/lex.c, stage0/ast.c, stage0/parse.c, stage0/gen_arm64.c, stage0/main.c (rewrite; remove m0/m05), stage0/mc.h (extend), scripts/test.sh, tests/001-return42.mc, tests/002-arith.mc, tests/003-infix.mc. arena.c and macho.c already exist — use sec_new/sym_new/reloc_add/macho_write as they are.

CLI (main.c) #

mc0 [--dump-tokens|--dump-ast|--dump-asm] input.mc [-o output.o]. Default for -o: out.o. Errors: file:line: message on stderr, exit 1 (use die2; add helper err_at(line, msg)).

Lexer (lex.c) #

• Tokenizes the whole file into a flat arena array before parsing.
• Token: { int id; const u8 *start; int len; i64 val; int line; } (simple struct, flat fields).
• Fixed ids: T_EOF=0 T_IDENT=1 T_INT=2 T_CHAR=3 T_STR=4 T_DIR=5 T_HOLE=6. T_DIR is #name (val = index into the list of known directives; unknown = error). T_HOLE is $1/$2/$name (val = number, or -1 if a name; $$name marks a gensym — just reserve the id, no semantics in M1).
• Mutable token table (piece A of the plan): array in insertion order { const char *text; int len; bool word; int id; }, ids starting at 256 in insertion order. The core registers, at init, in this fixed order: types u8 u16 u32 u64 i64 uptr void; keywords if else loop break continue return extern; punctuation ( ) { } [ ] , ;; operators + - * / % & | ^ ~ << >> == != < <= > >= && || ! =. Identifiers are looked up in the table (word=true) — if matched, they become that id. Punctuation/operators: matched by longest prefix, scanning the table (linear, deterministic).
• #token "text" registers a new lexeme (word if it starts with a letter/_). Processed by the parser when it hits the T_DIR, but since the file is tokenized all at once, the lexer needs to know about the new token before continuing: solution — the lexer is incremental (lex_next() on demand) and the parser keeps a 1-token lookahead. Do not pre-tokenize everything. (--dump-tokens then runs the lexer alone, without the parser, and does not see #token — acceptable and documented.)
• Literals: decimal integer and 0x hex; char 'a' with escapes \n \t \r \0 \\ \' \"; string with the same escapes (store decoded bytes in the arena; trailing NUL added by codegen in M3).
• Comments // to end of line and /* */. Correct line counting.
• --dump-tokens: one line per token: LINE ID TEXT (for INT, print the value).

AST (ast.c) #

• Nodes in a flat arena array, referenced by int index (never a pointer), 0 = none. struct Node { int kind; int op; int type; i64 val; const char *name; int a, b, c, d; int next; int line; } Lists linked via next. node_new(kind, line) returns the index.
• M1 kinds: N_INT N_STR N_CHAR? (use N_INT) N_IDENT N_UNARY N_BINARY N_CAST N_CALL N_RETURN N_BLOCK N_EXPRSTMT N_FUNC N_PARAM N_HOLE. Reserve the rest of the plan's enum values (N_IF N_LOOP N_BREAK N_CONTINUE N_ASSIGN N_VAR N_GLOBAL N_EXTERN N_ADDR N_INDEX) without implementing them.
• op for N_UNARY/N_BINARY = the operator token's id (from the table) — this way operators taught via #infix/#prefix without a template need no enum value of their own.
• Types: TY_VOID=0 TY_U8 TY_U16 TY_U32 TY_U64 TY_I64 TY_UPTR (plain int).
• node_copy_subst(n, holes[], nholes): deep copy substituting N_HOLE(i) with the index in holes[i]. This is the basis for #infix/#prefix now and for #rule in M9.
• --dump-ast: deterministic indented text, one node per line: KIND op=... val=... name=....

Parser (parse.c) #

• Recursive descent for declarations/statements; table-driven Pratt for expressions.
• Infix table in insertion order: { int tok; int prec; bool right; int tmpl; } (tmpl = index of an AST template with holes, or 0 = builtin operator → N_BINARY with op=tok). Prefix table: { int tok; int tmpl; } (0 = builtin → N_UNARY). Core precedences (higher binds tighter): || 1, && 2, | 3, ^ 4, & 5, == != 6, < <= > >= 7, << >> 8, + - 9, * / % 10. Builtin prefixes: - ~ ! (and & reserved for M2). Postfix: call f(a, b) (parse only in M1; codegen in M2) — prec 11.
• Primaries: INT, CHAR, STR, IDENT, ( expr ), ( type ) expr (cast), HOLE.
• M1 directives: #token "...", #infix "tok" PREC left|right EXPR, #prefix "tok" EXPR. The template's EXPR is parsed on the spot with the normal parser; $1/$2 become N_HOLE. When the operator is used, node_copy_subst with the operands. If the template is just $1 <op> $2 this works naturally. #infix on a token that already exists replaces the entry (linear search).
• Top level: type name ( params ) { body } → N_FUNC (name, type=return type, a=list of N_PARAM, b=N_BLOCK). M1 statements: return expr;, return;, block { }, expr;.
• Constant folding: fold(n) evaluates constant N_INT/N_UNARY/N_BINARY/N_CAST down to a single N_INT (u64 arithmetic with wraparound; signed /,%; division by zero = error). Run before codegen. Will be used by #define, #opcode and emit().

Codegen (gen_arm64.c) #

• Linear instruction buffer per function: array { int op; int rd, rn, rm; i64 imm; int label; int sym; } plus gen_encode(), which converts it into words in __text, resolving local labels (I_LABEL defines; I_B/I_BCOND/I_CBZ reference) and recording relocations via reloc_add for I_BL/I_ADRP/I_ADDLO with a symbol (used by M2/M3). --dump-asm prints the buffer as deterministic text ( add x9, x9, x10 etc.) before encoding.
• M1's minimal encoders (add every enum value from the plan, but implement only what M1 uses): movz/movk (load a 64-bit immediate in up to 4 instructions), mov rd, rm, add/sub/mul/sdiv, msub (for %), and/orr/eor (register), mvn, neg, lslv/lsrv/asrv, cmp + cset with a condition, and rd, rn, #imm for u8/u16 casts (0xff/0xffff), mov wd, wn for u32, stp/ldp x29,x30,[sp,#-16]!/[sp],#16, add/sub sp, sp, #imm, ret, b, b.cond, cbz.
• Registers by depth: an expression produces its value in register x(9+depth), depth 0..6; depth ≥ 7 → error "expression too deep" in M1 (spilling comes in M2). Comparisons → 0/1 via cset. &&/|| with short-circuit and labels. >> is asr if the left operand's type is i64, else lsr.
• Result type: simple rule — a literal is i64; a binary op inherits the left operand's type; a cast sets the type. No type-error checking in M1 beyond void in an expression.
• Prologue/epilogue: stp x29,x30,[sp,#-16]!; mov x29,sp; sub sp,sp,#frame / add sp,sp,#frame; ldp x29,x30,[sp],#16; ret. frame = 0 in M1 (but already computed and 16-aligned). return e → value in x0 (mov x0, x9) and branch to the function's single epilogue label.
• Symbols: function name becomes global _name in __TEXT,__text (align each function to 4).
• Emission order = source order. No hash tables anywhere.

Tests #

• scripts/test.sh COMPILER: for each tests/*.mc, compiles to build/tests/NAME.o, links with scripts/link.sh, runs it; reads // expect-exit: N and (if present) // expect-stdout: TEXT from the header and compares. Prints ok NAME / FAIL NAME (reason); exit 1 if any fails.
• tests/001-return42.mc: i64 main() { return 40 + 2; }
• tests/002-arith.mc: an expression with precedence, unaries, shifts, casts, %, &&/||, comparisons — result 42 by construction (e.g. return ((7 * 6) & 0xff) + (3 < 2) - ((u8) 256);).
• tests/003-infix.mc: #token "<+>" + #infix "<+>" 9 left ($1 + $2) * 2 and return 10 <+> 11; (= 42).

Acceptance (run for real and report the output) #

make stage0 && make stage0-san && make budget && make test green; build/mc0 --dump-tokens tests/001-return42.mc, --dump-ast, --dump-asm with stable output (run twice and diff).

Edit this page