nimcity/doc/part02/ch12.md

Chapter 12. Lexical analysis

Lexical analysis describes how letters and other characters form the “words” of a programming language in general. These “words” are technically called tokens and the rest of the compiler’s transformation pipeline works on tokens and not on single characters. The transformation pipeline is usually called phases of translation. A Nim compiler uses the following phases of translation:

1. Lexing: Turn a stream of characters into a stream of tokens.
2. Parsing: Turn a stream of tokens into an abstract syntax tree (AST).

3. Semantic analysis: Turn an AST to an annotated AST. The annotations are primarily type annotations as Nim is a statically typed language every expression needs to have a type. This chapter describes in detail the first phase, lexing. 12.1. Notation used in this chapter The language constructs are explained using an extended Backus–Naur form (EBNF), in which a* means 0 or more a's, a+ means 1 or more a's, and a? means an optional a (either no a or one a). Parentheses may be used to group elements. & is the lookahead operator; &a means that an a is expected but not consumed. The |, / symbols are used to mark alternatives and have the lowest precedence. / is the ordered choice that requires the parser to try the alternatives in the given order. / is often used to ensure that the grammar is not ambiguous.

                                                                      49
   

   Non-terminals start with a lowercase letter, abstract terminal symbols are in UPPERCASE. Verbatim terminal symbols (including keywords) are quoted with '. An example: ifStmt = 'if' expr ':' stmts ('elif' expr ':' stmts)* ('else' stmts)? The binary ^* operator is used as a shorthand for 0 or more occurrences separated by its second argument; likewise ^means 1 or more occurrences: a ^ b is short for a (b a)* and a ^* b is short for (a (b a))?. For example: arrayConstructor = '[' expr ^ ',' ']' A Nim program consists of one or more text source files containing Nim code. The text has to be encoded in UTF-8. Nim’s grammar is not defined directly on the Unicode input text. Instead, it is defined on a list of separate, non- overlapping tokens. A token can be classified to be one of the following: • A comment. • An identifier. • A keyword like if or type. • A (character, string, integer, floating-point number) literal. • An operator. • A delimiter like (, ,, ). (It covers the semicolon, the comma and the different types of brackets.) 12.2. Indentation Nim’s standard grammar describes an indentation sensitive language. This means that all the control structures are recognized by indentation. Indentation consists only of spaces; tabulators are not allowed.

        The "use tabs for indentation, spaces for alignment" rule never
        works sufficiently well in larger code-bases and even if it does
   

   

        work, it adds yet another source of friction for developers.
        Things are easier without such a rule. Since Nim uses an
        indentation based syntax and only allows spaces, the source
        code layout is portable across editors.
   

   50 The indentation handling is implemented as follows: The lexer annotates the following token with the preceding number of spaces; indentation is not a separate token. This trick allows parsing of Nim with only one token of lookahead. The parser uses a stack of indentation levels: the stack consists of integers counting the spaces. The indentation information is queried at strategic places in the parser but ignored otherwise: The pseudo-terminal IND{>} denotes an indentation that consists of more spaces than the entry at the top of the stack; IND{=} an indentation that has the same number of spaces. DED is another pseudo-terminal that describes the action of popping a value from the stack, IND{>} then implies to push onto the stack. With this notation we can now define the core of the grammar: A block of statements (simplified example): ifStmt = 'if' expr ':' stmt

        (IND{=} 'elif' expr ':' stmt)*
        (IND{=} 'else' ':' stmt)?
   

   simpleStmt = ifStmt / ... stmt = IND{>} stmt ^+ IND{=} DED # list of statements

   / simpleStmt                 # or a simple statement
   

   12.3. Comments Comments start anywhere outside a string or character literal with the hash character (#). Comments consist of a concatenation of comment pieces. A comment piece starts with # and runs until the end of the line. The end of line characters belong to the piece. If the next line only consists of a comment piece with no other tokens between it and the preceding one, it does not start a new comment: i = 0 # This is a single comment over multiple lines.

   The scanner merges these pieces.

   The same comment continues here.

   Documentation comments are comments that start with two hash characters (##). Documentation comments are tokens; they are only allowed at certain places in the input file as they belong to the syntax tree.

                                                                        51
   

   12.4. Multiline comments A multiline comment starts with #[ and ends with ]#: #[Comment here that can span multiple lines.]# Multiline comments can be nested: #[ #[ Multiline comment in already commented out code. ]# proc pT = discard ]# Multiline documentation comments exist and support nesting too: proc foo = ##[Long documentation comment

    here.
   

   ]## 12.5. Identifiers & Keywords Identifiers in Nim can be any string of letters, digits and underscores, with the following restrictions: • It has to begin with a letter. • It is not allowed to end with an underscore _. • Two successive underscores __ are not allowed: letter ::= 'A'..'Z' | 'a'..'z' | '\x80'..'\xff' digit ::= '0'..'9' IDENTIFIER ::= letter ( '_' )* Unicode characters with an ordinal value higher than 127 (non-ASCII) can be either classified as a letter or as operator. The details of this classification are not covered here as they might still change in the future. 52 The following keywords are reserved and cannot be used as identifiers: addr and as asm bind block break case cast concept const continue converter defer discard distinct div do elif else end enum except export finally for from func if import in include interface is isnot iterator let macro method mixin mod nil not notin object of or out proc ptr raise ref return shl shr static template try tuple type using var when while xor yield Some keywords are currently unused; they are reserved for future developments of the language. 12.6. Identifier equality Two identifiers are considered equal if the following algorithm returns true: proc sameIdentifier(a, b: string): bool = a[0] == b[0] and a.replace("", "").toLowerAscii == b.replace("", "").toLowerAscii That means only the first letters are compared in a case-sensitive manner. Other letters are compared case-insensitively within the ASCII range and underscores are ignored. This rule also applies to keywords, meaning that notin is the same as notIn and not_in.

        The eccentric rules with respect to identifier equality try to
   

    ensure more sensible naming practices where different things

        have different names rather than only different spellings.
                                                                      53
         Compare const       ROOT   =  root(Root) to const     RootUser =
         rootof(RootDir) to appreciate the benefits. Differences in
         spelling cannot be pronounced easily; as soon as two or more
         developers need to talk about their code-base the benefits of
         clearly distinctive names become apparent.
   

   12.7. String literals Terminal symbol in the grammar: STR_LIT. String literals can be delimited by matching double quotes, and can contain the following escape sequences : Table 1. Escape sequences for string literals Escape sequence Meaning \p platform specific newline: CRLF on Windows, LF on

                 Unix
   

   \r, \c carriage return \n, \l line feed (often called newline) \f form feed \t tabulator \v vertical tabulator \ backslash \" quotation mark \' apostrophe \'0'..'9'+ character with decimal value d; all decimal digits

                 directly following are used for the character
   

   \a alert \b backspace \e escape [ESC] \xHH character with hex value HH; exactly two hex digits are

                 allowed
   

   54 Escape sequence Meaning \uHHHH unicode codepoint with hex value HHHH; exactly four

                 hex digits are allowed
   

   \u{H+} unicode codepoint; all hex digits enclosed in {} are used

                 for the codepoint
   

   Strings in Nim may contain any 8-bit value, even embedded zeros. 12.8. Triple quoted string literals Terminal symbol in the grammar: TRIPLESTR_LIT. String literals can also be delimited by three double quotes """ ... """. Literals in this form may run for several lines, may contain " and do not interpret any escape sequences. For convenience, when the opening """ is followed by a newline (there may be whitespace between the opening """ and the newline), the newline (and the preceding whitespace) is not included in the string. The ending of the string literal is defined by the pattern """[^"]. In other words, this: """"long string within quotes"""" Produces: "long string within quotes" 12.9. Raw string literals Terminal symbol in the grammar: RSTR_LIT. There are also raw string literals that are preceded with the letter r (or R) and are delimited by matching double quotes (just like ordinary string literals) and do not interpret the escape sequences. This is especially convenient for regular expressions or Windows paths: var f = openFile(r"C:\texts\text.txt") # a raw string, so \t is no tab

                                                                          55
   

   To produce a single " within a raw string literal, it has to be doubled: r"a""b" Produces: a"b r"""" is not possible with this notation, because the three leading quotes introduce a triple quoted string literal. r""" is the same as """ since triple quoted string literals do not interpret escape sequences either. 12.10. Generalized raw string literals Terminal symbols in the grammar: GENERALIZED_STR_LIT, GENERALIZED_TRIPLESTR_LIT. The construct identifier"string literal" (without whitespace between the identifier and the opening quotation mark) is a generalized raw string literal. It is a shortcut for the construct identifier(r"string literal"), so it denotes a routine call with a raw string literal as its only argument. Generalized raw string literals are especially convenient for embedding mini languages directly into Nim (for example regular expressions). The construct identifier"""string literal""" exists too. It is a shortcut for identifier("""string literal"""). 12.11. Character literals Character literals are enclosed in single quotes '' and can contain the same escape sequences as strings - with one exception: the platform dependent newline (\p) is not allowed as it may be wider than one character (it can be the pair CR/LF). Here are the valid escape sequences for character literals: 56 Table 2. Escape sequences for character literals Escape sequence Meaning \r, \c carriage return \n, \l line feed \f form feed \t tabulator \v vertical tabulator \ backslash \" quotation mark \' apostrophe \'0'..'9'+ character with decimal value d; all decimal digits

                directly following are used for the character
   

   \a alert \b backspace \e escape [ESC] \xHH character with hex value HH; exactly two hex digits are

                allowed
   

   A char is not a Unicode character but a single byte. A character literal that does not end in ' is interpreted as ' if there is a preceding backtick token. There must be no whitespace between the preceding backtick token and the character literal. This special case ensures that a declaration like proc ’'customLiteral(s: string) is valid. proc ’'customLiteral(s: string) is the same as proc ’'\''customLiteral`(s: string). See also Section 12.12.1, “Custom Numeric Literals”.

                                                                      57
   

   12.12. Numeric Literals Numeric literals have the form: hexdigit = digit | 'A'..'F' | 'a'..'f' octdigit = '0'..'7' bindigit = '0'..'1' unary_minus = '-' # See the section about unary minus HEX_LIT = unaryminus? '0' ('x' | 'X' ) hexdigit ( [''] hexdigit )* DEC_LIT = unaryminus? digit ( [''] digit )* OCT_LIT = unaryminus? '0' 'o' octdigit ( [''] octdigit )* BIN_LIT = unaryminus? '0' ('b' | 'B' ) bindigit ( [''] bindigit )* INT_LIT = HEX_LIT

     | DEC_LIT
     | OCT_LIT
     | BIN_LIT
   

   INT8_LIT = INT_LIT ['\''] ('i' | 'I') '8' INT16_LIT = INT_LIT ['\''] ('i' | 'I') '16' INT32_LIT = INT_LIT ['\''] ('i' | 'I') '32' INT64_LIT = INT_LIT ['\''] ('i' | 'I') '64' UINT_LIT = INT_LIT ['\''] ('u' | 'U') UINT8_LIT = INT_LIT ['\''] ('u' | 'U') '8' UINT16_LIT = INT_LIT ['\''] ('u' | 'U') '16' UINT32_LIT = INT_LIT ['\''] ('u' | 'U') '32' UINT64_LIT = INTLIT ['\''] ('u' | 'U') '64' exponent = ('e' | 'E' ) ['+' | '-'] digit ( [''] digit )* FLOAT_LIT = unaryminus? digit ([''] digit)* (('.' digit (['_'] digit)* [exponent]) |exponent) FLOAT32_SUFFIX = ('f' | 'F') ['32'] FLOAT32_LIT = HEX_LIT '\'' FLOAT32_SUFFIX

         | (FLOAT_LIT | DEC_LIT | OCT_LIT | BIN_LIT) ['\'']
   

   FLOAT32_SUFFIX FLOAT64_SUFFIX = ( ('f' | 'F') '64' ) | 'd' | 'D' FLOAT64_LIT = HEX_LIT '\'' FLOAT64_SUFFIX

         | (FLOAT_LIT | DEC_LIT | OCT_LIT | BIN_LIT) ['\'']
   

   FLOAT64_SUFFIX CUSTOM_NUMERIC_LIT = (FLOAT_LIT | INT_LIT) '\'' CUSTOM_NUMERIC_SUFFIX

   CUSTOM_NUMERIC_SUFFIX is any Nim identifier that is not

   a pre-defined type suffix.

   As can be seen in the productions, numeric literals can contain underscores for readability. Integer and floating-point literals may be given in decimal (no 58 prefix), binary (prefix 0b), octal (prefix 0o), and hexadecimal (prefix 0x) notation. The fact that the unary minus - in a number literal like -1 is considered to be part of the literal is a late addition to the language. The rationale is that an expression -128'i8 should be valid and without this special case, this would be impossible — 128 is not a valid int8 value, only -128 is. For the unary_minus rule there are further restrictions that are not covered in the formal grammar. For - to be part of the number literal, its immediately preceding character has to be in the set {' ', '\t', '\n', '\r', ',', ';', '(', '[', '{'}. In the following examples, -1 is a single token: echo -1 echo(-1) echo [-1] echo 3,-1 "abc";-1 In the following examples, -1 is parsed as two separate tokens (as - and 1): echo x-1 echo (int)-1 echo [a]-1 "abc"-1 The suffix starting with an apostrophe (') is called a type suffix. Literals without a type suffix are of an integer type unless the literal contains a dot or E|e in which case it is of type float. This integer type is int if the literal is in the range low(int32)..high(int32), otherwise it is int64. For notational convenience, the apostrophe of a type suffix is optional if it is not ambiguous (only hexadecimal floating-point literals with a type suffix can be ambiguous).

                                                                            59
   

   The pre-defined type suffixes are: Table 3. Pre-defined type suffixes Type Resulting type of Suffix literal 'i8 int8 'i16 int16 'i32 int32 'i64 int64 'u uint 'u8 uint8 'u16 uint16 'u32 uint32 'u64 uint64 'f float32 'd float64 'f32 float32 'f64 float64 Literals must match the datatype, for example, 333'i8 is an invalid literal. Non-base-10 literals are used mainly for flags and bit pattern representations, therefore the checking is done on bit width and not on value range. Hence: 0b10000000'u8 == 0x80'u8 == 128, but: 0b10000000'i8 == 0x80'i8 == -1, instead of causing an overflow error. 12.12.1. Custom Numeric Literals If the suffix is not predefined, then the suffix is assumed to be a call to a proc, template, macro or other callable identifier that is passed the string containing the literal. The callable identifier needs to be declared with a special ' prefix: 60 import strutils type u4 = distinct uint8 # a 4-bit unsigned integer aka "nibble" proc 'u4(n: string): u4 =

   The leading ' is required.

   result = (parseInt(n) and 0x0F).u4 var x = 5'u4 More formally, a custom numeric literal 123'custom is transformed to r"123".'custom in the parsing step. There is no AST node kind that corresponds to this transformation. The transformation naturally handles the case that additional parameters are passed to the callee: import strutils type u4 = distinct uint8 # a 4-bit unsigned integer aka "nibble" proc 'u4(n: string; moreData: int): u4 = result = (parseInt(n) and 0x0F).u4 var x = 5'u4(123) Custom numeric literals are covered by the grammar rule named CUSTOM_NUMERIC_LIT. A custom numeric literal is a single token. 12.13. Operators Nim allows user-defined operators, in fact, Nim does not distinguish between user-defined and builtin operators. When one writes 1 + 2 it is a call to a plus operator (1, 2) which is subject to overload resolution. The system module is automatically imported in every Nim program and offers func \(a, b: int): int so the call will be resolved to system.+(1, 2). An operator is any combination of the following characters: = + - * / < > @ $ ~ & % | ! ? ^ . : \ (The grammar uses the terminal OPR to refer to operator symbols as defined here.) These keywords are also operators: and or not xor shl shr div mod in notin is isnot of as from.

                                                                         61
   

   ., =, :, :: are not available as general operators; they are used for other notational purposes. *: is as a special case treated as the two tokens * and : (to support var v*: T). The not keyword is always a unary operator, a not b is parsed as a(not b), not as (a) not (b). 12.14. Other tokens The following strings denote other tokens: ` ( ) { } [ ] , ; [. .] {. .} (. .) [: The slice operator .. takes precedence over other tokens that contain a dot: {..} are the three tokens: { and .. and }, and not the two tokens: {. and .}. 12.15. Unicode Operators These Unicode operators are also parsed as operators: ∙ ∘ × ★ ⊗ ⊘ ⊙ ⊛ ⊠ ⊡ ∩ ∧ # same priority as * (multiplication) ± ⊕ ⊖ ⊞ ⊟ ∪ ∨ # same priority as + (addition) Unicode operators can be combined with non-Unicode operator symbols. The usual precedence extensions then apply, for example, ×= is an assignment like operator just like *= is. No Unicode normalization step is performed.