Mini Lisp Parser

Rust Ruby code template intermediate

Parse S-expressions for a mini Lisp language with identifiers, numbers, strings, and nested lists.

Key Concepts

recursive list structure
s-expression syntax
atom types
transform to AST

Why Parse This Format?

S-expressions are a simple yet powerful notation for nested data structures and code. They're used in Lisp dialects, configuration formats, and data interchange.

Use Cases

Lisp/Scheme interpreters
Configuration files
Data serialization
AST representation

Input Format

S-expressions: atoms or parenthesized lists of expressions.

atom | '(' expr* ')'

Examples

(+ 1 2)VALID

Simple function call

(define x 42)VALID

Variable definition

(lambda (x) (* x x))VALID

Lambda expression

(display "Hello")VALID

String argument

(1 2 3INVALID

Unclosed parenthesis

Output Format

Hierarchical AST representing the S-expression structure.

Structure

Identifier

Symbol name

Integer

Whole number

Float

Decimal number

String

Quoted string

List

Sequence of expressions

Visual Overview

Rust

How the Code Works

Atom Types

builder = builder.rule("identifier", re(r"[a-zA-Z=*][a-zA-Z=*_]*"));
builder = builder.rule("integer", re(r"[+-]?[0-9]+"));
builder = builder.rule("float", re(r"[+-]?[0-9]+(\.[0-9]+)?([eE][+-]?[0-9]+)?"));
builder = builder.rule("string", seq(vec![
    dynamic(str("\"")),
    dynamic(re(r"([^\"\\]|\\.)")),
    dynamic(str("\"")),
]));

Lisp atoms are the leaf nodes of expressions: Identifiers allow special chars like `=` and `*` for operators. Floats support scientific notation.

List Rule

builder = builder.rule("list", seq(vec![
    dynamic(re(r"[ \t\n\r]*")),  // leading space
    dynamic(str("(")),
    dynamic(re(r"[ \t\n\r]*")),  // space after open
    dynamic(ref_("items")),
    dynamic(str(")")),
    dynamic(re(r"[ \t\n\r]*")),  // trailing space
]));

Lists are parenthesized sequences: Whitespace handling around delimiters keeps the grammar clean.

Items Rule

builder = builder.rule("items", dynamic(ref_("expr")).repeat(0));

Items are zero or more expressions: Empty lists `()` are valid; the repeat(0) allows this.

Expression Choice

builder = builder.rule("expr", choice(vec![
    dynamic(ref_("list")),
    dynamic(ref_("atom")),
]));

Expressions are either lists or atoms: Order matters: list first because it starts with `(`, distinguishing from identifiers.

AST Enum

pub enum LispExpr {
    Identifier(String),
    Integer(i64),
    Float(f64),
    String(String),
    List(Vec<LispExpr>),
}

The Rust enum represents all expression types: Recursive structure via `Vec<LispExpr>` enables arbitrary nesting.

Item Parsing

fn parse_items(input: &str) -> Result<Vec<LispExpr>, String> {
    let mut depth = 0;
    let mut in_string = false;
    // Track nesting depth and string context
    // to split only at top-level spaces
}

Space-separated items require careful handling: Depth tracking handles nested lists; string tracking prevents splitting inside quotes.

Item Parsing

fn parse_items(input: &str) -> Result<Vec<LispExpr>, String> {
    let mut depth = 0;
    let mut in_string = false;
    // Track nesting depth and string context
    // to split only at top-level spaces
}

Space-separated items require careful handling: Depth tracking handles nested lists; string tracking prevents splitting inside quotes.

Complete implementation

//! Mini Lisp Parser Example
//!
//! A simple S-expression parser demonstrating list parsing, atoms, and transforms.
//!
//! Run with: cargo run --example minilisp --no-default-features

#![allow(clippy::print_literal)]

/// Lisp expression AST
#[derive(Debug, Clone)]
pub enum LispExpr {
    Identifier(String),
    Integer(i64),
    Float(f64),
    String(String),
    List(Vec<LispExpr>),
}

impl std::fmt::Display for LispExpr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            LispExpr::Identifier(s) => write!(f, "{}", s),
            LispExpr::Integer(n) => write!(f, "{}", n),
            LispExpr::Float(n) => write!(f, "{}", n),
            LispExpr::String(s) => write!(f, "\"{}\"", s),
            LispExpr::List(items) => {
                write!(f, "(")?;
                for (i, item) in items.iter().enumerate() {
                    if i > 0 {
                        write!(f, " ")?;
                    }
                    write!(f, "{}", item)?;
                }
                write!(f, ")")
            }
        }
    }
}

/// Parse a lisp expression (simplified manual parsing for demo)
fn parse_lisp(input: &str) -> Result<LispExpr, String> {
    let input = input.trim();

    // List
    if input.starts_with('(') && input.ends_with(')') {
        let inner = &input[1..input.len() - 1];
        let items = parse_items(inner)?;
        return Ok(LispExpr::List(items));
    }

    // String
    if input.starts_with('"') && input.ends_with('"') {
        return Ok(LispExpr::String(input[1..input.len() - 1].to_string()));
    }

    // Float (has decimal point or exponent)
    if input.contains('.') || input.contains('e') || input.contains('E') {
        if let Ok(n) = input.parse::<f64>() {
            return Ok(LispExpr::Float(n));
        }
    }

    // Integer
    if let Ok(n) = input.parse::<i64>() {
        return Ok(LispExpr::Integer(n));
    }

    // Identifier
    if input
        .chars()
        .all(|c| c.is_alphanumeric() || c == '=' || c == '*' || c == '_' || c == '+' || c == '-')
    {
        return Ok(LispExpr::Identifier(input.to_string()));
    }

    Err(format!("Could not parse: {}", input))
}

/// Parse space-separated items
fn parse_items(input: &str) -> Result<Vec<LispExpr>, String> {
    let mut items = Vec::new();
    let mut current = String::new();
    let mut depth = 0;
    let mut in_string = false;
    let mut escape = false;

    for c in input.chars() {
        if escape {
            current.push(c);
            escape = false;
            continue;
        }

        match c {
            '\\' if in_string => {
                current.push(c);
                escape = true;
            }
            '"' => {
                current.push(c);
                in_string = !in_string;
            }
            '(' if !in_string => {
                current.push(c);
                depth += 1;
            }
            ')' if !in_string => {
                current.push(c);
                depth -= 1;
            }
            ' ' | '\t' | '\n' | '\r' if depth == 0 && !in_string => {
                if !current.trim().is_empty() {
                    items.push(parse_lisp(&current)?);
                }
                current.clear();
            }
            _ => {
                current.push(c);
            }
        }
    }

    if !current.trim().is_empty() {
        items.push(parse_lisp(&current)?);
    }

    Ok(items)
}

fn main() {
    println!("Mini Lisp Parser Example");
    println!("========================");
    println!();

    let inputs = [
        "(+ 1 2)",
        "(define x 42)",
        "(lambda (x) (* x x))",
        r#"(display "Hello, World!")"#,
        "(begin (define a 1) (define b 2) (+ a b))",
        r#"
(define test (lambda ()
  (begin
    (display "something")
    (display 1)
    (display 3.08))))
"#,
    ];

    for input in inputs {
        println!("Input: {}", input.trim().replace('\n', " "));
        match parse_lisp(input) {
            Ok(expr) => {
                println!("  Parsed: {}", expr);
                println!("  Debug: {:?}", expr);
            }
            Err(e) => {
                println!("  Error: {}", e);
            }
        }
        println!();
    }

    println!("---");
    println!("This example demonstrates parsing S-expressions with:");
    println!("* Nested lists: (f (g x) y)");
    println!("* Atoms: identifiers, integers, floats, strings");
    println!("* Recursive structure: lists can contain lists");
}

Ruby

How the Code Works

Expression Rule

rule(:expression) {
  space? >> str('(') >> space? >> body >> str(')') >> space?
}

S-expressions are recursively defined: Whitespace is optional around parentheses for flexible formatting.

Body Rule

rule(:body) {
  (expression | identifier | float | integer | string).repeat.as(:exp)
}

Body contains multiple expressions: The repeat allows empty lists `()` and nested structures.

Identifier Rule

rule(:identifier) {
  (match('[a-zA-Z=*]') >> match('[a-zA-Z=*_]').repeat).as(:identifier) >> space?
}

Identifiers allow operator characters: `=` and `*` are valid identifier chars for Lisp operators like `=` and `*`.

Float Rule

rule(:float) {
  (
    integer >> (
      str('.') >> match('[0-9]').repeat(1) |
      str('e') >> match('[0-9]').repeat(1)
    ).as(:e)
  ).as(:float) >> space?
}

Floats have decimal or exponent parts: Captures the integer part and the exponent/fraction separately.

String Rule

rule(:string) {
  str('"') >> (
    str('\\') >> any |
    str('"').absent? >> any
  ).repeat.as(:string) >> str('"') >> space?
}

Strings handle escape sequences: `str('\\') >> any` handles any escaped character including `\"`.

Transform Class

class Transform
  t.rule(:identifier => simple(:ident)) { ident.to_sym }
  t.rule(:string => simple(:str))       { str }
  t.rule(:integer => simple(:int))      { Integer(int) }
  t.rule(:float=>{:integer=> simple(:a), :e=> simple(:b)}) { Float(a + b) }
  t.rule(:exp => subtree(:exp))         { exp }
end

Transforms convert parse trees to Ruby objects: `simple(:x)` matches single values; `subtree(:x)` matches nested structures.

Transform Class

class Transform
  t.rule(:identifier => simple(:ident)) { ident.to_sym }
  t.rule(:string => simple(:str))       { str }
  t.rule(:integer => simple(:int))      { Integer(int) }
  t.rule(:float=>{:integer=> simple(:a), :e=> simple(:b)}) { Float(a + b) }
  t.rule(:exp => subtree(:exp))         { exp }
end

Transforms convert parse trees to Ruby objects: `simple(:x)` matches single values; `subtree(:x)` matches nested structures.

Complete implementation

# frozen_string_literal: true

# Reproduces [1] using parslet.
# [1] http://thingsaaronmade.com/blog/a-quick-intro-to-writing-a-parser-using-treetop.html

$LOAD_PATH.unshift "#{File.dirname(__FILE__)}/../lib"

require "pp"
require "parsanol/parslet"
require "parsanol/convenience"

module MiniLisp
  class Parser < Parsanol::Parser
    root :expression
    rule(:expression) do
      space? >> str("(") >> space? >> body >> str(")") >> space?
    end

    rule(:body) do
      (expression | identifier | float | integer | string).repeat.as(:exp)
    end

    rule(:space) do
      match('\s').repeat(1)
    end
    rule(:space?) do
      space.maybe
    end

    rule(:identifier) do
      (match("[a-zA-Z=*]") >> match("[a-zA-Z=*_]").repeat).as(:identifier) >> space?
    end

    rule(:float) do
      (
        integer >> (
          (str(".") >> match("[0-9]").repeat(1)) |
          (str("e") >> match("[0-9]").repeat(1))
        ).as(:e)
      ).as(:float) >> space?
    end

    rule(:integer) do
      ((str("+") | str("-")).maybe >> match("[0-9]").repeat(1)).as(:integer) >> space?
    end

    rule(:string) do
      str('"') >> (
        (str("\\") >> any) |
        (str('"').absent? >> any)
      ).repeat.as(:string) >> str('"') >> space?
    end
  end

  class Transform
    include Parsanol::Parslet

    attr_reader :t

    def initialize
      @t = Parsanol::Transform.new

      # To understand these, take a look at what comes out of the parser.
      t.rule(identifier: simple(:ident)) { ident.to_sym }

      t.rule(string: simple(:str))       { str }

      t.rule(integer: simple(:int))      { Integer(int) }

      t.rule(float: { integer: simple(:a), e: simple(:b) }) { Float(a + b) }

      t.rule(exp: subtree(:exp)) { exp }
    end

    def do(tree)
      t.apply(tree)
    end
  end
end

parser = MiniLisp::Parser.new
transform = MiniLisp::Transform.new

result = parser.parse_with_debug %{
  (define test (lambda ()
    (begin
      (display "something")
      (display 1)
      (display 3.08))))
}

# Transform the result
pp transform.do(result) if result

# Thereby reducing it to the earlier problem:
# http://github.com/kschiess/toylisp

Use it from TypeScript (WebAssembly)

The same grammar runs in the browser through the shipped wasm engine — checksum-verified load, parse with recovery, typed bindings:

import { initSync, PargArtifactJs } from "@parsanol/wasm";

// Browser: await init() — Node: initSync(readFileSync(wasmPath))
initSync(readFileSync(wasmPath));

const artifact = new PargArtifactJs(artifactJson); // checksum verified on load

// Parse with recovery: deepest position, partial tree, resync spans
const envelope = JSON.parse(artifact.parseShapeRecovering(entry, input));

// Bind captures to your model
const bound = artifact.applyBindings(entry, JSON.stringify(envelope.shape));

Compile the grammar with the Ruby compiler, load the artifact anywhere — and see the playgroundrun the shipped wasm engine live. The artifact's embedded tests replay on every engine, so the tree you get is the tree everyone gets.