summaryrefslogtreecommitdiff
path: root/nfa/src/lib.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2022-12-23 00:36:31 +0800
committerJSDurand <mmemmew@gmail.com>2022-12-23 00:36:31 +0800
commit8463dd24f815fe2b8f25fe9763e0a43023bfbb20 (patch)
tree343eea3c634efbbf72c64ed5dd778ecce60c3eea /nfa/src/lib.rs
parent9f1c88b863e247da3cd60d2792a7a13b18e25e53 (diff)
renaming core to chain and some other changes
Some changes: - The core crate is renamed to "chain". - The crate "viz" is added, which will provide layered graph drawing algorithms. - A function is added to convert from a grammar to the regular language of its left-linear closures. - A function is added to convert from a nondeterministic finite automaton to its "null" closure. A null closure is the same automaton with edges added, as if some edges are "null". Whether an edge is null is determined by a function. Combined with the previous change, we can convert a grammar to the regular language of the null closure of its left-linear closures. --- Now it remains to test more grammars and add an Atom trait, before finishing the part about compilations.
Diffstat (limited to 'nfa/src/lib.rs')
-rw-r--r--nfa/src/lib.rs94
1 files changed, 87 insertions, 7 deletions
diff --git a/nfa/src/lib.rs b/nfa/src/lib.rs
index 1e2a30c..b1d62b3 100644
--- a/nfa/src/lib.rs
+++ b/nfa/src/lib.rs
@@ -12,17 +12,23 @@ 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 {
+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>;
@@ -52,6 +58,65 @@ pub trait Regex<T: GraphLabel>: Graph + Display {
// 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.
@@ -68,9 +133,23 @@ pub trait Nfa<T: GraphLabel>: LabelGraph<T> {
Err(Error::UnsupportedOperation)
}
- /// Build a nondeterministic finite automaton out of a regular
- /// language.
- fn to_nfa(regex: impl Regex<T>) -> Self;
+ /// 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.
@@ -78,13 +157,14 @@ pub trait Nfa<T: GraphLabel>: LabelGraph<T> {
/// A state is dead if there are no edges going to the state.
fn remove_dead(&mut self) -> Result<(), Error>;
- /// For each empty transition from A to B, and for every edge from
- /// B to C, say, add an edge from A to C.
+ /// 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) -> Result<(), Error>;
+ fn nulling(&mut self, f: impl Fn(T) -> bool) -> Result<(), Error>;
}
pub mod default;