1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
#![warn(missing_docs)]
//! This crate implements non-deterministic finite automata.
//!
//! By default this uses the graph from the crate [`graph`]. To use
//! another external graph, add a module in which the external graph
//! implements the Graph trait from the [`graph`] crate, and then use
//! that external graph type as [`Graph`][graph::Graph] here.
pub mod error;
extern crate graph;
use core::fmt::Display;
use std::ops::{Deref, DerefMut};
use graph::{Graph, GraphLabel, LabelGraph};
use error::Error;
pub use desrec::DesRec;
use default::regex::RegexType;
/// The expected behaviour of a regular language.
///
/// Nondeterministic finite automata are equivalent to regular
/// languages. Since regular languages are easier to understand for a
/// human being, nondeterministic finite automata include the data for
/// the equivalent regular languages.
pub trait Regex<T: GraphLabel>: Graph + Display + Clone {
/// Return the label of a vertex, or an error if the node is
/// invalid.
fn vertex_label(&self, node_id: usize) -> Result<T, Error>;
#[inline]
/// Return the root node of the regular language.
///
/// Implementations can follow different conventions for the root
/// node, and hence this function.
///
/// If the regular language is empty, the implementation should
/// return None.
///
/// The default implementation uses the convention that the root
/// node is always the first node.
fn root(&self) -> Option<usize> {
if self.is_empty() {
None
} else {
Some(0)
}
}
// TODO: add functions that determine if certain "positions" in a
// regular language satisfy some special properties, like at the
// end of a Kleene star, or at the end of a regular language, et
// cetera. These might be needed later.
}
/// Since Option<T> does not inherit the Display from T, we wrap it to
/// provide an automatic implementation of Display.
#[derive(Debug, Clone, Copy, Ord, PartialOrd, Eq, PartialEq, Hash)]
pub struct DOption<T>(Option<T>);
impl<T> Default for DOption<T> {
fn default() -> Self {
Self(None)
}
}
impl<T> Deref for DOption<T> {
type Target = Option<T>;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl<T> DerefMut for DOption<T> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl<T: Display> Display for DOption<T> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.deref() {
Some(value) => Display::fmt(value, f),
None => write!(f, "ε"),
}
}
}
/// Substitute or Carry
///
/// This enumeration indicates whether a label from a regular
/// expression should be substituted by another regular expression, or
/// to be carried around in the resulting nondeterministic finite
/// automaton, in the process of the [`to_nfa`][Nfa::to_nfa] function.
///
/// # Transform labels
///
/// The label that is returned to be carried can be different from the
/// original label, as a way to transform the labels.
///
/// # Remark on the abbreviation
///
/// It happens "by chance" that this abbreviation coincides with the
/// abbreviation of "system on chip". Since I know nothing about this
/// topic, this is just a meaningless pun.
#[derive(Debug, Copy, Clone)]
pub enum SoC<T> {
/// To be substituted by another regular expression.
Sub(usize),
/// To carry around this label.
Carry(T),
}
/// The expected behvaiour of a nondeterministic finite automaton.
///
/// Every NFA is a special labelled graph.
pub trait Nfa<T: GraphLabel>: LabelGraph<T> {
/// Remove all empty transitions from the nondeterministic finite
/// automaton.
fn remove_epsilon(&mut self) -> Result<(), Error>;
/// Return a state-minimal NFA equivalent with the original one.
///
/// This is not required. It is just to allow me to experiment
/// with NFA optimization algorithms.
fn minimize(&self) -> Result<Self, Error> {
Err(Error::UnsupportedOperation)
}
/// When we convert a regular expression to a nondeterministic
/// finite automaton, the label should be optional, so we use a
/// different type for the result type.
type FromRegex<S: GraphLabel + Display + Default>;
/// Build a nondeterministic finite automaton out of a set of
/// regular expressions.
///
/// The SUB_PRED is a predicate function that returns an optional
/// index for a label. If it returns some index, then this means
/// we should substitute the index-th regular expression in the
/// set, whereever that label occurs in the set of regular
/// expressions.
fn to_nfa(
regexps: &[impl Regex<RegexType<T>>],
sub_pred: impl Fn(T) -> Result<SoC<T>, Error>,
) -> Result<Self::FromRegex<DOption<T>>, Error>;
/// Remove all dead states from the nondeterministic finite
/// automaton.
///
/// A state is dead if there are no edges going to the state.
fn remove_dead(&mut self) -> Result<(), Error>;
/// For each edge from A to B whose edge is considered nullable by
/// a function `f`, and for every edge from B to C, add an edge
/// from A to C.
///
/// This is needed specifically by the algorithm to produce a set
/// of atomic languages that represent "null-closed" derived
/// languages.
fn nulling(&mut self, f: impl Fn(T) -> bool) -> Result<(), Error>;
}
pub mod default;
pub mod desrec;
#[cfg(test)]
mod nfa_tests {}
|
