195 lines · plain
1=====================================================2Kaleidoscope: Kaleidoscope Introduction and the Lexer3=====================================================4 5.. contents::6 :local:7 8The Kaleidoscope Language9=========================10 11This tutorial is illustrated with a toy language called12"`Kaleidoscope <http://en.wikipedia.org/wiki/Kaleidoscope>`_" (derived13from "meaning beautiful, form, and view"). Kaleidoscope is a procedural14language that allows you to define functions, use conditionals, math,15etc. Over the course of the tutorial, we'll extend Kaleidoscope to16support the if/then/else construct, a for loop, user defined operators,17JIT compilation with a simple command line interface, debug info, etc.18 19We want to keep things simple, so the only datatype in Kaleidoscope20is a 64-bit floating point type (aka 'double' in C parlance). As such,21all values are implicitly double precision and the language doesn't22require type declarations. This gives the language a very nice and23simple syntax. For example, the following simple example computes24`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 then31 132 else33 fib(x-1)+fib(x-2)34 35 # This expression will compute the 40th number.36 fib(40)37 38We also allow Kaleidoscope to call into standard library functions - the39LLVM JIT makes this really easy. This means that you can use the40'extern' keyword to define a function before you use it (this is also41useful 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 51A more interesting example is included in Chapter 6 where we write a52little Kaleidoscope application that `displays a Mandelbrot53Set <LangImpl06.html#kicking-the-tires>`_ at various levels of magnification.54 55Let's dive into the implementation of this language!56 57The Lexer58=========59 60When it comes to implementing a language, the first thing needed is the61ability to process a text file and recognize what it says. The62traditional way to do this is to use a63"`lexer <http://en.wikipedia.org/wiki/Lexical_analysis>`_" (aka64'scanner') to break the input up into "tokens". Each token returned by65the lexer includes a token code and potentially some metadata (e.g. the66numeric 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 one71 // of these for known things.72 enum Token {73 tok_eof = -1,74 75 // commands76 tok_def = -2,77 tok_extern = -3,78 79 // primary80 tok_identifier = -4,81 tok_number = -5,82 };83 84 static std::string IdentifierStr; // Filled in if tok_identifier85 static double NumVal; // Filled in if tok_number86 87Each token returned by our lexer will either be one of the Token enum88values or it will be an 'unknown' character like '+', which is returned89as its ASCII value. If the current token is an identifier, the90``IdentifierStr`` global variable holds the name of the identifier. If91the current token is a numeric literal (like 1.0), ``NumVal`` holds its92value. We use global variables for simplicity, but this is not the93best choice for a real language implementation :).94 95The actual implementation of the lexer is a single function named96``gettok``. The ``gettok`` function is called to return the next token97from 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 read110characters one at a time from standard input. It eats them as it111recognizes them and stores the last character read, but not processed,112in LastChar. The first thing that it has to do is ignore whitespace113between tokens. This is accomplished with the loop above.114 115The next thing ``gettok`` needs to do is recognize identifiers and116specific keywords like "def". Kaleidoscope does this with this simple117loop: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 133Note that this code sets the '``IdentifierStr``' global whenever it134lexes an identifier. Also, since language keywords are matched by the135same 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 150This is all pretty straightforward code for processing input. When151reading a numeric value from input, we use the C ``strtod`` function to152convert it to a numeric value that we store in ``NumVal``. Note that153this isn't doing sufficient error checking: it will incorrectly read154"1.23.45.67" and handle it as if you typed in "1.23". Feel free to155extend it! Next we handle comments:156 157.. code-block:: c++158 159 if (LastChar == '#') {160 // Comment until end of line.161 do162 LastChar = getchar();163 while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');164 165 if (LastChar != EOF)166 return gettok();167 }168 169We handle comments by skipping to the end of the line and then return170the next token. Finally, if the input doesn't match one of the above171cases, it is either an operator character like '+' or the end of the172file. 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 186With this, we have the complete lexer for the basic Kaleidoscope187language (the `full code listing <LangImpl02.html#full-code-listing>`_ for the Lexer188is available in the `next chapter <LangImpl02.html>`_ of the tutorial).189Next we'll `build a simple parser that uses this to build an Abstract190Syntax Tree <LangImpl02.html>`_. When we have that, we'll include a191driver so that you can use the lexer and parser together.192 193`Next: Implementing a Parser and AST <LangImpl02.html>`_194 195