diff options
| -rw-r--r-- | docs/grammar.md | 253 |
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 ) } +``` |