path: root/docs/grammar.md

# 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 ) }
```