From 8463dd24f815fe2b8f25fe9763e0a43023bfbb20 Mon Sep 17 00:00:00 2001 From: JSDurand 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. --- repcore/src/plan.org | 59 ---------------------------------------------------- 1 file changed, 59 deletions(-) delete mode 100644 repcore/src/plan.org (limited to 'repcore/src/plan.org') 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. - -- cgit v1.2.3-18-g5258