nifty

Rust中生成确定有限状态自动机（DFA）的crate。

描述

此crate的目标不是成为一个高效的解析库。使用正则表达式来处理。
相反，此crate旨在保留遍历DFA状态图的完整性。

它允许你构建一个具有泛型类型 S 的状态的DFA，该状态识别的符号类型为泛型类型 T。你可以逐个遍历每个转移符号，或者你可以消耗一个符号迭代器，DFA将接受或拒绝。

使用DFABuilder或使用make_dfa!宏创建DFA。两种方法都确保DFA对于其字母表中的每个符号都有有效的转移。

示例

构建DFA

代码

use nifty::make_dfa;

fn main() {
    let q0 = "q0";
    let q1 = "q1";
    let q2 = "q2";
    let q3 = "q3";

    let mut dfa = make_dfa! {
        states { q0, q1, q2, q3 }
        accept { q0, q1 }
        start  { q0 }
        dead   { q3 }
        transitions {
            d(q0, 'a') = q1
            d(q0, 'b') = q3

            d(q1, 'a') = q1
            d(q1, 'b') = q2

            d(q2, 'a') = q1
            d(q2, 'b') = q2
        }
        recognizes { 
            "empty, or starts and ends with { a }"
        }
    };

    dbg!(&dfa);

    dbg!(dfa.evaluate("".chars()));
    dbg!(dfa.evaluate("a".chars()));
    dbg!(dfa.evaluate("b".chars()));
    dbg!(dfa.evaluate("aa".chars()));
    dbg!(dfa.evaluate("ab".chars()));
    dbg!(dfa.evaluate("abb".chars()));
    dbg!(dfa.evaluate("aba".chars()));
    dbg!(dfa.evaluate("abba".chars()));
    dbg!(dfa.evaluate("babba".chars()));
}

输出

[src/lib.rs:82] &dfa = DFA {
    recognizes: "empty, or starts and ends with { a }",
    states: {
        "q0",
        "q1",
        "q2",
        "q3",
    },
    accept_states: {
        "q0",
        "q1",
    },
    dead_states: {
        "q3",
    },
    goal_states: {},
    transitions: {
        'a': {
            "q0": "q1",
            "q1": "q1",
            "q2": "q1",
        },
        'b': {
            "q0": "q3",
            "q1": "q2",
            "q2": "q2",
        },
    },
    start: Some(
        "q0",
    ),
    current: "q0",
}


[src/main.rs:28] dfa.evaluate("".chars()) = Accept
[src/main.rs:29] dfa.evaluate("a".chars()) = Accept
[src/main.rs:30] dfa.evaluate("b".chars()) = Reject
[src/main.rs:31] dfa.evaluate("aa".chars()) = Accept
[src/main.rs:32] dfa.evaluate("ab".chars()) = Reject
[src/main.rs:33] dfa.evaluate("abb".chars()) = Reject
[src/main.rs:34] dfa.evaluate("aba".chars()) = Accept
[src/main.rs:35] dfa.evaluate("abba".chars()) = Accept
[src/main.rs:36] dfa.evaluate("babba".chars()) = Reject

跟踪路径

代码

use nifty::make_dfa;

fn main() {
    let q0 = "Seen { }";
    let q1 = "Seen { b }";
    let q2 = "Seen { ba }";
    let q3 = "Seen { bab }";

    let mut dfa = make_dfa! {
        states { q0, q1, q2, q3 }
        start  { q0 }
        goal   { q3 }
        transitions {
            d(q0, 'a') = q0
            d(q1, 'a') = q2
            d(q2, 'a') = q0

            d(q0, 'b') = q1
            d(q1, 'b') = q1
            d(q2, 'b') = q3
        }
        recognizes {
            "contains { bab }"
        }
    };  

    let path = "abaababa".chars()
        .map(|c| (c, dfa.get_next(&c)))
        .collect::<Vec<_>>();

    for tuple in &path {
        println!("{:?}", tuple);
    }   
}

输出

('a', "Seen { }")
('b', "Seen { b }")
('a', "Seen { ba }")
('a', "Seen { }")
('b', "Seen { b }")
('a', "Seen { ba }")
('b', "Seen { bab }")
('a', "Seen { bab }")