🦆 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/&Bforms 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_assertguarding 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;
nextis the active lookup chain — it changes as scopes are pushed and popped.all_nextis the master allocation chain — never modified after insertion. This is howsymtable_freeiterates all symbols for cleanup.headpoints to the current scope’s head.all_headpoints 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 flowparser_function.c— function declarations, calls, returnsparser_struct.c— struct definitionsparser_array.c— array accessparser_select.c— SELECT CASEparser_serialize.c— SERIALIZE / DESERIALIZEparser_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):
.(field access) — 12[(array subscript) — 11*/%— 10+-— 9<<>>— 8<<=>>=— 7==!=— 6&— 5^— 4|— 3&&— 2||— 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:
- Annotates every expression node with
evalTypeso codegen can trust it without re-deriving. - Validates type compatibility and increments
g_error_counton mismatch.
Key rules:
BOOLcannot appear in arithmetic.STRING+is only valid insidePRINT(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