From 169d2bd06003c39970bc94c99669a34b61bb7e45 Mon Sep 17 00:00:00 2001 From: dim Date: Mon, 8 Apr 2013 18:41:23 +0000 Subject: Vendor import of llvm trunk r178860: http://llvm.org/svn/llvm-project/llvm/trunk@178860 --- docs/tutorial/LangImpl1.html | 348 ------------------------------------------- 1 file changed, 348 deletions(-) delete mode 100644 docs/tutorial/LangImpl1.html (limited to 'docs/tutorial/LangImpl1.html') diff --git a/docs/tutorial/LangImpl1.html b/docs/tutorial/LangImpl1.html deleted file mode 100644 index 717454f..0000000 --- a/docs/tutorial/LangImpl1.html +++ /dev/null @@ -1,348 +0,0 @@ - - - - - Kaleidoscope: Tutorial Introduction and the Lexer - - - - - - - -

Kaleidoscope: Tutorial Introduction and the Lexer

- - - -
-

Written by Chris Lattner

-
- - -

Tutorial Introduction

- - -
- -

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. -

- -

-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.

- -

It is useful to point out ahead of time that this tutorial is really about -teaching compiler techniques and LLVM specifically, not 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 visitors, 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.

- -

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: -

- - - -

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.

- -

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!

- -
- - -

The Basic Language

- - -
- -

This tutorial will be illustrated with a toy language that we'll call -"Kaleidoscope" (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.

- -

Because we want to keep things simple, the only datatype in Kaleidoscope is a -64-bit floating point type (aka 'double' in C 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 Fibonacci numbers:

- -
-
-# 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)
-
-
- -

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:

- -
-
-extern sin(arg);
-extern cos(arg);
-extern atan2(arg1 arg2);
-
-atan2(sin(.4), cos(42))
-
-
- -

A more interesting example is included in Chapter 6 where we write a little -Kaleidoscope application that displays -a Mandelbrot Set at various levels of magnification.

- -

Lets dive into the implementation of this language!

- -
- - -

The Lexer

- - -
- -

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 "lexer" (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: -

- -
-
-// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
-// of these for known things.
-enum Token {
-  tok_eof = -1,
-
-  // commands
-  tok_def = -2, tok_extern = -3,
-
-  // primary
-  tok_identifier = -4, tok_number = -5,
-};
-
-static std::string IdentifierStr;  // Filled in if tok_identifier
-static double NumVal;              // Filled in if tok_number
-
-
- -

Each token returned by our lexer will either be one of the Token enum values -or it will be an 'unknown' character like '+', which is returned as its ASCII -value. If the current token is an identifier, the IdentifierStr -global variable holds the name of the identifier. If the current token is a -numeric literal (like 1.0), NumVal holds its value. Note that we use -global variables for simplicity, this is not the best choice for a real language -implementation :). -

- -

The actual implementation of the lexer is a single function named -gettok. The gettok function is called to return the next token -from standard input. Its definition starts as:

- -
-
-/// gettok - Return the next token from standard input.
-static int gettok() {
-  static int LastChar = ' ';
-
-  // Skip any whitespace.
-  while (isspace(LastChar))
-    LastChar = getchar();
-
-
- -

-gettok works by calling the C getchar() function to read -characters one at a time from standard input. It eats them as it recognizes -them and stores the last character read, but not processed, in LastChar. The -first thing that it has to do is ignore whitespace between tokens. This is -accomplished with the loop above.

- -

The next thing gettok needs to do is recognize identifiers and -specific keywords like "def". Kaleidoscope does this with this simple loop:

- -
-
-  if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
-    IdentifierStr = LastChar;
-    while (isalnum((LastChar = getchar())))
-      IdentifierStr += LastChar;
-
-    if (IdentifierStr == "def") return tok_def;
-    if (IdentifierStr == "extern") return tok_extern;
-    return tok_identifier;
-  }
-
-
- -

Note that this code sets the 'IdentifierStr' global whenever it -lexes an identifier. Also, since language keywords are matched by the same -loop, we handle them here inline. Numeric values are similar:

- -
-
-  if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
-    std::string NumStr;
-    do {
-      NumStr += LastChar;
-      LastChar = getchar();
-    } while (isdigit(LastChar) || LastChar == '.');
-
-    NumVal = strtod(NumStr.c_str(), 0);
-    return tok_number;
-  }
-
-
- -

This is all pretty straight-forward code for processing input. When reading -a numeric value from input, we use the C strtod function to convert it -to a numeric value that we store in NumVal. Note that this isn't doing -sufficient error checking: it will incorrectly read "1.23.45.67" and handle it as -if you typed in "1.23". Feel free to extend it :). Next we handle comments: -

- -
-
-  if (LastChar == '#') {
-    // Comment until end of line.
-    do LastChar = getchar();
-    while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
-    
-    if (LastChar != EOF)
-      return gettok();
-  }
-
-
- -

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:

- -
-
-  // Check for end of file.  Don't eat the EOF.
-  if (LastChar == EOF)
-    return tok_eof;
-  
-  // Otherwise, just return the character as its ascii value.
-  int ThisChar = LastChar;
-  LastChar = getchar();
-  return ThisChar;
-}
-
-
- -

With this, we have the complete lexer for the basic Kaleidoscope language -(the full code listing for the Lexer is -available in the next chapter of the tutorial). -Next we'll build a simple parser that uses this to -build an Abstract Syntax Tree. When we have that, we'll include a driver -so that you can use the lexer and parser together. -

- -Next: Implementing a Parser and AST -
- - -
-
- Valid CSS! - Valid HTML 4.01! - - Chris Lattner
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2012-05-03 00:46:36 +0200 (Thu, 03 May 2012) $ -
- - -- cgit v1.1