summaryrefslogtreecommitdiff
path: root/repcore/src
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 /repcore/src
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 'repcore/src')
-rw-r--r--repcore/src/grammar.rs59
-rw-r--r--repcore/src/lib.rs20
-rw-r--r--repcore/src/plan.org59
3 files changed, 0 insertions, 138 deletions
diff --git a/repcore/src/grammar.rs b/repcore/src/grammar.rs
deleted file mode 100644
index ee9f033..0000000
--- a/repcore/src/grammar.rs
+++ /dev/null
@@ -1,59 +0,0 @@
-//! This file implements the extected behaviours of grammars.
-
-// NOTE: We shall first start with a parser that works at the level of
-// characters. The purpose is to first experiment with the workings
-// and the performance of the algorithms, before optimising by using
-// regular expressions to classify inputs into tokens. In other
-// words, the current focus is not on the optimisations, whereas
-// scanners are for optimisations only, so to speak.
-
-/// The type of a terminal.
-///
-/// For the time being this is a wrapper around a string, but in the
-/// future it may hold more information of scanners.
-pub struct Terminal {
- // If we want to use scanners, per chance add them as a new field
- // here.
- name: String,
-}
-
-impl Terminal {
- /// Create a terminal with the given name.
- #[inline]
- pub fn new(name: String) -> Self {
- Self { name }
- }
-
- /// Return the name of the terminal.
- #[inline]
- pub fn name(&self) -> &str {
- &self.name
- }
-}
-
-/// The type of a non-terminal.
-///
-/// This is just a wrapper around a string.
-pub struct Nonterminal(String);
-
-impl Nonterminal {
- /// Return the name of the nonterminal.
- ///
- /// Just to improve readability.
- #[inline]
- pub fn name(&self) -> &str {
- &self.0
- }
-}
-
-/// The type of a terminal or a non-terminal.
-///
-/// Only an index is stored here. Actual data are stored in two other
-/// arrays.
-#[derive(Debug, Hash, Eq, PartialEq, Clone, Copy, Ord, PartialOrd)]
-pub enum TNT {
- /// Terminal variant
- Ter(usize),
- /// Nonterminal variant
- Non(usize),
-}
diff --git a/repcore/src/lib.rs b/repcore/src/lib.rs
deleted file mode 100644
index 589b61c..0000000
--- a/repcore/src/lib.rs
+++ /dev/null
@@ -1,20 +0,0 @@
-//! This package implements the core algorithm of the entire
-//! workspace: parsing with derivatives by means of regular nulling
-//! languages.
-
-pub mod grammar;
-
-pub fn add(left: usize, right: usize) -> usize {
- left + right
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn it_works() {
- let result = add(2, 2);
- assert_eq!(result, 4);
- }
-}
diff --git a/repcore/src/plan.org b/repcore/src/plan.org
deleted file mode 100644
index 13c2ee0..0000000
--- a/repcore/src/plan.org
+++ /dev/null
@@ -1,59 +0,0 @@
-#+TITLE: Plan of the package
-#+AUTHOR: Durand
-#+DATE: <2022-11-18 Ven 19:57>
-
-* Atomic Languages
-
-This describes the behaviours of atomic languages. The atomic
-language consists of the null closure of any non-terminal symbol in
-the grammar, and their deriavtives by terminals and non-terminal.
-
-* Derivative Languages
-
-This is the main driving device of the algorithm. Basically, the
-algorithm works by taking successive derivatives, according to the
-input symbol. At each step, we calculate the derivative language. In
-this process, we also compute some semiring value and store in a
-carrier. The end result of the algorithm is the final semiring
-value.
-
-If one wants simply to determine if the input string belongs to the
-grammar, one chooses the semiring to be the field with two elements,
-the boolean field. If one wants to find how many ways are there to
-derive a given input string, then one uses the semiring of natural
-numbers instead. If one wants, moreover, to find all the possible
-ways to derive a particular input string, then one can use the
-free semiring on the set of terminals and non-terminals of the
-grammar. Here the free semiring is the left-adjoint functor to the
-forgetful functor from the category of semirings to the category of
-sets.
-
-To be more specific, the free semiring on a set is given by sets of
-sequences of elements in the set. The addition of the semiring is the
-set union operation, and the multiplication is taking the respective
-concatenations.
-
-** Semirings
-
-So we need a module to define the behaviours of semirings, and provide
-some common semirings implementations. Then in the main driving force
-we can freely substitute different semirings, according to the
-particular needs.
-
-** Languages
-
-Then the main part is to define the behaviour of languages. This
-should be easy enough, since we already have the mechanism of graphs,
-nondeterministic automata, and semirings. All we need to do is to
-combine them together.
-
-* Testing ground
-
-I am in a strong need to test things out. The most important one is
-to visualize each step of the derivation, in a human-friendly manner.
-I need this to examine whether my atomic languages are wrongly
-implemented, or my atomic languages are wrongly derived, or my
-understanding of the main algorithm is plain wrong.
-
-This is the main reason I started this rewrite of the package.
-