The Brzozowski derivative of Regular Expression with Rust.

reg_exp.rs

/// The regular expression tree.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum RegExp {
    /// Declares a variable of the match result.
    Var(String, Box<RegExp>),
    /// Matching pattern of a chatacter.
    Let(char),
    /// Or pattern of patterns.
    Or(Box<RegExp>, Box<RegExp>),
    /// Concatenated pattern of patterns.
    And(Box<RegExp>, Box<RegExp>),
    /// Reptition (more than or equal to zero) of a pattern.
    Star(Box<RegExp>),
    /// Pattern which matches only the empty string.
    Epsilon,
    /// Pattern which matches nothing. The result will be false anytime.
    Empty,
}

impl RegExp {
    fn accepts_empty_str(&self) -> bool {
        match self {
            RegExp::Var(_, re) => re.accepts_empty_str(),
            RegExp::Let(_) => false,
            RegExp::Or(l, r) => l.accepts_empty_str() || r.accepts_empty_str(),
            RegExp::And(l, r) => l.accepts_empty_str() && r.accepts_empty_str(),
            RegExp::Star(_) => true,
            RegExp::Epsilon => true,
            RegExp::Empty => false,
        }
    }

    /// Calculates the Brzozowski derivative of `self` at `x`.
    pub fn derivative(&self, x: char) -> Self {
        // `self` is considered as a language, set of strings.
        // The Brzozowski derivative of `L` at `x` is defined as:
        // $$
        // (x-) L := \Set{ y : string | xy ∈ L }
        // $$
        // It removes preceding character `x` from only each string starting `x` in `L`.
        match self {
            // (x-) 0 = (x-) 1 = 0
            RegExp::Empty | RegExp::Epsilon => RegExp::Empty,
            RegExp::Let(c) => {
                // (x-) c = 1  (c = x)
                // (x-) c = 0  (c ≠ x)
                if c == &x {
                    RegExp::Epsilon
                } else {
                    RegExp::Empty
                }
            }
            // (x-) (v := re) = (v := (x-) re)
            RegExp::Var(_, re) => re.derivative(x),
            // (x-) (l | r) = (x-) l | (x-) r
            RegExp::Or(l, r) => RegExp::Or(l.derivative(x).into(), r.derivative(x).into()),
            RegExp::And(l, r) => {
                // if `"" ∈ l`, also `(x-)` can be applied to `r` because of getting through `l`.
                if l.accepts_empty_str() {
                    // (x-) lr = ((x-) l)r | (x-) r
                    RegExp::Or(
                        RegExp::And(l.derivative(x).into(), r.clone()).into(),
                        r.derivative(x).into(),
                    )
                } else {
                    // (x-) lr = ((x-) l)r
                    RegExp::And(l.derivative(x).into(), r.clone())
                }
            }
            // (x-) r* = ((x-) r)(r*)
            RegExp::Star(re) => {
                RegExp::And(re.derivative(x).into(), RegExp::Star(re.clone()).into())
            }
        }
    }
}

#[derive(Clone, PartialEq, Eq, Hash)]
pub enum ParseTree {
    /// Empty capture.
    Void,
    /// No capture.
    Nil,
    /// Literal capture.
    Lit(char),
    /// Paired capture.
    Pair(Box<ParseTree>, Box<ParseTree>),
    /// Left of `RegExp::Or` capture.
    Left(Box<ParseTree>),
    /// Right of `RegExp::Or` capture.
    Right(Box<ParseTree>),
    /// List of captures.
    Cons(Box<ParseTree>, Box<ParseTree>),
}

impl std::fmt::Debug for ParseTree {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        match self {
            ParseTree::Void => write!(fmt, "()"),
            ParseTree::Nil => write!(fmt, "nil"),
            ParseTree::Lit(c) => write!(fmt, "{}", c),
            ParseTree::Pair(l, r) => write!(fmt, "({:?}, {:?})", l, r),
            ParseTree::Left(pt) => fmt.debug_tuple("Left").field(pt).finish(),
            ParseTree::Right(pt) => fmt.debug_tuple("Right").field(pt).finish(),
            ParseTree::Cons(x, xs) => write!(fmt, "{:?} : {:?}", x, xs),
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum ParseError {
    InvalidRegExp,
}

impl ParseTree {
    fn make_eps(re: &RegExp) -> Result<Self, ParseError> {
        debug_assert!(re.accepts_empty_str());
        Ok(match re {
            RegExp::Star(_) => ParseTree::Nil,
            RegExp::And(l, r) => {
                ParseTree::Pair(Self::make_eps(l)?.into(), Self::make_eps(r)?.into())
            }
            RegExp::Or(l, r) => {
                if l.accepts_empty_str() {
                    ParseTree::Left(Self::make_eps(l)?.into())
                } else if r.accepts_empty_str() {
                    ParseTree::Right(Self::make_eps(r)?.into())
                } else {
                    return Err(ParseError::InvalidRegExp);
                }
            }
            RegExp::Epsilon => ParseTree::Void,
            _ => return Err(ParseError::InvalidRegExp),
        })
    }

    fn inject(&self, re: &RegExp, x: char) -> Result<Self, ParseError> {
        Ok(match (self, re) {
            (tree, RegExp::Var(_, re)) => tree.inject(re, x)?,
            (ParseTree::Pair(t, ts), RegExp::Star(re)) => {
                ParseTree::Cons(t.inject(re, x)?.into(), ts.clone())
            }
            (tree, RegExp::And(l, r)) => match tree {
                ParseTree::Pair(t, ts) => ParseTree::Pair(t.inject(l, x)?.into(), ts.clone()),
                ParseTree::Left(pt) => {
                    if let ParseTree::Pair(t, ts) = pt.as_ref() {
                        ParseTree::Pair(t.inject(l, x)?.into(), ts.clone())
                    } else {
                        return Err(ParseError::InvalidRegExp);
                    }
                }
                ParseTree::Right(pt) => {
                    ParseTree::Pair(Self::make_eps(l)?.into(), pt.inject(r, x)?.into())
                }
                _ => return Err(ParseError::InvalidRegExp),
            },
            (tree, RegExp::Or(l, r)) => match tree {
                ParseTree::Left(pt) => ParseTree::Left(pt.inject(l, x)?.into()),
                ParseTree::Right(pt) => ParseTree::Right(pt.inject(r, x)?.into()),
                _ => return Err(ParseError::InvalidRegExp),
            },
            (ParseTree::Void, RegExp::Let(c)) => {
                if c == &x {
                    ParseTree::Lit(x)
                } else {
                    return Err(ParseError::InvalidRegExp);
                }
            }
            _ => return Err(ParseError::InvalidRegExp),
        })
    }

    pub fn parse(re: &RegExp, target: &str) -> Result<Self, ParseError> {
        if let Some((x, xs)) = split_first_ch(target) {
            Self::parse(&re.derivative(x), xs).and_then(|tree| tree.inject(re, x))
        } else {
            Self::make_eps(re)
        }
    }
}

fn split_first_ch(s: &str) -> Option<(char, &str)> {
    let mut chars = s.chars();
    chars.next().map(|c| (c, chars.as_str()))
}

#[test]
fn abaacc() {
    // ( ( x : a* ) | ( b | c )* )*
    let re = RegExp::Star(
        RegExp::Or(
            RegExp::Var("x".into(), RegExp::Star(RegExp::Let('a').into()).into()).into(),
            RegExp::Star(RegExp::Or(RegExp::Let('b').into(), RegExp::Let('c').into()).into())
                .into(),
        )
        .into(),
    );

    let parsed = ParseTree::parse(&re, "abaacc").unwrap();

    // (
    //     Left(a nil)
    //     Right(Left(b) nil)
    //     Left(a a nil)
    //     Right(Right(c) Right(c) nil)
    //     nil
    // )
    assert_eq!(
        parsed,
        ParseTree::Cons(
            ParseTree::Left(
                ParseTree::Cons(ParseTree::Lit('a').into(), ParseTree::Nil.into()).into()
            )
            .into(),
            ParseTree::Cons(
                ParseTree::Right(
                    ParseTree::Cons(
                        ParseTree::Left(ParseTree::Lit('b').into()).into(),
                        ParseTree::Nil.into()
                    )
                    .into()
                )
                .into(),
                ParseTree::Cons(
                    ParseTree::Left(
                        ParseTree::Cons(
                            ParseTree::Lit('a').into(),
                            ParseTree::Cons(ParseTree::Lit('a').into(), ParseTree::Nil.into())
                                .into()
                        )
                        .into()
                    )
                    .into(),
                    ParseTree::Cons(
                        ParseTree::Right(
                            ParseTree::Cons(
                                ParseTree::Right(ParseTree::Lit('c').into()).into(),
                                ParseTree::Cons(
                                    ParseTree::Right(ParseTree::Lit('c').into()).into(),
                                    ParseTree::Nil.into()
                                )
                                .into()
                            )
                            .into()
                        )
                        .into(),
                        ParseTree::Nil.into()
                    )
                    .into()
                )
                .into()
            )
            .into()
        )
    );
}