diff options
Diffstat (limited to 'chain/src/plan.org')
| -rw-r--r-- | chain/src/plan.org | 28 |
1 files changed, 26 insertions, 2 deletions
diff --git a/chain/src/plan.org b/chain/src/plan.org index 75acf30..bbd6683 100644 --- a/chain/src/plan.org +++ b/chain/src/plan.org @@ -38,11 +38,30 @@ finite automata. * [X] Test the removal of dead states, where a state is dead if and only if no other states have an edge into that state. -- [-] Refactor [2/5] +- [-] Refactor [2/8] + [X] Implement a data type for graphs with labels on vertices and edges, but do not need to index edges by labels, which can index vertices by labels instead. + * [X] Test it. + [X] Implement a builder that borrows a graph mutably. + * [X] Test it. + + [ ] Implement a data type for graphs in which every node knows its + parents, and every node has a unique label but edges have no + labels. + * [ ] Test it. + + [ ] We need to record the expansions of those "virtual nodes". + That is, the virtual nodes represent atomic languages such as + [s]^{(t)} where s is a non-terminal and t is a terminal. To be more + specific, it represents the derivative of the left-linear closure + of the non-terminal s with respect to the terminal t. The + left-linear closure of s is the set of all strings (consisting of + terminals and non-terminals alike) that are derivable from s + alone, without consuming any inputs, by expanding according to the + grammar rules. This means that we need to know which + non-terminals were expanded in order to get to a state in [s]^{(t)}. + + [ ] Each edge in the chain-rule machine needs to be labelled also + with a position in the forest. This perfectly solves the problem + of those "plugs"! + [ ] When we pull in some regular language because of the left-linear expansion, we need to mark that branch as coming from left-linear expansions. This is necessary because we cannot @@ -66,7 +85,12 @@ + [X] First define a trait with the expected behaviours. + [ ] Then implement them as doubly labelled graphs. + [ ] Thenimplement finding derivatives by use of the chain rule. -- [-] Implement forests [1/2] +- [-] Implement forests [2/3] + + [X] Design a format of forests. This should be the most crucial + thing to do, in order to have a better understanding of the whole + picture. I need to have a clear understanding of the details of + the binarised shared packed parsed forests, that reflects the + regular expressions in the grammar equations. + [X] Define a trait with the expected behaviours. + [-] Implement them using adjacency map: we only need one label per edge, and we do not wish to exclude duplicate edges, and we do not |