Mini Programming Language Interpreter

A tree-walking interpreter executes a small imperative language by transforming source code into tokens (lexer), building an Abstract Syntax Tree of statements and expressions (parser), and evaluating nodes against a lexically scoped environment (evaluator). Supporting let bindings, assignment, if/else conditionals, while loops, and print statements exercises recursive AST modeling (Box<Expr>, Vec<Stmt>) and runtime value representation (Value).

Interpreter Pipeline

Source String
   |
   v  Lexer::tokenize()
Vec<Token>  ([Let, Ident("x"), Assign, Int(1), Semi, ...])
   |
   v  Parser::parse_program()
Vec<Stmt>   ([Stmt::Let { name: "x", expr }, Stmt::While { cond, body }, ...])
   |
   v  Interpreter::exec_program(&mut Environment)
Runtime Output + Final Environment State

Complete Implementation

use std::collections::HashMap;
use std::fmt;

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Token {
    Let,
    If,
    Else,
    While,
    Print,
    Ident(String),
    Int(i64),
    Plus,
    Minus,
    Star,
    Slash,
    Assign,
    EqEq,
    Lt,
    Gt,
    LParen,
    RParen,
    LBrace,
    RBrace,
    Semi,
    Eof,
}

pub fn tokenize(src: &str) -> Result<Vec<Token>, String> {
    let mut chars = src.chars().peekable();
    let mut tokens = Vec::new();

    while let Some(&ch) = chars.peek() {
        if ch.is_whitespace() {
            chars.next();
        } else if ch.is_ascii_digit() {
            let mut num = 0i64;
            while let Some(&d) = chars.peek() {
                if d.is_ascii_digit() {
                    num = num * 10 + (d as i64 - '0' as i64);
                    chars.next();
                } else {
                    break;
                }
            }
            tokens.push(Token::Int(num));
        } else if ch.is_ascii_alphabetic() || ch == '_' {
            let mut ident = String::new();
            while let Some(&c) = chars.peek() {
                if c.is_ascii_alphanumeric() || c == '_' {
                    ident.push(c);
                    chars.next();
                } else {
                    break;
                }
            }
            let tok = match ident.as_str() {
                "let" => Token::Let,
                "if" => Token::If,
                "else" => Token::Else,
                "while" => Token::While,
                "print" => Token::Print,
                _ => Token::Ident(ident),
            };
            tokens.push(tok);
        } else {
            chars.next();
            match ch {
                '+' => tokens.push(Token::Plus),
                '-' => tokens.push(Token::Minus),
                '*' => tokens.push(Token::Star),
                '/' => tokens.push(Token::Slash),
                '<' => tokens.push(Token::Lt),
                '>' => tokens.push(Token::Gt),
                '(' => tokens.push(Token::LParen),
                ')' => tokens.push(Token::RParen),
                '{' => tokens.push(Token::LBrace),
                '}' => tokens.push(Token::RBrace),
                ';' => tokens.push(Token::Semi),
                '=' => {
                    if chars.peek() == Some(&'=') {
                        chars.next();
                        tokens.push(Token::EqEq);
                    } else {
                        tokens.push(Token::Assign);
                    }
                }
                other => return Err(format!("unexpected character: '{other}'")),
            }
        }
    }
    tokens.push(Token::Eof);
    Ok(tokens)
}

#[derive(Debug, Clone, Copy)]
pub enum BinOp {
    Add,
    Sub,
    Mul,
    Div,
    Eq,
    Lt,
    Gt,
}

#[derive(Debug, Clone)]
pub enum Expr {
    Int(i64),
    Var(String),
    Binary {
        op: BinOp,
        lhs: Box<Expr>,
        rhs: Box<Expr>,
    },
}

#[derive(Debug, Clone)]
pub enum Stmt {
    Let {
        name: String,
        expr: Expr,
    },
    Assign {
        name: String,
        expr: Expr,
    },
    Print(Expr),
    If {
        cond: Expr,
        then_branch: Vec<Stmt>,
        else_branch: Vec<Stmt>,
    },
    While {
        cond: Expr,
        body: Vec<Stmt>,
    },
}

pub struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    pub fn new(tokens: Vec<Token>) -> Self {
        Self { tokens, pos: 0 }
    }

    fn peek(&self) -> &Token {
        &self.tokens[self.pos]
    }

    fn bump(&mut self) -> Token {
        let tok = self.tokens[self.pos].clone();
        if self.pos + 1 < self.tokens.len() {
            self.pos += 1;
        }
        tok
    }

    fn expect(&mut self, expected: Token) -> Result<(), String> {
        let actual = self.bump();
        if actual == expected {
            Ok(())
        } else {
            Err(format!("expected {expected:?}, found {actual:?}"))
        }
    }

    pub fn parse_program(&mut self) -> Result<Vec<Stmt>, String> {
        let mut stmts = Vec::new();
        while *self.peek() != Token::Eof {
            stmts.push(self.parse_stmt()?);
        }
        Ok(stmts)
    }

    fn parse_block(&mut self) -> Result<Vec<Stmt>, String> {
        self.expect(Token::LBrace)?;
        let mut stmts = Vec::new();
        while *self.peek() != Token::RBrace && *self.peek() != Token::Eof {
            stmts.push(self.parse_stmt()?);
        }
        self.expect(Token::RBrace)?;
        Ok(stmts)
    }

    fn parse_stmt(&mut self) -> Result<Stmt, String> {
        match self.peek().clone() {
            Token::Let => {
                self.bump();
                let Token::Ident(name) = self.bump() else {
                    return Err("expected identifier after 'let'".into());
                };
                self.expect(Token::Assign)?;
                let expr = self.parse_expr()?;
                self.expect(Token::Semi)?;
                Ok(Stmt::Let { name, expr })
            }
            Token::Print => {
                self.bump();
                let expr = self.parse_expr()?;
                self.expect(Token::Semi)?;
                Ok(Stmt::Print(expr))
            }
            Token::If => {
                self.bump();
                let cond = self.parse_expr()?;
                let then_branch = self.parse_block()?;
                let else_branch = if *self.peek() == Token::Else {
                    self.bump();
                    self.parse_block()?
                } else {
                    Vec::new()
                };
                Ok(Stmt::If {
                    cond,
                    then_branch,
                    else_branch,
                })
            }
            Token::While => {
                self.bump();
                let cond = self.parse_expr()?;
                let body = self.parse_block()?;
                Ok(Stmt::While { cond, body })
            }
            Token::Ident(name) => {
                self.bump();
                self.expect(Token::Assign)?;
                let expr = self.parse_expr()?;
                self.expect(Token::Semi)?;
                Ok(Stmt::Assign { name, expr })
            }
            other => Err(format!("unexpected token at statement start: {other:?}")),
        }
    }

    fn parse_expr(&mut self) -> Result<Expr, String> {
        let mut lhs = self.parse_additive()?;
        while let Token::EqEq | Token::Lt | Token::Gt = self.peek() {
            let op = match self.bump() {
                Token::EqEq => BinOp::Eq,
                Token::Lt => BinOp::Lt,
                Token::Gt => BinOp::Gt,
                _ => unreachable!(),
            };
            let rhs = self.parse_additive()?;
            lhs = Expr::Binary {
                op,
                lhs: Box::new(lhs),
                rhs: Box::new(rhs),
            };
        }
        Ok(lhs)
    }

    fn parse_additive(&mut self) -> Result<Expr, String> {
        let mut lhs = self.parse_multiplicative()?;
        while let Token::Plus | Token::Minus = self.peek() {
            let op = match self.bump() {
                Token::Plus => BinOp::Add,
                Token::Minus => BinOp::Sub,
                _ => unreachable!(),
            };
            let rhs = self.parse_multiplicative()?;
            lhs = Expr::Binary {
                op,
                lhs: Box::new(lhs),
                rhs: Box::new(rhs),
            };
        }
        Ok(lhs)
    }

    fn parse_multiplicative(&mut self) -> Result<Expr, String> {
        let mut lhs = self.parse_primary()?;
        while let Token::Star | Token::Slash = self.peek() {
            let op = match self.bump() {
                Token::Star => BinOp::Mul,
                Token::Slash => BinOp::Div,
                _ => unreachable!(),
            };
            let rhs = self.parse_primary()?;
            lhs = Expr::Binary {
                op,
                lhs: Box::new(lhs),
                rhs: Box::new(rhs),
            };
        }
        Ok(lhs)
    }

    fn parse_primary(&mut self) -> Result<Expr, String> {
        match self.bump() {
            Token::Int(n) => Ok(Expr::Int(n)),
            Token::Ident(name) => Ok(Expr::Var(name)),
            Token::LParen => {
                let expr = self.parse_expr()?;
                self.expect(Token::RParen)?;
                Ok(expr)
            }
            other => Err(format!("expected expression, found {other:?}")),
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Value {
    Int(i64),
    Bool(bool),
}

impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Value::Int(n) => write!(f, "{n}"),
            Value::Bool(b) => write!(f, "{b}"),
        }
    }
}

pub struct Interpreter {
    scopes: Vec<HashMap<String, Value>>,
    pub output: Vec<String>,
}

impl Interpreter {
    pub fn new() -> Self {
        Self {
            scopes: vec![HashMap::new()],
            output: Vec::new(),
        }
    }

    fn get_var(&self, name: &str) -> Result<Value, String> {
        for scope in self.scopes.iter().rev() {
            if let Some(&val) = scope.get(name) {
                return Ok(val);
            }
        }
        Err(format!("undefined variable '{name}'"))
    }

    fn assign_var(&mut self, name: &str, val: Value) -> Result<(), String> {
        for scope in self.scopes.iter_mut().rev() {
            if let Some(slot) = scope.get_mut(name) {
                *slot = val;
                return Ok(());
            }
        }
        Err(format!("cannot assign to undeclared variable '{name}'"))
    }

    pub fn eval_expr(&self, expr: &Expr) -> Result<Value, String> {
        match expr {
            Expr::Int(n) => Ok(Value::Int(*n)),
            Expr::Var(name) => self.get_var(name),
            Expr::Binary { op, lhs, rhs } => {
                let (Value::Int(a), Value::Int(b)) = (self.eval_expr(lhs)?, self.eval_expr(rhs)?)
                else {
                    return Err("binary operators require integer operands".into());
                };
                match op {
                    BinOp::Add => Ok(Value::Int(a + b)),
                    BinOp::Sub => Ok(Value::Int(a - b)),
                    BinOp::Mul => Ok(Value::Int(a * b)),
                    BinOp::Div => {
                        if b == 0 {
                            Err("division by zero".into())
                        } else {
                            Ok(Value::Int(a / b))
                        }
                    }
                    BinOp::Eq => Ok(Value::Bool(a == b)),
                    BinOp::Lt => Ok(Value::Bool(a < b)),
                    BinOp::Gt => Ok(Value::Bool(a > b)),
                }
            }
        }
    }

    pub fn exec_block(&mut self, stmts: &[Stmt]) -> Result<(), String> {
        self.scopes.push(HashMap::new());
        for stmt in stmts {
            self.exec_stmt(stmt)?;
        }
        self.scopes.pop();
        Ok(())
    }

    pub fn exec_stmt(&mut self, stmt: &Stmt) -> Result<(), String> {
        match stmt {
            Stmt::Let { name, expr } => {
                let val = self.eval_expr(expr)?;
                self.scopes.last_mut().unwrap().insert(name.clone(), val);
                Ok(())
            }
            Stmt::Assign { name, expr } => {
                let val = self.eval_expr(expr)?;
                self.assign_var(name, val)
            }
            Stmt::Print(expr) => {
                let val = self.eval_expr(expr)?;
                self.output.push(val.to_string());
                Ok(())
            }
            Stmt::If {
                cond,
                then_branch,
                else_branch,
            } => {
                if self.eval_expr(cond)? == Value::Bool(true) {
                    self.exec_block(then_branch)
                } else {
                    self.exec_block(else_branch)
                }
            }
            Stmt::While { cond, body } => {
                while self.eval_expr(cond)? == Value::Bool(true) {
                    self.exec_block(body)?;
                }
                Ok(())
            }
        }
    }
}

fn main() {
    let program_src = r#"
        let n = 6;
        let acc = 1;
        let step = 1;

        while step < n + 1 {
            acc = acc * step;
            if step == 3 {
                print acc;
            }
            step = step + 1;
        }
        print acc;
    "#;

    let tokens = tokenize(program_src).expect("lexing failed");
    let mut parser = Parser::new(tokens);
    let ast = parser.parse_program().expect("parsing failed");

    let mut interp = Interpreter::new();
    for stmt in &ast {
        interp.exec_stmt(stmt).expect("runtime error");
    }

    println!("Executed {} top-level statements.", ast.len());
    println!("Program stdout lines: {:?}", interp.output);
}

Executed 5 top-level statements.
Program stdout lines: ["6", "720"]