From 9d1c8e72300338bc2e5068f0e9699af386caf8ce Mon Sep 17 00:00:00 2001 From: Melody Horn Date: Thu, 1 Apr 2021 11:55:57 -0600 Subject: ideally, but clearly not actually, implement NFA-to-DFA --- bird-machine-macros/src/dfa.rs | 156 ++++++++++++++++++++++++++++++++++++ bird-machine-macros/src/lib.rs | 34 ++++---- bird-machine-macros/src/nfa.rs | 175 +++++++++++++++++++++++++++++++++++++++-- 3 files changed, 345 insertions(+), 20 deletions(-) create mode 100644 bird-machine-macros/src/dfa.rs (limited to 'bird-machine-macros') diff --git a/bird-machine-macros/src/dfa.rs b/bird-machine-macros/src/dfa.rs new file mode 100644 index 0000000..0aec059 --- /dev/null +++ b/bird-machine-macros/src/dfa.rs @@ -0,0 +1,156 @@ +use std::collections::{BTreeMap, BTreeSet, VecDeque}; + +use proc_macro2::TokenStream; +use quote::{quote, ToTokens}; + +use super::nfa::{Range, NFA}; + +/// A nondeterministic finite automaton. +/// By convention, always starts in state 0. +pub struct DFA { + transition_table: BTreeMap>, + accept_states: BTreeSet, +} + +struct LabeledDFA { + start_state: Label, + transition_table: BTreeMap>, + accept_states: BTreeSet