diff options
Diffstat (limited to 'docs/tutorial/OCamlLangImpl1.html')
| -rw-r--r-- | docs/tutorial/OCamlLangImpl1.html | 365 |
1 files changed, 365 insertions, 0 deletions
diff --git a/docs/tutorial/OCamlLangImpl1.html b/docs/tutorial/OCamlLangImpl1.html new file mode 100644 index 00000000000..73fe07bb840 --- /dev/null +++ b/docs/tutorial/OCamlLangImpl1.html @@ -0,0 +1,365 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" + "http://www.w3.org/TR/html4/strict.dtd"> + +<html> +<head> + <title>Kaleidoscope: Tutorial Introduction and the Lexer</title> + <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> + <meta name="author" content="Chris Lattner"> + <meta name="author" content="Erick Tryzelaar"> + <link rel="stylesheet" href="../_static/llvm.css" type="text/css"> +</head> + +<body> + +<h1>Kaleidoscope: Tutorial Introduction and the Lexer</h1> + +<ul> +<li><a href="index.html">Up to Tutorial Index</a></li> +<li>Chapter 1 + <ol> + <li><a href="#intro">Tutorial Introduction</a></li> + <li><a href="#language">The Basic Language</a></li> + <li><a href="#lexer">The Lexer</a></li> + </ol> +</li> +<li><a href="OCamlLangImpl2.html">Chapter 2</a>: Implementing a Parser and +AST</li> +</ul> + +<div class="doc_author"> + <p> + Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a> + and <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a> + </p> +</div> + +<!-- *********************************************************************** --> +<h2><a name="intro">Tutorial Introduction</a></h2> +<!-- *********************************************************************** --> + +<div> + +<p>Welcome to the "Implementing a language with LLVM" tutorial. This tutorial +runs through the implementation of a simple language, showing how fun and +easy it can be. This tutorial will get you up and started as well as help to +build a framework you can extend to other languages. The code in this tutorial +can also be used as a playground to hack on other LLVM specific things. +</p> + +<p> +The goal of this tutorial is to progressively unveil our language, describing +how it is built up over time. This will let us cover a fairly broad range of +language design and LLVM-specific usage issues, showing and explaining the code +for it all along the way, without overwhelming you with tons of details up +front.</p> + +<p>It is useful to point out ahead of time that this tutorial is really about +teaching compiler techniques and LLVM specifically, <em>not</em> about teaching +modern and sane software engineering principles. In practice, this means that +we'll take a number of shortcuts to simplify the exposition. For example, the +code leaks memory, uses global variables all over the place, doesn't use nice +design patterns like <a +href="http://en.wikipedia.org/wiki/Visitor_pattern">visitors</a>, etc... but it +is very simple. If you dig in and use the code as a basis for future projects, +fixing these deficiencies shouldn't be hard.</p> + +<p>I've tried to put this tutorial together in a way that makes chapters easy to +skip over if you are already familiar with or are uninterested in the various +pieces. The structure of the tutorial is: +</p> + +<ul> +<li><b><a href="#language">Chapter #1</a>: Introduction to the Kaleidoscope +language, and the definition of its Lexer</b> - This shows where we are going +and the basic functionality that we want it to do. In order to make this +tutorial maximally understandable and hackable, we choose to implement +everything in Objective Caml instead of using lexer and parser generators. +LLVM obviously works just fine with such tools, feel free to use one if you +prefer.</li> +<li><b><a href="OCamlLangImpl2.html">Chapter #2</a>: Implementing a Parser and +AST</b> - With the lexer in place, we can talk about parsing techniques and +basic AST construction. This tutorial describes recursive descent parsing and +operator precedence parsing. Nothing in Chapters 1 or 2 is LLVM-specific, +the code doesn't even link in LLVM at this point. :)</li> +<li><b><a href="OCamlLangImpl3.html">Chapter #3</a>: Code generation to LLVM +IR</b> - With the AST ready, we can show off how easy generation of LLVM IR +really is.</li> +<li><b><a href="OCamlLangImpl4.html">Chapter #4</a>: Adding JIT and Optimizer +Support</b> - Because a lot of people are interested in using LLVM as a JIT, +we'll dive right into it and show you the 3 lines it takes to add JIT support. +LLVM is also useful in many other ways, but this is one simple and "sexy" way +to shows off its power. :)</li> +<li><b><a href="OCamlLangImpl5.html">Chapter #5</a>: Extending the Language: +Control Flow</b> - With the language up and running, we show how to extend it +with control flow operations (if/then/else and a 'for' loop). This gives us a +chance to talk about simple SSA construction and control flow.</li> +<li><b><a href="OCamlLangImpl6.html">Chapter #6</a>: Extending the Language: +User-defined Operators</b> - This is a silly but fun chapter that talks about +extending the language to let the user program define their own arbitrary +unary and binary operators (with assignable precedence!). This lets us build a +significant piece of the "language" as library routines.</li> +<li><b><a href="OCamlLangImpl7.html">Chapter #7</a>: Extending the Language: +Mutable Variables</b> - This chapter talks about adding user-defined local +variables along with an assignment operator. The interesting part about this +is how easy and trivial it is to construct SSA form in LLVM: no, LLVM does +<em>not</em> require your front-end to construct SSA form!</li> +<li><b><a href="OCamlLangImpl8.html">Chapter #8</a>: Conclusion and other +useful LLVM tidbits</b> - This chapter wraps up the series by talking about +potential ways to extend the language, but also includes a bunch of pointers to +info about "special topics" like adding garbage collection support, exceptions, +debugging, support for "spaghetti stacks", and a bunch of other tips and +tricks.</li> + +</ul> + +<p>By the end of the tutorial, we'll have written a bit less than 700 lines of +non-comment, non-blank, lines of code. With this small amount of code, we'll +have built up a very reasonable compiler for a non-trivial language including +a hand-written lexer, parser, AST, as well as code generation support with a JIT +compiler. While other systems may have interesting "hello world" tutorials, +I think the breadth of this tutorial is a great testament to the strengths of +LLVM and why you should consider it if you're interested in language or compiler +design.</p> + +<p>A note about this tutorial: we expect you to extend the language and play +with it on your own. Take the code and go crazy hacking away at it, compilers +don't need to be scary creatures - it can be a lot of fun to play with +languages!</p> + +</div> + +<!-- *********************************************************************** --> +<h2><a name="language">The Basic Language</a></h2> +<!-- *********************************************************************** --> + +<div> + +<p>This tutorial will be illustrated with a toy language that we'll call +"<a href="http://en.wikipedia.org/wiki/Kaleidoscope">Kaleidoscope</a>" (derived +from "meaning beautiful, form, and view"). +Kaleidoscope is a procedural language that allows you to define functions, use +conditionals, math, etc. Over the course of the tutorial, we'll extend +Kaleidoscope to support the if/then/else construct, a for loop, user defined +operators, JIT compilation with a simple command line interface, etc.</p> + +<p>Because we want to keep things simple, the only datatype in Kaleidoscope is a +64-bit floating point type (aka 'float' in O'Caml parlance). As such, all +values are implicitly double precision and the language doesn't require type +declarations. This gives the language a very nice and simple syntax. For +example, the following simple example computes <a +href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci numbers:</a></p> + +<div class="doc_code"> +<pre> +# Compute the x'th fibonacci number. +def fib(x) + if x < 3 then + 1 + else + fib(x-1)+fib(x-2) + +# This expression will compute the 40th number. +fib(40) +</pre> +</div> + +<p>We also allow Kaleidoscope to call into standard library functions (the LLVM +JIT makes this completely trivial). This means that you can use the 'extern' +keyword to define a function before you use it (this is also useful for mutually +recursive functions). For example:</p> + +<div class="doc_code"> +<pre> +extern sin(arg); +extern cos(arg); +extern atan2(arg1 arg2); + +atan2(sin(.4), cos(42)) +</pre> +</div> + +<p>A more interesting example is included in Chapter 6 where we write a little +Kaleidoscope application that <a href="OCamlLangImpl6.html#example">displays +a Mandelbrot Set</a> at various levels of magnification.</p> + +<p>Lets dive into the implementation of this language!</p> + +</div> + +<!-- *********************************************************************** --> +<h2><a name="lexer">The Lexer</a></h2> +<!-- *********************************************************************** --> + +<div> + +<p>When it comes to implementing a language, the first thing needed is +the ability to process a text file and recognize what it says. The traditional +way to do this is to use a "<a +href="http://en.wikipedia.org/wiki/Lexical_analysis">lexer</a>" (aka 'scanner') +to break the input up into "tokens". Each token returned by the lexer includes +a token code and potentially some metadata (e.g. the numeric value of a number). +First, we define the possibilities: +</p> + +<div class="doc_code"> +<pre> +(* The lexer returns these 'Kwd' if it is an unknown character, otherwise one of + * these others for known things. *) +type token = + (* commands *) + | Def | Extern + + (* primary *) + | Ident of string | Number of float + + (* unknown *) + | Kwd of char +</pre> +</div> + +<p>Each token returned by our lexer will be one of the token variant values. +An unknown character like '+' will be returned as <tt>Token.Kwd '+'</tt>. If +the curr token is an identifier, the value will be <tt>Token.Ident s</tt>. If +the current token is a numeric literal (like 1.0), the value will be +<tt>Token.Number 1.0</tt>. +</p> + +<p>The actual implementation of the lexer is a collection of functions driven +by a function named <tt>Lexer.lex</tt>. The <tt>Lexer.lex</tt> function is +called to return the next token from standard input. We will use +<a href="http://caml.inria.fr/pub/docs/manual-camlp4/index.html">Camlp4</a> +to simplify the tokenization of the standard input. Its definition starts +as:</p> + +<div class="doc_code"> +<pre> +(*===----------------------------------------------------------------------=== + * Lexer + *===----------------------------------------------------------------------===*) + +let rec lex = parser + (* Skip any whitespace. *) + | [< ' (' ' | '\n' | '\r' | '\t'); stream >] -> lex stream +</pre> +</div> + +<p> +<tt>Lexer.lex</tt> works by recursing over a <tt>char Stream.t</tt> to read +characters one at a time from the standard input. It eats them as it recognizes +them and stores them in in a <tt>Token.token</tt> variant. The first thing that +it has to do is ignore whitespace between tokens. This is accomplished with the +recursive call above.</p> + +<p>The next thing <tt>Lexer.lex</tt> needs to do is recognize identifiers and +specific keywords like "def". Kaleidoscope does this with a pattern match +and a helper function.<p> + +<div class="doc_code"> +<pre> + (* identifier: [a-zA-Z][a-zA-Z0-9] *) + | [< ' ('A' .. 'Z' | 'a' .. 'z' as c); stream >] -> + let buffer = Buffer.create 1 in + Buffer.add_char buffer c; + lex_ident buffer stream + +... + +and lex_ident buffer = parser + | [< ' ('A' .. 'Z' | 'a' .. 'z' | '0' .. '9' as c); stream >] -> + Buffer.add_char buffer c; + lex_ident buffer stream + | [< stream=lex >] -> + match Buffer.contents buffer with + | "def" -> [< 'Token.Def; stream >] + | "extern" -> [< 'Token.Extern; stream >] + | id -> [< 'Token.Ident id; stream >] +</pre> +</div> + +<p>Numeric values are similar:</p> + +<div class="doc_code"> +<pre> + (* number: [0-9.]+ *) + | [< ' ('0' .. '9' as c); stream >] -> + let buffer = Buffer.create 1 in + Buffer.add_char buffer c; + lex_number buffer stream + +... + +and lex_number buffer = parser + | [< ' ('0' .. '9' | '.' as c); stream >] -> + Buffer.add_char buffer c; + lex_number buffer stream + | [< stream=lex >] -> + [< 'Token.Number (float_of_string (Buffer.contents buffer)); stream >] +</pre> +</div> + +<p>This is all pretty straight-forward code for processing input. When reading +a numeric value from input, we use the ocaml <tt>float_of_string</tt> function +to convert it to a numeric value that we store in <tt>Token.Number</tt>. Note +that this isn't doing sufficient error checking: it will raise <tt>Failure</tt> +if the string "1.23.45.67". Feel free to extend it :). Next we handle +comments: +</p> + +<div class="doc_code"> +<pre> + (* Comment until end of line. *) + | [< ' ('#'); stream >] -> + lex_comment stream + +... + +and lex_comment = parser + | [< ' ('\n'); stream=lex >] -> stream + | [< 'c; e=lex_comment >] -> e + | [< >] -> [< >] +</pre> +</div> + +<p>We handle comments by skipping to the end of the line and then return the +next token. Finally, if the input doesn't match one of the above cases, it is +either an operator character like '+' or the end of the file. These are handled +with this code:</p> + +<div class="doc_code"> +<pre> + (* Otherwise, just return the character as its ascii value. *) + | [< 'c; stream >] -> + [< 'Token.Kwd c; lex stream >] + + (* end of stream. *) + | [< >] -> [< >] +</pre> +</div> + +<p>With this, we have the complete lexer for the basic Kaleidoscope language +(the <a href="OCamlLangImpl2.html#code">full code listing</a> for the Lexer is +available in the <a href="OCamlLangImpl2.html">next chapter</a> of the +tutorial). Next we'll <a href="OCamlLangImpl2.html">build a simple parser that +uses this to build an Abstract Syntax Tree</a>. When we have that, we'll +include a driver so that you can use the lexer and parser together. +</p> + +<a href="OCamlLangImpl2.html">Next: Implementing a Parser and AST</a> +</div> + +<!-- *********************************************************************** --> +<hr> +<address> + <a href="http://jigsaw.w3.org/css-validator/check/referer"><img + src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> + <a href="http://validator.w3.org/check/referer"><img + src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> + + <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> + <a href="mailto:idadesub@users.sourceforge.net">Erick Tryzelaar</a><br> + <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br> + Last modified: $Date$ +</address> +</body> +</html> |