* Grady Booch bugs?
@ 1990-03-15 4:06 mlewis
0 siblings, 0 replies; only message in thread
From: mlewis @ 1990-03-15 4:06 UTC (permalink / raw)
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
---------------------------------------------------------------------------
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~1990-03-15 4:06 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1990-03-15 4:06 Grady Booch bugs? mlewis
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox