Interpreter in Rust (part 1)
Exploring the foundation of interpreters by building a custom lexer and REPL
Long distance runners sometimes train with weights strapped to their ankles or at high altitudes where the atmosphere is thin. When they later unburden themselves, the new relative ease of light limbs and oxygen-rich air enables them to run farther and faster. Implementing a language is a real test of programming skill. The code is complex and performance critical. You must master recursion, dynamic arrays, trees, graphs, and hash tables. — Robert Nystrom1
My goal in writing this interpreter and these notes is to learn. Therefore, I won’t be exploring topics like differences between a lexer, a tokenizer, and a scanner in deep details.
The full code is available in tealang repository
Fundamentals of Building an Interpreter
An interpreter or compiler consists of multiple layers. Each layer analyze and transform it into a higher-level representation. Starting with plain text or source code, it eventually ends up with structured with the proper syntax and grammar of the language.
Compiler translates the source code to machine code but does not execute it, whereas an interpreter takes the source code and executes it immediately.
Front-End Preparation
1. Lexing
Known as Lexical Analysis or sometimes Scanning. This is the layer that turns the source code into an accessible form known as tokens - done by lexer (sometimes referred as tokenizer or scanner).
Tokens are created from the stream of characters or chunks, it can be a single-character token or multiple
characters, like Semicolon(;) or Int(123). Usually Lexer ignores whitespaces, comments and only filter out
the code or the structure of code.
2. Parsing
This is the part where tokens get composed into meaningful expressions or statements - establishing a grammar
for the syntax. It does by building a tree - known as syntax tree, parse tree, or abstract syntax tree (AST).
The parser’s job is to make sure the syntax has no grammatical errors in code - known as syntax errors if it does. It
does it by arranging them into a proper sentence diagram, for an example: determines that 10 belongs to the
comparison and comparison belongs to if statement. (if (10 > 5))
3. Static Analysis
Parsing make sure the syntax is correct, the question is will it ensure the code is semantically correct? Mostly the first set of analysis is
called as binding or resolution. During such analysis each identifier gets wired with actual definition (such as where it stored locally or globally - scope).
If the language is statically typed, it will continue with type checking. For an instance x = "apple" + 5 will pass the parsing, but static analyzer
would flag that a string and a number cannot be added together, which is known as type error.
Then semantic insights has to be stored somewhere as well, and often they get stored as attributes on syntax tree as extra fields. Sometimes lookup table is used to store them or even transformed entirely into a new data structure.
Intermediate Representation (IR)
This sits right at the boundary between the Front-End and Back-End. A common ground or an internal format that acts as a bridge. Instead of writing 9 different compilers for Python, Java, and C against Intel, AMD, and ARM chips you can translate them to a common IR and then write 3 translators from IR to those chips.
Back-End
1. Optimization
The compiler looks at the IR code and optimize by rearranging it, deletes dead code, and tighten loops. A simple optimization would look like
x = 3 + 5 optimized as x = 8 so the computer doesn’t waste the CPU cycles.
2. Code Generation
The last step is converting it to machine code or known as compilation process which can be executed.
- In an Ahead-Of-Time (AOT) Compiler - It turns IR into native machine code specific to the CPU.
- In VM-based Interpreter - It turns IR into Bytecode, which is for a hypothetical, idealized machine - known as Virtual Machine.
3. Virtual Machine (VM)
A Software that mimic a hypothetical, physical CPU. Running it is slower than translating to native code but it provides simplicity and portability.
4. Runtime
If it is compiled to machine code, the OS loads and executes (not as part of compiling but user can) the program. If it is compiled to bytecode, the VM loads and runs it. Either way it require some services to support it. Such as,
- Garbage collector if the language manages memory by itself
- Type checker - Checking types at runtime (dynamic language)
- And others
Which are known as the runtime, each language has its own runtime and services.
Alternative or Shortcuts
Since it require a massive time to implement all the mentioned layers, there are few shortcuts or alternative options that lets use to use existing solutions or make it simpler.
- Tree-Walk Interpreters: Skip the IR and VM steps completely and execute the code directly from the AST (Abstract Syntax Tree).
It does all the Front-End work, then it walk through the tree and perform the action. For an instance if the node says
ADDthen it calls theaddfunction right then. Since it does not convert to IR or optimize, it is considered to be notoriously slow. - Single-Pass Compilers: Once the source code is read, it lexes, parses, and then immediately output to machine code or bytecode. So it’s terrible at optimization.
- Transpilers: Instead of writing code generator, an optimizer, and a runtime environment we can use an existing solution. A Transpiler (source-to-source) translates the code into an existing high-level language.
- Just-In-Time (JIT): When the program relies on a VM, a background profiler watches for the hot-spots - Code that run over and over again. So the JIT compiler takes those “hot” bytecode, compiles them into raw machine code and hot-swap the bytecode for the fast native code. But the catch is it gets incredibly complex and consume memory.
Building a Lexer
First we need to define the tokens and I am using Rust’s Enum here. The Token struct will be returned by the Lexer. (Check full code here)
#[derive(Debug, PartialEq, Clone)]
pub enum TokenType {
Illegal,
Eof,
...
}
#[derive(Debug, PartialEq, Clone)]
pub struct Token {
pub token_type: TokenType,
pub literal: String,
}
impl Token {
pub fn new(tt: TokenType, l: String) -> Self {
Token { token_type: tt, literal: l }
}
}I had started with a simple Lexer that looked like below, where the Lexer had input - text/code, position - the current
character position, read_position - look-ahead or next character position, and finally, the byte of the current character.
pub struct Lexer {
input: String,
position: usize,
read_position: usize,
ch: u8,
}Above pattern forces to think in-terms of state, tracking, and managing pointers. And reading multiple characters with a
look-ahead was spread across the code, forcing me to use multiple state checks and updates. Since iterators are very
effective at yielding, I switch to Peekable, which has, additional features that let us peek at the next characters without
advancing.
use std::{iter::Peekable, slice::Iter};
use crate::token::{Token, TokenType};
pub struct Lexer<'a> {
iter: Peekable<Iter<'a, u8>>,
}Lifetimes (‘a)
Because the iterator doesn’t hold the data but borrows it, the Lexer needs to know about that lifetime.
let mut input = String::new();
stdin().read_line(&mut input)?;
impl<'a> Lexer<'a> {
pub fn new(input: &'a str) -> Self {
Lexer {
iter: input.as_bytes().iter().peekable(),
}
}
}let mut input = String::new();- A block of memory gets allocated on the heap, and input has the ownership.pub fn new(input: &'a str) -> Self- String slice reference is being passed with the Lifespan Label (‘a) annotation which is like a contract guarantee. To make sure thatLexerdoes not outlive the string it’s being passed.input.as_bytes().iter().peekable()- Turns&strinto slice of byte reference(&[u8])and to iterator and then finally returned asPeekablewhich wraps iterator to allow look-ahead.- The
'alifetime annotation lets Rust’s borrow checker to verify thatLexerwon’t outlive theString. The'aacts as a contract that ties Lexer struct with lifetime of the underlying byte slice. - Also we need to have lifetime annotation
'anext toimplkeyword so that it can be declared as lifetime variable in that scope - similar to the generic function.
Next Token Implementation
PeekableThis struct holds a tiny, one-element buffer (anOption<Item>) under the hood.lexer.iter.peek()Returns next value without advancing the iterator.- Since the
peek()returns a reference to the item, meaning it returns&&u8and that’s why we need the double dereferenceif let Some(&&peek) = self.iter.peek().
impl<'a> Lexer<'a> {
//...new
pub fn next_token(&mut self) -> Token {
while self.iter.next_if(|&x| x.is_ascii_whitespace()).is_some() {}
let Some(&next_char) = self.iter.next() else {
return Token::new(TokenType::Eof, "".to_string());
};
// handling continous string, including '_'
if next_char.is_ascii_alphabetic() || next_char == b'_' {
let mut buffer = String::new();
buffer.push(next_char as char);
while let Some(&ch) = self
.iter
.next_if(|&x| x.is_ascii_alphanumeric() || *x == b'_')
{
buffer.push(ch as char);
}
return Token::lookup_ident(buffer);
}
// handling continous number - mainly integer
if next_char.is_ascii_digit() {
let mut buffer = String::new();
buffer.push(next_char as char);
while let Some(&ch) = self.iter.next_if(|&x| x.is_ascii_digit()) {
buffer.push(ch as char);
}
return Token::new(TokenType::Int, buffer);
}
match next_char {
b'=' => {
if let Some(&&peek) = self.iter.peek()
&& peek == b'='
{
Token::new(TokenType::EQ, "=".to_string())
} else {
Token::new(TokenType::Assign, "=".to_string())
}
}
b',' => Token::new(TokenType::Comma, ",".to_string()),
//...rest
_ => Token::new(TokenType::Illegal, "".to_string()),
}
}
}while self.iter.next_if(|&x| x.is_ascii_whitespace()).is_some() {}- This will consume all the leading whitespaces and stop exactly at the non-whitespace. Sinceiteris peekable it quietly call the.peek()to look at the next item in the buffer.- Since it is an iterator with look ahead it make it much cleaner and safer.
Making the Lexer an Iterator
- Implementing an Iterator trait for Lexer.
impl<'a> Iterator for Lexer<'a> {
type Item = Token;
fn next(&mut self) -> Option<Self::Item> {
let token = self.next_token();
if token.token_type != TokenType::Eof {
Some(token)
} else {
None
}
}
}
fn print_tokens(line: &str) {
let lexer = Lexer::new(line);
// while let token = lexer.next_token()
for token in lexer {
println!("out: {:?}", token);
}
}Building a Simple REPL
pub fn start() {
loop {
match read_input() {
Ok(line) => print_tokens(&line),
Err(e) => eprintln!("Encountered an error: {e}"),
}
}
}
// main.rs
fn main() {
let username = env::var("USER")
.or_else(|_| env::var("USERNAME"))
.unwrap_or_else(|_| String::from("there"));
println!("Hello {}! This is tealang programming language", username);
println!("Feel free to type in commands\n");
repl::start();
}- A simple REPL that takes in code and prints out the tokens back out
Hello danielkishan! This is tealang programming language
Feel free to type in commands
>>add <- fn(x, y) {x + y};
out: Token { token_type: Ident, literal: "add" }
out: Token { token_type: Define, literal: "<-" }
out: Token { token_type: Function, literal: "fn" }
out: Token { token_type: LParen, literal: "(" }
out: Token { token_type: Ident, literal: "x" }
out: Token { token_type: Comma, literal: "," }
out: Token { token_type: Ident, literal: "y" }
out: Token { token_type: RParen, literal: ")" }
out: Token { token_type: LBrace, literal: "{" }
out: Token { token_type: Ident, literal: "x" }
out: Token { token_type: Plus, literal: "+" }
out: Token { token_type: Ident, literal: "y" }
out: Token { token_type: RBrace, literal: "}" }
out: Token { token_type: Semicolan, literal: ";" }References
- Writing An Interpreter in Go
- Crafting Interpreters
- ChatGPT and Gemini