A lexer leaves Oxylisp with a flat stream of tokens, but evaluation needs nested structure. The parser’s job is to turn this:
[LeftParen, Symbol("+"), Integer(1), Integer(2), RightParen]into this tree representation:
CallExpression("+", [Literal(Integer(1)), Literal(Integer(2))])Lisp makes that job unusually direct. Its delimiters already describe the tree, so this parser needs no operator-precedence table. My main challenge was finding where each nested form ends without losing the tokens that follow it.
Why evaluation needs an abstract syntax tree
Consider (+ (* 2 3) 4). Evaluating it requires three steps:
- Evaluate the function
+. - Evaluate the arguments
(* 2 3)and4. - Apply the function to those results.
The first argument is another call, so the evaluator must repeat the same process for (* 2 3). A tree represents that dependency: the parent call depends on the values produced by its children.
Tokens describe syntax, forms describe meaning
The lexer produces Tokens. The parser converts them into Form values that can live in the abstract syntax tree (AST):
pub enum Tokens { Bounds(TokenBounds), Literal(Literal), Symbol(String), Key(String),}
pub enum Form { Root, Literal(Literal), CallExpression(String), Symbol(String), List, Record, Key(String),}Each form identifies one syntactic construct:
CallExpressionrepresents a call such as(+ 1 2).Listrepresents data such as[1 2 3].Recordrepresents key-value data such as{:name "Alice"}.Symbolrepresents a variable reference.Literalrepresents a number, string, or boolean.Keyrepresents a record key.Rootcontains the top-level forms.
Most tokens map directly to forms, so I use Rust’s From trait for the conversion:
impl From<Tokens> for Form { fn from(value: Tokens) -> Self { match value { Tokens::Bounds(_) => unreachable!(), Tokens::Literal(l) => Form::Literal(l), Tokens::Symbol(s) => Form::Symbol(s), Tokens::Key(k) => Form::Key(k), } }}Delimiter tokens are different. They do not become AST nodes. They tell the parser when to create and finish nested forms. The parser must keep them away from this conversion; another caller can still pass one and trigger unreachable!().
Recursive descent mirrors Lisp’s nested syntax
I made parse consume one token, update the current node, then recurse over the remaining slice. Opening delimiters start nested forms. Values become child nodes. Closing delimiters have already been accounted for by the delimiter-matching step, so this function skips them.
The excerpts below focus on parser control flow. They assume the surrounding Node, TokenBounds, Literal, and anyhow::Result definitions from Oxylisp.
pub fn parse(tokens: &[Tokens], mut parent_node: Node<Form>) -> Result<Node<Form>> { let Some((current_token, remaining_tokens)) = tokens.split_first() else { return Ok(parent_node); };
match current_token { Tokens::Bounds(TokenBounds::LeftParen) => { let (Tokens::Symbol(function_name), tokens_after_symbol) = remaining_tokens .split_first() .ok_or(anyhow!("Unexpected empty parens"))? else { return Err(anyhow!("Expected symbol after left paren")); }; parse_delimited_form( Form::CallExpression(function_name.clone()), TokenBounds::LeftParen, tokens_after_symbol, parent_node, ) } Tokens::Bounds(TokenBounds::LeftBracket) => { parse_delimited_form(Form::List, TokenBounds::LeftBracket, remaining_tokens, parent_node) } Tokens::Bounds(TokenBounds::LeftCurlyBraces) => { parse_delimited_form(Form::Record, TokenBounds::LeftCurlyBraces, remaining_tokens, parent_node) } Tokens::Bounds(_) => parse(remaining_tokens, parent_node), token => { let form: Form = token.clone().into(); parent_node.append(Node::new(form)); parse(remaining_tokens, parent_node) } }}Oxylisp gives a left parenthesis one extra rule: the next token must be a function-name symbol. Empty parentheses and calls without a leading symbol return errors instead of producing call nodes. This keeps the parser small, but it also means Oxylisp cannot place an arbitrary expression in function position as some Lisps can.
Square brackets and curly braces do not use that rule. Their contents are parsed as list and record children respectively.
Delimited forms split nested input from remaining input
When parse finds an opening delimiter, parse_delimited_form separates two regions: tokens inside the form and tokens after its closing delimiter.
fn parse_delimited_form( form_type: Form, opening_delimiter: TokenBounds, tokens_to_parse: &[Tokens], mut parent_node: Node<Form>,) -> Result<Node<Form>> { let (tokens_inside_delimiters, tokens_after_closing) = find_matching_delimiter(tokens_to_parse, opening_delimiter)?;
let parsed_form = parse(tokens_inside_delimiters, Node::new(form_type))?; parent_node.append(parsed_form);
parse(tokens_after_closing, parent_node)}I parse the inside region into a new node, append that node to its parent, then resume after the closer. Each inner opener repeats this process, so nesting needs no separate case.
A nesting counter finds the correct closing delimiter
Stopping at the first closing delimiter would fail on nested calls. find_matching_delimiter instead starts at depth one, increments the depth for each matching opener, and decrements it for each matching closer. Depth zero identifies the closer paired with the original opener.
fn find_matching_delimiter(tokens: &[Tokens], opening_delimiter: TokenBounds) -> Result<(&[Tokens], &[Tokens])> { let closing_delimiter = match opening_delimiter { TokenBounds::LeftParen => TokenBounds::RightParen, TokenBounds::LeftBracket => TokenBounds::RightBracket, TokenBounds::LeftCurlyBraces => TokenBounds::RightCurlyBraces, _ => return Err(anyhow!("Invalid opening delimiter")), };
let mut nesting_level = 1; for (index, token) in tokens.iter().enumerate() { match token { Tokens::Bounds(delimiter) if *delimiter == opening_delimiter => { nesting_level += 1; } Tokens::Bounds(delimiter) if *delimiter == closing_delimiter => { nesting_level -= 1; if nesting_level == 0 { let (inside, including_closer) = tokens.split_at(index); return Ok((inside, &including_closer[1..])); } } _ => {} } } Err(anyhow!("Unmatched {} - missing closing delimiter", match opening_delimiter { TokenBounds::LeftParen => "parenthesis '('", TokenBounds::LeftBracket => "bracket '['", TokenBounds::LeftCurlyBraces => "brace '{'", _ => "delimiter" } ))}The returned slices have separate jobs:
insidebecomes the input for the nested recursive parse.- The slice after the closer lets the parent parse continue.
If the matching closer never appears, the function reports which opening delimiter remained unmatched.
This version has syntax-validation holes. The counter tracks only delimiters of the same type as the current opener, while Tokens::Bounds(_) in parse skips unexpected closers. Malformed input such as (+ 1 ] 2) or a stray top-level ) can therefore produce an AST instead of an error. Records also accept any sequence of forms rather than enforcing key-value pairs.
Rejecting mixed or stray closers requires tracking every opener in a stack and checking each closer against the top entry. Record shape needs its own validation step. I left both constraints out of this parser version, but they are necessary before treating its output as validated syntax.
Trace the parser on one expression
For (+ 1 2), the parser creates CallExpression("+"), parses both integers as its children, and appends the completed call to Root:
Root└── CallExpression("+") ├── Literal(Integer(1)) └── Literal(Integer(2))A useful next step is to trace (+ (* 2 3) 4) through parse, parse_delimited_form, and find_matching_delimiter. Watch which token slice each call receives and where parsing resumes after each closer. That exercise exposes both why recursive descent fits Lisp and where the delimiter-validation hole appears.