worley@compass.UUCP (Dale Worley) (07/13/88)
Marc Shapiro writes:
I am hacking a new, much-improved bibtex-mode for GNU Emacs. For
this, I need a function which checks if point is *within* a certain
regular expression.
Yow! This isn't easy, you know. In the general case, it can't be
done straightforwardly unless you try *every* possible start location.
The only efficient algorithm I can think of involves:
(1) generating the state-machine for the regexp
(2) starting from the point, reading the buffer backwards character by
character, running the state-machine "in reverse" to find the set of
all states which the state-machine could reach at the point from some
start character (to do this efficiently, you have to produce an "in
reverse" state-machine, which is easy if you make it by reversing the
regexp and then transforming it into a state machine)
(3) starting from the point, read the buffer forward, starting the
state machine in each of the states that (2) has found to be
reachable. If any of the start states leads to a final state, the
point is inside the regexp
You might want to post your question on one of the theoretical CS
newsgroups, in case someone has already solved this problem.
Dale