Post
Rapid graph traversals gives us GC, eta-edge collapsing, & (via Fleischer's recursive algorithm) the strongly-connected subgraphs!
To merge redundant edges (converting NFAs to DFAs) we could ask our Parsing Unit "for these states & this input which states are next?" queueing non-duplicate results up to be merged & traversed.
We can optimize a DFA by converting its inverse-NFA into a DFA & inverting it back.
3/3 Fin! Or maybe I condensed too much?
To operate the different sub-CPUs I designed, assemblers (or maybe even libraries of magic constants!) may be enough, given how high-level the machine code is.
Though our Parsing Unit would need an optimizing assembler to ensure its machine code fits. And its firmware would offer smaller-scale optimizations as it merges in new parsing rules.
Its ability to be in multiple states at once would both simplify these optimization passes & reduce the need for them! Giving us fast graph traversals.
2/
Rapid graph traversals gives us GC, eta-edge collapsing, & (via Fleischer's recursive algorithm) the strongly-connected subgraphs!
To merge redundant edges (converting NFAs to DFAs) we could ask our Parsing Unit "for these states & this input which states are next?" queueing non-duplicate results up to be merged & traversed.
We can optimize a DFA by converting its inverse-NFA into a DFA & inverting it back.
3/3 Fin! Or maybe I condensed too much?
P.S. The smaller-scale version of these optimizations would use a small amount of scratch RAM (provided by a coprocessor) to inverse the graphs & deduplicate to-be-merged states. Once that gives us (fancy) tries, we can bootstrap a full-scale optimizer.
3.2/3.2 Truly fin! Unless questions?
@alcinnz this is my FAVORITE kind of stuff. i love love love this analysis and this entire format you're doing
Install bonfire.cafe
Get the full app experience
