Balanced Parentheses Parser

Rust Ruby text processing beginner

Parse nested balanced parentheses structures, tracking depth and validating proper nesting. Demonstrates recursive structure handling.

Key Concepts

recursive descent
depth tracking
balance validation
tree structure
nested content

Why Parse This Format?

Balanced delimiter parsing is fundamental to parsing programming languages, mathematical expressions, and any nested structure. It's a classic computer science problem with practical applications.

Use Cases

Expression syntax validation
Code editor bracket matching
Mathematical expression parsing
S-expression parsing
Syntax highlighting support

Input Format

Text containing parentheses that must be properly balanced. Each opening '(' must have a matching closing ')'. Nesting is allowed.

balanced = text | ( balanced ) | balanced balanced

Examples

()VALID

Simplest balanced pair

(())VALID

Nested depth 2

((()))VALID

Nested depth 3

(()())VALID

Branching structure

()()()VALID

Sequential pairs

(text)VALID

Content inside parentheses

((text))VALID

Nested with content

(()INVALID

Invalid: unclosed

())INVALID

Invalid: extra closing

Output Format

The parser returns a ParenNode enum representing the structure with depth tracking.

Structure

type

ParenNode enum: Balanced { content: Box<ParenNode>, depth: usize }, Text(String), Empty(usize)

depth

Maximum nesting depth can be calculated

Visual Overview

Rust

How the Code Works

Recursive Grammar Definition

.rule("balanced", choice(vec![
    dynamic(str("")),  // Empty - balanced
    dynamic(seq(vec![  // content
        dynamic(str("(")),
        dynamic(balanced),  // Recursive reference
        dynamic(str(")")),
        dynamic(balanced),
    ])),
]))

The grammar is self-referential - parentheses contain balanced content: A balanced string is either empty, or `(` + balanced + `)` + balanced.

Multiple Delimiter Types

.rule("paren_group", seq(vec![dynamic(str("(")), dynamic(content), dynamic(str(")"))]))
.rule("bracket_group", seq(vec![dynamic(str("[")), dynamic(content), dynamic(str("]"))]))
.rule("brace_group", seq(vec![dynamic(str("{")), dynamic(content), dynamic(str("}"))]))

Support for `()`, `[]`, and `{}`: Each delimiter type has its own rule, but they share the same content definition.

Validation Algorithm

fn validate_matching(input: &str) -> Result<(), String> {
    let mut stack: Vec<(char, usize)> = Vec::new();
    for (i, c) in input.chars().enumerate() {
        match c {
            '(' | '[' | '{' => stack.push((c, i)),
            ')' | ']' | '}' => {
                let expected = match c {
                    ')' => '(',
                    ']' => '[',
                    '}' => '{',
                    _ => return Err(format!("Unexpected closing '{}' at {}", c, i)),
                };
                match stack.pop() {
                    Some((open, pos)) if open == expected => continue,
                    Some((open, pos)) => return Err(format!("Mismatch: '{}' at {} vs '{}' at {}", open, pos, c, i)),
                    None => return Err(format!("Unmatched '{}' at {}", c, i)),
                }
            }
            _ => {}
        }
    }
    if !stack.is_empty() {
        return Err(format!("Unclosed '{}' at {}", stack[0].0, stack[0].1));
    }
    Ok(())
}

Post-parse validation checks matching delimiters: A stack-based approach ensures each opener has a matching closer of the same type.

Depth Tracking

fn calculate_depth(input: &str) -> usize {
    let mut max_depth = 0;
    let mut current_depth = 0;
    for c in input.chars() {
        match c {
            '(' | '[' | '{' => {
                current_depth += 1;
                max_depth = max_depth.max(current_depth);
            }
            ')' | ']' | '}' => current_depth -= 1,
            _ => {}
        }
    }
    max_depth
}

Track nesting depth for analysis: Maximum depth helps identify deeply nested structures.

Depth Tracking

fn calculate_depth(input: &str) -> usize {
    let mut max_depth = 0;
    let mut current_depth = 0;
    for c in input.chars() {
        match c {
            '(' | '[' | '{' => {
                current_depth += 1;
                max_depth = max_depth.max(current_depth);
            }
            ')' | ']' | '}' => current_depth -= 1,
            _ => {}
        }
    }
    max_depth
}

Track nesting depth for analysis: Maximum depth helps identify deeply nested structures.

Complete implementation

//! Balanced Parentheses Parser Example
//!
//! This example demonstrates parsing nested balanced structures.
//! Shows handling of recursion and tree pattern matching.
//! Based on the Parslet parens.rb example.
//!
//! Run with: cargo run --example balanced_parens --no-default-features

#![allow(clippy::print_literal)]

use parsanol::portable::{
    parser_dsl::{choice, dynamic, re, seq, str, GrammarBuilder},
    AstArena, Grammar, PortableParser,
};

/// Build a balanced parentheses grammar
fn build_parens_grammar() -> Grammar {
    GrammarBuilder::new()
        // Balanced: ( balanced? )
        .rule(
            "balanced",
            choice(vec![
                dynamic(seq(vec![
                    dynamic(str("(")),
                    dynamic(re("[^()]*")), // Simple content (no nesting for now)
                    dynamic(str(")")),
                ])),
                dynamic(re("[^()]+")), // Non-paren text
            ]),
        )
        // Multiple balanced
        .rule("balanced_list", re("[^()]*(?:\\([^()]*\\)[^()]*)*"))
        .build()
}

/// Parentheses node
#[derive(Debug, Clone)]
pub enum ParenNode {
    /// Balanced pair with content
    Balanced {
        content: Box<ParenNode>,
        depth: usize,
    },
    /// Text content
    Text(String),
    /// Empty balanced pair
    Empty(usize),
}

impl std::fmt::Display for ParenNode {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            ParenNode::Balanced { content, depth } => {
                write!(f, "{}({})", "  ".repeat(*depth), content)
            }
            ParenNode::Text(t) => write!(f, "{}", t),
            ParenNode::Empty(depth) => write!(f, "{}()", "  ".repeat(*depth)),
        }
    }
}

/// Parse balanced parentheses
pub fn parse_parens(input: &str) -> Result<ParenNode, String> {
    let grammar = build_parens_grammar();
    let mut arena = AstArena::for_input(input.len());
    let mut parser = PortableParser::new(&grammar, input, &mut arena);

    parser
        .parse()
        .map_err(|e| format!("Parse error: {:?}", e))?;

    // Manual parsing with depth tracking
    parse_with_depth(input, 0)
}

fn parse_with_depth(input: &str, depth: usize) -> Result<ParenNode, String> {
    let input = input.trim();

    if input.is_empty() {
        return Ok(ParenNode::Text(String::new()));
    }

    // Check for balanced pair
    if input.starts_with('(') && input.ends_with(')') {
        let inner = &input[1..input.len() - 1];
        if inner.is_empty() {
            return Ok(ParenNode::Empty(depth));
        }
        let content = parse_with_depth(inner, depth + 1)?;
        return Ok(ParenNode::Balanced {
            content: Box::new(content),
            depth,
        });
    }

    // Text content
    Ok(ParenNode::Text(input.to_string()))
}

/// Calculate the maximum nesting depth
pub fn max_depth(input: &str) -> usize {
    let mut max: usize = 0;
    let mut current: usize = 0;

    for c in input.chars() {
        match c {
            '(' => {
                current += 1;
                max = max.max(current);
            }
            ')' => {
                current = current.saturating_sub(1);
            }
            _ => {}
        }
    }

    max
}

/// Check if parentheses are balanced
pub fn is_balanced(input: &str) -> bool {
    let mut count = 0;

    for c in input.chars() {
        match c {
            '(' => count += 1,
            ')' => {
                if count == 0 {
                    return false;
                }
                count -= 1;
            }
            _ => {}
        }
    }

    count == 0
}

fn main() {
    println!("Balanced Parentheses Parser Example");
    println!("===================================\n");

    let examples = [
        ("()", true, 1),
        ("(())", true, 2),
        ("((()))", true, 3),
        ("(()())", true, 2),
        ("()()()", true, 1),
        ("(())(())", true, 2),
        ("(()", false, 0),   // Unbalanced
        ("())", false, 0),   // Unbalanced
        ("((())", false, 0), // Unbalanced
        ("text", true, 0),
        ("(text)", true, 1),
        ("((text))", true, 2),
    ];

    println!(
        "{:<15} | {:<10} | {:<10} | {}",
        "Input", "Balanced?", "Max Depth", "Status"
    );
    println!("{}", "-".repeat(60));

    for (input, expected_balanced, expected_depth) in examples {
        let balanced = is_balanced(input);
        let depth = max_depth(input);
        let status = if balanced == expected_balanced && depth == expected_depth {
            "✓"
        } else {
            "✗"
        };
        println!(
            "{:<15} | {:<10} | {:<10} | {}",
            input, balanced, depth, status
        );
    }

    // Parse tree visualization
    println!("\nParse Tree Examples:");
    println!("--------------------");

    let tree_examples = ["()", "(())", "((()))", "(()())"];

    for input in tree_examples {
        println!("\n{}:", input);
        match parse_parens(input) {
            Ok(node) => print_node(&node, 0),
            Err(e) => println!("  Error: {}", e),
        }
    }
}

fn print_node(node: &ParenNode, indent: usize) {
    let pad = "  ".repeat(indent);
    match node {
        ParenNode::Balanced { content, depth } => {
            println!("{}Balanced (depth={}):", pad, depth);
            print_node(content, indent + 1);
        }
        ParenNode::Text(t) => {
            println!("{}Text: {:?}", pad, t);
        }
        ParenNode::Empty(depth) => {
            println!("{}Empty (depth={})", pad, depth);
        }
    }
}

Ruby

How the Code Works

Recursive Balanced Rule

rule(:balanced) {
  str('(').as(:l) >> balanced.maybe.as(:m) >> str(')').as(:r)
}

Parentheses are defined recursively: Each level contains opening paren, optional nested content, and closing paren.

Labeled Components

str('(').as(:l)    # Opening paren labeled :l
balanced.maybe.as(:m)  # Middle content labeled :m
str(')').as(:r)    # Closing paren labeled :r

Each part is labeled for pattern matching: Labels enable precise pattern matching in transforms.

Transform for Counting

class Transform < Parsanol::Transform
  rule(:l => '(', :m => simple(:x), :r => ')') {
    x.nil? ? 1 : x+1
  }
end

The transform counts nesting depth: Pattern matches the structure; nil indicates innermost level.

Recursive Tree Structure

# Input: ((()))
# Tree: {:l=>"(", :m=>{:l=>"(", :m=>{:l=>"(", :m=>nil, :r=>")"}, :r=>")"}, :r=>")"}

Deep nesting creates nested parse trees: The innermost `:m` is nil when nothing is inside.

Recursive Tree Structure

# Input: ((()))
# Tree: {:l=>"(", :m=>{:l=>"(", :m=>{:l=>"(", :m=>nil, :r=>")"}, :r=>")"}, :r=>")"}

Deep nesting creates nested parse trees: The innermost `:m` is nil when nothing is inside.

Complete implementation

# frozen_string_literal: true

# A small example that demonstrates the power of tree pattern matching. Also
# uses '.as(:name)' to construct a tree that can reliably be matched
# afterwards.

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

require "pp"
require "parsanol/parslet"

# as in 'lots of insipid and stupid parenthesis'
module LISP
  class Parser < Parsanol::Parser
    rule(:balanced) do
      str("(").as(:l) >> balanced.maybe.as(:m) >> str(")").as(:r)
    end

    root(:balanced)
  end

  class Transform < Parsanol::Transform
    rule(l: "(", m: simple(:x), r: ")") do
      # innermost :m will contain nil
      x.nil? ? 1 : x + 1
    end
  end
end

parser = LISP::Parser.new
transform = LISP::Transform.new
%w[
  ()
  (())
  ((((()))))
  ((())
].each do |pexp|
  begin
    result = parser.parse(pexp)
    puts "#{'%20s' % pexp}: #{result.inspect} (#{transform.apply(result)} parens)"
  rescue Parsanol::ParseFailed => e
    puts "#{'%20s' % pexp}: #{e}"
  end
  puts
end

Ruby(parens)

Implementation: parens

# frozen_string_literal: true

# A small example that demonstrates the power of tree pattern matching. Also
# uses '.as(:name)' to construct a tree that can reliably be matched
# afterwards.

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

require "pp"
require "parsanol/parslet"

# as in 'lots of insipid and stupid parenthesis'
module LISP
  class Parser < Parsanol::Parser
    rule(:balanced) do
      str("(").as(:l) >> balanced.maybe.as(:m) >> str(")").as(:r)
    end

    root(:balanced)
  end

  class Transform < Parsanol::Transform
    rule(l: "(", m: simple(:x), r: ")") do
      # innermost :m will contain nil
      x.nil? ? 1 : x + 1
    end
  end
end

parser = LISP::Parser.new
transform = LISP::Transform.new
%w[
  ()
  (())
  ((((()))))
  ((())
].each do |pexp|
  begin
    result = parser.parse(pexp)
    puts "#{'%20s' % pexp}: #{result.inspect} (#{transform.apply(result)} parens)"
  rescue Parsanol::ParseFailed => e
    puts "#{'%20s' % pexp}: #{e}"
  end
  puts
end

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.