A Lisp interpreter starts with a small but unforgiving problem: turning source text into tokens without losing its structure. I kept Oxylisp’s syntax narrow so I could focus on that transformation instead of spending this first part on a large grammar.
Lisp fits that goal because its syntax has few special cases. Its limited token vocabulary and explicit delimiters keep the lexer focused. Operator precedence becomes relevant in the parser, not here.
Oxylisp syntax defines the lexer’s contract
I designed Oxylisp with numeric and string literals, plus lists and records. Square brackets delimit lists, and whitespace separates their elements:
[1 2 3]Curly braces delimit records, whose entries are key-value pairs:
{:a [3 5 7] :b "foo"}The intended surface syntax uses def to bind a value, defn to define a named function, and fn to create an anonymous function:
(def x 42)
(defn double [n] (* 2 n))
(def plus-five (map (fn [n] (+ n 5)) (range 0 10)))These examples give the lexer its contract. It must preserve delimiters, distinguish keys from symbols, parse primitive values, and reject text that belongs to none of those categories.
Four token variants preserve source structure
Lexing converts a sequence of characters into a sequence of tokens. I use four top-level token variants. The complete snippets in this post rely on these imports:
use anyhow::{anyhow, Result};use lazy_static::lazy_static;use regex::Regex;use std::collections::HashMap;pub enum Tokens { Bounds(TokenBounds), Literal(Literal), Symbol(String), Key(String),}Bounds marks the opening and closing delimiters for function calls, lists, and records:
pub enum TokenBounds { LeftParen, RightParen, LeftBracket, RightBracket, LeftCurlyBraces, RightCurlyBraces,}Literal holds values that later interpreter stages can work with directly:
pub enum Literal { Nil, Symbol(String), String(String), Integer(i32), Bool(bool), List(Vec<Literal>), Record(HashMap<String, Literal>),}Tokens::Symbol represents variable and function names. Key represents record keys without their leading colon. Literal::Symbol also exists in the shared literal type, but the lexer shown here never creates it. Keeping delimiters as tokens leaves the parser responsible for assembling nested lists, records, and calls.
Regular expressions classify non-delimiter tokens
I can match delimiter characters exactly. Symbols, keys, strings, and numbers need stricter patterns:
lazy_static! { static ref IS_SYMBOL: Regex = Regex::new(r"^[A-Za-z+*/-=<>!][A-Za-z0-9+*/-=<>!]*$") .expect("Invalid symbol regex pattern"); static ref IS_KEY: Regex = Regex::new(r"^:[A-Za-z+*/-=<>!][A-Za-z0-9+*/-=<>!]*$") .expect("Invalid key regex pattern"); static ref IS_STRING: Regex = Regex::new(r#"^"([^"\\]|\\.)*"$"#) .expect("Invalid string regex pattern"); static ref IS_INTEGER: Regex = Regex::new(r"^-?\d+$") .expect("Invalid integer regex pattern"); static ref IS_FLOAT: Regex = Regex::new(r"^-?\d+\.\d+$") .expect("Invalid float regex pattern");}Anchoring each pattern with ^ and $ requires the entire substring to match. The intended rule is that a key begins with : and a symbol begins with a letter or supported operator character. Integer and float patterns accept an optional leading minus sign.
The symbol and key patterns contain a bug: the unescaped hyphen inside each character class creates a range from / to =. That range includes digits, :, and ;, so the regex accepts prefixes the intended grammar forbids. Escaping the hyphen or moving it to the end of the class would express the intended rule, but I have left the implementation unchanged here.
Padding delimiters makes whitespace splitting possible
I chose to insert spaces around every delimiter, split the result on whitespace, and classify each substring. This avoids writing a character-by-character scanner, but it does not respect quoted-string boundaries.
A string such as "hello world" is split on its space. A string containing (, ), [, ], {, or } is altered when the lexer pads that delimiter. Fixing both cases requires a scanner that tracks whether it is inside a quoted string.
pub fn tokenize(expression: &str) -> Result<Vec<Tokens>> { let tokens: Result<Vec<Tokens>> = expression .replace('(', " ( ") .replace(')', " ) ") .replace('[', " [ ") .replace(']', " ] ") .replace('{', " { ") .replace('}', " } ") .split_whitespace() .map(tokenize_single) .collect();
tokens}
fn tokenize_single(token: &str) -> Result<Tokens> { match token { "(" => Ok(Tokens::Bounds(TokenBounds::LeftParen)), ")" => Ok(Tokens::Bounds(TokenBounds::RightParen)), "[" => Ok(Tokens::Bounds(TokenBounds::LeftBracket)), "]" => Ok(Tokens::Bounds(TokenBounds::RightBracket)), "{" => Ok(Tokens::Bounds(TokenBounds::LeftCurlyBraces)), "}" => Ok(Tokens::Bounds(TokenBounds::RightCurlyBraces)), "true" => Ok(Tokens::Literal(Literal::Bool(true))), "false" => Ok(Tokens::Literal(Literal::Bool(false))), "nil" => Ok(Tokens::Literal(Literal::Nil)), "+" | "-" | "*" | "/" | "=" | "<" | ">" | "or" => { Ok(Tokens::Symbol(token.to_string())) }, token if IS_KEY.is_match(token) => { if token.len() <= 1 { return Err(anyhow!("Invalid key token: {}", token)); } Ok(Tokens::Key(token[1..].to_string())) }, token if IS_STRING.is_match(token) => { if token.len() < 2 { return Err(anyhow!("Invalid string token: {}", token)); } let content = &token[1..token.len()-1]; let unescaped = unescape_string(content)?; Ok(Tokens::Literal(Literal::String(unescaped))) }, token if IS_FLOAT.is_match(token) => { let float_val: f64 = token.parse() .map_err(|_| anyhow!("Invalid float format: {}", token))?; let int_val = float_val as i32; Ok(Tokens::Literal(Literal::Integer(int_val))) }, token if IS_INTEGER.is_match(token) => { let int_val: i32 = token.parse() .map_err(|_| anyhow!("Integer overflow or invalid format: {}", token))?; Ok(Tokens::Literal(Literal::Integer(int_val))) }, token if IS_SYMBOL.is_match(token) => { Ok(Tokens::Symbol(token.to_string())) }, _ => Err(anyhow!("Unrecognized token: '{}'", token)), }}
fn unescape_string(s: &str) -> Result<String> { let mut result = String::new(); let mut chars = s.chars();
while let Some(ch) = chars.next() { if ch == '\\' { match chars.next() { Some('n') => result.push('\n'), Some('t') => result.push('\t'), Some('r') => result.push('\r'), Some('\\') => result.push('\\'), Some('"') => result.push('"'), Some(c) => return Err(anyhow!("Invalid escape sequence: \\{}", c)), None => return Err(anyhow!("Incomplete escape sequence at end of string")), } } else { result.push(ch); } }
Ok(result)}tokenize_single checks exact delimiters and primitive values first, then applies the regular expressions. When a key matches, I remove its leading colon. When a no-space string matches, I remove its quotes and pass the contents to unescape_string, which handles the supported escape sequences.
Two defensive length checks in these branches are redundant: the regular expressions already guarantee a valid key has more than one character and a matched string has both quotes. Inputs that fail those patterns reach the generic Unrecognized token error instead.
The float branch is lossy rather than true float support. It parses a matching value as f64, casts it to i32, and emits an integer literal because this token model has no float variant. 12.9 therefore becomes Integer(12). Integer literals outside the i32 range return an error, while Rust’s float-to-integer cast saturates values outside that range.
I reject any remaining substring instead of guessing what token it was meant to represent.
Tokenizing one function call
Given this expression:
(+ 40 2)The lexer produces:
[Tokens::Bounds(TokenBounds::LeftParen), Tokens::Symbol("+".to_string()), Tokens::Literal(Literal::Integer(40)), Tokens::Literal(Literal::Integer(2)), Tokens::Bounds(TokenBounds::RightParen)]The result preserves both the values and the call boundaries. I can now hand that flat stream to the parser, which will turn it into nested expressions.
Next, Part 2 builds the parser that consumes these tokens. Before moving on, try the lexer with a negative integer, an escaped string, and an out-of-range integer. Those inputs expose more of its contract than the happy-path call above.