diff options
author | JSDurand <mmemmew@gmail.com> | 2022-12-23 00:36:31 +0800 |
---|---|---|
committer | JSDurand <mmemmew@gmail.com> | 2022-12-23 00:36:31 +0800 |
commit | 8463dd24f815fe2b8f25fe9763e0a43023bfbb20 (patch) | |
tree | 343eea3c634efbbf72c64ed5dd778ecce60c3eea /repcore/src | |
parent | 9f1c88b863e247da3cd60d2792a7a13b18e25e53 (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.rs | 59 | ||||
-rw-r--r-- | repcore/src/lib.rs | 20 | ||||
-rw-r--r-- | repcore/src/plan.org | 59 |
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. - |