summaryrefslogtreecommitdiff
path: root/nfa
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-20 13:48:26 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-20 13:48:26 +0800
commit18d7955b7d84c00467ede38baae53f4ce1fb6908 (patch)
tree97d0746b82816a21d980636e50f8cdbeb804b518 /nfa
parent8f8d3d1a3c276be4be2e5d2e767ada564c47279a (diff)
chain: a prototype is added.
I have an ostensibly working prototype now. Further tests are needed to make sure that the algorithm meets the time complexity requirement, though.
Diffstat (limited to 'nfa')
-rw-r--r--nfa/src/default/nfa.rs2
-rw-r--r--nfa/src/default/regex.rs141
-rw-r--r--nfa/src/lib.rs4
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
}
}