> It would appear that NFA's are basically polynomials:
John H. Conway's first (I think) book was _Regular Algebra and Finite
Machines_. There might be a copy up on libgen.
This is why I've gotten a little less enthused with PEGs: the
committed choice and the lookahead in PEGs kind of ruin the
algebra. On the other hand if you take this Thompson-style approach to
context-free grammars instead of regular expressions, you end up with
almost the same code as Earley's.
That is, the "Antimirov partial derivative" of a regex with respect to
a character is a set of regexes, like {x,y,z}, such that x|y|z is the
Brzozowski derivative. Thompson's algorithm represents the Antimirov
derivative as a set of pointers. When I tried reconstructing Might et
al's "Yacc is Dead" from their general idea, I used Antimirov
derivatives instead of the Brzozowski ones they used, and that led
right to Earley. I believe you could write a scanning/parsing library
that does both with one mechanism -- more of the boundary-blurring you
brought up.
Conway's book has a chapter on CFG's too, which as usual I haven't
read yet either.
> 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.
And Knuth's MMIX has a boolean matrix-multiply instruction.
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
