Re: "tweetable" "symbolic" hex COM loader

> A really efficient modern NFA engine would probably skip these
> shenanigans and work in terms of bitvectors, alas.


It would appear that NFA's are basically polynomials:

	Sn = Mn /\ T * M(n-1) /\ T * T * M(n-2) /\ ... /\ T^n * S0
		where	Sn : state at input n
				Mn : literal matches at input n
				T    : transfer matrix

which, thanks to Horner's rule, can be evaluated iteratively:

	Sn = Mn /\ T * (Mn-1 /\ T * ( ... ) )

and hence (with appropriate choice of boolean parity) can be  
expressed as:

	Sn = (M + T * S(n-1))

which, being in matrix multiply-accumulate form, implies that modern  
NFA engines might well involve DSP/GPU shenanigans, or whatever is  
most suitable for often-sparse matrices.

(one might also imagine running the input in parallel across a state  
at a time, and seeing what actually links up once one has processed  
the final state.  This is unlikely to be useful, but maybe it's the  
angels algorithm?  (Turing commented that although angels might get  
away with having a single box with an infinite number of symbols, the  
rest of us should stick with a finite set of symbols on an infinite  
tape))

>> Based on Cox' description of the Thompson construction (and dim
>> memories of the Dragon book), I bashed out a nondeterministic regex
>> machine in an evening.  (Thompson, naturally, takes a route[0] that
>> comes naturally to language implementers[1])  It initially seemed a
>> bit wasteful, for we extract the tree structure once while parsing,
>> flatten everything down to a list of VM ops, and then essentially
>> implicitly reconstruct the tree when following the epsilon
>> transitions.  So the next version wound up very similar to Doug
>> McIlroy's recent Haskell interpretation:
>
> Which I haven't read, but it sounds like you might've also wound up
> similar to http://sebfisch.github.io/haskell-regexp/regexp-play.pdf
> (which I haven't read either, but it represents a set of NFA states as
> a regex tree with marks on the occupied states, apparently)

Neither of us went that far.  Labels for states are kind of  
arbitrary, so it's an obvious design decision.  I had considered  
using the tree, but thought it was overkill to index states by tree  
path, when the ordinal of the literal in the original regexp string  
(plus a start and accepting state at -1 and N) provides a nice small  
integer key suitable for a low-level state machine.  In fact, this  
separates concerns nicely, as one can build the literal match pool  
completely independently of the transfer matrix (as one might expect  
from the equation above).  Just like there's a difference between map  
and reduce, here the leaves of the parse tree go, in order, into the  
literal pool ("state definitions"), and the branches get  
independently folded down to provide the transfer matrix ("epsilon  
transitions"); submatch boundaries (which I postprocess) are yet  
another independent fold.  Note that literal leaves also pass  
unchanged through Thompson's postfix pass; it's just that instead of  
separating his basic blocks and control flow at that point, he merges  
them.  However, the tree (or in this case, graph) approach produces  
its motivation in Scene iii, Act 1, when they start interpreting  
infinite regexps ...

-Dave


-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss