Crate brzozowski

This crate provides an alternative implementation of a toy Regex engine that uses Brzozowski derivatives instead of building an automaton (either NFA or a DFA). This implementation closely follows the very educational Python implementation and provides similar APIs to it. Note that the set of supported regular expressions in general is minimal but in line with the Python implementation.

The recommended way to build an Expr out of a regular expression is via [std::string::FromStr]. For example:

use brzozowski::Expr;

let re = "b(a*)(na)*".parse::<Expr>().unwrap();
assert!(re.is_match("banana"));

The Expr’s are essentially a tree representation of the regular expression where the following operations are possible:

• Expr::Concat: Concatenate two strings together (i.e. <expr>·<expr>)
• Expr::Union: Take union of two strings (i.e. <expr>|<expr>)
• Expr::Kleene: Describe the Kleene star for a string (i.e. <expr>*).
• Expr::Term: The leaf nodes in the tree that represent characters of the alphabet.

To explore how the derivatives are calculated, check out the Expr::derivative, Expr::nulled, and Expr::simplify methods.

Structs

Augment

An iterator over the characters of the augmented regular expression, i.e. where the concatenation is injected wherever it is provided in regular expression implicitly.

Enums

Expr

A tree representation of a regular expression.

Functions

augment

Extend the input regex with an explicit concatenation operator (·).

augment_imperative

Extend the input regex with an explicit concatenation operator (·). This is an imperative implementation as compared to the iterative implementation of augment.

infix_to_postfix

Use the Shunting Yard algorithm to convert an infix expression to a postfix expression. This is the intermediate step to convert an infix regular expression into an Expr;