From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE,
	MSGID_SHORT autolearn=no autolearn_force=no version=3.4.4
Path: utzoo!attcan!uunet!ssbell!mcmi!unocss!mlewis
From: mlewis@unocss..unl.edu (mlewis)
Newsgroups: comp.lang.ada
Subject: Grady Booch bugs?
Keywords: Pattern-Matching
Message-ID: <2549@unocss..unl.edu>
Date: 15 Mar 90 04:06:52 GMT
Organization: U. of Nebraska at Omaha
List-Id: <comp.lang.ada>


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
---------------------------------------------------------------------------