1:orphan:
2
3=====================================================
4Kaleidoscope: Kaleidoscope Introduction and the Lexer
5=====================================================
6
7.. contents::
8   :local:
9
10The Kaleidoscope Language
11=========================
12
13This tutorial is illustrated with a toy language called
14"`Kaleidoscope <http://en.wikipedia.org/wiki/Kaleidoscope>`_" (derived
15from "meaning beautiful, form, and view"). Kaleidoscope is a procedural
16language that allows you to define functions, use conditionals, math,
17etc. Over the course of the tutorial, we'll extend Kaleidoscope to
18support the if/then/else construct, a for loop, user defined operators,
19JIT compilation with a simple command line interface, debug info, etc.
20
21We want to keep things simple, so the only datatype in Kaleidoscope
22is a 64-bit floating point type (aka 'double' in C parlance). As such,
23all values are implicitly double precision and the language doesn't
24require type declarations. This gives the language a very nice and
25simple 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
40We also allow Kaleidoscope to call into standard library functions - the
41LLVM 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
43useful 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
53A more interesting example is included in Chapter 6 where we write a
54little Kaleidoscope application that `displays a Mandelbrot
55Set <LangImpl06.html#kicking-the-tires>`_ at various levels of magnification.
56
57Let's dive into the implementation of this language!
58
59The Lexer
60=========
61
62When it comes to implementing a language, the first thing needed is the
63ability to process a text file and recognize what it says. The
64traditional 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
67the lexer includes a token code and potentially some metadata (e.g. the
68numeric 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
89Each token returned by our lexer will either be one of the Token enum
90values or it will be an 'unknown' character like '+', which is returned
91as its ASCII value. If the current token is an identifier, the
92``IdentifierStr`` global variable holds the name of the identifier. If
93the current token is a numeric literal (like 1.0), ``NumVal`` holds its
94value. We use global variables for simplicity, but this is not the
95best choice for a real language implementation :).
96
97The actual implementation of the lexer is a single function named
98``gettok``. The ``gettok`` function is called to return the next token
99from 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
112characters one at a time from standard input. It eats them as it
113recognizes them and stores the last character read, but not processed,
114in LastChar. The first thing that it has to do is ignore whitespace
115between tokens. This is accomplished with the loop above.
116
117The next thing ``gettok`` needs to do is recognize identifiers and
118specific keywords like "def". Kaleidoscope does this with this simple
119loop:
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
135Note that this code sets the '``IdentifierStr``' global whenever it
136lexes an identifier. Also, since language keywords are matched by the
137same 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
152This is all pretty straightforward code for processing input. When
153reading a numeric value from input, we use the C ``strtod`` function to
154convert it to a numeric value that we store in ``NumVal``. Note that
155this 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
157extend 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
171We handle comments by skipping to the end of the line and then return
172the next token. Finally, if the input doesn't match one of the above
173cases, it is either an operator character like '+' or the end of the
174file. 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
188With this, we have the complete lexer for the basic Kaleidoscope
189language (the `full code listing <LangImpl02.html#full-code-listing>`_ for the Lexer
190is available in the `next chapter <LangImpl02.html>`_ of the tutorial).
191Next we'll `build a simple parser that uses this to build an Abstract
192Syntax Tree <LangImpl02.html>`_. When we have that, we'll include a
193driver so that you can use the lexer and parser together.
194
195`Next: Implementing a Parser and AST <LangImpl02.html>`_
196
197