轻便型解析器

轻便型解析器是一个基于文本文件格式的Rust库，用于DFA、NFA和ε-NFA自动机。

用法

use dandy::dfa::Dfa;

fn main() {
    let raw_dfa = "
           a  b  c
    → * s₀ s₁ s₀ s₂
        s₁ s₂ s₁ s₁
      * s₂ s₂ s₂ s₂
    ";
    // First pass parses without checking validity of the DFA 
    let parsed_dfa = dandy::parser::dfa(raw_dfa).unwrap();
    // Second step checks the existence of all mentioned states and
    // the existence of an initial state
    let dfa: Dfa = parsed_dfa.try_into().unwrap();
    assert!(dfa.accepts(&["a", "b", "c", "c", "a"]));
    assert!(dfa.accepts(&["c", "b", "a"]));
    assert!(!dfa.accepts(&["a", "b", "b", "c"]));

    let equivalent_dfa = "
        a b c
    → * x z x y
      * y y y y
        z y w z
        w y z w
    ";
    let dfa2 = dandy::parser::dfa(equivalent_dfa).unwrap().try_into().unwrap();
    assert!(dfa.equivalent_to(&dfa2));
}

文件格式

使用的文件格式基本上就是一个转换表。第一行（标题行）应包含整个字母表，然后其余的行应包含状态，每行一个状态。行应从状态名称开始，然后对于字母表中的每个元素，在该元素上从该状态进行的转换。在状态名称之前，应使用 -> 或 → 来表示初始状态，使用 * 来表示该状态是接受状态。

DFA的示例

       a  b  c
→ * s₀ s₁ s₀ s₂
    s₁ s₂ s₁ s₁
  * s₂ s₂ s₂ s₂

此表表示接受字母表 'a'、'b'、'c' 的字符串的DFA，可以是

• 只有'b'
• 两个'a'
• 在第一个'a'出现之前有一个'c'

应使用空白作为 →、*、状态名称和转换条目之间的分隔符。只包含空白的行将被忽略，可以使用 # 添加注释，忽略该行的其余部分。忽略前导和尾随空白。条目不需要与其它行或字母表对齐。

要成为正确表示的DFA，必须为每个状态和字母表元素提供转换。必须定义所有引用的状态，并且必须恰好有一个初始状态。也不允许字母表有任何重复的元素。

NFA和ε-NFA的格式非常相似。对于每个状态转换，目标状态的集合用 { 表示，然后是空格分隔的列表中的状态，以及 }。要定义ε转换，应在字母表中添加ε字符。

ε-NFA的示例

     ε    a       b
→ s₀ {}   {s₁}    {s₀ s₂}
  s₁ {s₂} {s₄}    {s₃}
  s₂ {}   {s₁ s₄} {s₃}
  s₃ {s₅} {s₄ s₅} {}
  s₄ {s₃} {}      {s₅}
* s₅ {}   {s₅}    {s₅}

再次强调，应使用空白字符作为→、*、状态名称和转换条目之间的分隔符。同样，应使用空白字符作为每个集合中条目之间的分隔符。空转换（无转换）必须写成空集合{}。注释和前后空白字符的规则与DFAs相同。ε可以写成"eps"，也可以省略，以表示非ε-NFA。

正在进行中的笔记

这个包目前还处于开发中。字母表由String组成。这可能会改为字符或泛型类型，以方便降低内存占用和提高接受检查的易用性。目前实现的操作也非常有限。

操作

该库目前支持以下功能

• 解析和验证DFAs
• 解析和验证NFAs（带ε移动和不带ε移动）
• 生成适合重新解析DFAs和NFAs的表格
• 将DFAs转换为NFAs，将NFAs转换为DFAs
• 检查两个DFAs或两个NFAs是否等价
• 检查字符串是否被DFA或NFA接受
• 逐步评估字符串
• 识别并从DFA中删除不可达状态
• 识别并合并DFA中不可区分的状态
• 最小化DFA（通过执行上述两个步骤）
• 幂集构建，使用自定义组合器或
  • 并集（布尔或）
  • 交集（布尔与）
  • 差集（a且非b）
  • 对称差集（布尔异或）
• 解析正则表达式（验证在解析步骤中完成）
• 将正则表达式转换为NFAs