From 8463dd24f815fe2b8f25fe9763e0a43023bfbb20 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 23 Dec 2022 00:36:31 +0800
Subject: 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.
---
 nfa/src/lib.rs | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 87 insertions(+), 7 deletions(-)

(limited to 'nfa/src/lib.rs')

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;
-- 
cgit v1.2.3-18-g5258