WG211/M14Watson

I will present the design and implementation of SPARE TIME as an example of taxonomy-based software construction (TABASCO). SPARE TIME is a C++ toolkit for keyword pattern matching. It differs from other toolkits in that it is based on a taxonomy of keyword pattern matching algorithms. I will discuss the aims of TABASCO and of taxonomy construction and taxonomy-based toolkit design in particular, especially how the taxonomy structure induces the architecture and design of SPARE TIME. The taxonomy-oriented derivation also makes the toolkit easier to understand and use. The toolkit – like the taxonomy – contains the well known Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick and Commentz-Walter algorithms, as well as variants thereof.