Crafting a Compiler in Rust: Lexical Analysis
Tags: rust, compilers, tutorial, computerscience
Published: 2022-12-08 22:56:19

Let's create a project for the compiler. It'll be named `pernix-lang`. Inside the folder `pernix-lang`, the [Cargo Workspace](https://doc.rust-lang.org/book/ch14-03-cargo-workspaces.html) project locates here. I'll separate each different compiler phase into an individually distinct library crate.

## The Pernix Project Crate
Before going into writing the compiler, let's create a crate called `pernix_project`.

``` sh
cargo new --lib compiler/pernix_project
```

Add the newly created crate path in the `Cargo.toml` workspace file.

``` toml
[workspace]
members = [
    "compiler/pernix_project",
]
```
The workspace should look something like this: 
```
├── Cargo.toml
├── compiler/pernix_project
│   ├── Cargo.toml
│   └── src
│       └── src.rs
```

This crate contains all the code related to the language's project 
such as source files, directories, targets, and libraries.

Let's write code for the `pernix_project` crate. I'll create a new module inside the crate named `source_code`. This module contains the `SourceCode` and `SourcePosition` structs; these structs involve source file inputs.

- The `SourceCode` struct manages the content of the source file. It provides utility functions such as inspecting the source file's content by the line number. 
- The `SourcePosition` consists of two fields: line and column numbers.

Full Code Listing of [`source_code.rs`](https://github.com/Simmypeet/pernix-lang/blob/d81b2dd8ff89f2b20ed3e8a7babc8994a389e95e/compiler/pernix_project/src/source_code.rs)
``` rust
/// Represents a source code
pub struct SourceCode {
    source_code: String,
    source_name: String,
    new_line_ranges: Vec<Range<usize>>,
}

/// Represents a particular position in the source code, consisting of column
/// and line
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct SourcePosition {
    pub line: usize,
    pub column: usize,
}
```

Here's the snippet of the code of the `SourceCode` struct in action. 
``` rs
#[test]
fn test_line() {
    let source_code = SourceCode::new(
        "Hello, world!\n".to_string()
            + "My Name Is Pernix\n"
            + "I am a programming language\n"
            + "I am written in Rust\n"
            + "\n",
        "test".to_string(),
    );

    assert_eq!(source_code.line(1).unwrap(), "Hello, world!");
    assert_eq!(source_code.line(2).unwrap(), "My Name Is Pernix");
    assert_eq!(source_code.line(3).unwrap(), "I am a programming language");
    assert_eq!(source_code.line(4).unwrap(), "I am written in Rust");
    assert_eq!(source_code.line(5).unwrap(), "");
}
```

## The Pernix Lexer Crate

Before doing the actual code, let's discuss more in-depth **Lexical Analysis**. Generally speaking, **Lexical Analysis** is the phase where the source code is fed to a lexer or scanner and converted into a stream of tokens. When working with a lexer, you will likely stumble across these terms: lexeme and token.
- The **lexeme** is a term used to describe a sequence of characters matched by a well-defined pattern or rule.
- The **token** is a term used to describe a syntactic category that constitutes the lexeme.

For example, the following code would produce a token stream like this:

``` cpp
int main() {
    return 0;
}
```
| **TokenKind** | **Lexeme** |
|---------------|------------|
| IDENTIFIER    | int        |
| IDENTIFIER    | main       |
| PUNCTUATOR    | (          |
| PUNCTUATOR    | )          |
| PUNCTUATOR    | {          |
| KEYWORD       | return     |
| LITERAL       | 0          |
| PUNCTUATOR    | ;          |
| PUNCTUATOR    | }          |

Now that we've understood the basics of the Lexical Analysis phase, Let's create a library crate that contains the lexer for the compiler, `pernix_lexer`.

``` sh
cargo new --lib compiler/pernix_lexer
```
``` toml
[workspace]
members = [
    "compiler/pernix_project",
    "compiler/pernix_lexer",
]
```

Let's create a new module in this crate named `token`. This module contains the code related to the lexical token.

Now, let's write an enum with all token-kind values.

``` rs
/// Enumeration containing all patterns of token
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TokenKind {
    Identifier,
    Space,
    Comment,
    Keyword(Keyword),
    LiteralConstant,
    Punctuator(char),
    EndOfFile,
}
```

There're seven kinds of tokens defined here; Let's discuss each of them one by one.
- An **Identifier** is a string of characters used to give a name to a particular symbol or declaration.
- A **Space** represents a string of whitespaces defined in the source file, including whitespaces.
- A **Comment** represents a text in the source file that doesn't alter the program's behavior but is meant to be an annotation for the programmer.
- A **Keyword** is a string, similar to an identifier, but the language reserves since it often has a special meaning that commands particular program behavior.
- A **Literal Constant** is any hard-coded value in the source file, including numbers, boolean-value, and strings.
- A **Punctuator** is a token with syntactic and semantic meaning to the compiler, but the exact significance depends on the context.
- A **EndOfFile** signifies the end of the token stream.

Now let's write a `Token` struct, the data structure that the lexer will produce.

```rust
/// Represents a single token word; containing type of the token and its lexeme
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Token<'a> {
    token_kind: TokenKind,
    position_range: Range<SourcePosition>,
    lexeme: &'a str,
```

This struct has only three fields. It contains the kind of token, a string representing the lexeme, and a position in the source file that makes up this token.

### Error Handling

Having a sophisticated error-handling system is crucial when writing a compiler. It should include helpful information for the user and report a useful message.

Let's create a new module called `error`. This module contains code related to the error-handling system.

Next, create an enum called `Error`, containing all possible Lexical Error types.

``` rust
/// An enumeration containing all lexical errors
pub enum Error<'a> {
    InvalidCharacter {
        position: SourcePosition,
        character: char,
        source_refernece: &'a SourceCode,
    },
    UnterminatedMultilineComment {
        multiline_comment_position: SourcePosition,
        source_refernece: &'a SourceCode,
    },
}
```

Each enum variant stores all necessary information about the error that can use to report the error message.

Next, implement an associated function that prints out the error message based on the stored information.

Full Code Listing of [`error.rs`](https://github.com/Simmypeet/pernix-lang/blob/d81b2dd8ff89f2b20ed3e8a7babc8994a389e95e/compiler/pernix_lexer/src/error.rs)
``` rust
impl<'a> Error<'a> {
    /// Prints the error message to the standard output
    pub fn print_error(&self) { ... }
}
```

> The ellipses here signify that the code is lengthy and will not be included here. However, the complete code listing is provided at the beginning as a link to the GitHub repository.

### Writing the Lexer

Now, back to writing the lexer. I will write the code of the lexer in the `lib.rs` file. The `Lexer` struct consumes the characters and omits one token at a time -- kind of like an iterator.

Psuedo code of using the lexer:
``` rust
let mut lexer = Lexer::new(&source_code);
let first_token = lexer.lex();
let second_token = lexer.lex();
```

Let's write a `Lexer` struct.
``` rust
/// Represents a lexer in lexical analysis which transforms source code into a
/// token stream
pub struct Lexer<'a> {
    source_code: &'a SourceCode,
    chars: Peekable<CharIndices<'a>>,
    current_position: SourcePosition,
}
```

It contains a reference to the input source code, an iterator using `Peekable<CharIndices>`, and a variable for tracking the current lexing position.

Before writing the code for lexing, we need a helper function that eats one character at a time; keeps tracking its current source code position; and returns the character value and the UTF-8 byte position, which is used for slicing the source code for constructing the lexeme.

``` rust
impl<'a> Lexer<'a> {
    // returns the current character and the its byte index , and moves to the
    // next character
    fn next(&mut self) -> Option<(usize, char)> {
        let next = self.chars.next();

        // increment to the next position
        match next {
            Some(char) => {
                if char.1 == '\n' {
                    self.current_position.line += 1;
                    self.current_position.column = 1;
                } else {
                    self.current_position.column += 1;
                }
            }
            _ => {}
        }
        next
    }
}
```

Next, we need a hash table that stores every reserved keyword in the language. I'll use the `lazy_static` crate from `crates.io` for this case.

``` rust
lazy_static! {
    static ref KEYWORD: HashMap<&'static str, Keyword> = {
        let mut map = HashMap::new();
        map.insert("return", Keyword::Return);
        map
    };
}
```

After that, we got everything required for writing the `lex` function. As discussed earlier, it moves the characters forward and returns the token.

Full Code Listing of [`lib.rs`](https://github.com/Simmypeet/pernix-lang/blob/d81b2dd8ff89f2b20ed3e8a7babc8994a389e95e/compiler/pernix_lexer/src/lib.rs)
``` rust
impl<'a> Lexer<'a> {
    /// Lexes the current word; returns the corresponding token and moves to
    /// the next token.
    pub fn lex(&mut self) -> Result<Token<'a>, Error<'a>> { ... }
}
```

The actual implementation is lengthy, but I'll briefly explain how the function is implemented.

First, the function eats the first character by calling the `next` function and moves to the next character. If it returns `None,` the `lex` function exits immediately and returns the `EndOfFile` token. Otherwise, it proceeds. Next, from the given first character, the function now has a clue of what kind of token will be. The character is then matched against these following if-else branches to determine their token kind.

> Python is used here, as the psuedo-code for brevity and conciseness.

- If the first character is whitespace, the function eats all the next consecutive whitespaces if there are any. The token is categorized as `TokenKind::Space`.
``` python
if first_char.is_whitespace():   
    while self.peek().is_whitespace():
        self.next()
    return SPACE    
```

- If the first character is a forward slash, the function checks whether or not the next character is a forward slash too; if it is the comment is found, the lexer skips all the characters following after until the new line is located, the token is classified as `TokenKind::Comment`. Otherwise, the lexer typed the single forward slash as `TokenKind::Punctuator`.
``` python
else if first_char == '/':
    if self.peek() == '/':
        while self.peek() != '\n' || self.peek() != END_OF_FILE:
            self.next()
        # eat the '\n'
        self.next()
        return COMMENT
    else
        return PUNCTUATOR
```

- If the first character is an alphabet or underscore, the function eats all the next alphabet or underscore. Next, the function checks whether the given string that has just been eaten is in the keyword hash table. If it is, the token is `TokenKind::Keyword`; otherwise, it is `TokenKind::Identifier`.
``` python
else if first_char.is_alphabet_or_underscore():
    string = first_char
    while self.peek().is_alphabet_or_underscore():
        string += self.next()
    
    if string in keyword_table:
        return KEYWORD
    else
        return IDENTIFIER
```
- This one is the simplest; if the first character is punctuation, simply categorize the token as `TokenKind::Punctuator`.
-  If the first character is a numeric digit, the function eats all the next numeric digits -- works similarly to the identifier. The token is classified as `TokenKind::LiteralConstant`.
``` python
else if first_char.is_digit():
    string = first_char
    while self.peek().is_digit():
        string += self.next()
    
    return LITERAL_CONSTANT
```

Finally, the last else branch returns the `Err` variant signifying an invalid character is found. 
``` rust
// this character can't be categorized under any token kinds
else {
    return Err(Error::InvalidCharacter {
        position: first_position,
        character: first_char,
        source_refernece: self.source_code,
    });
}
```

## Summary
That's it; we've essentially created a simple lexer in Rust, which can tokenize the source code into a stream of tokens. You can find all the code listings in the [GitHub](https://github.com/Simmypeet/pernix-lang/tree/d81b2dd8ff89f2b20ed3e8a7babc8994a389e95e) repository.