nanore

nanore是用Rust编写的适用于任意数据类型的微型（≃ 0.2K SLOC）正则表达式匹配器。

• 时间复杂度为O(|regexp||sequence|)，空间复杂度为O(|regexp|)。没有指数级膨胀。
• 支持在线匹配。
• 匹配状态可以在任何时候复制。
• 支持正则表达式权重。
• 支持路径标记。

示例

基础

[源代码，Rust]

use nanore::*;

let re = RegExRoot::<_, ()>::new(
    atom(|_, e| *e % 2 != 0) * atom(|_, e| *e % 2 == 0) + rep(atom(|_, e| *e > 0))
);
let mut m = Matcher::new(&re);

assert!(m.is_match());
m.feed(&1);
assert!(m.is_match());
m.feed(&2);
assert!(m.is_match());
m.feed(&3);
assert!(m.is_match());
m.feed(&0);
assert!(!m.is_match());

构造：*（连接），+（选择），rep()，opt()，eps()，atom()，any()，val()，weight()，mark()。

标记 & 路径

[源代码，Rust]

#[derive(Clone, Copy, PartialEq, Eq)]
enum Marker { Foo, Bar }

let re = RegExRoot::new(
    rep(mark(Marker::Foo) * val('a') + mark(Marker::Bar) * val('b'))
);
let mut m = Matcher::new(&re);

m.feed(&'a');
m.feed(&'b');
m.feed(&'a');
m.feed(&'b');
assert!(m.is_match());
assert!(m.path() == [(0, Marker::Foo), (1, Marker::Bar), (2, Marker::Foo), (3, Marker::Bar)]);

权重

[源代码，Rust]

let re = RegExRoot::new(
    rep(mark(Marker::Foo) * val('a')) * rep(weight(-1) * mark(Marker::Bar) * val('a'))
);
let mut m = Matcher::new(&re);

m.feed(&'a');
m.feed(&'a');
m.feed(&'a');
m.feed(&'a');
assert!(m.is_match());
assert!(m.path() == [(0, Marker::Bar), (1, Marker::Bar), (2, Marker::Bar), (3, Marker::Bar)]);

应用：查找最长的斐波那契数列

[源代码，Rust]

#[derive(Clone, Copy, PartialEq, Eq)]
enum Marker { Bgn, End }

let xs = [1, 1, 2, 3, 5, 3, 2, 3, 5, 8, 13, 21, 34];
//        ^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^^^^^^

let re = RegExRoot::new(
    rep(weight(1) * any()) * mark(Marker::Bgn) *
    any() * any() * rep(atom(|i, x| *x == xs[i - 2] + xs[i - 1])) *
    mark(Marker::End) * rep(weight(1) * any())
);
let mut m = Matcher::new(&re);
m.feed_iter(&xs);

assert!(m.path() == [(6, Marker::Bgn), (13, Marker::End)]);

参考

加权正则表达式匹配:: nanore使用（该论文的子集）中的方法。请注意，这个想法简单而优雅，但由于隐式生成的ε-NFA中的ε转换，有一些非平凡的部分（请参阅empty，final和shift）。nanore将正常转换和ε转换分开处理，这看起来与这篇论文（请参阅nanore中的shift()和propagate()）略有不同）。函数式正则表达式匹配:: 关于上述论文的优秀文章，用日语撰写。