1 files changed, 253 insertions, 0 deletions
diff --git a/docs/grammar.md b/docs/grammar.md
new file mode 100644
index 0000000..eee54e2
--- /dev/null
+++ b/docs/grammar.md
@@ -0,0 +1,253 @@
+# Catskill Language Grammar
+
+Catskill is a low-level systems programming language inspired by recent modern
+developments in language design.
+This document aims to describe the grammar as currently implemented by the
+initial bootstrapping compiler's (named "catboot") parsing pass.
+It represents the current reality of the language, as it is now.
+This does mean that the grammar will change in the future!
+
+Rule names match the kinds in `boot/tree.c` so this doc can double as a
+reference when reading the parser.
+The production naming as defined in this grammar is mirrored as closely
+as possible by the actual parse tree the compiler produces, and can be
+used as a reference into the tree and the parser.
+
+Also, please note that here we do not encode every single grammar production
+into the exact mathematical language grammar, some things are enforced by the
+parser and the passes further on on the fly, like associativity or precedence,
+or even some construct which are not allowed to occur in some specific places.
+This saves us some code and also allows for slightly easier diagnostical messages
+for some cases. (This document isn't really an exercise in scientific rigor,
+it's supposed to be a reference for the actual practical implementation!)
+
+## Notation
+
+The grammar uses a relaxed EBNF flavour, because following the exact syntax is annoying: :)
+
+- `production = rule` defines single a production (possibly over multiple lines).
+- `a | b` is alternation; `a b` is concatenation.
+- `[ a ]` makes `a` optional.
+- `{ a }` is zero or more repetitions of `a`.
+- `( a )` groups alternatives.
+- `"text"` is a literal token.
+- UPPERCASE names are terminal tokens produced by lexing.
+- `#` starts a line-comment.
+
+## Lexical grammar
+
+```ebnf
+source = { token } EOF
+token = WHITESPACE
+	| COMMENT
+	| NEWLINE
+	| symbol
+	| word
+	| literal
+	| NAME
+
+# whitespace and comments are completely discarded.
+WHITESPACE = " " | "\t"
+COMMENT = "#" { not_newline }
+# newlines can terminate statements.
+NEWLINE = "\n"
+
+# words and names share a single lexical shape.
+# we match any lexeme against the keywords first, anything else becomes a name.
+word_or_name = ident_char { ident_tail_char }
+ident_char = "A".."Z" | "a".."z" | "_"
+ident_tail_char = ident_char | "0".."9"
+
+word = "fun" | "if" | "else" | "for" | "loop"
+	| "break" | "continue" | "defer" | "switch" | "return"
+	| "var" | "let"
+	| "type" | "variant" | "class"
+	| "true" | "false"
+
+# literals
+literal = INT_LITERAL | FLOAT_LITERAL | STRING_LITERAL
+INT_LITERAL = digit { digit }
+FLOAT_LITERAL = digit { digit } "." digit { digit }
+STRING_LITERAL = '"' { not_quote } '"'
+digit = "0".."9"
+
+# multi-character symbols are matched eagerly, e.g. "<<=" before "<<".
+symbol = "(" | ")" | "{" | "}" | "[" | "]" | ","
+	| "." | ".." | "..."
+	| "!" | "?" | "~" | "|" | "^"
+	| "+" | "-" | "*" | "/" | "%" | "&" | "="
+	| "++" | "--" | "**"
+	| "&&" | "||" | "==" | "!=" | "<" | "<=" | ">" | ">="
+	| "<<" | ">>"
+	| "+=" | "-=" | "*=" | "/=" | "%="
+	| "&&=" | "||="
+	| "&=" | "|=" | "^="
+	| "<<=" | ">>="
+```
+
+## Tree grammar
+
+```ebnf
+# a translation unit is a stream of statements at the top level.
+unit = { statement statement_end }
+statement_end = NEWLINE | EOF
+
+statement = statement_declaration
+	| statement_conditional
+	| statement_loop
+	| statement_block
+	| statement_return
+	| statement_break
+	| statement_continue
+	| statement_defer
+	| statement_pragma
+	| statement_expression
+
+# declarations
+
+statement_declaration = ( "var" | "let" ) bare_declaration
+bare_declaration = NAME { "," NAME } type "=" expression
+
+# statements
+
+statement_conditional = "if" expression block
+	{ "else" "if" expression block }
+	[ "else" block ]
+
+statement_loop = statement_loop_for_each
+	| statement_loop_c
+	| statement_loop_while
+	| statement_loop_endless
+statement_loop_for_each = "for" bare_declaration block
+statement_loop_c = "for" bare_declaration "," expression "," expression block
+statement_loop_while = "loop" expression block
+statement_loop_endless = "loop" block
+
+statement_block = block
+statement_return = "return" [ expression ]
+statement_break = "break"
+statement_continue = "continue"
+statement_defer = "defer" ( block | expression )
+statement_expression = expression
+
+# pragmas
+# one pragma statement may carry multiple.
+statement_pragma = "|" pragma { "," pragma }
+pragma = NAME { pragma_argument }
+pragma_argument = INT_LITERAL | FLOAT_LITERAL | STRING_LITERAL | NAME
+
+# blocks
+# the final statement may omit terminator.
+block = "{" { statement statement_end } [ statement ] "}"
+
+# expressions
+
+expression = expression_binary_operation
+expression_binary_operation = expression_unary_operation
+	[ binary_op expression_binary_operation ]
+
+# unary
+expression_unary_operation = unary_op expression_unary_operation
+	| ( "++" | "--" ) expression_unary_operation
+	| expression_postfix
+
+unary_op = "-" | "!" | "~" | "&" | "*"
+
+# postfix chain
+expression_postfix = expression_primary { postfix_tail }
+postfix_tail = expression_call
+	| expression_construct
+	| expression_subscript
+	| expression_member
+	| expression_try
+	| expression_must
+	| expression_increment_decrement
+
+expression_call = "(" argument_group ")"
+expression_construct = "{" argument_group "}" # forbidden in statement-clause contexts!
+expression_subscript = "[" expression "]"
+expression_member = "." NAME
+expression_try = "?"
+expression_must = "!"
+expression_increment_decrement = "++" | "--" # postfix form
+
+argument_group = argument { "," argument }
+argument = [ NAME "=" ] expression
+
+# primary expressions
+expression_primary = expression_name
+	| expression_integer_literal
+	| expression_float_literal
+	| expression_string_literal
+	| expression_boolean_literal
+	| expression_group
+	| expression_function
+	| expression_type
+
+expression_name = NAME
+expression_integer_literal = INT_LITERAL
+expression_float_literal = FLOAT_LITERAL
+expression_string_literal = STRING_LITERAL
+expression_boolean_literal = "true" | "false"
+expression_group = "(" expression ")"
+expression_function = "fun" function_header block
+
+expression_type = "type" type
+	| "variant" "{" variant_cases "}"
+	| "class" "{" class_methods "}"
+
+# binary operators, weakest to strongest
+# precedence and associativity are resolved as an additional step,
+# the grammar does not carry this information:
+# * `..` is non-associative
+# * right-associative: `=` (& compounds) and **`
+# * left-associative: everything else
+binary_op = "=" | "+=" | "-=" | "*=" | "/=" | "%=" # 1 (precedence)
+	| "&&=" | "||="
+	| "&=" | "|=" | "^=" | "<<=" | ">>="
+	| ".." # 2
+	| "||" # 3
+	| "&&" # 4
+	| "|" # 5
+	| "^" # 6
+	| "&" # 7
+	| "==" | "!=" # 8
+	| "<" | "<=" | ">" | ">=" # 9
+	| "<<" | ">>" # 10
+	| "+" | "-" # 11
+	| "*" | "/" | "%" # 12
+	| "**" # 13
+
+# types
+
+type = type_inner [ "?" ] # maybe `?`
+type_inner = type_name
+	| type_variant
+	| type_class
+	| type_function
+	| type_structure
+	| type_tuple
+	| type_array
+	| type_map
+	| type_reference
+
+type_name = NAME
+type_variant = "variant" "{" variant_cases "}"
+type_class = "class" "{" class_methods "}"
+type_function = "fun" function_header
+type_structure = "{" struct_fields "}"
+type_tuple = "(" [ type { "," type } ] ")"
+type_array = "[" type "]"
+type_map = "[" type "=" type "]"
+type_reference = "&" type
+
+# common shapes
+
+function_header = "(" [ parameter { "," parameter } ] ")" [ type ]
+parameter = [ "..." ] NAME [ type ]
+
+struct_fields = { NAME type ( "," | NEWLINE ) }
+variant_cases = { variant_case ( "," | NEWLINE ) }
+variant_case = NAME [ type ]
+class_methods = { NAME function_header ( "," | NEWLINE ) }
+```