dodo
A programming language for the TRS-80 Color Computer
Star 0
Fork 0
Watch
dodo docs grammar.md
12 kB · 269 lines
Markdown
at main

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 #

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 #

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 #

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                  (* &region 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<Unit, E> — 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 #

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 
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] #

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.