docs/tutorial/LangImpl1.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3
   4 <html>
   5 <head>
   6   <title>Kaleidoscope: Tutorial Introduction and the Lexer</title>
   7   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   8   <meta name="author" content="Chris Lattner">
   9   <link rel="stylesheet" href="../llvm.css" type="text/css">
  10 </head>
  11
  12 <body>
  13
  14 <div class="doc_title">Kaleidoscope: Tutorial Introduction and the Lexer</div>
  15
  16 <ul>
  17 <li><a href="index.html">Up to Tutorial Index</a></li>
  18 <li>Chapter 1
  19   <ol>
  20     <li><a href="#intro">Tutorial Introduction</a></li>
  21     <li><a href="#language">The Basic Language</a></li>
  22     <li><a href="#lexer">The Lexer</a></li>
  23   </ol>
  24 </li>
  25 <li><a href="LangImpl2.html">Chapter 2</a>: Implementing a Parser and AST</li>
  26 </ul>
  27
  28 <div class="doc_author">
  29   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
  30 </div>
  31
  32 <!-- *********************************************************************** -->
  33 <div class="doc_section"><a name="intro">Tutorial Introduction</a></div>
  34 <!-- *********************************************************************** -->
  35
  36 <div class="doc_text">
  37
  38 <p>Welcome to the "Implementing a language with LLVM" tutorial.  This tutorial
  39 runs through the implementation of a simple language, showing how fun and
  40 easy it can be.  This tutorial will get you up and started as well as help to
  41 build a framework you can extend to other languages.  The code in this tutorial
  42 can also be used as a playground to hack on other LLVM specific things.
  43 </p>
  44
  45 <p>
  46 The goal of this tutorial is to progressively unveil our language, describing
  47 how it is built up over time.  This will let us cover a fairly broad range of
  48 language design and LLVM-specific usage issues, showing and explaining the code
  49 for it all along the way, without overwhelming you with tons of details up
  50 front.</p>
  51
  52 <p>It is useful to point out ahead of time that this tutorial is really about
  53 teaching compiler techniques and LLVM specifically, <em>not</em> about teaching
  54 modern and sane software engineering principles.  In practice, this means that
  55 we'll take a number of shortcuts to simplify the exposition.  For example, the
  56 code leaks memory, uses global variables all over the place, doesn't use nice
  57 design patterns like visitors, etc... but it is very simple.  If you dig in and
  58 use the code as a basis for future projects, fixing these deficiencies shouldn't
  59 be hard.</p>
  60
  61 <p>I've tried to put this tutorial together in a way that makes chapters easy to
  62 skip over if you are already familiar with or are uninterested in the various
  63 pieces.  The structure of the tutorial is:
  64 </p>
  65
  66 <ul>
  67 <li><b><a href="#language">Chapter #1</a>: Introduction to the Kaleidoscope
  68 language, and the definition of its Lexer</b> - This shows where we are going
  69 and the basic functionality that we want it to do.  In order to make this
  70 tutorial maximally understandable and hackable, we choose to implement
  71 everything in C++ instead of using lexer and parser generators.  LLVM obviously
  72 works just fine with such tools, feel free to use one if you prefer.</li>
  73 <li><b><a href="LangImpl2.html">Chapter #2</a>: Implementing a Parser and
  74 AST</b> - With the lexer in place, we can talk about parsing techniques and
  75 basic AST construction.  This tutorial describes recursive descent parsing and
  76 operator precedence parsing.  Nothing in Chapters 1 or 2 is LLVM-specific,
  77 the code doesn't even link in LLVM at this point. :)</li>
  78 <li><b><a href="LangImpl3.html">Chapter #3</a>: Code generation to LLVM IR</b> -
  79 With the AST ready, we can show off how easy generation of LLVM IR really
  80 is.</li>
  81 <li><b><a href="LangImpl4.html">Chapter #4</a>: Adding JIT and Optimizer
  82 Support</b> - Because a lot of people are interested in using LLVM as a JIT,
  83 we'll dive right into it and show you the 3 lines it takes to add JIT support.
  84 LLVM is also useful in many other ways, but this is one simple and "sexy" way
  85 to shows off its power. :)</li>
  86 <li><b><a href="LangImpl5.html">Chapter #5</a>: Extending the Language: Control
  87 Flow</b> - With the language up and running, we show how to extend it with
  88 control flow operations (if/then/else and a 'for' loop).  This gives us a chance
  89 to talk about simple SSA construction and control flow.</li>
  90 <li><b><a href="LangImpl6.html">Chapter #6</a>: Extending the Language:
  91 User-defined Operators</b> - This is a silly but fun chapter that talks about
  92 extending the language to let the user program define their own arbitrary
  93 unary and binary operators (with assignable precedence!).  This lets us build a
  94 significant piece of the "language" as library routines.</li>
  95 <li><b><a href="LangImpl7.html">Chapter #7</a>: Extending the Language: Mutable
  96 Variables</b> - This chapter talks about adding user-defined local variables
  97 along with an assignment operator.  The interesting part about this is how
  98 easy and trivial it is to construct SSA form in LLVM: no, LLVM does <em>not</em>
  99 require your front-end to construct SSA form!</li>
 100 <li><b><a href="LangImpl8.html">Chapter #8</a>: Conclusion and other useful LLVM
 101 tidbits</b> - This chapter wraps up the series by talking about potential
 102 ways to extend the language, but also includes a bunch of pointers to info about
 103 "special topics" like adding garbage collection support, exceptions, debugging,
 104 support for "spaghetti stacks", and a bunch of other tips and tricks.</li>
 105
 106 </ul>
 107
 108 <p>By the end of the tutorial, we'll have written a bit less than 700 lines of
 109 non-comment, non-blank, lines of code.  With this small amount of code, we'll
 110 have built up a very reasonable compiler for a non-trivial language including
 111 a hand-written lexer, parser, AST, as well as code generation support with a JIT
 112 compiler.  While other systems may have interesting "hello world" tutorials,
 113 I think the breadth of this tutorial is a great testament to the strengths of
 114 LLVM and why you should consider it if you're interested in language or compiler
 115 design.</p>
 116
 117 <p>A note about this tutorial: we expect you to extend the language and play
 118 with it on your own.  Take the code and go crazy hacking away at it, compilers
 119 don't need to be scary creatures - it can be a lot of fun to play with
 120 languages!</p>
 121
 122 </div>
 123
 124 <!-- *********************************************************************** -->
 125 <div class="doc_section"><a name="language">The Basic Language</a></div>
 126 <!-- *********************************************************************** -->
 127
 128 <div class="doc_text">
 129
 130 <p>This tutorial will be illustrated with a toy language that we'll call
 131 "<a href="http://en.wikipedia.org/wiki/Kaleidoscope">Kaleidoscope</a>" (derived
 132 from "meaning beautiful, form, and view").
 133 Kaleidoscope is a procedural language that allows you to define functions, use
 134 conditionals, math, etc.  Over the course of the tutorial, we'll extend
 135 Kaleidoscope to support the if/then/else construct, a for loop, user defined
 136 operators, JIT compilation with a simple command line interface, etc.</p>
 137
 138 <p>Because we want to keep things simple, the only datatype in Kaleidoscope is a
 139 64-bit floating point type (aka 'double' in C parlance).  As such, all values
 140 are implicitly double precision and the language doesn't require type
 141 declarations.  This gives the language a very nice and simple syntax.  For
 142 example, the following simple example computes <a
 143 href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci numbers:</a></p>
 144
 145 <div class="doc_code">
 146 <pre>
 147 # Compute the x'th fibonacci number.
 148 def fib(x)
 149   if x &lt; 3 then
 150     1
 151   else
 152     fib(x-1)+fib(x-2)
 153
 154 # This expression will compute the 40th number.
 155 fib(40)
 156 </pre>
 157 </div>
 158
 159 <p>We also allow Kaleidoscope to call into standard library functions (the LLVM
 160 JIT makes this completely trivial).  This means that you can use the 'extern'
 161 keyword to define a function before you use it (this is also useful for mutually
 162 recursive functions).  For example:</p>
 163
 164 <div class="doc_code">
 165 <pre>
 166 extern sin(arg);
 167 extern cos(arg);
 168 extern atan2(arg1 arg2);
 169
 170 atan2(sin(.4), cos(42))
 171 </pre>
 172 </div>
 173
 174 <p>A more interesting example is included in Chapter 6 where we write a little
 175 Kaleidoscope application that <a href="LangImpl6.html#example">displays
 176 a Mandelbrot Set</a> at various levels of magnification.</p>
 177
 178 <p>Lets dive into the implementation of this language!</p>
 179
 180 </div>
 181
 182 <!-- *********************************************************************** -->
 183 <div class="doc_section"><a name="lexer">The Lexer</a></div>
 184 <!-- *********************************************************************** -->
 185
 186 <div class="doc_text">
 187
 188 <p>When it comes to implementing a language, the first thing needed is
 189 the ability to process a text file and recognize what it says.  The traditional
 190 way to do this is to use a "<a
 191 href="http://en.wikipedia.org/wiki/Lexical_analysis">lexer</a>" (aka 'scanner')
 192 to break the input up into "tokens".  Each token returned by the lexer includes
 193 a token code and potentially some metadata (e.g. the numeric value of a number).
 194 First, we define the possibilities:
 195 </p>
 196
 197 <div class="doc_code">
 198 <pre>
 199 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
 200 // of these for known things.
 201 enum Token {
 202   tok_eof = -1,
 203
 204   // commands
 205   tok_def = -2, tok_extern = -3,
 206
 207   // primary
 208   tok_identifier = -4, tok_number = -5,
 209 };
 210
 211 static std::string IdentifierStr;  // Filled in if tok_identifier
 212 static double NumVal;              // Filled in if tok_number
 213 </pre>
 214 </div>
 215
 216 <p>Each token returned by our lexer will either be one of the Token enum values
 217 or it will be an 'unknown' character like '+', which is returned as its ASCII
 218 value.  If the current token is an identifier, the <tt>IdentifierStr</tt>
 219 global variable holds the name of the identifier.  If the current token is a
 220 numeric literal (like 1.0), <tt>NumVal</tt> holds its value.  Note that we use
 221 global variables for simplicity, this is not the best choice for a real language
 222 implementation :).
 223 </p>
 224
 225 <p>The actual implementation of the lexer is a single function named
 226 <tt>gettok</tt>. The <tt>gettok</tt> function is called to return the next token
 227 from standard input.  Its definition starts as:</p>
 228
 229 <div class="doc_code">
 230 <pre>
 231 /// gettok - Return the next token from standard input.
 232 static int gettok() {
 233   static int LastChar = ' ';
 234
 235   // Skip any whitespace.
 236   while (isspace(LastChar))
 237     LastChar = getchar();
 238 </pre>
 239 </div>
 240
 241 <p>
 242 <tt>gettok</tt> works by calling the C <tt>getchar()</tt> function to read
 243 characters one at a time from standard input.  It eats them as it recognizes
 244 them and stores the last character read, but not processed, in LastChar.  The
 245 first thing that it has to do is ignore whitespace between tokens.  This is
 246 accomplished with the loop above.</p>
 247
 248 <p>The next thing <tt>gettok</tt> needs to do is recognize identifiers and
 249 specific keywords like "def".  Kaleidoscope does this with this simple loop:</p>
 250
 251 <div class="doc_code">
 252 <pre>
 253   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
 254     IdentifierStr = LastChar;
 255     while (isalnum((LastChar = getchar())))
 256       IdentifierStr += LastChar;
 257
 258     if (IdentifierStr == "def") return tok_def;
 259     if (IdentifierStr == "extern") return tok_extern;
 260     return tok_identifier;
 261   }
 262 </pre>
 263 </div>
 264
 265 <p>Note that this code sets the '<tt>IdentifierStr</tt>' global whenever it
 266 lexes an identifier.  Also, since language keywords are matched by the same
 267 loop, we handle them here inline.  Numeric values are similar:</p>
 268
 269 <div class="doc_code">
 270 <pre>
 271   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
 272     std::string NumStr;
 273     do {
 274       NumStr += LastChar;
 275       LastChar = getchar();
 276     } while (isdigit(LastChar) || LastChar == '.');
 277
 278     NumVal = strtod(NumStr.c_str(), 0);
 279     return tok_number;
 280   }
 281 </pre>
 282 </div>
 283
 284 <p>This is all pretty straight-forward code for processing input.  When reading
 285 a numeric value from input, we use the C <tt>strtod</tt> function to convert it
 286 to a numeric value that we store in <tt>NumVal</tt>.  Note that this isn't doing
 287 sufficient error checking: it will incorrectly read "1.23.45.67" and handle it as
 288 if you typed in "1.23".  Feel free to extend it :).  Next we handle comments:
 289 </p>
 290
 291 <div class="doc_code">
 292 <pre>
 293   if (LastChar == '#') {
 294     // Comment until end of line.
 295     do LastChar = getchar();
 296     while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
 297
 298     if (LastChar != EOF)
 299       return gettok();
 300   }
 301 </pre>
 302 </div>
 303
 304 <p>We handle comments by skipping to the end of the line and then return the
 305 next token.  Finally, if the input doesn't match one of the above cases, it is
 306 either an operator character like '+' or the end of the file.  These are handled
 307 with this code:</p>
 308
 309 <div class="doc_code">
 310 <pre>
 311   // Check for end of file.  Don't eat the EOF.
 312   if (LastChar == EOF)
 313     return tok_eof;
 314
 315   // Otherwise, just return the character as its ascii value.
 316   int ThisChar = LastChar;
 317   LastChar = getchar();
 318   return ThisChar;
 319 }
 320 </pre>
 321 </div>
 322
 323 <p>With this, we have the complete lexer for the basic Kaleidoscope language
 324 (the <a href="LangImpl2.html#code">full code listing</a> for the Lexer is
 325 available in the <a href="LangImpl2.html">next chapter</a> of the tutorial).
 326 Next we'll <a href="LangImpl2.html">build a simple parser that uses this to
 327 build an Abstract Syntax Tree</a>.  When we have that, we'll include a driver
 328 so that you can use the lexer and parser together.
 329 </p>
 330
 331 </div>
 332
 333 <!-- *********************************************************************** -->
 334 <hr>
 335 <address>
 336   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 337   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 338   <a href="http://validator.w3.org/check/referer"><img
 339   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
 340
 341   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
 342   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
 343   Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
 344 </address>
 345 </body>
 346 </html>