mlewis@unocss..unl.edu (mlewis) (03/15/90)
I recently put in the code in Booch's Software Tools for the fast
(Boyer-Moore) pattern-matching package. I did make a few changes
to the code, and for the last several weeks, it has been included
by most of our programmers who needed it, with unqualified success.
Tody, I broke it, and I can't see what the problem is. The search
pattern is "XXX", and it can't find it when the XXX (which SHOULD
match) is at string_thing(30..32). I modified the string_thing
so that the XXX is at (31.33), and it matched. This is, I think,
pathological behavior for this algorithm. The skip_table was
3,4,3, which I think should have been 3,2,3, but this happened
late this afternoon, and I haven't had a chance to really take it
apart (and no time either - facing a deadline on this other package).
Boyer-Moore is a non-trivial, non-obvious algorithm. Is it the
algorithm, is there a bug in Booch's code, or did I introduce it
with my minor modifications? I made it a procedure instead of a
function, and took out the constraint exception as a loop
terminator. The call is Pattern_Match(String,In_String,Found,At),
where Found is an out Boolean, and At is a Positive, the position
in the string where the match occurred.
Any help would be appreciated, since this is a pretty subtle bug,
and I am still gleaning understanding of the algorithm from the
debugger (Vax/VMS).
Marc
--
---------------------------------------------------------------------------
Na khuya mne ehto gavno? | Internet: cs057@zeus.unl.edu
preferred machine->| UUCP: uunet!btni!unocss!mlewis
---------------------------------------------------------------------------