grep replacement (backref in egrep ?? whoa!)

[andrew at alice.UUCP]

In article <515 at yunexus.UUCP>, oz at yunexus.UUCP writes:
> Just how do you propose to implement the back-referencing trick in 
> a properly constructed (nfa and/or nfa->dfa conversion static or
> on-the-fly) egrep ?? I presume that after each match of the
> \(reference\) portion, you would have to on-the-fly modify the \n
> portion of the fsa. Gack! Do you have a theoretically solid algorithm
> [say, within the context of Aho/Sethi/Ullman's Dragon Book chapter on
> regular expressions] for this ??  I would be much interested.

theoretically solid is not what i would call it but the algorithm is simple
enough once you have a subroutine for egrep that matches a pattern against
an input with a match of at least n input chars. you just do what you have to
do: an exponential back-tracking algorithm. thus, back-referencing is not done
inside the fsa, but as part of a (complicated0 control function. I realise
this sounds vague but i can't give you the details until i do it. al aho has
done it and probably understands this stuff as well as anyone in the world.