grep replacement (backref in egrep ?? whoa!)

[Ozan Yigit]

In article <7962 at alice.UUCP> andrew at alice.UUCP writes:
>
>21) subroutine versions of the pattern matching stuff.
>	....
>	.... the other two are egrep and back-referencing egrep.
>	lastly, regexp will be reimplemented.
>
>Andrew Hume

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.

oz
-- 
The DeathStar rotated slowly,	      |  Usenet: ...!utzoo!yunexus!oz
towards its target, and sparked       |  ....!uunet!mnetor!yunexus!oz
an intense SUNbeam. The green world   |  Bitnet: oz@[yulibra|yuyetti]
of unics evaporated instantly...      |  Phonet: +1 416 736-5257x3976