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