A programming language interpreter made in Rust

https://craftinginterpreters.com/

This book walks through how to implement an interpreter for a scripting language.

Divided into 2 parts, the book first teaches how to build a simple tree-walking interpreter in Java, and then later goes over how to implement a bytecode virtual machine interpreter in a lower level language like C.

This repo is an implementation of the first half, but in Rust. I did my best to stick close to the original implementation while making best use of Rust's language features. Along the way I also wrote tests, making it easy to refactor and run regression tests. As a result, I feel like the end product is a very clean implementation of an interpreter.

How to Run

Running a Code File

$ cd rlox
$ cargo run my_code.lox

Running Tests

$ cd rlox
$ cargo test

Language Features

• operators
  • arithmetic (+, -, *, /)
  • Comparison (<, <=, =, >, >=)
  • logical (!, and, or)
• variables
• if statements
• loops
• Functions
• Closures
• Classes
• Inheiritance

Interpreter Steps

     Raw Text Input
          |
          ▼
    Scanner/Lexxer
          |
          ▼
        Tokens
          |
          ▼
        Parser
          |
          ▼
  Abstract Syntax Tree
          |
          ▼
     Interpreter
          |
          ▼
     Code Executed

Language Grammar

program     -> declaration* EOF;

Declarations

declaration -> classDecl
             | funDecl
             | varDecl
             | statement ;

classDecl   -> "class" IDENTIFIER ( "<" IDENTIFIER )?
                "{" function* "}" ;
funDecl     -> "fun" function ;
varDecl     -> "var" IDENTIFIER ( "=" expression )? ";" ;

Statements

statement   -> exprStmt
             | forStmt
             | ifStmt
             | printStmt
             | returnStmt
             | returnStmt
             | whileStmt
             | block ;

exprStmt    -> expression ";" ;
forStmt     -> "for (" ( varDecl | exprStmt | ";" ) expression? ";" expression? ")"
                statement ;
ifStmt      -> "if (" expression ")" statement
                ( "else" statement )? ;
printStmt   -> "print" expression ";" ;
returnStmt  -> "return" expression? ";" ;
whileStmt   -> "while (" expression ")" statement ;
block       -> "{" declaration* "}" ;

Expressions

expression  -> assignment ;

assignment  -> ( call "." )? IDENTIFIER "=" assignment | logic_or ;

logic_or    -> logic_and ( "or" logic_and )* ;
logic_and   -> equality ( "and" equality )* ;
equality    -> comparison ( ( "!=" | "==" ) comparison )* ;
comparison  -> term ( ( ">" | ">=" | "<" | "<=" ) term)* ;
term        -> factor ( ( "-" | "+" ) factor )*
factor      -> unary ( ( "/" | "*" ) unary )* ;

unary       -> ( "!" | "-" ) unary | call ;
call        -> primary ( "(" arguments? ")" | "." IDENTIFIER )* ;
primary     -> "true" | "false" | "nil" | "this"
               | NUMBER | STRING | IDENTIFIER | "(" expression ")"
               | "super." IDENTIFIER ;

Utility Rules

function    -> IDENTIFIER "(" parameters? ")" block ;
parameters  -> IDENTIFIER ( "," IDENTIFIER )* ;
arguments   -> expression ( "," expression )* ;

Potential Next Steps

• Go through the second half of the book and attempt to recreate the bytecode VM in Rust
• Add additional features to this implementation such as ternaries, anonymous functions, etc.