Status

Nothing works: Rust code completely outdated. Maybe one day I'll fix it.

State corresponds to the Chapter 7 of the original tutorial (i.e. mutable variables implemented).

LLVM tutorial in the Rust language.

This tutorial is a work in progress and at the moment I'm working on getting it fully working with the latest Rust and on improvinvg the way it uses LLVM.

Chapter 0. Introduction
Chapter 1. Parser and AST implementation
Chapter 2. LLVM IR code generation
Chapter 3. Optimizer and JIT support
Chapter 4. Extending Kaleidoscope: control flow
- If/Then/Else
  - Lexer and parser changes for if/then/else
  - IR generation for if/then/else
- 'For' loop
  - Lexer and parser changes for the 'for' loop
  - IR generation for the 'for' loop
Chapter 5. Extending Kaleidoscope: user-defined operators
Chapter 6. Extending Kaleidoscope: mutable variables

Chapter 0. Introduction

This tutorial shows how to implement a simple programming language using LLVM and Rust. Its first goal is to show how to use LLVM to create a simple REPL, so some knowledge of Rust is assumed. To be honest, author himself is a very beginner both in Rust and LLVM, so any feedback is highly appreciated.

The code in the repository corresponds to the state of your program at the end of the last chapter and serves as a starting point for further experiments.

If you want to look at code that corresponds to a given chapter, see chapters directory. Link to relevant code is attached to every chapter (work in progress).

To experiment with the code in this repo you need:

the latest Rust compiler
Cargo Rust package manager
LLVM (I have used ver. 3.6)

To build the code just clone the repo and execute

cargo build

Then you will find an executable named iron-kaleidoscope in the target directory.

Basic variant of the Kaleidoscope language

In this tutorial we will use a simple functional language named Kaleidoscope. In this chapter its basic variant will be presented. New features will be added in the next chapters step by step.

The language has only one type: 64-bit floating point numbers (f64 in the Rust terminology).

The first variant of the language is very limited and even not Turing complete. It includes only function defenitions (or declarations) and function invocations together with some simple arithmetic operators. Examples follow.

Arithmetic expression:

1 + 2 * (3 - 4);

Function definition:

def plus(x, y)
    x + y

Function invocation:

plus(1 2)

Extern function declaration and invocation:

extern sin(x);

sin(1)

Every statement except of definitions and declarations in Kaleidoscope is an expression and has the corresponding value. Quite similar to Rust. Function body is just an expression, its value is returned. No explicit return operator is used.

To show the end of an expression or definition (declaration) we use ';' character. ',' character in function prototypes/calls is equivalent to the space character. Comments are started by '#' and last until the end of the line.

Names of variables start with an alphabetical character and contain any number of alphanumerical characters. Reserved words at the moment include def and extern. Any non-alphanumerical non-whitespace character different from '(', ')', ';' and ',' is treated as an operator.

A number literal is a nonempty sequence of decimal digits, possibly containing a decimal point character.

The project structure

To create a REPL we will need (corresponding source files are shown in parenthesis):

the lexer (lexer.rs)
the parser (parser.rs)
the IR builder (builder.rs)
the JIT compiler (jitter.rs)
the driver (driver.rs)

We'll use Cargo as a build system for this project. All sources will live in the src directory. Project will have two crates: library and binary. All real functionality will be implemented in the library, and the binary will just parse command line arguments and invoke the driver.

Cargo.toml file is quite straightforward.

The lexer

To implement the lexer we'll use regular expressions. We have the next types of tokens (and corresponding regexes given in the notation used by the Rust regex library):

def and extern keywords (def|extern)
identifier (\p{Alphabetic}\w*)
number literal (\d+\.?\d*)
semicolon (;)
opening and closing parenthesis (\(|\))
comma (,)
operator (\S)

The corresponding enumeration looks like this:

#[derive(PartialEq, Clone, Debug)]
pub enum Token {
    Def,
    Extern,
    Delimiter, //';' character
    OpeningParenthesis,
    ClosingParenthesis,
    Comma,
    Ident(String),
    Number(f64),
    Operator(String)
}

Note, that to use enumeration members without scopes as we later do, you need to add some uses at the beginning of your module (it is needed since changing enums to be scoped in Rust):

pub use self::Token::{
    Def,
    Extern,
    Delimiter,
    OpeningParenthesis,
    ClosingParenthesis,
    Comma,
    Ident,
    Number,
    Operator
};

We do not mention those uses explicitly in the following.

Our parser function will accept a string with input characters and produce a vector of tokens. It will look like this:

pub fn tokenize(input: &str) -> Vec<Token> {
    // regex for commentaries (start with #, end with the line end)
    let comment_re = regex!(r"(?m)#.*\n");
    // remove commentaries from the input stream
    let preprocessed = comment_re.replace_all(input, "\n");

    let mut result = Vec::new();

    // regex for token, just union of straightforward regexes for different token types
    // operators are parsed the same way as identifier and separated later
    let token_re = regex!(concat!(
        r"(?P<ident>\p{Alphabetic}\w*)|",
        r"(?P<number>\d+\.?\d*)|",
        r"(?P<delimiter>;)|",
        r"(?P<oppar>\()|",
        r"(?P<clpar>\))|",
        r"(?P<comma>,)|",
        r"(?P<operator>\S)"));

    for cap in token_re.captures_iter(preprocessed.as_str()) {
        let token = if cap.name("ident").is_some() {
            match cap.name("ident").unwrap() {
                "def" => Def,
                "extern" => Extern,
                ident => Ident(ident.to_string())
            }
        } else if cap.name("number").is_some() {
            match cap.name("number").unwrap().parse() {
                Ok(number) => Number(number),
                Err(_) => panic!("Lexer failed trying to parse number")
            }
        } else if cap.name("delimiter").is_some() {
            Delimiter
        } else if cap.name("oppar").is_some() {
            OpeningParenthesis
        } else if cap.name("clpar").is_some() {
            ClosingParenthesis
        } else if cap.name("comma").is_some() {
            Comma
        } else {
            Operator(cap.name("operator").unwrap().to_string())
        };

        result.push(token)
    }

    result
}

Quite simple function. About regex in Rust you can read here.

Some comments: we create regex with different groups matching to different types of tokens. Then we match it on the input string and iterate over captures, looking what token we have matched. Identifiers are matched in the same regex with keywords, as they have the same microsyntax. They are separated later with the additional match.

To experiment with this lexer you can create a simple main function that reads lines from the input one by one and shows the recognized tokens. Full code for this chapter is available, but is a little bit more complex then needed as it is autogenerated from the full code.

Chapter 1. AST and parser implementation

In this chapter we will build a parser for the Kaleidoscope language. First we need to define its grammar and how to represent the parsing results. Then we can use Recursive Descent Parsing and Operator-Precedence Parsing to produce the Abstract Syntax Tree from the stream of tokens recognized by the lexer.

The grammar

This grammar description uses the dialect of Extended Backus-Naur Form (EBNF) described in the Rust reference. Identifiers that start with the lowercase name non-terminals. Identifiers that start with the uppercase name terminals and correspond to the names in the Token enum defined in the lexer.

program          : [[statement | expression] Delimiter ? ]*;
statement        : [declaration | definition];
declaration      : Extern prototype;
definition       : Def prototype expression;
prototype        : Ident OpeningParenthesis [Ident Comma ?]* ClosingParenthesis;
expression       : [primary_expr (Op primary_expr)*];
primary_expr     : [Ident | Number | call_expr | parenthesis_expr];
call_expr        : Ident OpeningParenthesis [expression Comma ?]* ClosingParenthesis;
parenthesis_expr : OpeningParenthesis expression ClosingParenthesis;

The Abstract Syntax Tree (AST)

Now we'll create data types corresponding to every item in the Kaleidoscope grammar.

program          : [[statement | expression] Delimiter ? ]*;

Program is a sequence of statements and expressions. To make life easier in the future we will close every expression in an anonymous function (we'll use this during JIT compilation). So, there are two types of items in the program after such a closure: declarations and definitions. Declarations are just function prototypes, when definitions are function prototypes combined with a function body.

The data type corresponding to the programm will be:

Vec<ASTNode>

where ASTNode is defined as

#[derive(PartialEq, Clone, Debug)]
pub enum ASTNode {
    ExternNode(Prototype),
    FunctionNode(Function)
}

ExternNode corresponds to the declaration item in the grammar and FunctionNode corresponds to the definition item.

We define Prototype and Function according to the grammar:

definition       : Def prototype expression;
prototype        : Ident OpeningParenthesis [Ident Comma ?]* ClosingParenthesis;

#[derive(PartialEq, Clone, Debug)]
pub struct Function {
    pub prototype: Prototype,
    pub body: Expression
}

#[derive(PartialEq, Clone, Debug)]
pub struct Prototype {
    pub name: String,
    pub args: Vec<String>
}

Functions are typed only by the number of arguments, as the onliest type in the Kaleidoscope language is an f64 number.

The only thing left to define is the data type that corresponds to the expression item. This one is the most complicated and difficult to parse, as it includes binary expressions with operator precedence.

expression       : [primary_expr (Op primary_expr)*];
primary_expr     : [Ident | Number | call_expr | parenthesis_expr];
call_expr        : Ident OpeningParenthesis [expression Comma ?]* ClosingParenthesis;
parenthesis_expr : OpeningParenthesis expression ClosingParenthesis;

Expression data type will be an enum with entries corresponding to every possible expression type:

#[derive(PartialEq, Clone, Debug)]
pub enum Expression {
    LiteralExpr(f64),
    VariableExpr(String),
    BinaryExpr(String, Box<Expression>, Box<Expression>),
    CallExpr(String, Vec<Expression>)
}

LiteralExpr is a number (Number token). VariableExpr is a variable name (Ident token). So far we have only one type of variables: function parameters. BinaryExpr has information about operator name and subexpressions. And CallExpr fully corresponds to its definition in the grammar.

We did not need a representation for the parenthesis_expr item, as the precedence of evaluation is encoded in the tree formed by BinaryExpr, so parenthesis are used only during parsing. Also, note that Expression definition not fully corresponds to the grammar (grammar has a sequence of primary expressions devided by operators, when here we have a binary tree of binary expressions), we will speak about it later in the section about binary expressions parsing.

Now we can proceed with parsing, as both our input format (the sequence of tokens) and the AST we want to have as the result of parsing are known.

Parser implementation: introduction

Before starting parser implementation we should think about one general question: how will REPL receive the input and how should it work with it. Basically, REPL should allow user to type statements line by line, parsing every line as it is entered. If the line contains not finished statement, REPL should consume line by line until it has something finished that can be interpreted (either declaration/definition or free expression).

As an input we can accept two variables: already parsed AST and tokens that we still need to parse:

tokens : &[Token], parsed_tree : &[ASTNode]

As a result we will have again pair of a parsed AST and tokens that were not parsed because they form nothing finished. Also we need some kind of error handling. It will be achieved by the usage of Result with an error message:

pub type ParsingResult = Result<(Vec<ASTNode>, Vec<Token>), String>;

The function prototype for the parsing function looks like this:

pub fn parse(tokens : &[Token], parsed_tree : &[ASTNode], settings : &mut ParserSettings) -> ParsingResult
pub fn parse(tokens : &[Token], parsed_tree : &[ASTNode], settings : &mut ParserSettings) -> ParsingResult;

At the moment ParserSettings can be just an empty enum, in the nearest future we will use them for handling binary expressions (they will contain information about operator precedence). They are mutable because later on we may want to add some dynamically defined constructions to the language that will need additional information to be stored in the parser settings.

Top level parse function

The majority of the parsing will be done by the recursive descent parser. This kind of parsers is easy for understanding and implementation. Every production rule in the grammar has a corresponding function, these functions call each other according to the production rules.

We will need to handle input tokens efficiently, being able to pick them one by one, or return back to the input vector, this can be easily