Wednesday, 18 November 2026

🦆 Part 2 — Front End: Lexer, Parser, Symbol Table, Type Checker

Lexer (lexer.c)

The lexer is hand-written, single-pass, token-at-a-time. Nothing fancy — no DFA tables, no regex, just a switch on the first character.

Notable features:

  • Radix literals: 0x1F (hex), 0b1010 (binary), &HFF (QBasic-style hex), &B1010 (QBasic-style binary). The &H/&B forms are particularly nice because they round-trip cleanly to QBASIC programmers.
  • String escapes: \n, \t, \r, \\, \", \', \0.
  • Character literals: 'a' (single quotes). This interacts badly with QBASIC-style ' comments, which duckBASIC does not support — comments are //.
  • Token names array with a _Static_assert guarding against enum drift.

The lexer is intentionally simple. No diagnostic recovery, no multi-byte UTF-8, no raw strings. Every token is either recognized or produces TOKEN_ERROR and the parser will halt.

AST (ast.h, ast.c)

The AST is a tagged union of node types. Every node is an ASTNode struct:

typedef struct ASTNode {
    ASTNodeType type;
    DataType evalType;       // resolved type, set by typechecker
    bool print_no_newline;
    int line;

    struct ASTNode *left;
    struct ASTNode *right;
    struct ASTNode *next;    // statement chaining

    union {
        char *name;                          // identifier
        int32_t intVal;                      // int literal / float raw bits
        char *strVal;                        // string literal
        unsigned char charVal;               // char literal

        struct { ... } ifNode;
        struct { ... } whileNode;
        struct { ... } forNode;
        struct { ... } arrayAccess;
        struct { ... } functionDecl;
        struct { ... } functionCall;
        struct { ... } structDecl;
        struct { ... } fieldAccess;
        struct { ... } structVar;
        struct { ... } selectNode;
        struct { ... } caseNode;
        struct { ... } serializeNode;
    } attr;
} ASTNode;

The union keeps nodes compact (about 100 bytes each). The next pointer chains statements into a linked list, so a block is just a NODE_BLOCK whose left is the first statement and each statement’s next points to the following one.

The union overlap is a known footgun. attr.name (a char*) and attr.fieldAccess.object (also a pointer) occupy the same bytes. Reading attr.name on a NODE_FIELD_ACCESS produces a garbage pointer, which is exactly what caused the mov [var_], ax bug we spent a session debugging.

Symbol table (symtable.c)

The symbol table is a linked list of Symbol structs. It uses three pointer fields to maintain two separate lists simultaneously:

typedef struct Symbol {
    char name[128];
    DataType type;
    int offset;
    int class_type;          // SYM_SCALAR, SYM_ARRAY, SYM_STRUCT_DEF, etc.
    int is_local;
    int is_builtin;
    short stack_offset;

    union {
        struct { ... } array;
        struct { ... } struct_def;
        struct { ... } struct_var;
        struct { ... } function;
        struct { ... } constant;
    } metadata;

    struct Symbol *next;       // active scope lookup chain
    struct Symbol *all_next;   // master allocation chain (for cleanup)
} Symbol;
  • next is the active lookup chain — it changes as scopes are pushed and popped.
  • all_next is the master allocation chain — never modified after insertion. This is how symtable_free iterates all symbols for cleanup.
  • head points to the current scope’s head. all_head points to the master list.

Scope push/pop is done via snapshots:

ScopeSnapshot snap = symtable_save_scope(p->symTable);
// ... insert local symbols ...
symtable_restore_scope(p->symTable, snap);

Restoring just resets table->head to the snapshot’s head. Memory is never freed until symtable_free at the very end.

This design is simple but not scalable — lookups are O(n) linear scans. For a 16-bit compiler, that’s fine. For a production compiler, you’d want a hash table.

Parser (parser.c + parser_*.c)

The parser is recursive descent for statements and precedence climbing for expressions. Each grammar production is a function.

The parser is split across multiple files by grammar area:

  • parser.c — core (statement dispatch, expression engine, block parser, DIM handling)
  • parser_if.c, parser_while.c, parser_for.c — control flow
  • parser_function.c — function declarations, calls, returns
  • parser_struct.c — struct definitions
  • parser_array.c — array access
  • parser_select.c — SELECT CASE
  • parser_serialize.c — SERIALIZE / DESERIALIZE
  • parser_import.c — IMPORT statement (file inclusion)

The expression engine uses precedence climbing:

ASTNode* parse_expression(Parser *p, int precedence)
{
    // 1. Parse a prefix (literal, identifier, unary operator, paren)
    // 2. While the next token has higher precedence than the argument:
    //    - Consume the operator
    //    - Parse RHS with the operator's precedence
    //    - Build a binary node
    return left;
}

Precedence levels (highest to lowest):

  1. . (field access) — 12
  2. [ (array subscript) — 11
  3. * / % — 10
  4. + - — 9
  5. << >> — 8
  6. < <= > >= — 7
  7. == != — 6
  8. & — 5
  9. ^ — 4
  10. | — 3
  11. && — 2
  12. || — 1

Error recovery is panic-mode: on failure, skip tokens until a \n, }, or EOF, then continue. This means a syntax error in one statement doesn’t cascade into forty subsequent errors.

Type checker (typecheck.c)

The type checker walks the AST after parsing and before codegen. It does two things:

  1. Annotates every expression node with evalType so codegen can trust it without re-deriving.
  2. Validates type compatibility and increments g_error_count on mismatch.

Key rules:

  • BOOL cannot appear in arithmetic.
  • STRING + is only valid inside PRINT (concatenation).
  • Array indices must be INT.
  • Function call arguments must be type-assignable.

The typechecker re-creates function scope by re-inserting parameters and locals into the symbol table, then checks the body, then restores scope. This is a second pass over the AST — the parser already did one symbol-table pass — which is why there are two name-lookup paths (parser + typechecker) plus the codegen’s third path.

This duplication is the source of the “three lookup paths” bug class. Fixing it properly would require a unified resolve_name helper used by all three passes — a Phase 2 refactor.

No comments:

Post a Comment

🦆Part 5 — Looking Forward What Phase 1 has 75 tests passing on both backends Structs , struct params, arrays of structs, local structs...