src/doc/grammar.md

   1 # **This is a work in progress**
   2
   3 % The Rust Grammar
   4
   5 # Introduction
   6
   7 This document is the primary reference for the Rust programming language grammar. It
   8 provides only one kind of material:
   9
  10   - Chapters that formally define the language grammar and, for each
  11     construct.
  12
  13 This document does not serve as an introduction to the language. Background
  14 familiarity with the language is assumed. A separate [guide] is available to
  15 help acquire such background familiarity.
  16
  17 This document also does not serve as a reference to the [standard] library
  18 included in the language distribution. Those libraries are documented
  19 separately by extracting documentation attributes from their source code. Many
  20 of the features that one might expect to be language features are library
  21 features in Rust, so what you're looking for may be there, not here.
  22
  23 [guide]: guide.html
  24 [standard]: std/index.html
  25
  26 # Notation
  27
  28 Rust's grammar is defined over Unicode codepoints, each conventionally denoted
  29 `U+XXXX`, for 4 or more hexadecimal digits `X`. _Most_ of Rust's grammar is
  30 confined to the ASCII range of Unicode, and is described in this document by a
  31 dialect of Extended Backus-Naur Form (EBNF), specifically a dialect of EBNF
  32 supported by common automated LL(k) parsing tools such as `llgen`, rather than
  33 the dialect given in ISO 14977. The dialect can be defined self-referentially
  34 as follows:
  35
  36 ```antlr
  37 grammar : rule + ;
  38 rule    : nonterminal ':' productionrule ';' ;
  39 productionrule : production [ '|' production ] * ;
  40 production : term * ;
  41 term : element repeats ;
  42 element : LITERAL | IDENTIFIER | '[' productionrule ']' ;
  43 repeats : [ '*' | '+' ] NUMBER ? | NUMBER ? | '?' ;
  44 ```
  45
  46 Where:
  47
  48 - Whitespace in the grammar is ignored.
  49 - Square brackets are used to group rules.
  50 - `LITERAL` is a single printable ASCII character, or an escaped hexadecimal
  51   ASCII code of the form `\xQQ`, in single quotes, denoting the corresponding
  52   Unicode codepoint `U+00QQ`.
  53 - `IDENTIFIER` is a nonempty string of ASCII letters and underscores.
  54 - The `repeat` forms apply to the adjacent `element`, and are as follows:
  55   - `?` means zero or one repetition
  56   - `*` means zero or more repetitions
  57   - `+` means one or more repetitions
  58   - NUMBER trailing a repeat symbol gives a maximum repetition count
  59   - NUMBER on its own gives an exact repetition count
  60
  61 This EBNF dialect should hopefully be familiar to many readers.
  62
  63 ## Unicode productions
  64
  65 A few productions in Rust's grammar permit Unicode codepoints outside the ASCII
  66 range. We define these productions in terms of character properties specified
  67 in the Unicode standard, rather than in terms of ASCII-range codepoints. The
  68 section [Special Unicode Productions](#special-unicode-productions) lists these
  69 productions.
  70
  71 ## String table productions
  72
  73 Some rules in the grammar &mdash; notably [unary
  74 operators](#unary-operator-expressions), [binary
  75 operators](#binary-operator-expressions), and [keywords](#keywords) &mdash; are
  76 given in a simplified form: as a listing of a table of unquoted, printable
  77 whitespace-separated strings. These cases form a subset of the rules regarding
  78 the [token](#tokens) rule, and are assumed to be the result of a
  79 lexical-analysis phase feeding the parser, driven by a DFA, operating over the
  80 disjunction of all such string table entries.
  81
  82 When such a string enclosed in double-quotes (`"`) occurs inside the grammar,
  83 it is an implicit reference to a single member of such a string table
  84 production. See [tokens](#tokens) for more information.
  85
  86 # Lexical structure
  87
  88 ## Input format
  89
  90 Rust input is interpreted as a sequence of Unicode codepoints encoded in UTF-8.
  91 Most Rust grammar rules are defined in terms of printable ASCII-range
  92 codepoints, but a small number are defined in terms of Unicode properties or
  93 explicit codepoint lists. [^inputformat]
  94
  95 [^inputformat]: Substitute definitions for the special Unicode productions are
  96   provided to the grammar verifier, restricted to ASCII range, when verifying the
  97   grammar in this document.
  98
  99 ## Special Unicode Productions
 100
 101 The following productions in the Rust grammar are defined in terms of Unicode
 102 properties: `ident`, `non_null`, `non_star`, `non_eol`, `non_slash_or_star`,
 103 `non_single_quote` and `non_double_quote`.
 104
 105 ### Identifiers
 106
 107 The `ident` production is any nonempty Unicode string of the following form:
 108
 109 - The first character has property `XID_start`
 110 - The remaining characters have property `XID_continue`
 111
 112 that does _not_ occur in the set of [keywords](#keywords).
 113
 114 > **Note**: `XID_start` and `XID_continue` as character properties cover the
 115 > character ranges used to form the more familiar C and Java language-family
 116 > identifiers.
 117
 118 ### Delimiter-restricted productions
 119
 120 Some productions are defined by exclusion of particular Unicode characters:
 121
 122 - `non_null` is any single Unicode character aside from `U+0000` (null)
 123 - `non_eol` is `non_null` restricted to exclude `U+000A` (`'\n'`)
 124 - `non_star` is `non_null` restricted to exclude `U+002A` (`*`)
 125 - `non_slash_or_star` is `non_null` restricted to exclude `U+002F` (`/`) and `U+002A` (`*`)
 126 - `non_single_quote` is `non_null` restricted to exclude `U+0027`  (`'`)
 127 - `non_double_quote` is `non_null` restricted to exclude `U+0022` (`"`)
 128
 129 ## Comments
 130
 131 ```antlr
 132 comment : block_comment | line_comment ;
 133 block_comment : "/*" block_comment_body * "*/" ;
 134 block_comment_body : [block_comment | character] * ;
 135 line_comment : "//" non_eol * ;
 136 ```
 137
 138 **FIXME:** add doc grammar?
 139
 140 ## Whitespace
 141
 142 ```antlr
 143 whitespace_char : '\x20' | '\x09' | '\x0a' | '\x0d' ;
 144 whitespace : [ whitespace_char | comment ] + ;
 145 ```
 146
 147 ## Tokens
 148
 149 ```antlr
 150 simple_token : keyword | unop | binop ;
 151 token : simple_token | ident | literal | symbol | whitespace token ;
 152 ```
 153
 154 ### Keywords
 155
 156 <p id="keyword-table-marker"></p>
 157
 158 |          |          |          |          |        |
 159 |----------|----------|----------|----------|--------|
 160 | abstract | alignof  | as       | be       | box    |
 161 | break    | const    | continue | crate    | do     |
 162 | else     | enum     | extern   | false    | final  |
 163 | fn       | for      | if       | impl     | in     |
 164 | let      | loop     | match    | mod      | move   |
 165 | mut      | offsetof | once     | override | priv   |
 166 | proc     | pub      | pure     | ref      | return |
 167 | sizeof   | static   | self     | struct   | super  |
 168 | true     | trait    | type     | typeof   | unsafe |
 169 | unsized  | use      | virtual  | where    | while  |
 170 | yield    |          |          |          |        |
 171
 172
 173 Each of these keywords has special meaning in its grammar, and all of them are
 174 excluded from the `ident` rule.
 175
 176 ### Literals
 177
 178 ```antlr
 179 lit_suffix : ident;
 180 literal : [ string_lit | char_lit | byte_string_lit | byte_lit | num_lit ] lit_suffix ?;
 181 ```
 182
 183 #### Character and string literals
 184
 185 ```antlr
 186 char_lit : '\x27' char_body '\x27' ;
 187 string_lit : '"' string_body * '"' | 'r' raw_string ;
 188
 189 char_body : non_single_quote
 190           | '\x5c' [ '\x27' | common_escape | unicode_escape ] ;
 191
 192 string_body : non_double_quote
 193             | '\x5c' [ '\x22' | common_escape | unicode_escape ] ;
 194 raw_string : '"' raw_string_body '"' | '#' raw_string '#' ;
 195
 196 common_escape : '\x5c'
 197               | 'n' | 'r' | 't' | '0'
 198               | 'x' hex_digit 2
 199 unicode_escape : 'u' hex_digit 4
 200                | 'U' hex_digit 8 ;
 201
 202 hex_digit : 'a' | 'b' | 'c' | 'd' | 'e' | 'f'
 203           | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
 204           | dec_digit ;
 205 oct_digit : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' ;
 206 dec_digit : '0' | nonzero_dec ;
 207 nonzero_dec: '1' | '2' | '3' | '4'
 208            | '5' | '6' | '7' | '8' | '9' ;
 209 ```
 210
 211 #### Byte and byte string literals
 212
 213 ```antlr
 214 byte_lit : "b\x27" byte_body '\x27' ;
 215 byte_string_lit : "b\x22" string_body * '\x22' | "br" raw_byte_string ;
 216
 217 byte_body : ascii_non_single_quote
 218           | '\x5c' [ '\x27' | common_escape ] ;
 219
 220 byte_string_body : ascii_non_double_quote
 221             | '\x5c' [ '\x22' | common_escape ] ;
 222 raw_byte_string : '"' raw_byte_string_body '"' | '#' raw_byte_string '#' ;
 223
 224 ```
 225
 226 #### Number literals
 227
 228 ```antlr
 229 num_lit : nonzero_dec [ dec_digit | '_' ] * float_suffix ?
 230         | '0' [       [ dec_digit | '_' ] * float_suffix ?
 231               | 'b'   [ '1' | '0' | '_' ] +
 232               | 'o'   [ oct_digit | '_' ] +
 233               | 'x'   [ hex_digit | '_' ] +  ] ;
 234
 235 float_suffix : [ exponent | '.' dec_lit exponent ? ] ? ;
 236
 237 exponent : ['E' | 'e'] ['-' | '+' ] ? dec_lit ;
 238 dec_lit : [ dec_digit | '_' ] + ;
 239 ```
 240
 241 #### Boolean literals
 242
 243 **FIXME:** write grammar
 244
 245 The two values of the boolean type are written `true` and `false`.
 246
 247 ### Symbols
 248
 249 ```antlr
 250 symbol : "::" "->"
 251        | '#' | '[' | ']' | '(' | ')' | '{' | '}'
 252        | ',' | ';' ;
 253 ```
 254
 255 Symbols are a general class of printable [token](#tokens) that play structural
 256 roles in a variety of grammar productions. They are catalogued here for
 257 completeness as the set of remaining miscellaneous printable tokens that do not
 258 otherwise appear as [unary operators](#unary-operator-expressions), [binary
 259 operators](#binary-operator-expressions), or [keywords](#keywords).
 260
 261 ## Paths
 262
 263 ```antlr
 264 expr_path : [ "::" ] ident [ "::" expr_path_tail ] + ;
 265 expr_path_tail : '<' type_expr [ ',' type_expr ] + '>'
 266                | expr_path ;
 267
 268 type_path : ident [ type_path_tail ] + ;
 269 type_path_tail : '<' type_expr [ ',' type_expr ] + '>'
 270                | "::" type_path ;
 271 ```
 272
 273 # Syntax extensions
 274
 275 ## Macros
 276
 277 ```antlr
 278 expr_macro_rules : "macro_rules" '!' ident '(' macro_rule * ')' ;
 279 macro_rule : '(' matcher * ')' "=>" '(' transcriber * ')' ';' ;
 280 matcher : '(' matcher * ')' | '[' matcher * ']'
 281         | '{' matcher * '}' | '$' ident ':' ident
 282         | '$' '(' matcher * ')' sep_token? [ '*' | '+' ]
 283         | non_special_token ;
 284 transcriber : '(' transcriber * ')' | '[' transcriber * ']'
 285             | '{' transcriber * '}' | '$' ident
 286             | '$' '(' transcriber * ')' sep_token? [ '*' | '+' ]
 287             | non_special_token ;
 288 ```
 289
 290 # Crates and source files
 291
 292 **FIXME:** grammar? What production covers #![crate_id = "foo"] ?
 293
 294 # Items and attributes
 295
 296 **FIXME:** grammar?
 297
 298 ## Items
 299
 300 ```antlr
 301 item : mod_item | fn_item | type_item | struct_item | enum_item
 302      | static_item | trait_item | impl_item | extern_block ;
 303 ```
 304
 305 ### Type Parameters
 306
 307 **FIXME:** grammar?
 308
 309 ### Modules
 310
 311 ```antlr
 312 mod_item : "mod" ident ( ';' | '{' mod '}' );
 313 mod : [ view_item | item ] * ;
 314 ```
 315
 316 #### View items
 317
 318 ```antlr
 319 view_item : extern_crate_decl | use_decl ;
 320 ```
 321
 322 ##### Extern crate declarations
 323
 324 ```antlr
 325 extern_crate_decl : "extern" "crate" crate_name
 326 crate_name: ident | ( string_lit as ident )
 327 ```
 328
 329 ##### Use declarations
 330
 331 ```antlr
 332 use_decl : "pub" ? "use" [ path "as" ident
 333                           | path_glob ] ;
 334
 335 path_glob : ident [ "::" [ path_glob
 336                           | '*' ] ] ?
 337           | '{' path_item [ ',' path_item ] * '}' ;
 338
 339 path_item : ident | "mod" ;
 340 ```
 341
 342 ### Functions
 343
 344 **FIXME:** grammar?
 345
 346 #### Generic functions
 347
 348 **FIXME:** grammar?
 349
 350 #### Unsafety
 351
 352 **FIXME:** grammar?
 353
 354 ##### Unsafe functions
 355
 356 **FIXME:** grammar?
 357
 358 ##### Unsafe blocks
 359
 360 **FIXME:** grammar?
 361
 362 #### Diverging functions
 363
 364 **FIXME:** grammar?
 365
 366 ### Type definitions
 367
 368 **FIXME:** grammar?
 369
 370 ### Structures
 371
 372 **FIXME:** grammar?
 373
 374 ### Constant items
 375
 376 ```antlr
 377 const_item : "const" ident ':' type '=' expr ';' ;
 378 ```
 379
 380 ### Static items
 381
 382 ```antlr
 383 static_item : "static" ident ':' type '=' expr ';' ;
 384 ```
 385
 386 #### Mutable statics
 387
 388 **FIXME:** grammar?
 389
 390 ### Traits
 391
 392 **FIXME:** grammar?
 393
 394 ### Implementations
 395
 396 **FIXME:** grammar?
 397
 398 ### External blocks
 399
 400 ```antlr
 401 extern_block_item : "extern" '{' extern_block '}' ;
 402 extern_block : [ foreign_fn ] * ;
 403 ```
 404
 405 ## Visibility and Privacy
 406
 407 **FIXME:** grammar?
 408
 409 ### Re-exporting and Visibility
 410
 411 **FIXME:** grammar?
 412
 413 ## Attributes
 414
 415 ```antlr
 416 attribute : "#!" ? '[' meta_item ']' ;
 417 meta_item : ident [ '=' literal
 418                   | '(' meta_seq ')' ] ? ;
 419 meta_seq : meta_item [ ',' meta_seq ] ? ;
 420 ```
 421
 422 # Statements and expressions
 423
 424 ## Statements
 425
 426 **FIXME:** grammar?
 427
 428 ### Declaration statements
 429
 430 **FIXME:** grammar?
 431
 432 A _declaration statement_ is one that introduces one or more *names* into the
 433 enclosing statement block. The declared names may denote new slots or new
 434 items.
 435
 436 #### Item declarations
 437
 438 **FIXME:** grammar?
 439
 440 An _item declaration statement_ has a syntactic form identical to an
 441 [item](#items) declaration within a module. Declaring an item &mdash; a
 442 function, enumeration, structure, type, static, trait, implementation or module
 443 &mdash; locally within a statement block is simply a way of restricting its
 444 scope to a narrow region containing all of its uses; it is otherwise identical
 445 in meaning to declaring the item outside the statement block.
 446
 447 #### Slot declarations
 448
 449 ```antlr
 450 let_decl : "let" pat [':' type ] ? [ init ] ? ';' ;
 451 init : [ '=' ] expr ;
 452 ```
 453
 454 ### Expression statements
 455
 456 **FIXME:** grammar?
 457
 458 ## Expressions
 459
 460 **FIXME:** grammar?
 461
 462 #### Lvalues, rvalues and temporaries
 463
 464 **FIXME:** grammar?
 465
 466 #### Moved and copied types
 467
 468 **FIXME:** Do we want to capture this in the grammar as different productions?
 469
 470 ### Literal expressions
 471
 472 **FIXME:** grammar?
 473
 474 ### Path expressions
 475
 476 **FIXME:** grammar?
 477
 478 ### Tuple expressions
 479
 480 **FIXME:** grammar?
 481
 482 ### Unit expressions
 483
 484 **FIXME:** grammar?
 485
 486 ### Structure expressions
 487
 488 ```antlr
 489 struct_expr : expr_path '{' ident ':' expr
 490                       [ ',' ident ':' expr ] *
 491                       [ ".." expr ] '}' |
 492               expr_path '(' expr
 493                       [ ',' expr ] * ')' |
 494               expr_path ;
 495 ```
 496
 497 ### Block expressions
 498
 499 ```antlr
 500 block_expr : '{' [ view_item ] *
 501                  [ stmt ';' | item ] *
 502                  [ expr ] '}' ;
 503 ```
 504
 505 ### Method-call expressions
 506
 507 ```antlr
 508 method_call_expr : expr '.' ident paren_expr_list ;
 509 ```
 510
 511 ### Field expressions
 512
 513 ```antlr
 514 field_expr : expr '.' ident ;
 515 ```
 516
 517 ### Array expressions
 518
 519 ```antlr
 520 array_expr : '[' "mut" ? vec_elems? ']' ;
 521
 522 array_elems : [expr [',' expr]*] | [expr ',' ".." expr] ;
 523 ```
 524
 525 ### Index expressions
 526
 527 ```antlr
 528 idx_expr : expr '[' expr ']' ;
 529 ```
 530
 531 ### Unary operator expressions
 532
 533 **FIXME:** grammar?
 534
 535 ### Binary operator expressions
 536
 537 ```antlr
 538 binop_expr : expr binop expr ;
 539 ```
 540
 541 #### Arithmetic operators
 542
 543 **FIXME:** grammar?
 544
 545 #### Bitwise operators
 546
 547 **FIXME:** grammar?
 548
 549 #### Lazy boolean operators
 550
 551 **FIXME:** grammar?
 552
 553 #### Comparison operators
 554
 555 **FIXME:** grammar?
 556
 557 #### Type cast expressions
 558
 559 **FIXME:** grammar?
 560
 561 #### Assignment expressions
 562
 563 **FIXME:** grammar?
 564
 565 #### Compound assignment expressions
 566
 567 **FIXME:** grammar?
 568
 569 #### Operator precedence
 570
 571 The precedence of Rust binary operators is ordered as follows, going from
 572 strong to weak:
 573
 574 ```
 575 * / %
 576 as
 577 + -
 578 << >>
 579 &
 580 ^
 581 |
 582 < > <= >=
 583 == !=
 584 &&
 585 ||
 586 =
 587 ```
 588
 589 Operators at the same precedence level are evaluated left-to-right. [Unary
 590 operators](#unary-operator-expressions) have the same precedence level and it
 591 is stronger than any of the binary operators'.
 592
 593 ### Grouped expressions
 594
 595 ```antlr
 596 paren_expr : '(' expr ')' ;
 597 ```
 598
 599 ### Call expressions
 600
 601 ```antlr
 602 expr_list : [ expr [ ',' expr ]* ] ? ;
 603 paren_expr_list : '(' expr_list ')' ;
 604 call_expr : expr paren_expr_list ;
 605 ```
 606
 607 ### Lambda expressions
 608
 609 ```antlr
 610 ident_list : [ ident [ ',' ident ]* ] ? ;
 611 lambda_expr : '|' ident_list '|' expr ;
 612 ```
 613
 614 ### While loops
 615
 616 ```antlr
 617 while_expr : "while" no_struct_literal_expr '{' block '}' ;
 618 ```
 619
 620 ### Infinite loops
 621
 622 ```antlr
 623 loop_expr : [ lifetime ':' ] "loop" '{' block '}';
 624 ```
 625
 626 ### Break expressions
 627
 628 ```antlr
 629 break_expr : "break" [ lifetime ];
 630 ```
 631
 632 ### Continue expressions
 633
 634 ```antlr
 635 continue_expr : "continue" [ lifetime ];
 636 ```
 637
 638 ### For expressions
 639
 640 ```antlr
 641 for_expr : "for" pat "in" no_struct_literal_expr '{' block '}' ;
 642 ```
 643
 644 ### If expressions
 645
 646 ```antlr
 647 if_expr : "if" no_struct_literal_expr '{' block '}'
 648           else_tail ? ;
 649
 650 else_tail : "else" [ if_expr | if_let_expr
 651                    | '{' block '}' ] ;
 652 ```
 653
 654 ### Match expressions
 655
 656 ```antlr
 657 match_expr : "match" no_struct_literal_expr '{' match_arm * '}' ;
 658
 659 match_arm : attribute * match_pat "=>" [ expr "," | '{' block '}' ] ;
 660
 661 match_pat : pat [ '|' pat ] * [ "if" expr ] ? ;
 662 ```
 663
 664 ### If let expressions
 665
 666 ```antlr
 667 if_let_expr : "if" "let" pat '=' expr '{' block '}'
 668                else_tail ? ;
 669 else_tail : "else" [ if_expr | if_let_expr | '{' block '}' ] ;
 670 ```
 671
 672 ### While let loops
 673
 674 ```antlr
 675 while_let_expr : "while" "let" pat '=' expr '{' block '}' ;
 676 ```
 677
 678 ### Return expressions
 679
 680 ```antlr
 681 return_expr : "return" expr ? ;
 682 ```
 683
 684 # Type system
 685
 686 **FIXME:** is this entire chapter relevant here? Or should it all have been covered by some production already?
 687
 688 ## Types
 689
 690 ### Primitive types
 691
 692 **FIXME:** grammar?
 693
 694 #### Machine types
 695
 696 **FIXME:** grammar?
 697
 698 #### Machine-dependent integer types
 699
 700 **FIXME:** grammar?
 701
 702 ### Textual types
 703
 704 **FIXME:** grammar?
 705
 706 ### Tuple types
 707
 708 **FIXME:** grammar?
 709
 710 ### Array, and Slice types
 711
 712 **FIXME:** grammar?
 713
 714 ### Structure types
 715
 716 **FIXME:** grammar?
 717
 718 ### Enumerated types
 719
 720 **FIXME:** grammar?
 721
 722 ### Pointer types
 723
 724 **FIXME:** grammar?
 725
 726 ### Function types
 727
 728 **FIXME:** grammar?
 729
 730 ### Closure types
 731
 732 ```antlr
 733 closure_type := [ 'unsafe' ] [ '<' lifetime-list '>' ] '|' arg-list '|'
 734                 [ ':' bound-list ] [ '->' type ]
 735 procedure_type := 'proc' [ '<' lifetime-list '>' ] '(' arg-list ')'
 736                   [ ':' bound-list ] [ '->' type ]
 737 lifetime-list := lifetime | lifetime ',' lifetime-list
 738 arg-list := ident ':' type | ident ':' type ',' arg-list
 739 bound-list := bound | bound '+' bound-list
 740 bound := path | lifetime
 741 ```
 742
 743 ### Object types
 744
 745 **FIXME:** grammar?
 746
 747 ### Type parameters
 748
 749 **FIXME:** grammar?
 750
 751 ### Self types
 752
 753 **FIXME:** grammar?
 754
 755 ## Type kinds
 756
 757 **FIXME:** this this probably not relevant to the grammar...
 758
 759 # Memory and concurrency models
 760
 761 **FIXME:** is this entire chapter relevant here? Or should it all have been covered by some production already?
 762
 763 ## Memory model
 764
 765 ### Memory allocation and lifetime
 766
 767 ### Memory ownership
 768
 769 ### Memory slots
 770
 771 ### Boxes
 772
 773 ## Tasks
 774
 775 ### Communication between tasks
 776
 777 ### Task lifecycle