Path: utzoo!attcan!uunet!husc6!bloom-beacon!gatech!rutgers!bellcore!faline!thumper!ulysses!andante!alice!andrew
From: andrew@alice.UUCP
Newsgroups: comp.unix.wizards
Subject: Re: grep replacement (backref in egrep ?? whoa!)
Summary: theory
Message-ID: <7989@alice.UUCP>
Date: 16 Jun 88 05:29:23 GMT
References: <7962@alice.UUCP> <515@yunexus.UUCP>
Organization: AT&T Bell Laboratories, Murray Hill NJ
Lines: 16

In article <515@yunexus.UUCP>, oz@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.