diff options
Diffstat (limited to 'nfa')
| -rw-r--r-- | nfa/src/default/nfa.rs | 2 | ||||
| -rw-r--r-- | nfa/src/default/regex.rs | 141 | ||||
| -rw-r--r-- | nfa/src/lib.rs | 4 |
3 files changed, 145 insertions, 2 deletions
diff --git a/nfa/src/default/nfa.rs b/nfa/src/default/nfa.rs index a23c056..8d657d5 100644 --- a/nfa/src/default/nfa.rs +++ b/nfa/src/default/nfa.rs @@ -212,7 +212,7 @@ impl<T: GraphLabel + Display> Nfa<T> for DefaultNFA<T> { let top_label = regex.vertex_label(top_index)?; let nfa_start = offset + 2 * top_index; - let nfa_end = offset + 2 * top_index + 1; + let nfa_end = nfa_start + 1; match top_label { RegexType::Kleene => { diff --git a/nfa/src/default/regex.rs b/nfa/src/default/regex.rs index c8ad370..1e3e87b 100644 --- a/nfa/src/default/regex.rs +++ b/nfa/src/default/regex.rs @@ -359,6 +359,147 @@ impl<T: GraphLabel> DefaultRegex<T> { Ok(result) } + + /// Use a function to format the labels of the regular expressions + /// and format the entire regular expression with this aid, with a + /// dot at a specified position. + pub fn to_string_with_dot<F>(&self, mut f: F, dot_pos: usize) -> Result<String, std::fmt::Error> + where + F: FnMut(T) -> String, + { + #[derive(Copy, Clone)] + enum StackElement { + Seen(usize), + Unseen(usize), + } + + impl StackElement { + fn index(&self) -> usize { + match self { + Seen(index) => *index, + Unseen(index) => *index, + } + } + + fn is_seen(self) -> bool { + matches!(self, Seen(_)) + } + } + + use StackElement::{Seen, Unseen}; + + let mut result = String::new(); + + let mut stack: Vec<StackElement> = Vec::new(); + let mut types = self.types.clone(); + types.push(RegexType::Paren); + + stack.push(Unseen(0)); + + while let Some(top) = stack.pop() { + let node_type = types.get(top.index()).unwrap(); + + match node_type { + RegexType::Kleene => { + if !top.is_seen() { + stack.push(Seen(top.index())); + + if self.degree(top.index()).unwrap() > 1 { + write!(result, "(")?; + stack.push(Unseen(types.len() - 1)); + } + + stack.extend( + self.graph + .children_of(top.index()) + .unwrap() + .map(Unseen) + .rev(), + ); + } else { + write!(result, "*")?; + } + } + RegexType::Plus => { + if !top.is_seen() { + stack.push(Seen(top.index())); + stack.extend( + self.graph + .children_of(top.index()) + .unwrap() + .map(Unseen) + .rev(), + ); + } else { + write!(result, "+")?; + } + } + RegexType::Optional => { + if !top.is_seen() { + stack.push(Seen(top.index())); + stack.extend( + self.graph + .children_of(top.index()) + .unwrap() + .map(Unseen) + .rev(), + ); + } else { + write!(result, "?")?; + } + } + RegexType::Or => { + if !top.is_seen() { + write!(result, "(")?; + + let len = self.len(); + + stack.push(Unseen(types.len() - 1)); + + for (child_index, child) in self + .graph + .children_of(top.index()) + .unwrap() + .enumerate() + .rev() + { + if child_index != len - 1 && child_index != 0 { + stack.push(Unseen(child)); + stack.push(Seen(top.index())); + } else { + stack.push(Unseen(child)); + } + } + } else { + write!(result, "|")?; + } + } + RegexType::Paren => { + write!(result, ")")?; + } + RegexType::Empty => { + stack.extend( + self.graph + .children_of(top.index()) + .unwrap() + .map(Unseen) + .rev(), + ); + + if self.graph.is_empty_node(top.index()).unwrap() { + write!(result, "ε")?; + } + } + RegexType::Lit(label) => write!(result, "{}", f(*label))?, + } + + if top.index() == dot_pos { + write!(result, " · ")?; + } + } + + Ok(result) + } } impl<T: GraphLabel + Display + Debug> Display for DefaultRegex<T> { diff --git a/nfa/src/lib.rs b/nfa/src/lib.rs index c1906e1..4440ea6 100644 --- a/nfa/src/lib.rs +++ b/nfa/src/lib.rs @@ -150,15 +150,17 @@ impl<T: GraphLabel> NfaLabel<T> { pub fn get_value(&self) -> T { self.value } + /// Retrieve the moved position from the label. #[inline] pub fn get_moved(&self) -> usize { self.moved } + /// Retrieve whether or not the label comes from left-linear /// expansions. #[inline] - pub fn get_left_p(&self) -> bool { + pub fn is_left_p(&self) -> bool { self.left_p } } |