Here’s part 4 of my infinite part series on developing a compiler from scratch.  See all the posts here.

I’ve decided to change things up a bit on the compiler project.  Instead of writing the tokenizer and parser from scratch, I’m going to check out a new language that’s part of Microsoft’s “Oslo” Project.  Oslo includes a language called M, which is primarily designed for developing data models.  M is actually three languages, MGraph, MSchema and MGrammar.  MGraph is a language for defining abstract graphs, for example:

Universities {
    Canada {
        BritishColumbia {
            SFU { 
                Name { "Simon Fraser University" }, 
                Location { "Burnaby, BC" } 
            },
            UBC { 
                Name { "University of British Columbia" }, 
                Location { "Vancouver, BC" } 
            }
        }
    }
}

MSchema is a language for defining the schema for these graphs, for example

module Universities {
    type University {
        Name : Text#100,
        Location : Text#100
    }
}

Finally, MGrammar is a language for defining custom Domain-Specific Languages (DSLs) which map to MGraph graphs. This is the language that is most useful to this project. After all, a general-purpose programming language is just a DSL where the "Domain" is very broad :). So, I've spent a few hours this week whipping up an MGrammar grammar for Duh, and the results are promising.  I’ll be posting some details on that in the next post, but first we need to explore a key concept in compilers, Abstract Syntax Trees.

The end goal of the tokenization and parsing phases of a compiler is to produce an Abstract Syntax Tree (or AST) representing the source code.  This is probably best illustrated by an example, so consider this expression:

5+6

This is an addition operation, using 5 and 6 as the arguments, which we represent in an AST like this (using the MGraph syntax above):

Add { 5, 6 }

Similarly, more complex expressions can be translated to trees:

5+6*(3+4)

Becomes:

Add { 5, Multiply { 6, Add { 3, 4 } } }

Which represents the following instructions:

• Add 3 and 4
• Multiply that result by 6
• Add 5 to that result

Essentially, we are building up the expression from the bottom of the tree up.  This makes it much easier to convert the expression into code.

I’ll post the MGrammar file for the language when I finish it up in a day or so, then its on to writing the code to do the parsing.

Here comes part 3 of my infinite part series on developing a compiler from scratch.  See all the posts here.

The first phase of compilation is called Tokenization.  Tokenization is the process of taking individual characters in the source code file and grouping them into more conceptual “Tokens.”  We’re not parsing the language, or checking syntax, we’re just grouping related characters together.  Why do we do this?  If we skipped this step, we’d be passing characters directly to our parser.  The parser doesn’t care that the text contains the characters ‘f’ ‘o’ ‘o’, it cares that the source file contains an Identifier called “foo”.  There’s also a separation of concerns issue.  In theory, if you wanted to allow accented Unicode characters like è, ê, ã, à, etc. (you may see blocks or ‘?’ characters instead of the real characters, if so just pretend they’re there :D) as valid characters in identifiers, you should only have to change the Tokenizer (to accept those characters and use them, along with the regular alphanumeric characters, to build identifier tokens).  The formal name for Tokenization is actually “Lexical Analysis,” and sometimes the Tokens are called “Atoms.”

So, how do we Tokenize text?  There are lots of tools out there, most of which let you define your tokens using Regular Expressions (so an identifier would be: “[_A-Za-z][_0-9A-Za-z]*”, one letter or underscore followed by zero or more letters, numbers or underscores).  These tools build state machines (aka “Finite Automata”) that basically walk through all the Regular Expressions until exactly one of them matches the current text buffer.  Tools like “lex” basically allow you to build a full-featured, efficient, Tokenizer by simply writing Regular Expressions.

However, that would be too easy for this series :).  Instead, I’m using a very simple, hand-coded, Tokenizer which walks through the characters, using “if” and “switch” statements to decide what tokens to output.  However, we can’t just simply iterate through the characters.  Consider the ”->” operator in Duh (see Part 1).  Duh supports the simple arithmetic operators, specifically “-“, and I plan to support inequality operators (i.e “<”, “>”, etc.), so in theory, the “->” operator could be outputted as a pair of tokens: MINUS and GREATERTHAN (I’ll use ALLCAPS to denote the names of tokens).  However, this would be putting a larger burden on the parser to detect the MINUS GREATERTHAN pattern.  Instead, we can take advantage of “lookahead”

The Tokenizer uses the .Net TextReader class, which lets us walk, one character at a time, through the characters in a body of text.  However, once we’ve called the Read method, the TextReader moves on to the next character and the next time we call it, we’ll get the next character.  So, in order to properly parse the “->” operator, we need a way to look at the next character, without moving the reader.  Fortunately, the TextReader also has the Peek method, which does exactly that.

So now, when we encounter a “-“ symbol, we look at the next character.  If it is a “>”, we output an ARROW token, and move to the next character.  Otherwise, we output a MINUS token and leave the reader at the “>” character.  Then, in the next iteration, we read the “>” and output a GREATERTHAN token.

Phew, that was a bit long, and more theoretical than I like, but I’ll post some code in the next part.  Next time, we’ll look at the actual code for the Tokenizer.

Well, this is a good sign, I’m posting part 2 :).  As I said in Part 1, there are no promises here.  This series may not go anywhere, I may have to drop it due to my other commitments (school, work, etc.).

In the next few posts, I’m going to talk about the Tokenization phase of the compiler.  Before I go into too much detail on that though, I want to talk about newlines.

In Windows, a new line in a text file is indicated by a pair of characters: A Carriage Return (commonly referred to as “\r'”, as that is the C/C++ string escape sequence for it) followed by a Line Feed (”\n”).  However, in Unix-based operating systems, a new line is often indicated by a Line Feed character alone.  To add even more confusion, the Mac OS uses a Carriage Return character alone. 

A compiler needs to track line numbers accurately, in order to report errors, so we need be extra careful around newlines.  We could simply use the current operating system’s default newline characters, but that makes it difficult for multi-platform development.  Instead, we’ll normalize the newlines so that all three different types are properly understood by our compiler.

To do this, I’ve written a “Decorator” class which inherits from the abstract TextReader class provided in the .Net framework.  This “Newline Normalizing” decorator wraps an existing TextReader and does all the work of normalizing new line characters  TextReader provides two methods that need to be implemented, Read and Peek.  Read returns the current character from the text and moves the reader one character forwards (so that the next call to Read will return the next character).  Peek also returns the current character from the text but does not move the reader forward.  The “Newline Normalizing” reader implements these two methods using the following code

public override int Peek() {
    // Get the next character
    int i = Adaptee.Peek();
    
    // If the character is a '\r' newline, just return '\n'.  
    // Unlike Read, we aren't going to read ahead to check for \r\n
    // because that will happen when the user calls Read()
    if (i == (int)'\r') {
        i =  (int)'\n';
    }

    return i;
}

public override int Read() {
    // Get the next character
    int i = Adaptee.Read();

    // If the character is a '\r' newline, we're going to normalize it to '\n'
    // However, if the newline is '\r\n', we need to return it as one character, so
    // we check ahead for that
    if (i == (int)'\r') {
        if (Adaptee.Peek() == (int)'\n') {
            Adaptee.Read(); // Skip the '\n'
        }
        i = (int)'\n';
    }

    return i;
}

Essentially, if the character we read from the source (the “Adaptee” as I call it) is a ‘\n’, we just pass it along.  If the character is a ‘\r’, we are going to return ‘\n’, but first we first check to see if it is immediately followed by a ‘\n’.  If it is, we skip the extra character.  The result is that no matter which newline sequence is used, this TextReader will return it as a single ‘\n’ character.

Next post, I’ll start talking about the Tokenization process.

EDIT: Whoops, wrote the wrong course number (CMPT 376), corrected below.  I’m taking CMPT 376, Writing for Computer Scientists, this semester, must have gotten myself mixed up :)

Ok, I’m going to try something here, and I don’t know if I’ll manage to finish it.  My all-time favorite class in my school career (so far) has been CMPT 379 – Compiler Design.  The class basically consisted of me writing a compiler in Visual C++, with weekly lectures and code reviews from the professor (it was a small class).  Since then, I’ve been trying to think of a reason to write a compiler (i.e. a language that can be ported to .Net, or a useful domain-specific language, etc.).  Then, this morning, as I walked back to the Computing Science common room from the Gym (after my morning workout), I found a reason.  I think compilers are some of the most interesting pieces of software, and I thought that if I wrote a series of blog posts in which I developed a compiler, maybe I could share that passion with others. 

So, here’s the plan:  I’ve designed an, extremely simple, language that I’m going to walk through writing a compiler for.  The initial version will target .Net IL code (since it’s a stack machine system, which is much easier to generate code for).  Once I’ve implemented the simple language, I think it’d be awesome if my readers could jump in and propose some ideas for new language features, and I’ll try to blog about implementing them.

To be honest, this project may well fall flat on its face.  Writing a compiler is not a simple task, no matter how simple the language.  However, I do think it will be fun (while it lasts), so let’s give it a try!

So, step one is: Define your language!  The most essential part of compiler design is having a very clear idea of the purpose of your language.  The language I’m going to design is called “Duh”, because it’s probably about as simple as it gets (maybe a little more complex than Brainf**k (NOTE: link target does include a few four-letter words :D)).  Here’s a sample Duh program

print "Enter your age: ";
ageInput : string;
age : int;
ageInput = readline;
age = ageInput -> int;
print "In 10 years you will be " + (age + 10) -> string + ". Wow, that's old"

Pretty simple, eh?  Line 1 is a simple print statement, which accepts a string and write it to the console.  Lines 2 and 3 declare variables of string and 32-bit integer types (decided to use a more Pascal-esque variable declaration format, just for fun).  Lines 4 and 5 assign values to those variables.  Line 4 uses another built-in function, readline, which reads a line of text from the console.  Note that we don’t even support initializing variables in the declaration!  That’s ok though, this is just a toy language, we can add initializations later.  Line 5 introduces the “->” conversion operator, which takes the value on the left and converts it to the type on the right.  It’s not quite the same as a cast, because it will try to convert the value, if it can.  Finally, we add 10 to the value the user entered and convert it to a string, then we place that string into a large message and print it to the console.

Well, here goes nothing!  Feel free to post your initial comments.  I hope you’ll follow along!  I’ll be posting full source code with every post