# Dodo Grammar Sketch The full surface as designed so far. Productions marked **[post-slice]** are reserved (keywords lexed, syntax settled) but not implemented in the vertical slice. Everything unmarked is slice scope. Notation: EBNF-ish. `*` zero-or-more, `?` optional, `|` alternation, `( )` grouping, quoted strings are literal tokens, UPPERCASE names are token classes. The grammar is LL(2)-friendly: every production is distinguishable by at most two tokens of lookahead, so a hand-written recursive-descent parser needs no backtracking. ## 1. Lexical grammar ```ebnf comment = "#" (any char except newline)* (* no block comments *) lower_ident = [a-z_] [a-z0-9_]* (* values, functions, regions *) upper_ident = [A-Z] [A-Za-z0-9]* (* types, variant constructors *) upper_snake = [A-Z] [A-Z0-9_]* "_" [A-Z0-9_]* (* consts; disjoint from upper_ident via the "_" *) int_literal = dec_literal | hex_literal | bin_literal dec_literal = [0-9] [0-9_]* hex_literal = "0x" [0-9A-Fa-f] [0-9A-Fa-f_]* bin_literal = "0b" [01] [01_]* (* handy for VDG bit patterns *) keywords = "fn" | "let" | "var" | "const" | "at" | "if" | "else" | "while" | "loop" | "for" | "in" | "as" | "return" | "true" | "false" | "and" | "or" | "not" | "type" | "match" | "arena" | "panic" (* reserved now *) operators = "+" | "-" | "*" | "/" | "%" | "+%" | "-%" | "*%" | "==" | "!=" | "<" | "<=" | ">" | ">=" | "&" | "|" | "^" | "<<" | ">>" | "=" | "->" | "=>" | ".." | "." | "?" | "," | ";" | "(" | ")" | "[" | "]" | "{" | "}" | ":" | "<" | ">" (* ";" appears only inside "[T; N]" / "[expr; N]" — it is never a statement terminator *) ``` ### Statement termination (Option C) The lexer emits a synthetic `TERM` token at a newline **only if** all of: - (a) not enclosed in `(...)` or `[...]` (tracked by a bracket-depth counter; `{...}` does **not** suppress `TERM` — braces are blocks) - (b) the previous token **can end a statement** — the exact set: identifier, integer literal, `true`, `false`, `)`, `]`, `}`, `?`, `return` (bare `return` is a complete statement, so `return⏎ x = 5` is two statements — `return expr` must start `expr` on the same line). A line ending in any other token (binary operators, `,`, `=`, `=>`, `{`, keywords like `if`/`in`/`as`, ...) is an unambiguous continuation, since no statement can end with one. - (c) the next token **can begin a statement** — i.e. it is *not* one of: `.`, `?`, `|`, `)`, `]`, `}`, `else`, `..`, or a binary-only operator (`/`, `%`, `+%`, `-%`, `*%`, `==`, `!=`, `<=`, `>=`, `<<`, `>>`, `^`, `and`, `or`) The dual-role tokens (`-`, `*`, `&`, `(`, `[`, plus the never-prefix but error-prone `+`, `<`, `>`) are deliberately excluded from the *leading* set (c): a line starting with one of them is always a new statement — `*ptr = 5` after a complete expression can never be silently absorbed as multiplication. In the *trailing* direction they're harmless: a line ending in `-` can only be a continuation, and rule (b) already covers it. Multiple blank lines produce at most one `TERM`; rules (b) and (c) make a `TERM` after `{` or before `}` impossible, which is what gives blocks their tail expression. ## 2. Module structure ```ebnf module = item* item = fn_decl | global_decl | const_decl | type_decl global_decl = "var" lower_ident ":" type ( at_clause | "=" expr ) TERM at_clause = "at" int_literal (* MMIO: no init, no storage *) const_decl = "const" const_name ":" type "=" const_expr TERM const_name = upper_snake | upper_ident | lower_ident (* convention is SCREAMING_CASE; a single word like COLS lexes as upper_ident — fine, decl position disambiguates. In expressions, a screaming-case name resolves as a const *) fn_decl = "fn" lower_ident generic_params? "(" param_list? ")" ( "->" type )? block generic_params = "<" generic_param ( "," generic_param )* ">" generic_param = upper_ident | lower_ident (* type param [post-slice] | region param *) param_list = param ( "," param )* ","? param = lower_ident ":" type type_decl = "type" upper_ident generic_params? "=" type_body TERM type_body = record_body | sum_body record_body = "{" field ( "," field )* ","? "}" field = lower_ident ":" type sum_body = "|"? variant ( "|" variant )* variant = upper_ident variant_payload? variant_payload = "(" type ( "," type )* ")" | record_body ``` ## 3. Types ```ebnf type = named_type | array_type | pointer_type | never_type named_type = upper_ident type_args? type_args = "<" type_arg ( "," type_arg )* ">" type_arg = type | lower_ident (* type [post-slice] | region *) array_type = "[" type ";" const_expr "]" pointer_type = "&" lower_ident type (* ®ion T *) never_type = "Never" (* just a named type; listed for emphasis *) ``` Slice primitives: `Uint8`, `Int8`, `Uint16`, `Int16`, `Bool`, `Unit`, `Never`. - **`Unit`** (Rust's `()`): exactly one value; the type of blocks and functions with no tail expression. `fn f(...)` with no `->` means `-> Unit`. Spellable as an ordinary type name — useful for e.g. `Result` — but has no literal; it only arises implicitly. - **`Never`** (Rust's `!`): zero values; the type of expressions that provably don't proceed — `loop { }` without break, `panic(...)`, `return` in expression position. Coerces to every type (a value that can't exist may claim any type), which is what lets a `match` arm `panic` while the other arms produce a real value. `fn main() -> Never` is the ROM-target entry signature; `fn main()` (i.e. `-> Unit`) is the disk-target one. ## 4. Statements and blocks ```ebnf block = "{" stmt* "}" (* the last stmt in a block, if an expression, is the block's value; otherwise the block has type Unit *) stmt = let_stmt | var_stmt | assign_stmt | while_stmt | for_stmt | loop_stmt | return_stmt | arena_stmt | expr_stmt let_stmt = "let" pattern ( ":" type )? "=" expr TERM var_stmt = "var" lower_ident ( ":" type )? "=" expr TERM assign_stmt = place "=" expr TERM place = lower_ident ( "[" expr "]" | "." lower_ident )* (* also "*" place for pointer stores [post-slice] *) while_stmt = "while" expr block TERM? loop_stmt = "loop" block TERM? (* type: Never *) for_stmt = "for" for_binding "in" expr block TERM? for_binding = "var"? pattern (* "var" = by-ref mutable *) return_stmt = "return" expr? TERM arena_stmt = "arena" lower_ident block TERM? (* [post-slice] *) expr_stmt = expr TERM ``` In the slice, `pattern` is just `lower_ident | "_"`; the full pattern grammar (§6) arrives with `match`. ## 5. Expressions Precedence, loosest to tightest. Each level is left-associative unless noted. This ordering deliberately fixes C's mistake: bitwise operators bind **tighter** than comparisons, so `raw & 0x10 != 0` means `(raw & 0x10) != 0`. | # | Level | Operators | Notes | |---|------------|--------------------------------|-------| | 1 | range | `..` | non-associative | | 2 | or | `or` | short-circuit | | 3 | and | `and` | short-circuit | | 4 | not | `not` | prefix | | 5 | comparison | `==` `!=` `<` `<=` `>` `>=` | **non-chaining**: `a < b < c` is a parse error | | 6 | bit-or | `\|` | | | 7 | bit-xor | `^` | | | 8 | bit-and | `&` | | | 9 | shift | `<<` `>>` | | | 10 | additive | `+` `-` `+%` `-%` | checked / wrapping | | 11 | multiplicative | `*` `/` `%` `*%` | see division note | | 12 | cast | `as` Type | postfix, repeatable | | 13 | unary | `-` `*`(deref) | deref [post-slice] | | 14 | postfix | call `(...)`, index `[...]`, field/UFCS `.x` / `.f(...)`, `?` | `?` [post-slice] | | 15 | primary | literals, ident, `(expr)`, `[...]` array literals, `if`, `match`, block | | ```ebnf expr = range_expr range_expr = or_expr ( ".." or_expr )? or_expr = and_expr ( "or" and_expr )* and_expr = not_expr ( "and" not_expr )* not_expr = "not" not_expr | cmp_expr cmp_expr = bitor_expr ( cmp_op bitor_expr )? (* at most one: non-chaining *) cmp_op = "==" | "!=" | "<" | "<=" | ">" | ">=" bitor_expr = bitxor_expr ( "|" bitxor_expr )* bitxor_expr = bitand_expr ( "^" bitand_expr )* bitand_expr = shift_expr ( "&" shift_expr )* shift_expr = add_expr ( ( "<<" | ">>" ) add_expr )* add_expr = mul_expr ( ( "+" | "-" | "+%" | "-%" ) mul_expr )* mul_expr = cast_expr ( ( "*" | "/" | "%" | "*%" ) cast_expr )* cast_expr = unary_expr ( "as" type )* unary_expr = "-" unary_expr | "*" unary_expr | postfix_expr postfix_expr = primary_expr postfix* postfix = "(" arg_list? ")" (* call *) | "[" expr "]" (* index *) | "." lower_ident ( "(" arg_list? ")" )? (* field / UFCS call *) | "?" (* [post-slice] *) arg_list = expr ( "," expr )* ","? primary_expr = int_literal | "true" | "false" | lower_ident | upper_ident struct_or_variant? (* [post-slice] *) | "(" expr ")" | array_literal | if_expr | match_expr (* [post-slice] *) | block array_literal = "[" ( expr ( "," expr )* ","? )? "]" | "[" expr ";" const_expr "]" (* repeat: [0x00; 512] *) if_expr = "if" expr block ( "else" ( if_expr | block ) )? (* also "if" "let" pattern "=" expr block ... [post-slice] *) struct_or_variant = "{" field_init ( "," field_init )* ","? "}" | "(" arg_list ")" field_init = lower_ident ":" expr ``` `upper_ident` in expression position (bare variant like `None`, or `Point { x: 1, y: 2 }`) is the one place needing 2-token lookahead, to distinguish a construction from a comparison like `x < LIMIT`. That, plus `if cond { ... }` vs. struct literals in scrutinee position, is resolved Rust-style: **no struct literals in `if`/`while`/`for`/`match` headers** without parens. ## 6. Patterns [post-slice] ```ebnf pattern = "_" | lower_ident | int_literal | upper_ident pattern_payload? (* variant *) | "(" pattern ( "," pattern )* ")" (* tuple, if tuples happen *) pattern_payload = "(" pattern ( "," pattern )* ")" | "{" field_pat ( "," field_pat )* ","? "}" field_pat = lower_ident ( ":" pattern )? (* shorthand binds the name *) match_expr = "match" expr "{" match_arm ( "," match_arm )* ","? "}" match_arm = pattern "=>" ( expr | block ) ``` ## 7. Micro-decisions this grammar forced (review these) 1. **Boolean operators are keywords: `and` / `or` / `not`.** The examples never used one. Words fit the ML lean, and keeping `&`/`|` exclusively bitwise avoids the C-family `&`/`&&` confusion in what will be a very bitwise-heavy language. `!` stays unused (free for future use). 2. **Bitwise binds tighter than comparison** (see §5) — deliberate break from C, matches how the examples were already written. 3. **Comparisons are non-chaining.** `a < b < c` is a parse error, not a `Bool`-compared-to-`Uint8` type error. Cheap in a hand parser, better diagnostics. 4. **`/` and `%` exist but the 6809 has no divide instruction** — every `/` is a software routine call (tens of cycles minimum). Grammar keeps them; the compiler strength-reduces powers of two to shifts. Worth a future lint ("division by non-constant on this target"). 5. **`0b` binary literals added** — near-mandatory ergonomics for sprite rows and PIA masks. 6. **No struct literals in control-flow headers** (Rust's rule) to keep `if x { }` unambiguous. 7. **Casts are postfix-repeatable** (`x as Uint16 as Int16` parses; the typechecker can still reject weird chains). 8. **Unary `+` doesn't exist.** One less dual-role token. ```