docs/tutorial/MyFirstLanguageFrontend/LangImpl01.rst

   1 :orphan:
   2
   3 =====================================================
   4 Kaleidoscope: Kaleidoscope Introduction and the Lexer
   5 =====================================================
   6
   7 .. contents::
   8    :local:
   9
  10 The Kaleidoscope Language
  11 =========================
  12
  13 This tutorial is illustrated with a toy language called
  14 "`Kaleidoscope <http://en.wikipedia.org/wiki/Kaleidoscope>`_" (derived
  15 from "meaning beautiful, form, and view"). Kaleidoscope is a procedural
  16 language that allows you to define functions, use conditionals, math,
  17 etc. Over the course of the tutorial, we'll extend Kaleidoscope to
  18 support the if/then/else construct, a for loop, user defined operators,
  19 JIT compilation with a simple command line interface, debug info, etc.
  20
  21 We want to keep things simple, so the only datatype in Kaleidoscope
  22 is a 64-bit floating point type (aka 'double' in C parlance). As such,
  23 all values are implicitly double precision and the language doesn't
  24 require type declarations. This gives the language a very nice and
  25 simple syntax. For example, the following simple example computes
  26 `Fibonacci numbers: <http://en.wikipedia.org/wiki/Fibonacci_number>`_
  27
  28 ::
  29
  30     # Compute the x'th fibonacci number.
  31     def fib(x)
  32       if x < 3 then
  33         1
  34       else
  35         fib(x-1)+fib(x-2)
  36
  37     # This expression will compute the 40th number.
  38     fib(40)
  39
  40 We also allow Kaleidoscope to call into standard library functions - the
  41 LLVM JIT makes this really easy. This means that you can use the
  42 'extern' keyword to define a function before you use it (this is also
  43 useful for mutually recursive functions).  For example:
  44
  45 ::
  46
  47     extern sin(arg);
  48     extern cos(arg);
  49     extern atan2(arg1 arg2);
  50
  51     atan2(sin(.4), cos(42))
  52
  53 A more interesting example is included in Chapter 6 where we write a
  54 little Kaleidoscope application that `displays a Mandelbrot
  55 Set <LangImpl06.html#kicking-the-tires>`_ at various levels of magnification.
  56
  57 Let's dive into the implementation of this language!
  58
  59 The Lexer
  60 =========
  61
  62 When it comes to implementing a language, the first thing needed is the
  63 ability to process a text file and recognize what it says. The
  64 traditional way to do this is to use a
  65 "`lexer <http://en.wikipedia.org/wiki/Lexical_analysis>`_" (aka
  66 'scanner') to break the input up into "tokens". Each token returned by
  67 the lexer includes a token code and potentially some metadata (e.g. the
  68 numeric value of a number). First, we define the possibilities:
  69
  70 .. code-block:: c++
  71
  72     // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
  73     // of these for known things.
  74     enum Token {
  75       tok_eof = -1,
  76
  77       // commands
  78       tok_def = -2,
  79       tok_extern = -3,
  80
  81       // primary
  82       tok_identifier = -4,
  83       tok_number = -5,
  84     };
  85
  86     static std::string IdentifierStr; // Filled in if tok_identifier
  87     static double NumVal;             // Filled in if tok_number
  88
  89 Each token returned by our lexer will either be one of the Token enum
  90 values or it will be an 'unknown' character like '+', which is returned
  91 as its ASCII value. If the current token is an identifier, the
  92 ``IdentifierStr`` global variable holds the name of the identifier. If
  93 the current token is a numeric literal (like 1.0), ``NumVal`` holds its
  94 value. We use global variables for simplicity, but this is not the
  95 best choice for a real language implementation :).
  96
  97 The actual implementation of the lexer is a single function named
  98 ``gettok``. The ``gettok`` function is called to return the next token
  99 from standard input. Its definition starts as:
 100
 101 .. code-block:: c++
 102
 103     /// gettok - Return the next token from standard input.
 104     static int gettok() {
 105       static int LastChar = ' ';
 106
 107       // Skip any whitespace.
 108       while (isspace(LastChar))
 109         LastChar = getchar();
 110
 111 ``gettok`` works by calling the C ``getchar()`` function to read
 112 characters one at a time from standard input. It eats them as it
 113 recognizes them and stores the last character read, but not processed,
 114 in LastChar. The first thing that it has to do is ignore whitespace
 115 between tokens. This is accomplished with the loop above.
 116
 117 The next thing ``gettok`` needs to do is recognize identifiers and
 118 specific keywords like "def". Kaleidoscope does this with this simple
 119 loop:
 120
 121 .. code-block:: c++
 122
 123       if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 124         IdentifierStr = LastChar;
 125         while (isalnum((LastChar = getchar())))
 126           IdentifierStr += LastChar;
 127
 128         if (IdentifierStr == "def")
 129           return tok_def;
 130         if (IdentifierStr == "extern")
 131           return tok_extern;
 132         return tok_identifier;
 133       }
 134
 135 Note that this code sets the '``IdentifierStr``' global whenever it
 136 lexes an identifier. Also, since language keywords are matched by the
 137 same loop, we handle them here inline. Numeric values are similar:
 138
 139 .. code-block:: c++
 140
 141       if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 142         std::string NumStr;
 143         do {
 144           NumStr += LastChar;
 145           LastChar = getchar();
 146         } while (isdigit(LastChar) || LastChar == '.');
 147
 148         NumVal = strtod(NumStr.c_str(), 0);
 149         return tok_number;
 150       }
 151
 152 This is all pretty straightforward code for processing input. When
 153 reading a numeric value from input, we use the C ``strtod`` function to
 154 convert it to a numeric value that we store in ``NumVal``. Note that
 155 this isn't doing sufficient error checking: it will incorrectly read
 156 "1.23.45.67" and handle it as if you typed in "1.23". Feel free to
 157 extend it!  Next we handle comments:
 158
 159 .. code-block:: c++
 160
 161       if (LastChar == '#') {
 162         // Comment until end of line.
 163         do
 164           LastChar = getchar();
 165         while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
 166
 167         if (LastChar != EOF)
 168           return gettok();
 169       }
 170
 171 We handle comments by skipping to the end of the line and then return
 172 the next token. Finally, if the input doesn't match one of the above
 173 cases, it is either an operator character like '+' or the end of the
 174 file. These are handled with this code:
 175
 176 .. code-block:: c++
 177
 178       // Check for end of file.  Don't eat the EOF.
 179       if (LastChar == EOF)
 180         return tok_eof;
 181
 182       // Otherwise, just return the character as its ascii value.
 183       int ThisChar = LastChar;
 184       LastChar = getchar();
 185       return ThisChar;
 186     }
 187
 188 With this, we have the complete lexer for the basic Kaleidoscope
 189 language (the `full code listing <LangImpl02.html#full-code-listing>`_ for the Lexer
 190 is available in the `next chapter <LangImpl02.html>`_ of the tutorial).
 191 Next we'll `build a simple parser that uses this to build an Abstract
 192 Syntax Tree <LangImpl02.html>`_. When we have that, we'll include a
 193 driver so that you can use the lexer and parser together.
 194
 195 `Next: Implementing a Parser and AST <LangImpl02.html>`_
 196